Skip to main content

Local Delivery Service (DoorDash / Instacart)

Sharpened prompt. Design a food and grocery delivery platform handling 3M orders/day across 500k merchants and 1M couriers, assigning couriers to orders near-optimally rather than greedily, predicting a delivery time that is accurate to within five minutes, batching multiple orders onto one courier without making anyone's food cold, and staying correct when the store is out of the item the customer ordered.

Ride-hailing matches one rider to one driver. Delivery matches one courier to several orders, across three independent parties (customer, merchant, courier), where every party's timing is uncertain. That combinatorial and temporal complexity is the whole problem.

1. Problem framing​

Functional requirements​

  • Browse merchants and menus; place an order; track it live.
  • Assign couriers to orders, potentially batching several orders per trip.
  • Predict and communicate a delivery ETA; update it as reality diverges.
  • Handle substitutions and out-of-stock items mid-shop.

Non-functional requirements​

PropertyTargetConsequence
Assignment qualityWithin ~10% of optimal total delivery timeGreedy nearest-courier is not good enough; batch and optimise
Assignment latencyDecision within a 20–30s batching windowThe window is a deliberate cost, and it must be justified
ETA accuracyP50 error < 4 min, P90 < 12 minDecompose into sub-models; a single end-to-end model is worse
Food qualityPrep completion within a few minutes of courier arrivalDispatch timing is as important as dispatch choice
Inventory accuracy> 95% on groceryReal-time signals from shoppers feed back into availability

Back-of-the-envelope​

Orders:       3M/day = 35/sec avg, ~200/sec at dinner peak
Couriers:     1M total, ~150k online at peak
Assignment:   200 orders/sec × 30s window = 6,000 orders per batch in a large market
              Candidate couriers per order ~ 50  ->  cost matrix 6,000 × 50 = 300k edges
              Min-cost flow on that: tens of milliseconds. Very tractable.
Locations:    150k couriers × ping/5s = 30k writes/sec  (small vs Uber)
ETA calls:    every order page view + every tracking refresh ≈ 50k/sec

The key realisation: the optimisation is small. A market's batch is thousands of edges, not millions, because assignment is local by construction. That makes exact methods affordable, and saying so justifies not reaching for a heuristic.

2. High-level architecture​

3. Component inventory​

ComponentConcrete choiceWhy this one
OptimiserGoogle OR-Tools min-cost flow, or the Hungarian algorithm for pure 1:1Exact, fast at this size, and easy to extend with side constraints
Batching window20–30s timer per marketTrades a little latency for a large quality gain (see 4.1)
Courier indexH3 cells with TTL, same as UberCandidate retrieval must be in memory
ETA modelsLightGBM per component, features from FeastDecomposed models are debuggable; a monolith is not
Merchant signalsPOS integration where available, tablet confirmations otherwisePrep-time ground truth is the single most valuable data source
Order statePostgres with a state machine + outboxOrders are money and must be transactional
Live trackingWebSocket per active orderCustomers refresh obsessively; push beats polling

4. The toughest parts​

4.1 Matching as a global optimisation, not a greedy loop​

Why it's hard. Greedy assignment ("give each order to its nearest available courier, in arrival order") is locally sensible and globally poor. A classic failure:

             Order A (ready now)      Order B (ready in 12 min)
Courier 1:   2 min away               3 min away
Courier 2:   9 min away               4 min away

Greedy (A first): A→C1 (2 min), B→C2 (4 min).   Total wait = 2 + 4 = 6, but B's
                  courier idles 8 minutes at the store.
Optimal:          A→C1, B→C2 with C2 dispatched 8 minutes later — same assignment,
                  different TIMING. Greedy gets the pairing right and the timing wrong.

Harder case (A ready in 12 min, B ready now):
Greedy (A first): A→C1 (idles 10 min at store), B→C2 (9 min away, food sits).
Optimal:          A→C2, B→C1. Total lateness drops by ~11 minutes.

Greedy also cannot express constraints that couple orders (batching, courier capacity, vehicle type) because it decides one order at a time.

Solution — batch orders over a short window and solve a min-cost assignment.

from ortools.graph.python import min_cost_flow

def assign(orders, couriers):
    smcf = min_cost_flow.SimpleMinCostFlow()
    SRC, SINK = 0, len(orders) + len(couriers) + 1
    o_off, c_off = 1, 1 + len(orders)

    for i, o in enumerate(orders):
        smcf.add_arc_with_capacity_and_unit_cost(SRC, o_off + i, 1, 0)
    for j, c in enumerate(couriers):
        # Capacity > 1 lets one courier take a batch of orders (see 4.3).
        smcf.add_arc_with_capacity_and_unit_cost(c_off + j, SINK, c.capacity, 0)

    for i, o in enumerate(orders):
        for j, c in enumerate(candidates(o, couriers)):     # ~50, not all 150k
            smcf.add_arc_with_capacity_and_unit_cost(
                o_off + i, c_off + j, 1, int(cost(o, c) * 100))

    smcf.set_node_supply(SRC, len(orders))
    smcf.set_node_supply(SINK, -len(orders))
    smcf.solve()
    return extract_assignment(smcf)

