Compute unique-dasher concurrency with tie-breaking
Company: Rippling
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
You are given N delivery assignments, each as (dasherId, startTime, endTime) with 0 <= startTime < endTime. A single dasher may hold multiple overlapping orders. Design an algorithm to compute:
(
1) the maximum number of simultaneously active dashers at any moment (count each dasher at most once at any instant), and
(
2) one timestamp (or interval) when this maximum occurs. Use an event-sweep approach: specify the event format, how you avoid double-counting when the same dasher has multiple overlapping orders (e.g., maintain a per-dasher active-order counter that changes the global active-dasher count only on 0->1 and 1->0 transitions), and your tie-breaking policy when multiple events share the same timestamp (process end (-
1) before start (+
1)). In Python, show a correct sort key that enforces these rules (e.g., key=(time, delta, dasherId) with delta in {-1,+1}) and explain why putting dasherId before delta can break correctness. Analyze time and space complexity.
Quick Answer: The question evaluates understanding of sweep-line/event-sweep algorithms, interval overlap handling, tie-breaking and stable sort ordering as they affect deduplicating concurrent entities, situated in the Coding & Algorithms domain.