Compute the Eddington number from ride distances
Company: Liftoff
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given a list of positive integers `distances`, where `distances[i]` is the distance traveled on day `i`, compute the cyclist’s **Eddington number** `E`:
`E` is the largest integer such that there are at least `E` days with distance **≥ E**.
Return `E`.
Examples:
- `distances = [1, 3, 3, 5, 6]` → `E = 3` (three days have distance ≥ 3)
- `distances = [10, 8, 5, 4, 3]` → `E = 4` (four days have distance ≥ 4)
- `distances = [1, 1, 1]` → `E = 1`
Constraints: `1 ≤ n ≤ 2e5`, `1 ≤ distances[i] ≤ 1e9`. Aim for an efficient solution.
Quick Answer: This question evaluates a candidate's competence in array manipulation, ordering/selection techniques, counting thresholds, and algorithmic complexity analysis required to compute the Eddington number.
Given a list of positive integers `distances`, where `distances[i]` is the distance traveled on day `i`, compute the cyclist's **Eddington number** `E`.
`E` is the largest integer such that there are at least `E` days with distance **≥ E**.
Return `E`.
Examples:
- `distances = [1, 3, 3, 5, 6]` → `E = 3` (three or more days have distance ≥ 3)
- `distances = [10, 8, 5, 4, 3]` → `E = 4` (four days have distance ≥ 4)
- `distances = [1, 1, 1]` → `E = 1`
Aim for an efficient solution: with up to 2×10^5 days and distances as large as 10^9, an O(n) counting approach is expected rather than sorting or per-candidate scanning.
Constraints
- 1 ≤ n ≤ 2×10^5 (n = number of days)
- 1 ≤ distances[i] ≤ 10^9
- The answer E satisfies 0 ≤ E ≤ n
Examples
Input: ([1, 3, 3, 5, 6],)
Expected Output: 3
Explanation: Days with distance ≥ 3 are 3, 3, 5, 6 (four days, ≥ 3 holds). Days with distance ≥ 4 are only 5, 6 (two days, < 4). So the largest valid E is 3.
Input: ([10, 8, 5, 4, 3],)
Expected Output: 4
Explanation: Days with distance ≥ 4 are 10, 8, 5, 4 (four days). Days with distance ≥ 5 are 10, 8, 5 (three days, < 5). So E = 4.
Hints
- The Eddington number E can never exceed the number of days n, so any distance larger than n can be treated as exactly n for counting purposes.
- Build a count array bucket[k] = number of days with distance exactly k (capping at n). Then iterate e from n down to 1, accumulating the number of days with distance ≥ e, and return the first e where that running total is at least e.
- This is the classic 'cap and count' technique, identical in spirit to computing the h-index. It runs in O(n) time and avoids sorting or scanning all distances for each candidate E.