← Liftoff Interview Insights

Liftoff·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
May 2026

Summary

Liftoff coding screen for a software engineer role, just the one problem about computing an Eddington number from an array of distances. Pretty niche concept if you haven't seen it before.

Questions Asked (1)

Q1

Given an array of daily cycling distances, find the Eddington number E, defined as the largest integer where you have at least E days with a distance of at least E. Return that value.

Algorithms & Data Structures
Author's notes

I'd never heard of the Eddington number before so I spent a minute just re-reading the problem to make sure I understood what it was asking.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Sort the array in descending order, then iterate through it to find the largest index i (1-based) where the distance at that index is at least i. The Eddington number is the maximum such i. Alternatively, use a frequency array or counting sort for O(n) time when distances are bounded.

Pro tip: Clarify whether the input array can be modified and mention that sorting is often acceptable, but if the distances are large or the array is huge, a counting approach can be more efficient. Also, handle edge cases like empty array or all zeros.

1. Understand the definition

Restate the problem: E is the largest integer such that there are at least E days with distance >= E. Confirm with the interviewer if needed.

2. Choose an approach

Decide between sorting (O(n log n)) or counting (O(n + max_distance)). Sorting is simpler and usually sufficient; counting is better for large n with bounded distances.

3. Implement the algorithm

For sorting: sort descending, then loop i from 0 to n-1, if arr[i] >= i+1, update E = i+1, else break. For counting: build frequency array, then iterate from largest possible E downwards, accumulating counts until count >= E.

4. Test with examples

Walk through a small example, e.g., [5,3,2,1] -> sorted [5,3,2,1], E=2 because at index 1 (0-based) distance 3 >= 2, but at index 2 distance 2 < 3. Also test edge cases: empty array, all zeros, all large numbers.

5. Analyze complexity

State time and space complexity: sorting O(n log n) time, O(1) extra space if in-place; counting O(n + max_distance) time, O(max_distance) space. Discuss trade-offs.

Key Points to Mention

  • Sorting the array in descending order simplifies the condition check.
  • The Eddington number is at most the square root of the sum of distances, but this is not needed for the algorithm.
  • Edge cases: empty array returns 0, all zeros returns 0, array with one element returns 1 if distance >=1 else 0.
  • Time complexity: O(n log n) for sorting, O(n) for counting if distances are bounded.
  • Space complexity: O(1) extra for sorting (if in-place), O(max_distance) for counting.
  • The algorithm can be optimized by noting that E cannot exceed n, so we only need to check up to n.

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