Design a Ride-Sharing Dispatch Service

This page is one interview loop in three rounds. All three rounds design the same system. Each round opens with the interviewer raising the scope, and the design from the round before has to evolve to meet it.

You can start at any round. Rounds 2 and 3 open with a "Where we left off" summary that catches you up.

Loop Opener: What Is Ride Dispatch?

You Already Know One: a Taxi Dispatcher With a Radio and a Map

Picture an old taxi office. A dispatcher sits in front of a big city map with pins for every cab. The phone rings: "Pick me up at 5th and Main." The dispatcher looks at the map, picks the closest free cab, and calls it on the radio: "Car 12, pickup at 5th and Main, can you take it?" Car 12 says yes, the dispatcher moves its pin to "busy", and tells the caller a cab is coming. Only one car gets the job, even if three drivers shout "mine!" at the same time, because there is only one dispatcher.

A ride dispatch service is that office in software. Drivers' phones report where they are every few seconds. Riders ask for a ride. The service picks a driver, offers the trip to that driver's phone, and the driver accepts or declines.

A few words we'll use all page:

What Makes It Hard

• Everything moves. A place in a proximity search sits still for years. A driver moves 30 m between two pings. Our index is rewritten hundreds of thousands of times a second at national scale.
• Exactly one. Two drivers can tap "accept" in the same millisecond; two riders' requests can pick the same driver at the same moment. The answer must be one driver per trip and one trip per driver, every time.
• Nearest isn't best. The nearest car by straight line may be across a river. Giving every rider the nearest car in arrival order can strand the next rider.
• It's a market. When a concert ends, 20,000 people want rides from one block. Prices have to rise there, smoothly, without making prices jump from one street to the next.

The Question the Whole Loop Answers

How do we match each rider to exactly one good driver in seconds, fairly, while everyone is moving?

The answer grows every round:

• Round 1: keep live driver locations in memory by cell, find nearby available drivers, and make the offer and the acceptance conditional writes so a trip can only be taken once.
• Round 2: match in small batches instead of first-come-first-served, rank by road ETA, lock the driver as well as the trip, fence late acceptances, and add surge pricing.
• Round 3: turn the service into a marketplace of city cells across regions, with pooled and scheduled rides, a fairness objective, safety paths and a region failover that doesn't strand anyone mid-trip.

This loop reuses ideas from three earlier loops. The spatial index basics (cells, neighbors, exact distance) are taught in the proximity service loop; road ETAs come from the maps and routing loop; charging the rider and paying the driver belong to the payment processing loop. We link them instead of re-teaching them.

---

Round 1 · Mid-level · "Dispatch for One City's Taxi Company"

~35 min · SDE II (L5) · 1 region, 3 AZs · 5,000 drivers online at peak · 1,250 pings/s · 5 requests/s planned · first offer < 2 s · 99.9%

R1.1 Establish Design Scope

The interviewer says: "A taxi company in one city wants an app. Riders request a ride; a nearby driver gets it. Design the backend." Before drawing anything, we ask.

Out of scope for this round: surge pricing, batching several requests together, pooled rides, and scheduled rides.

R1.2 Functional Requirements, Derived Step by Step

Not yet: surge pricing, batch matching, pooled rides, scheduled rides.

R1.3 Non-Functional Requirements: the Questions

We name each quality in words first; the numbers come in R1.7.

• Time to match. A rider watching a spinner gives up fast. The first offer must leave our servers quickly, so that the common case ("the first driver accepts after a few seconds") ends in a match within about 10 seconds.
• Never two drivers on one trip. If two drivers both think they have the rider, one drives across town for nothing and both lose trust in the app. This is the correctness bar of the round.
• Availability. A taxi company's app being down at rush hour is lost income for every driver.
• Location write volume. Every online driver writes every 4 seconds, whether anything happens or not. Writes outnumber ride requests by more than 200 to one.

R1.4 The API

Drivers and riders keep one WebSocket each: a long-lived, two-way connection over TLS, so the server can push an offer or a status change the instant it happens instead of waiting for the phone to ask. Actions that need a clear answer (request, accept, decline) are ordinary HTTPS calls. See WebSocket, SSE and Long Polling.

Driver location (a WebSocket message, every 4 s)

jsonCopy
{ "type": "loc", "seq": 18231, "lat": 40.748412, "lon": -73.985661,
  "heading": 182, "speed_mps": 7.4, "ts": "2026-09-28T18:04:12.250Z" }

seq increases by one per ping on the phone, so the server can drop a ping that arrives after a newer one (phones reconnect, and old messages can arrive late). The phone's clock is not trusted for ordering; seq is.

Request a trip

httpCopy
POST /v1/trips HTTP/1.1
Host: api.citytaxi.example
Authorization: Bearer <rider token>
Idempotency-Key: 6f1c2d0e-7b5a-4d0c-9a51-3c2b8e1f0a77
Content-Type: application/json

{ "pickup":  { "lat": 40.748412, "lon": -73.985661 },
  "dropoff": { "lat": 40.761432, "lon": -73.977622 } }

jsonCopy
{ "trip_id": "t_7f3a91", "status": "REQUESTED", "created_at": "2026-09-28T18:04:13.020Z" }

The Idempotency-Key makes a retry safe: the trip is stored under the rider and that key, so a phone that lost the response and sends again gets the same trip back, not a second trip. If the retry finds the trip already stored, the server also makes sure the trip is still being matched (step 1.4's sweeper picks up any trip that isn't); a retry that only says "already have it" and does nothing else could leave a trip that nobody is working on.

