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.
Quick Answer: 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
Solution
def assign_dashers(drivers, orders, max_pickup_distance):
# Copy drivers to avoid mutating caller input
ds = []
for d in drivers:
ds.append({
'id': d['id'],
'x': d['x'],
'y': d['y'],
'vehicle': d['vehicle'],
'rating': float(d.get('rating', 0.0)),
'available_at': int(d.get('available_at', 0))
})
# Prepare orders with stable index and sort key
os = []
for idx, o in enumerate(orders):
os.append({
'id': o['id'],
'px': o['px'],
'py': o['py'],
'dx': o['dx'],
'dy': o['dy'],
'ready_at': int(o['ready_at']),
'vehicle': o['vehicle'],
'idx': idx
})
os.sort(key=lambda o: (o['ready_at'], o['id']))
# Prepare result aligned to input order positions
n = len(orders)
result = [[orders[i]['id'], -1] for i in range(n)]
def manhattan(x1, y1, x2, y2):
return abs(x1 - x2) + abs(y1 - y2)
for o in os:
best = None
best_key = None
for d in ds:
if d['vehicle'] != o['vehicle']:
continue
if d['available_at'] > o['ready_at']:
continue
dist = manhattan(d['x'], d['y'], o['px'], o['py'])
if dist > max_pickup_distance:
continue
key = (dist, -d['rating'], d['id'])
if best_key is None or key < best_key:
best = d
best_key = key
if best is not None:
travel = manhattan(best['x'], best['y'], o['px'], o['py']) + manhattan(o['px'], o['py'], o['dx'], o['dy'])
best['x'] = o['dx']
best['y'] = o['dy']
best['available_at'] = o['ready_at'] + travel
result[o['idx']][1] = best['id']
return result
Explanation
Sort orders by readiness time and process online. For each order, filter drivers by vehicle match, availability at ready_at, and pickup distance threshold. Among eligible drivers, choose the one minimizing (pickup distance, -rating, id). Update the chosen driver's location and availability based on Manhattan travel time for pickup and delivery, then continue. Results are returned in the original order list order, using -1 when no driver is eligible.
Time complexity: O(D * O). Space complexity: O(D + O).
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.