Compute concurrent online drivers
Company: Rippling
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
##### Question
Given each driver’s chronologically sorted delivery records, build an algorithm that, for a timestamp t, returns how many distinct drivers were online at any moment in the previous 24 hours. Optimize using per-driver binary search and justify the complexity.
Quick Answer: This question evaluates proficiency in algorithms and temporal data handling, including the use of efficient search techniques and complexity reasoning to count distinct active drivers over a sliding 24-hour window.
You are given N drivers. For each driver, you are provided a chronologically sorted list of non-overlapping online sessions, each as an inclusive interval [start, end] of integer seconds since epoch. Given a query timestamp t, return how many distinct drivers were online at any moment during the previous 24 hours, defined as the inclusive window [t-86400, t]. A driver counts once if any of their intervals intersects this window.
Constraints
- 0 <= N == len(drivers) <= 200000
- Sum of all intervals across all drivers <= 1000000
- For each driver, intervals are sorted by start ascending and are non-overlapping
- Intervals use inclusive endpoints: start <= end
- Timestamps are integers: -10^15 <= start, end, t <= 10^15
- Return value is in [0, N]
Hints
- A driver is counted if there exists an interval [s,e] with s <= t and e >= t-86400.
- Because intervals are sorted and non-overlapping, only the last interval with start <= t needs to be checked for overlap with the window.
- Use binary search per driver to find the rightmost interval whose start <= t, then verify if its end >= t-86400.