def cost(order, courier) -> float:
    # Minimise LATENESS, not distance. This is the single most important line.
    arrive_store   = now() + courier.eta_to(order.store)
    depart_store   = max(arrive_store, order.ready_at)          # whoever is later
    deliver_at     = depart_store + eta(order.store, order.customer)
    lateness       = max(0, deliver_at - order.promised_at)

    return (1.0 * lateness
          + 0.3 * max(0, arrive_store - order.ready_at)          # food sitting cold
          + 0.2 * max(0, order.ready_at - arrive_store)          # courier idling
          + 0.5 * courier.deadhead_km
          - 0.4 * courier.fairness_credit)                       # equalise earnings

Two points that make this a strong answer. The objective is lateness, not distance — distance is a proxy that produces bad assignments whenever prep times differ, which is always. And the cost function is where the product lives: courier fairness, food quality, and deadhead miles are all terms you can tune, which is impossible in a greedy matcher.

Justify the batching window explicitly. Waiting 25 seconds before assigning costs every order 25 seconds; the optimiser typically saves several minutes of average delivery time. Net strongly positive — but only in dense markets. In a sparse market with two couriers online, batching adds latency and changes nothing, so the window should shrink to zero. Making the window density-adaptive is the detail that shows you have thought past the algorithm.

4.2 ETA as a sum of five uncertain things​

Why it's hard. A single model predicting "minutes until delivery" from raw features is opaque, hard to debug, and systematically wrong in ways you cannot diagnose. Total delivery time is genuinely a composition of independent processes with different drivers and different error behaviour, and one of them — restaurant prep time — is controlled by someone with no incentive to be accurate.

Solution — decompose, model each component separately, and propagate uncertainty rather than just the mean.

T_total = T_prep  ⊕  T_courier_to_store  ⊕  T_wait_at_store  ⊕  T_drive  ⊕  T_park_handoff
          │           │                      │                  │            │
          merchant    routing + traffic      queueing            routing      building type,
          history,    (same as Uber)         at the merchant     + traffic    floor, gate code
          item count,
          time of day
def predict_eta(order, courier) -> Distribution:
    # Each component returns (mean, variance) — uncertainty is first-class.
    prep  = prep_model.predict(store=order.store, items=order.items,
                               hour=now().hour, current_backlog=order.store.open_orders)
    toa   = routing.eta(courier.pos, order.store.pos)
    wait  = wait_model.predict(store=order.store, hour=now().hour)   # queue at counter
    drive = routing.eta(order.store.pos, order.customer.pos)
    hand  = handoff_model.predict(building_type=order.customer.building,
                                  floor=order.customer.floor, has_gate=order.customer.gated)

    # Courier travel and prep OVERLAP — the courier waits only if they arrive early.
    to_pickup = max(prep.mean, toa.mean) + wait.mean
    mean = to_pickup + drive.mean + hand.mean
    var  = prep.var + toa.var + wait.var + drive.var + hand.var
    return Distribution(mean, math.sqrt(var))

# Quote a percentile, not the mean. Late is much worse than early.
quoted = predict_eta(order, courier).percentile(0.75)

Three things worth saying. max(prep, travel) not prep + travel — the two happen concurrently, and getting this wrong inflates every ETA. Quote P75, not P50, because the cost of being late is asymmetric. And each sub-model is separately monitorable: when ETAs degrade, you can see it was the prep model for pizza merchants on Fridays, which is a fixable finding rather than "the model got worse."

Prep time deserves special attention because it is the largest error source. The merchant's own estimate is unreliable (they are busy and optimistic), so the model learns from observed ready-times: when a courier arrives and waits 11 minutes, that is ground truth. Feed it back nightly and per-merchant.

4.3 Batching orders without ruining any of them​

Why it's hard. Putting two orders on one courier roughly halves delivery cost, which is the difference between a profitable and an unprofitable unit economy. But batching makes the first customer's food sit while the courier picks up and delivers the second, and a bad batch (two orders going opposite directions) makes both deliveries terrible. The decision must also be made before you know how prep times will actually resolve.

Solution — treat batching as a constrained feasibility check, then let the optimiser price it.

