Largest Rider Group Where Every Rider's Companion-Count Limits Hold
Company: Uber Freight
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Overview: A coding problem about forming the largest group of riders for a shared car, where each rider accepts only a minimum and maximum number of fellow passengers. It tests reasoning about per-rider interval constraints, careful handling of group-size edge cases, and meeting a linear-time requirement.
Read the full Uber Freight Software Engineer interview experience this question came from
Constraints
- 1 <= N <= 10^5, where N = len(low) == len(high)
- 0 <= low[i] <= high[i] <= 10^9
- Required time complexity: O(N)
- The answer is an integer in [0, N]; no input or output value exceeds 2^31 - 1
Examples
Input: ([0, 1, 1, 2, 2], [1, 2, 2, 4, 4])
Expected Output: 3
Explanation: Source Example 1: four riders accept exactly 2 others so k = 3 works; k = 4 and k = 5 fail (a feasible size followed by infeasible larger ones).
Input: ([2, 2, 2, 0], [2, 2, 3, 0])
Expected Output: 3
Explanation: Source Example 2: k = 1 works, k = 2 fails, k = 3 works again, k = 4 fails; feasibility is not monotone in k.
Hints
- Fix a group size k. Does it matter which riders you pick, or only how many riders accept exactly k - 1 others?
- Feasibility does not have to grow or shrink steadily with k: Example 2 has a working size of 3 while size 2 fails, so consider every size.
- Only k - 1 values from 0 to N - 1 can ever occur, so a rider's acceptable range can be clipped to that interval before you use it.
Community answers
Answer by bitFox