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.
Overview: 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.
Read the full Rippling Software Engineer interview experience this question came from
You are given a list of delivery assignments. Each assignment is a tuple `(dasherId, startTime, endTime)` with `0 <= startTime < endTime`. An assignment is active on the half-open interval `[startTime, endTime)`.
A single dasher may hold multiple overlapping orders, but at any instant that dasher must be counted at most once.
Write a function `solution(assignments)` that returns a list `[maxDashers, left, right]` where:
- `maxDashers` is the maximum number of distinct dashers active at the same time.
- `[left, right)` is the earliest interval between consecutive event times where this maximum occurs.
- If `assignments` is empty, return `[0, -1, -1]`.
Expected approach: use an event sweep.
- Represent each order as two events `(time, delta, dasherId)`.
- Use `delta = +1` for a start event and `delta = -1` for an end event.
- Maintain a per-dasher active-order counter. The global active-dasher total changes only when a dasher transitions from `0 -> 1` active orders or from `1 -> 0` active orders.
- When multiple events share the same timestamp, process all end events before start events. In Python, a correct sort key is `key=lambda e: (e[0], e[1], e[2])` because `-1 < +1`.
- A key like `(time, dasherId, delta)` can break correctness because it may process a start at time `t` before an end at time `t` just because the start has a smaller `dasherId`, violating the required end-before-start tie rule.
Important: process all events at the same timestamp before evaluating the interval to the next timestamp.
Constraints
- 0 <= N <= 2 * 10^5, where N is the number of assignments
- 0 <= startTime < endTime <= 10^9
- dasherId is an integer
- The assignments are not necessarily sorted
Examples
Input: []
Expected Output: [0, -1, -1]
Explanation: There are no assignments, so the maximum number of active dashers is 0 and no interval exists.
Input: [(1, 1, 5), (1, 2, 6), (2, 3, 4)]
Expected Output: [2, 3, 4]
Explanation: Dasher 1 has overlapping orders but still counts only once. On [3, 4), dashers 1 and 2 are both active, so the maximum distinct count is 2.
Hints
- Turn every assignment into two sweep events. What event ordering guarantees that an order ending at time t is removed before an order starting at time t is added?
- Because the same dasher can have overlapping orders, keep a hash map from dasherId to its active-order count. Only change the distinct-dasher total when that count moves between 0 and 1.
Community answers
Answer by rmeda188
from collections import defaultdict
def max_concurrent_dashers(assignments):
if not assignments:
return [0, -1, -1]
events = []
for dasher_id, start, end in assignments:
events.append((start, 1, dasher_id))
events.append((end, -1, dasher_id))
# End (-1) before start (+1) at the same timestamp
events.sort(key=lambda x: (x[0], x[1]))
active_count = defaultdict(int)
active_dashers = 0
max_dashers = 0
max_start = -1
max_end = -1
i = 0
while i < len(events):
current_time = events[i][0]
# Process all events at current_time
while i < len(events) and events[i][0] == current_time:
_, delta, dasher_id = events[i]
if delta == 1:
active_count[dasher_id] += 1
# Count dasher only when first assignment becomes active
if active_count[dasher_id] == 1:
active_dashers += 1
else:
active_count[dasher_id] -= 1
# Remove dasher only when all assignments are inactive
if active_count[dasher_id] == 0:
active_dashers -= 1
i += 1
# Need a next event time to form [left, right)
if i == len(events):
break
next_time = events[i][0]
# This interval is [current_time, next_time)
if active_dashers > max_dashers:
max_dashers = active_dashers
max_start = current_time
max_end = next_time
return [max_dashers, max_start, max_end]