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
A car can take a group of riders on a shared trip. There are `N` riders, and each rider has two limits: rider `i` is willing to share the trip with at least `low[i]` and at most `high[i]` other riders. If `k` riders travel together, each of them shares the trip with exactly `k - 1` others, so every chosen rider must satisfy `low[i] <= k - 1 <= high[i]`.
Return the largest `k` for which some group of `k` riders satisfies every rider in the group. The interviewer required `O(N)` time.
### Function Signature
```python
def max_group_size(low: list[int], high: list[int]) -> int:
```
### Rules
- Any subset of the riders may be chosen. Assume the car has room for all `N` riders, so the only limits are the riders' own.
- Riders who are not chosen impose no condition.
- If no group of one or more riders works, return `0`.
### Constraints
- `1 <= N <= 10^5`, where `N = len(low) == len(high)`
- `0 <= low[i] <= high[i] <= 10^9`
- Required time complexity: `O(N)`.
### Examples
**Example 1**
```text
Input: low = [0, 1, 1, 2, 2]
high = [1, 2, 2, 4, 4]
Output: 3
```
Riders 1, 2, 3 and 4 all accept exactly 2 others, so any three of them can travel together. A group of 4 would need every member to accept 3 others, and a group of 5 would need every member to accept 4 others; in both cases only riders 3 and 4 qualify.
**Example 2**
```text
Input: low = [2, 2, 2, 0]
high = [2, 2, 3, 0]
Output: 3
```
Riders 0, 1 and 2 each travel with exactly 2 others. A group of 4 fails because only rider 2 accepts 3 others. Rider 3 only travels alone, and no group of 2 works even though a group of 3 does.
**Example 3**
```text
Input: low = [1, 2]
high = [1, 3]
Output: 0
```
A single rider would need to accept 0 others, and neither does. A pair fails because rider 1 needs at least 2 others.
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