Compute peak concurrent drivers in 24 hours
Company: Rippling
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given delivery intervals across multiple drivers, compute the maximum number of distinct drivers simultaneously active within the last 24 hours from a query time T. Each delivery is a tuple (driver_id, start_time, end_time) with start_time < end_time; a driver may have multiple intervals. A driver counts as active at a moment if at least one of their intervals covers that moment. Implement peak_concurrent_drivers(T) that returns the maximum number of distinct active drivers in the half-open window [T − 24h, T). Clearly define inclusivity rules (e.g., end exclusive), required data structures, and the algorithm’s time and space complexity. Assume streaming inserts and queries over time.
Quick Answer: This question evaluates the ability to design algorithms and data structures for streaming interval data, specifically computing peak distinct-driver concurrency over a half-open 24-hour time window with attention to boundary inclusivity and distinct-count semantics.
You are given a stream of operations on delivery intervals. Each add operation is a tuple ("add", driver_id, start_time, end_time) and inserts a half-open delivery interval [start_time, end_time) for that driver. Each query operation is a tuple ("query", T) and asks for the maximum number of distinct drivers that are simultaneously active at some moment inside the half-open 24-hour window [T - 24, T). A driver is active at time x if at least one of that driver's inserted intervals contains x. If a driver has multiple overlapping or touching intervals, that driver still counts only once at any moment. Process operations in order: a query only sees adds that appeared earlier in the stream. Return the answer for every query in order.
For an efficient solution, use two layers of data structures: a hash map from driver_id to that driver's merged intervals, and a global range-add/range-max structure over compressed timestamps.
Constraints
- 1 <= len(operations) <= 20000
- For every add operation, start_time < end_time
- -10^9 <= start_time, end_time, T <= 10^9
- driver_id is an integer
- The query window is always the half-open interval [T - 24, T)
Examples
Input: ([("add", 1, 0, 10), ("add", 2, 5, 15), ("query", 12)],)
Expected Output: [2]
Explanation: In the window [-12, 12), driver 1 is active on [0, 10) and driver 2 on [5, 12). The peak overlap is 2 on [5, 10).
Input: ([("add", 1, 0, 10), ("add", 1, 5, 12), ("add", 2, 6, 8), ("query", 9), ("query", 13)],)
Expected Output: [2, 2]
Explanation: Driver 1's two intervals overlap, so they count as one distinct driver. Driver 2 overlaps driver 1 on [6, 8), making the peak 2 for both queries.
Hints
- A single driver must never be counted twice at the same time. Maintain each driver's coverage as a sorted list of merged intervals, and when a new interval arrives, only add the parts not already covered by that driver.
- After coordinate compression, every newly uncovered sub-interval becomes a range +1 update on a segment tree, and every query becomes a range maximum query on [T - 24, T).