← Liftoff Interview Insights

Liftoff·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Coding question for a Software Engineer role at Liftoff. One algorithmic problem, nothing too wild, but the definition of the Eddington number tripped me up for a minute before I got my head around it.

Questions Asked (1)

Q1

Given an array of daily cycling distances, compute the Eddington number: the largest integer E such that there are at least E days where the distance ridden was at least E. Return that value.

Algorithms & Data Structures
Author's notes

The definition itself took me an embarrassingly long time to internalize.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the problem definition and edge cases, then propose an efficient algorithm. Sort the array in descending order and find the largest index i (1-based) where the i-th element is at least i. Alternatively, use counting sort for O(n) time when distances are bounded.

Pro tip: Mention that the Eddington number is a special case of the h-index, and that sorting descending allows a simple linear scan. Also, note that if the array is unsorted, sorting is O(n log n), but counting sort can achieve O(n) if distances are integers within a known range.

1. Clarify the problem

Restate the definition: find the largest E such that at least E days have distance ≥ E. Confirm input format (array of integers) and output (integer).

2. Consider edge cases

Discuss empty array (return 0), all zeros (return 0), and large values. Also consider if distances can be negative (assume non-negative).

3. Propose a sorting-based solution

Sort the array in descending order. Iterate through the sorted array; for each index i (1-based), if the element at i-1 is ≥ i, update E = i. Return E.

4. Analyze complexity and alternatives

Time complexity O(n log n) due to sorting, space O(1) if in-place. Mention counting sort for O(n) time if distances are bounded, but note it requires extra space.

5. Test with examples

Walk through a small example, e.g., [5, 3, 2, 1] → sorted [5,3,2,1]; i=1:5≥1, i=2:3≥2, i=3:2<3 → E=2. Verify correctness.

Key Points to Mention

  • Definition of Eddington number and its relation to the h-index.
  • Sorting in descending order simplifies the condition to a linear scan.
  • Time complexity: O(n log n) for comparison sort, O(n) with counting sort if distances are bounded.
  • Space complexity: O(1) extra space for in-place sort, O(n) for counting sort.
  • Edge cases: empty array, all zeros, and distances larger than array length.
  • Potential optimization: use binary search on sorted array to find E in O(log n) after sorting.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.