def can_batch(a: Order, b: Order) -> bool:
    # Hard constraints first — cheap rejections.
    if distance(a.store, b.store) > 1.5_km:            return False   # pickups far apart
    if distance(a.customer, b.customer) > 2.5_km:      return False   # dropoffs far apart
    if abs(a.ready_at - b.ready_at) > 8 * 60:          return False   # timing mismatch
    if a.needs_hot_bag and b.needs_cold_bag:           return False   # physical conflict
    if a.volume + b.volume > COURIER_CAPACITY:         return False

    # Detour test: how much worse is the batched route than the solo routes?
    solo   = route_time(a) + route_time(b)
    batched = best_batched_route_time(a, b)            # 2 pickups + 2 dropoffs, ordered
    return (batched - max(route_time(a), route_time(b))) < 7 * 60     # ≤7 min added

def batch_cost(a, b, courier) -> float:
    added_a = delay_to(a, batched_route)
    added_b = delay_to(b, batched_route)
    # Price the customer harm; the optimiser then chooses batching only when the
    # efficiency gain outweighs it.
    return (base_cost(a, courier) + base_cost(b, courier)
            - BATCH_SAVING
            + 1.5 * added_a + 1.5 * added_b
            + (3.0 if a.has_hot_items and added_a > 5*60 else 0))

The framing to give: "I don't decide to batch — I let the optimiser decide, by giving it batched pairs as candidate assignments with their true cost including customer harm. Batching becomes an economic choice per pair rather than a global policy."

Two operational refinements: order the stops optimally within a batch (it is a tiny TSP — four stops, brute-forceable), and allow late un-batching if prep times diverge more than expected before pickup, since committing early to a batch that reality invalidated is worse than reassigning.

4.4 The store is out of the item​

Why it's hard. Grocery inventory data is stale by hours and frequently wrong. A shopper in the aisle discovers the customer's oat milk is out of stock. Now you need a decision from a customer who may be in a meeting, in a workflow that cannot block — the shopper is standing in the aisle being paid by the minute.

Solution — predict substitutions in advance, ask asynchronously, and always have a default.

async def handle_out_of_stock(shop_session, item):
    # 1. Ranked substitutions, computed BEFORE the shop begins so there is no latency.
    subs = substitution_model.rank(item, store=shop_session.store,
                                   customer_history=shop_session.customer.prefs)

    # 2. Push to the customer, but do NOT block on them.
    await notify.push(shop_session.customer, SubstitutionRequest(item, subs[:3]),
                      priority="p1", ttl=180)

    # 3. The shopper keeps shopping. The decision is collected out of band.
    shop_session.defer(item, deadline=now() + 180)

    # 4. On timeout, apply the customer's standing preference. Never stall the shop.
    #    Preference is set once at signup: "best match" / "same brand only" / "refund".
    return shop_session.customer.substitution_default

# Close the loop: every stockout is a training signal for availability prediction.
await kafka.send("inventory.observed", {
    "store_id": shop_session.store.id, "sku": item.sku,
    "available": False, "observed_at": now(),
})

The feedback loop in step 5 is the highest-leverage part and the one candidates miss: shoppers physically inspecting shelves generate the only reliable inventory signal you have. Feeding those observations into a per-store, per-SKU availability model lets you hide likely-unavailable items at browse time, which prevents the problem instead of handling it. Availability decays as a function of time since last observation, restock schedule, and demand rate.

4.5 A three-sided marketplace where supply is a design problem​

Why it's hard. You need enough couriers online, in the right neighbourhoods, at the right times. Couriers are independent contractors who choose when and where to work. Too few and orders go undelivered; too many and everyone's earnings drop and they stop showing up next week. Unlike ride-hailing, demand is extremely peaked — dinner is 40% of daily volume in a two-hour window.

Solution — forecast, incentivise ahead of time, and admit demand when supply cannot meet it.

# Two hours ahead, per market region:
forecast = demand_model.predict(region, horizon="2h")          # orders/hour
supply   = supply_model.predict(region, horizon="2h")          # expected online couriers
gap      = forecast / max(1, supply * ORDERS_PER_COURIER_HOUR)

if gap > 1.15:
    # Incentives must be offered EARLY: a courier needs time to travel and decide.
    await incentives.offer(region, kind="peak_pay",
                           amount=price_from_gap(gap), window="18:00-20:00")

if gap > 1.5:
    # Demand-side admission control: better to quote honestly than to fail late.
    await pricing.raise_delivery_fee(region, factor=min(1.6, gap))
    await eta_service.inflate(region, factor=gap)              # honest, longer ETAs
if gap > 2.0:
    await availability.pause_new_orders(region, reason="capacity")

The graceful degradation ladder is what makes this a systems answer rather than a business one: incentivise → price → lengthen ETAs → stop accepting orders. Each step is less pleasant and each is far better than accepting an order you cannot deliver, which costs a refund, a courier's wasted trip, and a customer.

Say this explicitly: "Accepting an order you cannot fulfil is the most expensive possible outcome, so admission control is a feature. The system should refuse work before it fails at work."

4.6 The order state machine across three parties​