The offer (pushed to one driver's WebSocket)

jsonCopy
{ "type": "offer", "trip_id": "t_7f3a91", "pickup": { "lat": 40.748412, "lon": -73.985661 },
  "distance_m": 640, "expires_at": "2026-09-28T18:04:28.060Z" }

Accept and decline

httpCopy
POST /v1/trips/t_7f3a91/accept HTTP/1.1
Authorization: Bearer <driver token>

httpCopy
POST /v1/trips/t_7f3a91/decline HTTP/1.1
Authorization: Bearer <driver token>

Status codes

Recap

• Pings every 4 s over a WebSocket, ordered by seq; offers pushed on the same socket.
• Trips requested with an idempotency key; accept and decline are HTTPS calls; 409 when the offer isn't yours any more.
• One offer at a time, 15 s to answer, 5 km search radius.

R1.5 Design Evolution: From a SQL Table to Conditional Offers

Each step is a problem, your turn to think, the answer, and what it costs us.

Step 1.0: The Baseline

A PostgreSQL table drivers(driver_id, lat, lon, status, updated_at) with a spatial index. Every ping runs UPDATE drivers SET lat = ..., lon = ... WHERE driver_id = .... A ride request runs "nearest available driver within 5 km" as a spatial query (PostGIS ST_DWithin, ordered by distance), sets the trip's driver, and sends the offer.

It works for a demo, and at 5,000 drivers it would even keep up for a while. The weaknesses show up as soon as we look at what the table does all day.

Step 1.1: 250 GPS Writes a Second Into SQL, and It Only Grows

Primitive: Geospatial Indexing: Geohash, Quadtree and S2

Step 1.2: Find Available Drivers Near the Pickup

Step 1.3: Two Drivers Accepted the Same Trip

Primitive: Distributed Locks and Leases

Step 1.4: The Driver Never Answered

Step 1.5: The Trip Jumped From Requested to Completed

Round 1 Step Summary

R1.6 Architecture v1

Synthesizing vector architecture diagram...

Pings flow left to right into memory; decisions flow through DynamoDB's conditional writes. The index learns each driver's status from DynamoDB's own change stream, never from a second write by the dispatch service.

Why the index gets status from the change stream. The dispatch service could write the driver's status to DynamoDB and then to Valkey. That's a dual write: a crash between the two leaves the index saying "available" for a driver who is on a trip (or the reverse), with no record that anything was missed. Instead, DynamoDB Streams (an ordered, per-item log of every change to the table, kept 24 hours) feeds a small Lambda function that copies status into the driver's hash as status_hint, with the item's version so an older change never overwrites a newer one. The hint can be a second behind. That's fine, because the hint only filters candidates; the conditional write in DynamoDB is what decides.

The same stream drives the rider's notifications: when a trip item changes to MATCHED, the Lambda pushes "driver on the way" to the rider's gateway connection. A crash can't lose that message, because the stream re-delivers until the function succeeds; the rider's app ignores a duplicate.

The car on the rider's map. Once a trip is MATCHED, the gateway holding the driver's socket forwards that driver's pings to the trip's channel (Valkey sharded pub/sub, SPUBLISH trip:<id>), and the gateway holding the rider's socket, subscribed to that channel, pushes them on. At the evening peak about 4,200 trips are in progress (R1.7), so about 1,050 position updates a second go to riders.

Tables

A trip item stays under 1 KB. Breadcrumbs (the pings along a trip) aren't stored in it.

Tracing a request that gets matched

Synthesizing vector architecture diagram...

The offer left about 40 ms after the request; the driver took about 6 s to tap. The timer still fires later and finds nothing to do.

Tracing an offer that times out

1. 18:10:02.000: trip t_91c0e2 is offered to driver d_3310 with offer_expires_at 18:10:17.000; a timer message is queued with a 16 s delay.
2. The driver doesn't respond.
3. 18:10:18.000: the timer message becomes visible; a worker picks it up about 20 ms later.
4. The worker runs SET status = REQUESTED, declined = [d_3310] if status = OFFERED AND offer_driver = d_3310. It succeeds.
5. It takes the next driver from the stored candidate list (re-checking the index for availability, since 16 seconds have passed), queues a new timer, writes the new offer, and pushes it. The rider has now waited about 16 s longer than in the happy path.
6. If d_3310's accept arrives at 18:10:18.050, its condition (status = OFFERED AND offer_driver = d_3310) fails: 409 Conflict, "This ride is no longer available."

R1.7 Numbers

Targets

Traffic

Memory

The index is tiny. We use a cache cluster for its speed and its failover, not its size.

Storage

Latency budget: request to offer on the socket (dependent steps add):

The phone's own network adds 100 ms to a second or more on top; that's why the target leaves room.

Monthly cost (us-east-1 on-demand list prices, 730 hours a month; check the AWS Pricing Calculator before quoting):

About 1.46M trips a month for $670: under a twentieth of a cent per trip.

R1.8 Trade-Offs

Geohash vs H3 for driver cells

Both would work for one city. We chose H3 because Round 2 counts supply and demand per cell for surge, and equal-distance rings make "widen the search by one ring" and "smooth across neighbors" simple. The geohash mechanics (prefixes, the 3×3 block, cell sizes by latitude) are worked through in the proximity loop.

In-memory index vs a database-backed index

For one city either works; the in-memory index wins because the data is disposable and the writes never stop.

R1.9 Failure Modes

R1.10 Pillar Check

R1.11 Round 1 Rubric and Follow-Ups

What a strong mid-level (L5) answer shows

• Keeps disposable, fast-changing positions in memory and durable trips in a database, and says why.
• Uses a cell index with rings, knows how far a ring reaches, and widens it only when needed.
• Refuses "check, then set", and makes the accept a single conditional write.
• Knows that DynamoDB TTL is not a timer, and builds a durable timer with an expiry check.
• Enforces a trip state machine on the server.
• Names the gap it leaves: a driver can still receive two offers at once.

Follow-up questions

1. "Why not put a TTL on each member of the cell set instead of on the driver's hash?" Answer: Valkey sets have no per-member TTL; only whole keys expire. The hash carries the TTL, readers skip members whose hash is gone or names another cell, and the reader removes those members. The 30-second keep-alive re-add covers the opposite problem, a member missing after a failover.

2. "The rider cancels at the same moment the driver accepts. What happens?" Answer: both are conditional writes on the same item. If the accept lands first, the trip is MATCHED, and the cancel (allowed from MATCHED) moves it to CANCELLED, and the driver is told. If the cancel lands first, the trip is CANCELLED, and the accept's condition (status = OFFERED) fails with 409. There is no state in which both "succeed" inconsistently.

3. "Why 16 seconds on the timer and not 15?" Answer: the offer expires at 15 s by the offer's own timestamp. The extra second gives an accept tapped at 14.9 s on a slow network time to arrive and win the conditional write before the timer moves the trip on. The timer's own condition (OFFERED to this driver) keeps it harmless either way.

Interview gotchas from this round's wrong answers

---

Round 2 · Senior · "1M Drivers, Surge, and No Double-Booking"

~40 min · Senior SDE (L6) · 1 region, 3 AZs · 2M drivers online at peak · 500,000 pings/s · 10M trips/day · 2,500 requests/s and 12,500 searches/s planned · dispatch P99 < 1 s · 99.99%

R2.0 Where We Left Off

This is what the candidate says aloud in the first 60 seconds of Round 2. If you're starting here, it's everything you need from Round 1.

Round 1 in 60 seconds. "We built dispatch for one city's taxi company: 5,000 drivers pinging every 4 seconds, 1,250 pings a second at peak, about 5 ride requests a second. Live positions live in Valkey, not SQL: a hash per driver with a 15-second TTL, and a set per H3 resolution-8 cell, with a keep-alive re-add so a lost set entry heals within 30 seconds. To find drivers we read k-rings around the pickup, 19 cells first and up to 169 for the full 5 km, and stop only when enough drivers lie inside the ring's guaranteed reach. Trips and driver state live in DynamoDB. The accept is one conditional write: MATCHED only if the trip is still OFFERED to this driver and not expired, so a second driver gets 409. Offers expire by a timestamp in that condition plus an SQS message delayed 16 seconds, never by DynamoDB TTL, and every trip move is a conditional update in a state machine. The index learns driver status from DynamoDB's change stream, never from a dual write. About $670 a month. Open costs: first-come-first-served matching, straight-line ranking, no surge, and a driver can still be offered two trips at once."

Architecture v1, compact

Synthesizing vector architecture diagram...

Round 1 in one picture: positions in memory, decisions in conditional writes, timers in a queue.

Round 1 step summary

Open costs: greedy matching; straight-line distance; driver can hold two offers; no prices that respond to demand.

R2.1 The Scope Raise

Interviewer: "We're now a national ride-hailing app. At a normal busy hour about a million drivers are online, and on the busiest nights of the year about two million. We do 10 million trips a day. At rush hour some riders wait 15 minutes while cars sit a few streets away. We need prices that rise where demand beats supply, without flickering from one street to the next. Last week a driver got two trips at once and both riders were furious. Rank pickups by real driving time. And dispatch has to feel instant."

Scope change

The "Not yet" list from R1.2 comes back: surge pricing and batch matching are now in scope. Pooled and scheduled rides stay out until Round 3.

R2.2 What Breaks in the Round 1 Design

The order we fix it in: matching first (2.1), because every later piece plugs into the batch; then ETAs as its cost function (2.2); then the two correctness fixes (2.3, 2.4); then surge (2.5); and last the ingest pipeline that everything reads (2.6).

R2.3 New Requirements and API Additions

A fare quote with the surge multiplier and its expiry

httpCopy
POST /v1/quotes HTTP/1.1
Authorization: Bearer <rider token>
Content-Type: application/json

{ "pickup": { "lat": 40.748412, "lon": -73.985661 },
  "dropoff": { "lat": 40.761432, "lon": -73.977622 }, "product": "standard" }

jsonCopy
{ "quote": "q1.eyJmIjoxNjIwLCJtIjoxLjM1LCJ4IjoiMjAyNi0wOS0yOFQxODowNjoxM1oifQ.9vK2...",
  "fare_cents": 1620, "surge_multiplier": 1.35, "pickup_eta_s": 240,
  "expires_at": "2026-09-28T18:06:13Z" }

The quote is a signed token: fare, multiplier, pickup and dropoff cells, product and expiry, with an HMAC signature from a key only the pricing service holds. The app can show it but can't change it, and we don't store a row per quote (a rider looks at many prices and books few). It's valid for 120 seconds. POST /v1/trips now carries the quote; the trip service checks the signature and the expiry against its own clock, and stores the fare in the trip. A used_quotes item keyed by the quote ID is written with attribute_not_exists, in the same transaction as the trip, so one quote can create only one trip.

Offers now carry an offer number

jsonCopy
{ "type": "offer", "trip_id": "t_7f3a91", "epoch": 4,
  "pickup": { "lat": 40.748412, "lon": -73.985661 }, "pickup_eta_s": 210,
  "fare_estimate_cents": 1180, "expires_at": "2026-09-28T18:04:28.060Z" }

httpCopy
POST /v1/trips/t_7f3a91/accept HTTP/1.1
Authorization: Bearer <driver token>
Content-Type: application/json

{ "epoch": 4 }

The driver status model, stored in the drivers table and shown in the driver app:

Offer cascades. A decline or a timeout sends the rider back into the next matching batch for that zone, with more priority each time (step 2.1), and with the drivers who already said no excluded. After 90 seconds without a match, the rider is told there are no cars nearby and offered a wider search.

Recap

• Quotes are signed, expire after 120 s, and are locked into the trip at booking.
• Every offer has an epoch; the accept must present it.
• Drivers are OFFLINE, AVAILABLE, OFFERED or ON_TRIP, and only AVAILABLE drivers get offers.

R2.4 Design Evolution: From Nearest Car to a Fair Market

Step 2.1: Greedy Matching Strands Some Riders

Synthesizing vector architecture diagram...

The batch loop replaces Round 1's fixed cascade: a rider whose offer fails simply joins the next batch with a bigger boost.

Step 2.2: The Nearest Car Is 10 Minutes Away Across a River

Step 2.3: A Driver Accepted Two Trips at Once

Primitives: Distributed Locks and Leases · Two-Phase Commit and Saga Orchestration

Step 2.4: A Late Accept After the Offer Expired

Drill: The GC pause that corrupted shared storage (why a lease that expires by time doesn't protect the store is the second wrong answer and the late-arrival table above; why optimistic concurrency in the store instead of an external lock manager, and its contention cost, is the paragraph "Why conditional writes in the store")

Step 2.5: Demand Spikes in One Area

Synthesizing vector architecture diagram...

Caps join at the last step, on every quote, so no snapshot, fallback or restart can drop them.

Step 2.6: 500,000 Location Writes a Second

Synthesizing vector architecture diagram...

One stream, two readers: the index gets positions within about half a second; the lake and surge get the same pings without touching the index.

Primitive: Message Queues vs Event Streams

Drill: The ride-hailing hotspot on New Year's Eve (why one fixed cell size fails when density varies a thousandfold is point 3, with R1's ring widening for sparse areas; why not GEORADIUS/GEOSEARCH on one key instead of our own cell index is the second wrong answer; the in-process spatial index alternative is in R2.7)

Round 2 Step Summary

R2.5 Architecture v2

Synthesizing vector architecture diagram...

Pings flow down the left into memory and the lake. Requests flow down the right into zone matchers, which lock drivers and trips in DynamoDB and push offers through the gateways. Everything that follows a decision (status hints, rider notices) comes from DynamoDB's own change streams.

Zone matchers. Each city is cut into matching zones of a few dozen square kilometers. Each zone is owned by one matcher task through a lease item in DynamoDB (renewed every 2 seconds, a fencing epoch on each renewal). If two tasks briefly both think they own a zone (a paused owner, a slow renewal), both may make offers; the driver and trip conditions still allow only one of any conflicting offers, so the lease only needs to be mostly right.

Tracing a batch match in zone nyc-mid-14, batch closing at 18:04:12.000:

Synthesizing vector architecture diagram...

Offers go out in parallel, so the batch pays for one offer's latency, not three. The lost lock on D2 costs R3 one more batch, 2 seconds.

Tracing a double-accept race. Trip t_7f3a91 is offered to D2 at epoch 4. D1 (whose epoch-3 offer expired) and D2 both tap accept within the same 10 ms.

1. D1's transaction checks the trip: offer_driver = D1? No (it's D2); offer_epoch = 3? No (it's 4). Cancelled. D1 gets 409, "This ride is no longer available."
2. D2's transaction checks the trip (OFFERED to D2 at epoch 4, not expired) and the driver (OFFERED, trip t_7f3a91, epoch 4). Both hold: trip MATCHED, D2 ON_TRIP. 200.
3. The trips table's change stream delivers the MATCHED change (epoch 4) to the notifier Lambda, which pushes "driver on the way" to the rider.
4. The timer for epoch 4 fires at 16 s, finds MATCHED, and does nothing.

Even if D1's request had arrived first, the result would be the same: its conditions fail on the driver and epoch, not on timing.

Tracing a surge quote

1. 18:03:00: Flink closes the 18:01–18:03 window. The concert cell 882a100d63fffff has D = 60, S = 10; smoothing gives 1.35 (step 2.5). The time smoothing starts from the previous minute's 1.00: 0.3 × 1.35 + 0.7 × 1.00 = 1.105, so this minute publishes 1.11.
2. 18:03:04: Flink writes the city's snapshot, version 52,918, and flips the pointer.
3. 18:04:00: the next window gives 1.35 again; 0.3 × 1.35 + 0.7 × 1.105 = 1.18. Snapshot 52,919 at 18:04:04.
4. 18:04:07: a rider in the cell asks for a quote. The pricing service's 10-second cache holds snapshot 52,918 (loaded at 18:03:58), so the multiplier is 1.11; the cap table has no cap for the city. Base fare $12.00 → $13.32. The signed quote expires at 18:06:07.
5. The rider books at 18:05:30 (within 120 s): the trip stores $13.32 and 1.11, whatever the snapshot says by then.

Losing an AZ. Gateways, matchers, updaters and routing servers run in three AZs; DynamoDB, Kinesis and SQS are regional. Drivers connected to the lost AZ's gateways reconnect to the others with jittered backoff; their hashes live on for 15 s, and a driver who takes longer simply reappears on their next ping. A reconnecting driver's gateway asks whether they hold a live offer and re-sends it. Valkey promotes replicas in the surviving AZs; the keep-alive re-add heals set entries lost to asynchronous replication within 30 s.

R2.6 Numbers and Cost

Traffic

Live state

Memory isn't the constraint; commands per second are.

Valkey commands at peak (planning estimates):

We plan 200,000 commands a second per cache.r7g.xlarge node (4 vCPU, 26 GiB; an assumption to load-test). 8 shards × 3 nodes = 24, 8 per AZ. Writes: 900,000 ÷ 8 primaries = 112,500 each, 56% busy; the replicas carry reads. After losing an AZ, every shard still has a primary (promoted where needed) and at least one replica: primaries stay at 56%, and 450,000 reads on 8 remaining replicas are 28%.

DynamoDB write units per trip (transactional items cost 2 units; the hold check is billed like one)

Per day: 10M × 25 + 2.5M × 17 = 292.5M write units; a month (30.4 days) is 8.89 billion.

At the planned peak, the trips table takes about 27,000 write units a second (about 24,000 before trip creation became a transaction with the quote check) and drivers about 17,000; both are under the default on-demand limit of 40,000 per table, but not by much, so we raise both quotas and set warm throughput before launch.

Storage

Latency budget: dispatch, from the batch closing to the offer on the driver's socket (dependent steps add; the three offers of a batch run in parallel, so they count once):

The target is measured from the batch closing. What the rider feels is up to 2 s of batch window plus this: about 2.1 s to the first offer at P99, plus the phone networks on both ends. The 1 s target leaves room for a slow routing call or a retried transaction.

Latency budget: rider search ("cars near you"): WAF and ALB 3 ms + index 4 ms + one ring widening 3 ms + ETA for 3 cars 30 ms + serialize 2 ms = 42 ms at P99.

Location freshness, from a ping reaching the gateway to the index: gateway buffer ≤ 100 ms + PutRecords about 30 ms + the reader's wait for its next poll (two readers share a shard's 5 reads a second, so each polls about 2.5 times a second) ≤ 400 ms + script and set writes about 5 ms = ≤ 535 ms. Add up to 4 s since the last ping: a position is at most about 4.5 s old, 63 m for a car at 50 km/h.

