Debug a driver assignment bug
Company: DoorDash
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given a service that selects the best delivery driver ("dasher") for an order, users report incorrect assignments. With a provided codebase and failing scenario, reproduce the bug, write a minimal failing unit/integration test, pinpoint the root cause (e.g., stale location cache, incorrect sort comparator, time-unit mismatch, concurrency/race), and implement a fix. Explain your debugging process, the fix, and its complexity. Add observability (structured logs, metrics) and safeguards (timeouts, retries, circuit breakers). Discuss edge cases: no candidates, ties, GPS jitter, late position updates, partial outages, and performance under high load.
Quick Answer: This question evaluates debugging, root-cause analysis, unit/integration test design, observability, and system-resilience competencies within the Coding & Algorithms domain, emphasizing practical skills in reproducing failures, isolating defects, and implementing targeted fixes.
A delivery service assigns the best available driver (a "dasher") to an order, but users report incorrect assignments. The root causes in the old implementation were a time-unit bug (timestamps are in milliseconds, while the freshness threshold is given in seconds) and inconsistent tie-breaking when GPS jitter makes multiple drivers appear equally close.
Implement the corrected driver selector.
Each dasher is represented as a 4-tuple:
(driver_id, distance_meters, last_update_ms, available)
Selection rules:
1. Ignore any dasher that is unavailable, has missing distance/last update (None), or has a negative distance.
2. A location update is stale if its age is greater than stale_after_seconds * 1000. If last_update_ms is in the future because of clock skew, treat its age as 0.
3. Among all valid dashers, find the minimum distance d_min.
4. Because of GPS jitter, any dasher with distance <= d_min + jitter_tolerance_m is considered equally close.
5. From those equally close dashers, choose the one with the most recent last_update_ms.
6. If there is still a tie, choose the dasher with the smallest driver_id.
7. If no valid dasher exists, return -1.
In a real debugging interview, you would also discuss minimal failing tests, observability, retries, timeouts, and circuit breakers. For this coding exercise, implement the corrected selector function.
Constraints
- 0 <= len(dashers) <= 200000
- Each dasher is a tuple: (driver_id, distance_meters, last_update_ms, available)
- distance_meters and last_update_ms may be None; such dashers must be ignored
- 0 <= stale_after_seconds <= 10^6
- 0 <= jitter_tolerance_m <= 10^6
Examples
Input: ([(1, 100, 80000, True), (2, 120, 98000, True)], 100000, 30, 5)
Expected Output: 1
Explanation: Dasher 1 is only 20 seconds old, so it is still fresh. The old bug would incorrectly treat 30 seconds as 30 milliseconds. The correct answer is driver 1 because it is clearly closer than driver 2.
Input: ([], 100000, 30, 5)
Expected Output: -1
Explanation: There are no candidates, so no assignment can be made.
Hints
- Be very careful with time units: current_time_ms and last_update_ms are milliseconds, but stale_after_seconds is in seconds.
- You do not need to sort the whole list. First find the minimum valid distance, then scan again to apply the tie-break rules.