In this article
Before you start
This page is one step of the distributed systems interview learning path.
Why interviewers ask this
A wrong dispatch design costs real minutes for real people, so a round on a ride, delivery or game-lobby system usually reaches this question. Candidates report versions of it in interviews for ride-hailing, food-delivery and game companies, as a delivery question, a ride-dispatch backend or a battle-royale lobby.
The question separates three levels. A weak answer says "find the nearest driver" and stops. A strong answer names the pieces: a location index, a candidate search, a matching rule and an offer step. A Staff-level answer explains why the matching rule should look at many requests together, what that costs in waiting time, and how the system stays correct when a driver ignores an offer or a region goes down. It also separates matching, which picks pairs, from dispatch, which carries the pair through to a confirmed trip.
Dispatch and matching from first principles
- Dispatch
- Dispatch is the end-to-end process in a marketplace that turns a request into a confirmed job, covering candidate search, the choice of a pair, the offer to the supplier, the accept or decline, and any retry.
- Assignment problem
- The assignment problem is the task of pairing each of n requests with a different one of n suppliers so that the total cost of all pairs is as small as possible, given a cost for every possible pair (with unequal sides, extra dummy rows or columns make the table square).
- Batching window
- A batching window is a short, fixed stretch of time, a few seconds, during which a matching service collects incoming requests and then decides all their pairs in one step instead of one at a time.
In plain words
Picture a taxi rank with several taxis and several people waiting. A clerk who sends the nearest taxi to each person as they walk up works fast. That clerk may send the only taxi that suits the second person to the first. A clerk who waits a moment, looks at everyone, and then pairs them up wastes less driving. The analogy breaks in one place. A real platform cannot see every future request, so it only compares the requests it has collected so far.
In one precise sentence, dispatch and matching keeps a live map of free suppliers. It builds a cost for each nearby pair and chooses the pairs with the lowest total cost. Then it offers each pair to its supplier.
Step 1: Keep a live map of supply and demand
A location index is a store that always knows where each free driver is. Drivers send their global positioning system (GPS) position every few seconds, and the service files each driver under a geo cell. A geo cell is a small fixed area of the map with an identifier, so that finding nearby drivers means reading a few cells instead of scanning every driver.
Uber's H3 grid is one public example: it divides the globe into hexagons, and the company uses it to measure supply and demand per hexagon, for instance for surge pricing. A hexagon is a handy shape for this because all six of its neighbors sit at the same distance from its center, where a square has two distances (sides and corners), as the Uber article explains. The grid has sixteen resolutions, and each finer one has cells of one seventh the area.
The load is a back-of-the-envelope sum: with 100,000 free drivers (illustrative) each sending one update every 4 seconds (illustrative), the index absorbs 25,000 writes per second.1
You now have the input of everything that follows: a fresh, searchable picture of where supply is.
Step 2: Narrow candidates and score each pair
A new request needs candidates, and scanning every driver is wasteful. The matcher looks up the request's cell and the rings of neighbor cells around it. On a hexagon grid, the cell plus k rings holds 1 + 3k(k + 1) cells: 7 cells for one ring, 19 for two, 37 for three.1 With 100,000 drivers spread over 2,000 cells (illustrative), that is about 50 drivers per cell, so a two-ring search checks about 950 drivers instead of 100,000.1
Each candidate pair then gets a cost, most often the ETA from the driver to the pickup, taken from a routing service. Real systems add terms such as a driver already heading that way, fairness between drivers, or the quality of the trip, but the output is the same: a cost for every candidate pair. This is a bipartite graph, with drivers on one side, requests on the other, and a cost on every link.
You now have a small table of costs instead of a whole city to search.
Step 3: Batch requests and pick the lowest total cost
A greedy rule assigns each request the cheapest free driver at the time it is handled. It is fast and simple, and it is often not the best overall, because the cheapest driver for one request may be the only good driver for the next. The fix is to collect requests for a batching window, build the cost table, and solve the assignment problem on it. The textbook method, Kuhn's Hungarian method (1955), in its later O(n³) form (Edmonds and Karp, 1972), needs on the order of n cubed steps for n requests: 1,000 steps for n = 10 and 1,000,000 for n = 100.1 Trying every pairing is hopeless, since 100 requests have a factorial with 158 digits.1
The window has a price. An order that arrives at a random moment inside a window of w seconds waits w/2 seconds on average: 1.0 second for a 2-second window and 2.5 seconds for a 5-second one.1 The window is worth it when the saving in ETA is much larger than that wait.
Step 4: Offer the job, wait, and retry
A chosen pair is only a proposal. The offer service sends the job to the driver, starts a time limit, and waits for accept or decline. If the driver declines or the time limit passes, the request goes back into the next batch, with the declining driver excluded for this request, so that it is never offered the same job twice. If the driver accepts, the service records the assignment once and marks the driver busy so no second offer reaches them.
Recording the accept must be idempotent, meaning a repeated message changes nothing, because phones retry messages. The same care applies to the notification path; see webhooks for retries and duplicate delivery. You now have the whole loop: a live map, candidate scoring, a joint choice, and an offer with a way back.
Step-by-step description
- Drivers are filed under map cells.
- Nearby cells give scored candidates.
- One assignment picks the pairs.
- The offer is sent and retried.
- A location index keeps live driver positions in map cells.
- The matcher scores candidates by ETA.
- A batch matcher picks the pairs with the lowest total.
- An offer service re-dispatches when a driver declines.
Knowing it is half the job. Saying it is the other half.
Interview Clozo is an AI interview copilot for real interview rounds: it hears the question and puts a strong answer on your screen, and you say it in your own words. See the features or how it works.
Start Free Trial →Worked example
Take three free drivers and three new orders, with these illustrative ETAs in minutes. Driver 1 needs 2, 3 and 9 for orders 1, 2 and 3. Driver 2 needs 3, 8 and 9. Driver 3 needs 7, 9 and 4.1
Nearest-first handles the orders in arrival order. Order 1 takes driver 1 (2 minutes). Order 2 then has only drivers 2 (8) and 3 (9) left and takes driver 2. Order 3 takes driver 3 (4). The total is 2 + 8 + 4 = 14 minutes.1 The best pairing sends driver 2 to order 1 (3), driver 1 to order 2 (3) and driver 3 to order 3 (4), a total of 10 minutes.1 Order 1 got a slightly worse driver, and the total fell by 4 minutes. With three drivers there are only 6 possible pairings, so a reader can check every one by hand.1
| Quantity | Value (computed or illustrative) |
|---|---|
| Total ETA, nearest-first, 3 orders | 14 minutes |
| Total ETA, best pairing, 3 orders | 10 minutes |
| Simulation mean total ETA, nearest-first, 4 orders | 22.83 minutes |
| Simulation mean total ETA, batched best pairing, 4 orders | 21.35 minutes |
| Mean saving per order | 0.37 minutes (about 22 seconds) |
| Trials where batching was strictly better | 51.7% |
| Mean added wait, 2-second window | 1.0 second |
| Mean added wait, 5-second window | 2.5 seconds |
| Driver location writes, 100,000 drivers | 25,000 per second |
The simulation drops 6 drivers and 4 orders at random points of a 10 km by 10 km square (illustrative), with 2 minutes of ETA per kilometer, over 3,000 seeded trials.1 In more than half of them the joint choice beat nearest-first, and the average saving of about 22 seconds per order is larger than the 1.0 to 2.5 seconds the window adds on average.1 The numbers depend on the made-up geometry, so the useful lesson is the method: run the comparison on your own traffic before choosing a window.
Text description of the diagram
- Nearest-first totals 14 minutes of ETA.
- The best pairing totals 10 minutes.
Trade-offs and edge cases
Minimum total cost is not the only goal. Nearest-first has the lowest decision time and the highest waste; batched minimum-cost has the lowest total wait but adds the window; stable matching, from Gale and Shapley (1962), looks for pairs in which no driver and no request would both prefer each other to their assigned partner, which matters when both sides have preferences, as with a driver choosing among orders. It optimizes a different thing, so the two are not interchangeable.
Text description of the diagram
- Greedy assigns each request as it arrives.
- Batched matching solves one assignment problem per window.
- Stable matching leaves no pair that would both prefer to switch.
Edge cases that interviewers probe:
- Hot spots. A stadium letting out puts thousands of requests in a few cells. Search wider rings or split the busy area into more cells, and expect a longer batch.
- Boundaries. A driver just across a cell edge is a good candidate for a request just inside it; this is why the search reads neighbor rings, not only the request's own cell.
- Region failure. A sensible design keeps each city's state in one shard so a matching decision never needs a cross-region lock. Use consistent hashing or a city map to place shards; the distributed cache page covers moving keys when a node is added. When the shard holding a city fails, driver locations are soft state: a standby shard rebuilds them from the next GPS pings within a few update intervals. Offers and accepted assignments go to a replicated durable store, so the failover node resumes them and does not double-assign a driver.
- Duplicates. Each driver can sit in only one offer at a time, and concurrent matchers must not offer the same driver twice; see concurrency interview questions for locks and compare-and-set.
- Overload. Under peak demand, shed work early with limits, as in a distributed rate limiter, and widen the window gradually rather than failing.
Payment for the finished trip is a separate problem with its own retry rules; see how to design a payment system. Event streams that measure supply and demand per cell look like an ad click aggregator pipeline.
How to answer it in an interview
How would you design dispatch and matching for a ride or delivery app?
I would split it into four parts. A location index keeps live driver positions in map cells. For each request I read nearby cells and score candidates by estimated arrival time. Then I collect requests for a short window, a few seconds, and solve one assignment problem to minimize total wait, because nearest-first can be worse overall. Finally an offer service sends the job, waits for an accept with a time limit, and re-dispatches if the driver declines. The trade-off is that the window adds a small wait to buy better pairs. For scale I would shard by city.
The spoken structure: name the four parts in order, say why you match in batches, state the cost of the window, then add sharding and retries.
Common mistakes
- "I give each request the nearest free driver." (wrong) It is fast but can raise the total wait. (right) "Nearest-first is my baseline; I batch for a few seconds and solve for the lowest total cost."
- "Matching and dispatch are the same thing." (wrong) Matching only picks pairs. (right) "Matching picks pairs; dispatch also covers the offer, the accept or decline, the time limit and the retry."
- "I scan every driver for every request." (wrong) That does not scale. (right) "I index drivers by map cell and search the request's cell and its neighbors."
- "Stable matching and minimum-cost matching are the same." (wrong) They optimize different things. (right) "Minimum cost lowers the total; stable matching removes pairs that would both prefer to switch."
- "The accept message is processed once." (wrong) Messages are retried and can arrive twice. (right) "I make the accept idempotent and guard each driver against two live offers."
Follow-up questions
How do you design a system that helps a delivery driver decide which orders to pick up, and how does the platform assign orders at scale?
On the driver side, rank offered orders by expected earnings per hour, using payout divided by the travel, waiting and delivery time. On the platform side, replace that per-driver choice with the batched assignment above, so that orders and drivers are paired together and each driver sees only a few offers.
How do you design a matchmaking system for a 50-player battle-royale lobby with short queue times across regions?
A battle-royale matchmaker has no separate supply side: every player is both. Group players by region and a skill band, fill a lobby of 50 from the band, and widen the band as a player waits, so the 30-second queue limit becomes a deadline that widens the skill band. Keep one queue shard per region and move players across regions only when a region is short.
Is matching the same thing as dispatch?
No. Matching chooses which supplier and request go together, while dispatch also sends the offer, handles accept, decline and time-out, and retries.
What happens when a driver does not answer an offer?
The offer's time limit expires, the driver is excluded for that request, and the request returns to the next batch. The service records the expiry so a late accept from that driver is refused.
What is the difference between stable matching and minimum-cost matching?
Minimum-cost matching lowers the total cost of all pairs. Stable matching leaves no driver and request who would both rather be paired with each other, which can cost more in total.
How do you keep dispatch reliable under peak demand?
Keep each city's state in its own shard, limit requests at the edge, widen the batching window before dropping work, and make every offer and accept idempotent so that retries are safe.
- Dispatch and matching finds candidates by map cell, scores them by ETA, picks pairs, then offers and retries.
- Nearest-first is a fast baseline that can raise the total wait; a batching window lets one assignment choose better pairs.
- The window adds about half its length in wait per order, so measure the saving against that cost.
- Matching picks pairs; dispatch also owns the offer, the time limit and the re-dispatch.
- Shard by city, make accepts idempotent, and never let one driver hold two live offers.
Sources
- H3: Uber's Hexagonal Hierarchical Spatial Index — Uber Engineering (Brodsky), accessed 2026-10-26, 27 Jun 2018
- H3 documentation: Hexagonal hierarchical geospatial indexing system — H3 project (official documentation), accessed 2026-10-26, 26 Oct 2026
- The Hungarian method for the assignment problem — Naval Research Logistics Quarterly (Kuhn), 1 Mar 1955
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems — Journal of the ACM 19(2) (Edmonds and Karp), 1 Apr 1972
- College Admissions and the Stability of Marriage — The American Mathematical Monthly (Gale and Shapley), 1 Jan 1962