Availability. 99.99% of a 30.4-day month is 43,776 min × 0.0001 ≈ 4.4 minutes. We don't claim "five nines": 99.999% allows 5.26 minutes a year, less than one bad deploy or a single regional incident.

Monthly cost (us-east-1 on-demand list prices, 730 hours a month):

That's 304 million trips a month for about $29.9K: under a tenth of a cent per trip ($0.098 per thousand). The biggest lines are Valkey, DynamoDB and the gateways, in that order.

R2.7 Trade-Offs

Greedy vs batch vs continuous re-dispatch (figures are rough, for comparison only)

We batch in busy zones and fall back to greedy per zone when a batch has fewer than 2 riders or the solver misses its deadline.

The batch window length

Spatial index

Valkey index vs an in-process index per matcher. Each matcher could keep its own city's drivers in memory (an S2 or quadtree library), fed straight from the stream: no network hop, and lookups in microseconds. The costs: every process must consume every ping for its area and rebuild on start, and search tasks and matchers would each need their own copy. At one region with shared search and matching fleets, a shared index is simpler. Round 3's city cells make the in-process option more attractive.

Step Functions vs SQS for offer timers. Step Functions can run the offer cascade as a state machine with a 15-second wait. Standard workflows cost $0.025 per 1,000 state transitions; at about 10 transitions per request and 12.5M requests a day, that's about $95,000 a month. Express workflows are cheaper per request but bill for their whole duration while they wait (up to 5 minutes per execution). An SQS delay message per offer costs about $685 a month, and our conditional writes already hold the state machine. We chose SQS.