Why it's hard. An order passes through the customer, the merchant, and the courier, each with their own app, their own connectivity, and their own ability to cancel. The merchant can reject after acceptance. The courier can drop an order mid-route. The customer can cancel while the food is being cooked. Each of those has different money consequences — who eats the cost of prepared food?

Solution — an explicit state machine with per-transition financial policy, and a saga for the money.

created → merchant_confirmed → prep_started → ready
                                                 ↘
       courier_assigned → at_store → picked_up → delivered
                                                 ↘
   cancel paths:  by_customer | by_merchant | by_courier | by_system
   each with:     refund_policy, merchant_compensation, courier_compensation
CANCEL_POLICY = {
  ("by_customer", "created"):            Policy(refund=1.0, merchant=0.0, courier=0.0),
  ("by_customer", "prep_started"):       Policy(refund=0.5, merchant=0.5, courier=0.0),
  ("by_customer", "picked_up"):          Policy(refund=0.0, merchant=1.0, courier=1.0),
  ("by_merchant", "*"):                  Policy(refund=1.0, merchant=0.0, courier=0.3),
  ("by_system",   "*"):                  Policy(refund=1.0, merchant=1.0, courier=1.0),
}

Encoding the policy as data rather than branching code means Finance can reason about it, it can be audited, and changing it is a config change rather than a deploy. That is a small thing that reads as very senior.

The money itself runs as a saga: authorise the card at order time, capture on delivery, and compensate on cancellation. Never capture before the food is handed over — refunds cost payment fees and chargebacks cost far more. Cross-reference the payment system for the orchestration details.

4.7 Live tracking that does not lie​

Why it's hard. Customers watch the tracking map obsessively. If the ETA jumps from 15 minutes to 30 and back to 20, trust collapses even if the final delivery is on time. But the underlying prediction genuinely does change — the courier hit traffic, the store was slow. Showing raw model output produces a flickering, anxiety-inducing UI.

Solution — separate the internal estimate from the displayed promise.

class DisplayedETA:
    """Internal estimates update freely; the customer-facing number is governed."""
    def update(self, internal_mean: float):
        # Only move the display when the change is large enough to matter.
        if abs(internal_mean - self.shown) < 3 * 60:
            return
        # Never let it improve by more than a little at a time — a number that
        # jumps around reads as broken even when it improves.
        if internal_mean < self.shown:
            self.shown = max(internal_mean, self.shown - 2 * 60)
        else:
            self.shown = internal_mean                # be honest about delays, promptly
            self.notify("Your order is running a bit late")   # explain, don't just move
        self.last_changed = now()

Delays get communicated immediately and with a reason; improvements get applied gradually. That asymmetry matches how people actually experience waiting, and pointing it out shows product judgement alongside the engineering.

Push updates over a WebSocket per active order rather than letting the app poll — 3M orders/day with a 5-second poll during a 30-minute delivery window is a lot of wasted requests, and push gives you the courier's live position for the map anyway.

5. What breaks first​

EventFirst failureMitigation
Dinner peakCourier supply shortfall, ETAs inflateForecast-driven incentives 2h ahead; admission control ladder
Big game / weather eventDemand spike plus courier no-showsPause new orders per region rather than failing them late
Merchant POS integration downNo ready-time signal, prep model blindFall back to per-merchant historical priors; widen ETA uncertainty
Optimiser slow or unavailableAssignment stalls entirelyDegrade to greedy nearest-courier — worse, but never zero
Location index lagAssignments to couriers who movedTTL'd positions; validate at offer time
Grocery inventory badly staleSubstitution storm, shopper time wastedObservation feedback loop; hide low-availability SKUs at browse

The optimiser fallback row is worth calling out in the interview: the sophisticated component must have a dumb fallback. Min-cost flow is better than greedy, but greedy is infinitely better than nothing, and an optimiser without a fallback is a single point of failure for the entire marketplace.

6. Cheat sheet​

  • Assignment: 20–30s batching window (density-adaptive) → min-cost flow over ~50 candidates per order → sequential offers.
  • Objective is lateness, not distance. The cost function carries food quality, courier idle time, deadhead, and fairness.
  • ETA: decompose into prep / to-store / wait / drive / handoff; max(prep, travel) not sum; propagate variance; quote P75.
  • Batching: hard feasibility constraints, then price customer harm into the optimiser's cost. Don't policy it, price it.
  • Inventory: predict substitutions ahead of time, never block the shopper, and treat every stockout as a training label.
  • Supply: forecast 2h ahead; ladder of incentives → pricing → longer ETAs → admission control.
  • Cancellations: policy as data, keyed by (who, state); money as a saga with capture on delivery.
  • The one-liner: "A three-sided assignment problem where the objective is lateness, prep time is the dominant uncertainty, and the highest-leverage engineering is admitting when you cannot deliver rather than optimising harder."