Quick Overview

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.

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.

Overview: 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

  1. A driver is counted if there exists an interval [s,e] with s <= t and e >= t-86400.
  2. Because intervals are sorted and non-overlapping, only the last interval with start <= t needs to be checked for overlap with the window.
  3. Use binary search per driver to find the rightmost interval whose start <= t, then verify if its end >= t-86400.

Loading coding console...

Show the approach

Approach

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