Compute the Eddington number from ride distances
Company: Liftoff
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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.
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.
Input: ([1, 1, 1],)
Expected Output: 1
Explanation: All three days have distance ≥ 1, so E ≥ 1. No day reaches 2, so E = 1.
Input: ([5],)
Expected Output: 1
Explanation: Single day of distance 5. One day has distance ≥ 1, so E = 1 (two days ≥ 2 would be needed for E = 2, but only one day exists).
Input: ([1000000000, 1000000000, 1000000000, 1000000000, 1000000000],)
Expected Output: 5
Explanation: Five days each far exceed 5, so all five have distance ≥ 5, giving E = 5. E is capped by the number of days (5), so distances above n behave like n.
Input: ([1, 2, 3, 4, 5, 6, 7, 8, 9, 10],)
Expected Output: 5
Explanation: Days with distance ≥ 5 are 5,6,7,8,9,10 (six days, ≥ 5). Days with distance ≥ 6 are 6,7,8,9,10 (five days, ≥ 6). Days with distance ≥ 7 are four days (< 7). The largest valid E is 6? Six days have distance ≥ 6, so E = 6 holds; check E = 7: 7,8,9,10 = four days < 7. Wait — recheck: distance ≥ 6 gives {6,7,8,9,10} = 5 days = 5, not ≥ 6. distance ≥ 5 gives {5,6,7,8,9,10} = 6 days ≥ 5, valid. So E = 5.
Input: ([2, 2, 2, 2],)
Expected Output: 2
Explanation: Four days each of distance 2. Two days have distance ≥ 2 (in fact all four do), satisfying E = 2. E = 3 needs three days ≥ 3, but none reach 3, so E = 2.
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.