R2.8 Failure Modes

Primitive: Circuit Breaker, Bulkhead and Fault Tolerance

R2.9 Production Gotchas

R2.10 Pillar Check

R2.11 Round 2 Rubric and Follow-Ups

What a strong senior (L6) answer shows

• Replaces greedy matching with a batch assignment, works a small example by hand, knows the Hungarian algorithm's O(n³), and sees that minimizing the total can hurt one rider.
• Explains why a wait-time boost matters only when riders outnumber drivers.
• Locks the driver as well as the trip, in one transaction, before the offer goes out.
• Fences offers with an epoch, and shows that a condition without server time is still safe because status and epoch decide, not the clock.
• Designs surge with spatial and temporal smoothing, locked quotes, complete snapshots and caps as a separate layer.
• Sizes storage by the average rate and memory by the peak, and knows which of the two limits each component.

Follow-up questions

1. "Why not offer each trip to the 3 nearest drivers at once to save time?" Answer: with the driver lock, each of the 3 drivers would be locked for this trip and unavailable to anyone else for up to 15 s, although only one can win: we'd take 3 drivers off the market to fill 1 trip. Without the lock we're back to one driver holding several offers. Sequential offers chosen by the batch, with a short timeout, are the better trade.

2. "A matcher crashes between the offer transaction and the push. What happens?" Answer: the timer message was queued before the transaction, so 16 s later the timer worker finds the offer still OFFERED, expired and unanswered, releases the driver and the trip, and the rider goes back into the next batch. If the matcher's own retry runs first, it finds its offer already recorded and re-sends the push rather than skipping it.

