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]
Solution
def count_online_drivers(drivers, t):
window_start = t - 86400
window_end = t
count = 0
for intervals in drivers:
if not intervals:
continue
# Binary search for rightmost interval with start <= window_end
lo, hi = 0, len(intervals) - 1
idx = -1
while lo <= hi:
mid = (lo + hi) // 2
if intervals[mid][0] <= window_end:
idx = mid
lo = mid + 1
else:
hi = mid - 1
if idx != -1 and intervals[idx][1] >= window_start:
count += 1
return countExplanation
We need to know if a driver has any interval overlapping the inclusive window [t-86400, t]. Since each driver's intervals are sorted by start and non-overlapping, among all intervals with start <= t, only the last such interval can possibly overlap the window; if it does not, earlier intervals end even earlier and cannot overlap. Therefore, for each driver, we binary search for the rightmost interval with start <= t and then check if its end >= t-86400. This yields per-driver O(log k) time, where k is that driver's number of intervals.
Time complexity: O(D log K_avg), where D is the number of drivers and K_avg is the average number of intervals per driver. Space complexity: O(1) additional space.
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.