Quick Overview

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.

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.

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

  1. Be very careful with time units: current_time_ms and last_update_ms are milliseconds, but stale_after_seconds is in seconds.
  2. You do not need to sort the whole list. First find the minimum valid distance, then scan again to apply the tie-break rules.

Loading coding console...

Show the approach

Approach

The solution selects the best available "dasher" with two linear passes over the list, applying a shared validity filter.

Validity filter (is_valid). A dasher is a 4-tuple (driver_id, distance_meters, last_update_ms, available). It is rejected if it isn't a length-4 sequence, is unavailable, has None distance or update, or has negative distance. For freshness it computes age = current_time_ms - last_update_ms; a future timestamp (clock skew) clamps age to 0. The dasher survives only if age <= stale_after_seconds * 1000 — this is the key time-unit fix, converting the seconds threshold into milliseconds to match the ms timestamps.

Pass 1 — minimum distance. Scan every dasher, and among the valid ones track min_distance (d_min).

Pass 2 — jitter-tolerant tie-break. If no valid dasher exists, return -1. Otherwise set threshold = d_min + jitter_tolerance_m. Re-scan; any valid dasher with distance <= threshold is treated as "equally close." Among these, pick the best by lexicographic priority:

  1. largest last_update_ms (most recent location), then
  2. smallest driver_id on a tie.

This is enforced by the chained if/elif: a strictly newer update wins; an equal update with a smaller id wins. best_id starts at None and is returned (or -1) at the end.

Why correct. The jitter band is defined relative to the true minimum, so it can only be computed after d_min is known — hence two passes. The tie-break order exactly matches rules 5–6, and the age clamping plus *1000 conversion fix the two stated bugs.

Time complexity:
O(n)
Space complexity:
O(1)