In a ride-hailing dispatcher, when would you match riders to drivers in short batching windows instead of greedily assigning each rider the nearest driver?
answer
- locally versus globally optimal
- riders compete for the same drivers
- riders x drivers cost matrix
- the window is added wait
- density decides, per area
basics
~20 sBatch where demand and supply are dense enough that riders in the same few seconds compete for the same drivers; a joint assignment then lowers total pickup time. Where requests are sparse, greedy matching is simpler and adds no wait.
solid answer
~50 s**Greedy** matching gives each request, on arrival, its best available driver. It is simple and adds no wait, but it is **locally optimal**: an early rider can take the only driver that suits a later rider. **Batching** holds requests for a short window, often a second or two, builds a matrix of pickup ETAs for riders x nearby drivers, and solves an **assignment problem** to minimise total or worst-case ETA. Example: ETAs A-X 2, A-Y 3, B-X 4, B-Y 10 minutes; greedy with A first gives 2 + 10 = 12, the joint optimum gives 3 + 4 = 7. The costs are added wait, solver compute that grows quickly with batch size, and tuning. So I would batch in **dense areas at peak**, and use greedy or a very short window where a window rarely holds more than one rider.
go deeper
Recall the two strategies: assign each rider immediately, or wait a moment and assign several riders together.
Work a small example where greedy is worse, and explain how a cost matrix and an assignment solver fix it.
Describe the operational costs - wait, solver compute, ETA matrix load, declines - and the greedy fallback when the solver times out.
Decide per area from density and metrics, choose between total and worst-case objectives, and run the rollout as an experiment rather than a global switch.
## The two strategies A **ride-hailing dispatcher** decides which available driver gets each ride request. - **Greedy matching** - when a request arrives, rank nearby available drivers by pickup ETA and offer the ride to the best one immediately. - **Batched matching** - hold incoming requests for a short **window**, then look at all waiting riders and all nearby available drivers together and pick the assignment that is best **for the whole batch**. Neither is correct in general. The choice is a trade-off between **latency and simplicity** on one side and **global match quality** on the other. ## Why greedy can be poor Greedy decisions are made one rider at a time, in arrival order. Consider two riders and two drivers, with pickup ETAs in minutes: | | Driver X | Driver Y | |---|---|---| | Rider A | 2 | 3 | | Rider B | 4 | 10 | - **Greedy, A first**: A takes X (2), leaving B with Y (10). Total 12, and B waits 10 minutes. - **Joint assignment**: A takes Y (3), B takes X (4). Total 7, and the worst wait is 4. A gives up one minute and B gains six. Greedy cannot see this, because when it decided for A, B's request did not exist yet. The effect grows when many riders and drivers are packed together, which is exactly what happens downtown at rush hour or after a large event. ## How batching works 1. **Collect** requests for a window, per area, for example one to two seconds. 2. **Gather candidates** - for each rider, a bounded set of nearby available drivers from the geo index. 3. **Build a cost matrix** - rows are riders, columns are drivers, cells are pickup ETAs from the ETA service; impossible pairs get infinite cost. 4. **Solve** - an optimal assignment algorithm (for example the Hungarian algorithm or a min-cost flow) or a fast heuristic (sort all pairs by cost and take them greedily without reusing a rider or driver). 5. **Claim and offer** - each chosen pair still goes through the conditional driver claim; a failed claim or a decline sends the rider into the next window. ```pseudocode every windowLength per area: riders = waitingRequests(area) if riders is empty: continue drivers = union of nearestAvailable(r, limit = 20) for r in riders cost = etaService.matrix(riders, drivers) # rows x columns pairs = solveAssignment(cost) # minimise total ETA for (rider, driver) in pairs: if not claimDriver(driver, rider): # conditional write requeue(rider) ``` The window length and candidate limit are illustrative. ## The costs of batching - **Added wait** - every rider waits up to one window before any offer goes out. A window must stay short compared with typical pickup times. - **Compute** - optimal assignment scales roughly with the cube of the batch size, so batches are kept small by **partitioning by area** and capping candidates. - **ETA load** - a matrix call asks for riders x drivers ETAs instead of a short list per rider. - **Objective choice** - minimising **total** ETA can leave one rider with a long wait; adding a cap or penalty for the **worst** wait trades a little total for fairness. - **Declines** - a driver who declines breaks the plan; expected-value costs that include acceptance likelihood help. - **Operational complexity** - windows, partitions and solver timeouts all need tuning and monitoring. ## When each wins | Situation | Better choice | Reason | |---|---|---| | Sparse requests, few riders per window | Greedy | Batches hold one rider, so waiting buys nothing | | Dense area at peak | Batching | Riders compete for the same drivers; joint assignment helps | | Very tight latency expectation | Greedy or very short window | Wait budget is too small | | Shared or pooled rides | Batching | Pairing riders with each other is inherently a joint problem | A common production shape is **adaptive**: the window length is chosen per area from recent demand, collapsing towards zero where requests are sparse. ## Deciding as a lead - Define the **metric first**: average pickup time, a high percentile of pickup time, completion rate, driver idle time. - **Experiment** by area, because the benefit depends on density; a global switch hides where batching helps and where it only adds wait. - Keep the **greedy path** as a fallback when the solver or ETA matrix times out. - Remember that the double-assignment guard is needed in **both** designs; batching improves the choice, not the safety.
- Minimising total pickup time leaves one rider with a very long wait. How would you adjust the objective?Add a penalty that grows faster than linearly with each rider's ETA, or a hard cap that rejects pairs above a threshold, so the solver trades a little total time for a better worst case. Riders who have already waited through earlier windows can also get a priority weight, so they are not repeatedly passed over.
- The assignment solver times out during a demand spike. What should dispatch do?Fall back to greedy for that window: rank each rider's candidates and claim drivers in arrival order. Matching quality drops a little, but riders keep getting offers. Shrinking the area partitions or the per-rider candidate limit also reduces solver work for the next windows.
Greedy is seating restaurant guests at the best free table the moment each walks in; batching is pausing a minute to seat the next few groups together so that a large party is not left without a big table.
saying these in an interview costs you the question
- Batching is always better because it finds the global optimum.
- Greedy nearest-driver matching gives the lowest total pickup time.
- Longer batching windows have no cost to riders.
- Batching removes the need for a double-assignment guard.
- One global window length works for every city and hour.