Design dasher-to-order assignment algorithm
Company: DoorDash
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are building a real-time 'dasher picker' that assigns delivery drivers (Dashers) to incoming orders. Define objective(s) (e.g., minimize ETA and cancellations, maximize fairness/earnings), constraints (driver capacity, distance, pickup/delivery windows, batching), and signals (location, status, vehicle type, ratings, surge). Propose data structures and an algorithm (e.g., greedy with priority queues, bipartite matching/flow, or scoring + auction) that scales under high churn with partial information. Analyze time/space complexity and discuss handling delayed locations, reassignments, and adversarial cases.
Overview: This question evaluates a candidate's skills in real-time algorithm design and systems thinking for dynamic matching and optimization, including scalability, time/space complexity analysis, and handling partial or delayed information.
You are given drivers and orders in a real-time delivery system. For each order, assign at most one driver using an online greedy policy at the order's ready_at time. Each driver has an id, location (x,y), vehicle type, rating, and available_at time. Each order has an id, pickup (px,py), dropoff (dx,dy), ready_at time, and required vehicle type. A driver is eligible for an order if: (1) the driver's vehicle matches the order's vehicle, (2) the driver is available at or before the order's ready_at, and (3) the Manhattan distance from the driver's current location to the order's pickup is <= max_pickup_distance. Among eligible drivers, choose the driver minimizing (pickup distance, -rating, driver id). After assignment, update the driver's location to the dropoff and set available_at to ready_at + (distance driver->pickup + distance pickup->dropoff). Process orders in non-decreasing ready_at; break ties by smaller order id. Return a list of [order_id, driver_id] for each input order index; use -1 for unassigned orders.
Constraints
- 1 <= len(drivers), len(orders) <= 2000
- All ids are unique integers
- Coordinates x,y,px,py,dx,dy are integers in [-10^6, 10^6]
- ready_at, available_at are integers in [0, 10^9]
- rating is a float in [0.0, 5.0]
- vehicle is a lowercase string; exact match required between driver and order
- Use Manhattan distance: |x1-x2| + |y1-y2|
- Orders are assigned immediately at ready_at; they cannot wait for a later driver
- Return one pair [order_id, driver_id] per input order; driver_id is -1 if no eligible driver exists
Hints
- Sort orders by (ready_at, id) and process sequentially.
- For each order, scan drivers to filter eligibility, then choose by the tuple (pickup_distance, -rating, driver_id).
- Use Manhattan distance to avoid floating-point error.
- Update driver state after assignment: new location is dropoff; available_at increases by pickup+delivery travel.
- If many drivers, consider spatial bucketing or a regional index to speed eligibility checks.