3. "How do you know surge is working as intended?" Answer: we measure outcomes, not multipliers: completion rate and pickup wait in surging cells versus nearby cells, how fast supply arrives after a surge starts, and how often neighboring cells oscillate. And we replay past days through a changed pricing formula before shipping it.

Interview gotchas from this round's wrong answers

---

Round 3 · Architect · "Global Marketplace: Fairness, Pooling, Safety"

~45 min · Principal (L7) · 6 regions in 3 pairs · 5M drivers online summed over regional peaks · 1.25M pings/s · 25M trips/day · per-city SLOs · 99.99% per region

R3.0 Where We Left Off

This is what the candidate says aloud in the first 60 seconds of Round 3. If you're starting here, it's everything you need from Rounds 1 and 2.

Round 2 in 60 seconds. "We run national ride-hailing from one region: 2 million drivers at the weekly peak, 500,000 pings a second, 10 million trips a day, planned for 2,500 requests and 12,500 searches a second. Gateways batch pings into Kinesis; updaters write Valkey hashes and H3 cell sets at two complete resolutions, so a missing key always means empty; Flink computes surge and writes a 30-day Parquet lake sized by the average rate, about 4.9 TB. Matching runs in 2-second batches per zone as an assignment problem, Hungarian in O(n³), on road ETAs from the routing engine, with a wait-time boost that decides who gets scarce cars. An offer is a DynamoDB transaction that locks the driver and the trip and checks a separate holds table; every offer has an epoch, and accepts must present it, so late or paused accepts can't win. Timers are SQS delay messages. Surge is per cell, smoothed across neighbors and over time, published as complete snapshots, capped by a separate caps table, and locked into a signed quote. Dispatch P99 is about 109 ms after the batch closes. About $29.9K a month. Open costs: one region serves the country, one rider per car, no scheduling, no fairness measure, and nothing for safety."

Architecture v2, compact

Synthesizing vector architecture diagram...

Round 2 in one picture: positions flow through a stream into memory; decisions are DynamoDB transactions; everything downstream follows DynamoDB's change streams.

Round 2 step summary

Open costs: one region; one rider per car; no reservations; fairness unmeasured; no safety paths.

R3.1 The Scope Raise

Interviewer: "We're global now: hundreds of cities in dozens of countries, 5 million drivers online across our regions' peaks. Every city has its own rules: airport queues, licensing, which products are allowed. Product wants shared rides and rides booked for tomorrow morning. Drivers are posting that the algorithm is unfair. Riders want to share their trip with family and get help fast in an emergency. And last quarter a regional outage stranded riders mid-trip; that can't happen again."

Scope change

R3.2 What Breaks in the Round 2 Design

R3.3 New Requirements and API Additions

Product types in the request

httpCopy
POST /v1/trips HTTP/1.1
Authorization: Bearer <rider token>
Idempotency-Key: 0c9d7e21-43a8-4f5b-b1e2-7d6c5a4b3f21
Content-Type: application/json

{ "quote": "q1.eyJmIjo5NDAsIm0iOjEuMCwicCI6InBvb2wi...",
  "product": "pool", "seats": 1,
  "pickup": { "lat": 51.507351, "lon": -0.127758 },
  "dropoff": { "lat": 51.515419, "lon": -0.141099 } }

A scheduled ride adds "pickup_at": "2026-09-29T07:00:00+01:00", and the response has status: RESERVED.

City configuration (one document per city, versioned, loaded by that city's cell):

yamlCopy
city: london
home_region: eu-west-1
standby_region: eu-central-1
products: [standard, pool, scheduled]
matching:
  batch_window_s: 2
  max_pickup_eta_min: 15
  fairness_weight: 0.1        # minutes of ETA per idle minute (step 3.4)
surge:
  max_multiplier: 2.5
pool:
  max_detour_pct: 40
  max_detour_min: 8
  max_pickup_wait_min: 8
airport_queues:
  - name: LHR
    dispatch: first_in_first_out
licensing:
  required_documents: [private_hire_licence]

Share my trip

httpCopy
POST /v1/trips/t_4be1c2/share HTTP/1.1
Authorization: Bearer <rider token>

jsonCopy
{ "url": "https://share.rides.example/s/st1.eyJ0IjoidF80YmUxYzIiLCJ4IjoxNzkwNjIyMzAwfQ.K3q...",
  "expires_at": "2026-09-28T19:05:00Z" }

Emergency

httpCopy
POST /v1/trips/t_4be1c2/emergency HTTP/1.1
Authorization: Bearer <rider or driver token>
Content-Type: application/json

{ "lat": 51.511201, "lon": -0.133004, "kind": "rider_safety" }

Returns 202 Accepted with an incident ID. The phone also offers the local emergency number directly; our API never replaces it.

R3.4 Design Evolution: A Marketplace of City Cells

Step 3.1: Hundreds of Cities, Each With Its Own Rules

Primitive: Circuit Breaker, Bulkhead and Fault Tolerance

Step 3.2: Pooled Rides

Step 3.3: Scheduled Rides for 7 am

Step 3.4: Drivers Say It's Unfair

Step 3.5: Share My Trip, Get Help

Step 3.6: A Region Is Down Mid-Trip

Primitive: Cloud Disaster Recovery and Multi-Region Active-Active

Round 3 Step Summary

R3.5 Global Architecture

Synthesizing vector architecture diagram...

Each region runs its home cities and holds warm replicas of its partner's. Front doors forward by the city map, not by DNS, so a phone that lands in the wrong region still reaches the city's owner.

Tracing a pooled match in London

Synthesizing vector architecture diagram...

The insertion is checked on times from the routing matrix, and committed only if the car's route hasn't changed since the matcher read it.

Tracing a scheduled ride

1. 21:14 the evening before: a rider books a 07:00 pickup in a suburb. The trip is RESERVED, fare locked.
2. 04:00: the forecast shows 3 available drivers expected in that resolution-7 cell in the 06:45 slot; below the threshold of 5, so the reservation offer shows a £4 early-booking bonus (an illustrative amount; the policy sets it).
3. 06:00 (T − 60 min): offered to 2 opted-in drivers forecast nearby. One accepts at 06:04 and becomes RESERVED_FOR this trip.
4. 06:30 (T − 30 min): that driver's batch offers are limited to trips ending within 10 minutes' drive of the pickup by 06:55.
5. 06:52: the driver is 6 minutes away; the trip moves to MATCHED and then ARRIVING as normal.
6. Had nobody accepted by 06:40 (T − 20 min), the trip would have entered the normal batches with the maximum boost.

Tracing a regional failover mid-trip: eu-west-1 fails at 18:00:00

Synthesizing vector architecture diagram...

About two minutes from failure to new matches: 30 s of detection, a minute of confirmation, then reconnects. Trips in progress never stopped.

R3.6 Numbers and Cost

Drivers and traffic per region (each region's own peak; the pairs are in overlapping time zones)

Daily totals. As in Round 2, a day's average online is a quarter of the peak: 1.25M drivers, 312,500 pings/s. Trips scale with it: 10M × 2.5 = 25M trips a day (289/s average), about 760M a month.

Storage

Standby sizing, with per-AZ rounding. Each region provisions Valkey and routing for its own peak plus its partner's, since the partner's peak comes at nearly the same hour. Round 2 needed 4 Valkey shards and 3 routing servers per million drivers:

Routing load with pooling: Round 2's 31 vCPUs busy per 2M drivers, plus 24% for pool insertions, is about 29 vCPUs busy in a 1.5M region and 39 in a 2.0M region. Six 16-vCPU servers have 96 vCPUs: 30% and 40% busy, 45% and 61% with an AZ lost. No extra servers are needed for pooling.

Monthly cost. We build it from Round 2's measured lines (us-east-1 prices), per million drivers at peak:

Replication between the paired regions has no cross-region data transfer charge for global tables; we pay the replicated writes in the standby, and nothing else for moving the data.

Prices outside us-east-1 differ. We assume us-west-2 matches us-east-1, and uplifts of about +10% in eu-west-1 and ap-south-1 and about +20% in eu-central-1 and ap-southeast-1 (assumptions; replace with each region's list prices from the calculator).

About 760M trips a month for $125K: $0.16 per thousand trips, up from Round 2's $0.098. The difference is the price of surviving a region: every region pays for its partner's peak in Valkey and routing, and for replicated writes.

Per-city SLO example (London): time to first offer P99 < 3 s (2 s window + dispatch); match within 60 s for 97% of standard requests; pickup ETA within ±2 minutes of the quoted ETA for 90% of trips. Each city's targets live in its config; failing one pages that city cell's owners.

R3.7 Trade-Offs

City cells vs one global system

Pooling efficiency vs detours

Fairness vs ETA. Every minute of fairness boost can cost a rider up to that minute. We cap the term at 2 minutes and measure, by replay, how much total ETA it costs before raising a city's weight. The trade is explicit, owned and audited, which is the point: before, it was being made silently by where drivers happened to park.

Closing the loop. Round 1 answered "who gets this trip?" with one conditional write. Round 3 answers it with batches, road ETAs, surge, pooling, reservations and fairness terms, across six regions. Underneath, the invariant never changed: a driver reaches ON_TRIP for a trip only through a conditional write that proves they hold that trip's current offer, and they can hold only one. Every feature in this loop plugs into that same write.

R3.8 Failure Modes

R3.9 Runbook and Incident Response

Golden signals, per city and per region OPS 8 · REL 6

Emergency surge cap procedure REL 5

1. Decide scope: one cell, a list of cells, or the whole city.
2. Write the cap rows (command 2). The pricing service loads caps every 10 s; confirm quotes in the area show the capped multiplier.
3. If the formula itself is broken, pin the last good snapshot version and set the city's kill switch to 1.0.
4. List trips charged above the cap since the incident began, for automatic refunds.
5. Remove the caps only after the fix is deployed and a replay of the incident window shows sane multipliers.

Fallback to greedy matching (a solver or routing problem in one city): set the city's matching mode (command 3); matchers read it every 10 s. Greedy with straight-line fallback ETAs is worse but never stuck.

Regional failover procedure REL 13

1. Confirm it's the region: several services, health checks and the AWS Health Dashboard agree.
2. Check the partner's replica lag (command 4) to estimate what may be lost.
3. Flip each affected city in the city map, incrementing its owner epoch (command 5), written in the standby region. Confirm the front doors in every region now forward those cities to the standby.
4. Restart the change feeds on the promoted side: confirm the standby's stream consumers for the failed region's tables are running and acting for the flipped cities, and that their iterator age is falling (commands 6 and 7). Without them, the standby's index gets no status hints and riders get no notifications.
5. Trigger the "re-send active trip state" job for the flipped cities.
6. Scale gateways and cells in the standby (command 8); watch Valkey (command 9) and time to first offer.
7. Failback later, city by city at quiet hours: flip back with a new epoch after the old region has caught up on replication, then run the conflict reconciliation report.

Go deeper: CLI playbook

Plain commands an on-call engineer runs one at a time. Replace names, times and IDs with real ones.

textCopy
# 1. Alarms firing for dispatch in a region
aws cloudwatch describe-alarms --region eu-west-1 --state-value ALARM --alarm-name-prefix dispatch-

# 2. Emergency surge cap for one city (the pricing service loads caps every 10 s)
aws dynamodb put-item --region eu-west-1 --table-name surge_caps --item '{"scope":{"S":"city#london"},"max_multiplier":{"N":"1.5"},"reason":{"S":"storm emergency"},"expires_at":{"N":"1790704800"}}'

# 3. Switch one city's matching to greedy
aws ssm put-parameter --region eu-west-1 --name /dispatch/london/matching-mode --value GREEDY --type String --overwrite

# 4. Replica status of a failed region's trips table, seen from the standby
aws dynamodb describe-table --region eu-central-1 --table-name trips-euw1 --query "Table.Replicas"

# 5. Flip a city to the standby region with a new owner epoch
aws dynamodb update-item --region eu-central-1 --table-name city-map --key '{"city":{"S":"london"}}' --update-expression "SET owner_region = :r, owner_epoch = owner_epoch + :one" --expression-attribute-values '{":r":{"S":"eu-central-1"},":one":{"N":"1"}}'

# 6. The standby's stream consumers for the failed region's trips table
aws lambda list-event-source-mappings --region eu-central-1 --function-name trip-notifier-euw1

# 7. Iterator age of that consumer over the last 15 minutes
aws cloudwatch get-metric-statistics --region eu-central-1 --namespace AWS/Lambda --metric-name IteratorAge --dimensions Name=FunctionName,Value=trip-notifier-euw1 --start-time 2026-09-28T18:00:00Z --end-time 2026-09-28T18:15:00Z --period 60 --statistics Maximum

# 8. Scale out gateways in the standby
aws ecs update-service --region eu-central-1 --cluster dispatch --service gateways --desired-count 300

# 9. State of the standby's driver index
aws elasticache describe-replication-groups --region eu-central-1 --replication-group-id driver-index

R3.10 Pillar Check

R3.11 Round 3 Rubric and Follow-Ups

What an architect (L7) answer adds over L6

• Turns one service into city cells with config, cell-by-cell rollout and per-city SLOs.
• Treats pooling as route insertion with explicit promises, and commits it with the same conditional-write discipline as single rides.
• Plans scheduled rides as forecast plus early commitment plus fallback, not as a normal request at a later time.
• Makes fairness a measured, capped, audited part of the objective, and names the owner of the policy.
• Builds safety paths that skip normal shedding and retention.
• Designs region failure around what the phones already know, knows the limits of global tables (asynchronous, last writer wins, transactions atomic only locally, MRSC without transactions), and routes by a city map rather than by DNS.

Follow-up questions

1. "Why not make the standby region active for the same city, so failover is instant?" Answer: two regions writing the same city's drivers and trips would resolve conflicts by last writer wins, and a transaction in one region isn't atomic in the other: a driver could end up matched in both. One writer per city with an owner epoch keeps the invariant, at the price of about two minutes of failover for new requests. Trips in progress don't notice.

2. "How do you know the fairness term isn't just moving unfairness somewhere else?" Answer: we measure the distributions, not one number: idle time and earnings per online hour across drivers, pickup waits across riders and neighborhoods, before and after, by replay and then by a zone-level A/B test. A change ships only if the driver spread narrows without the rider spread widening past a set limit.

3. "A pool rider's detour promise is broken by traffic after the match. Whose problem is it?" Answer: ours, visibly: we detect it from the ETA updates, stop inserting more riders into that car, adjust the fare per policy, and count it in the city's detour metric, which feeds back into that city's limits.

Interview gotchas from this round's wrong answers

---

Loop Closer: Interview Strategy for All Three Rounds

How to Run Each 60-Minute Round

For how to spend a single 45-minute round, see the 45-minute interview blueprint.

The Two Sentences That Matter Most

• Opening any round: "Positions are disposable and change every 4 seconds, so they live in memory by cell; decisions are permanent, so each one is a conditional write that proves the trip is still offered to this driver, with an expiry checked by our clock and a durable timer to move on."
• When scale arrives: "I'll match in short batches as an assignment problem on road ETAs, lock the driver and the trip in one transaction before the offer goes out, fence every offer with an epoch, and keep every override, from driver holds to surge caps, in its own layer that no update can overwrite."

Well-Architected Review Sheet

Interviewers rarely ask "which pillar is this?". They ask the pillar's question in plain words. Rehearse one sentence per row.

Rubric Across Levels