System design interview question

Design Uber

Q: How do you index millions of moving points so that "available drivers within 2 km" is a microsecond query while positions change every few seconds?

A Location service per city holding an in-memory index: cell → set of driver ids, and driver → (cell, position, status, ts). Cells at roughly 1 km (H3 resolution 8 or S2 level 13). Pings update both maps; a nearby query reads the pickup cell plus one ring, expanding to two rings if fewer than 10 available candidates. Last-known positions are mirrored to Redis with a TTL, which is both the rebuild source after a restart and the fallback query path (GEOSEARCH) during it. Very dense cells can be subdivided by using a finer level for the query in those areas.

Q: Offer each request to the closest driver immediately, or wait a moment and solve the assignment across many requests and drivers?

Dispatch groups incoming requests by area and runs a matching tick every 1–2 seconds in busy areas (immediately when there is no contention). Each tick builds a cost matrix of ETA from candidate drivers to requests, adjusted for fairness and acceptance history, and solves the assignment (Hungarian for small matrices, a greedy approximation for large ones). The result is a proposed driver per request; offers go out sequentially with a lock and a 15 s acceptance window; declines feed back into the next tick. The trip row's guarded update is the final arbiter. Explain that "wait a second to match better" is the same principle as the matchmaking queue for games.

Q: Hundreds of thousands of trips in progress, millions watching the map. How do positions and status changes reach the right phones?

Persistent WebSocket per active rider and driver with a registry of user → gateway server. Trip status changes: Trip service emits an event; a consumer looks up both participants and pushes; missed pushes are recovered by the client fetching trip state on reconnect. Assigned-driver position: the Location service forwards that driver's pings directly to the rider's socket at the fast interval. Map cars: clients subscribe to the cells in their viewport; a fan-out consumer aggregates pings per cell every 3–4 s and pushes one message per subscribed rider with lightly obfuscated positions and rotating tokens. Everything on the map path is at-most-once by design.

Q: Pickup ETA and fare are shown before the rider commits. How are they computed fast and honoured fairly?

Quote path: one routing call for distance and duration, a Redis read for the surge multiplier of the pickup cell, and a precomputed pickup ETA per cell (refreshed every few seconds from the nearest available drivers) so the quote does not wait on candidate ranking. Store quote id, inputs, multiplier, fare, and a 5-minute expiry. Trip creation references the quote and inherits its fare. At completion, compare the driven route to the quoted one; adjust only under defined rules (rider-requested stops, material detours, waiting time, tolls) and itemise them on the receipt. Fallback when routing is unavailable: haversine distance × a per-city road factor and historical speed profile, with the quote marked approximate.

Q: Which parts of this system need strong consistency, and how do you keep them small?

A trips table per city shard with a state column, a driver_id, and a partial unique index on driver_id for active states; every transition is an UPDATE with a WHERE on the expected current state; the outbox pattern publishes trip events after commit. Redis holds the driver lock (advisory, TTL), live statuses, and last positions. A sweeper resolves trips stuck in transitional states by consulting the source that knows (dispatcher heartbeats, driver pings). The payment charge uses the trip id as its idempotency key so a retried completion cannot double charge. Name the boundary explicitly in the interview: strong consistency for trips and assignment, eventual for everything else.

Match riders with nearby drivers in seconds, track trips live, and price them, for millions of concurrent users worldwide.

Last updated 2026-09-20. Difficulty: hard. Patterns: geospatial, matching, streaming, marketplace. Reported at Uber and 4 more with Pro.

Walk through a strong candidate's answer, turn by turn.

The interviewer asks, the candidate answers and draws, and you press Next. Pause to answer yourself at the key decisions, and ask the coach anything along the way.

Walk through it Take the mock interview

Functional requirements

Rider requests a trip from pickup to destination. Gets an upfront price and an ETA for the pickup before confirming.
Match the request with a nearby available driver. Driver can accept or decline; on decline or timeout, offer to the next candidate.
Live location of drivers. Riders see nearby cars on the map before requesting and their assigned car approaching after.
Trip lifecycle. Requested → matched → driver en route → in progress → completed → paid. Both sides see status changes in real time.
Pricing and surge. Upfront fare from distance, time, and a demand multiplier per area. The quoted fare is honoured if the route is followed.
Payments and receipts. Charge the rider at trip end; pay out drivers on a schedule. Assume the payment system from the payments question.
Out of scope. Ratings, support, fraud detection, pooled rides, and the driver onboarding and document verification process.

Non-functional requirements

Scale (20 M trips/day · 5 M concurrent drivers). Drivers are the write-heavy population: every online driver reports location every few seconds.
Match time (p95 < 10 s to a confirmed driver). Includes the driver's acceptance window. Slow matching is the most visible failure.
Location freshness (< 5 s stale on the rider's map). Drives the ping interval and the push path to riders.
Consistency (one driver, one trip). A driver is never assigned two trips at once and a request is never matched twice. Hard invariant.
Availability (99.99 % for request and match). Degrade pricing and ETA before degrading matching; a trip with an approximate ETA beats no trip.
Latency for ETA and price (p95 < 1 s). Shown before the rider confirms; uses the routing engine from the maps question.
Regional isolation. A city's matching must not be affected by load or failure in another region. Data locality for privacy.

Back-of-envelope estimates

Driver location pings per second: ~1.25 M. 5 M concurrent drivers × one ping every 4 s = 1.25 M pings/s. The dominant write stream; each ping ~100 B → ~125 MB/s ingest.
Trip requests per second: ~230 avg · ~1 k peak. 20 M trips/day ÷ 86 400 ≈ 230/s average; evening and event peaks 4–5×. Matching is CPU cheap per request; the hard part is the geospatial lookup under the ping write load.
Concurrent active trips: ~350 k. 230 trips/s × ~25 min average trip = 230 × 1 500 s ≈ ~350 k trips in progress at once (Little's law). Each has two live participants receiving updates.
Rider map updates per second: ~2–5 M pushes. Riders browsing see ~10 nearby cars refreshed every 4 s; riders in a trip see one car. With ~2 M riders viewing the map: 2 M × 10 ÷ 4 = 5 M car-position pushes/s. Batch per rider into one message: ~500 k messages/s.
Geo index size: ~500 MB. 5 M drivers × ~100 B (id, cell, lat, lng, heading, status, ts) = ~500 MB. Fits in memory in one region's index; partition by city or coarse cell for isolation and parallelism.
Nearby-driver query cost: ~9 cells · ~50 candidates. A pickup query covers the pickup's cell and its 8 neighbours at a cell size of ~1 km (S2 level 13 or H3 res 8). In a dense city that is ~50–200 drivers, then filter by status and ETA. Tens of microseconds in memory.
Trip event storage: ~40 GB/day. Each trip stores ~20 state events plus a location trace of ~400 points × 20 B ≈ 10 KB. 20 M × (10 KB + 1 KB events) ≈ ~220 GB/day raw; compress traces 5× → ~40–50 GB/day. Hot for a week, then cold storage.

Components

Rider app: Requests trips, shows nearby cars and the assigned driver approaching, and receives trip status over a persistent connection. Sends its own location during the trip for the trace and for arrival detection.
Driver app: Reports location every few seconds while online, receives trip offers with a countdown, accepts or declines, and drives the trip states (arrived, started, completed).
API + WebSocket gateway: REST for requests and state changes; WebSocket per active rider and driver for pushes. Routes to the regional deployment for the user's city. Holds a connection registry (user → server) so services can push.
Location service (ingest · geo index): Ingests driver pings, validates and smooths them, updates the in-memory geo index (driver → cell) and the last-known position store, and publishes pings to the stream. Answers "available drivers near (lat, lng)".
Geo index (in-memory · S2/H3 cells): Sharded by city. Maps each cell id to the set of driver ids currently in it, plus a driver → (cell, position, status, ts) map. Updated on every ping; a nearby query reads the pickup cell and its neighbours.
Trip service (state machine): Owns the trip lifecycle and its invariants. Creates the request, runs the matching flow with the Dispatch service, applies driver responses, records state changes transactionally, and emits trip events.
Dispatch service (matching): Given a request, gets candidates from the geo index, ranks by ETA (routing service) and other factors, and offers the trip to drivers one at a time or in a small batch with an acceptance timeout. Enforces one-driver-one-trip with a lock per driver.
Pricing & surge: Computes upfront fares from distance and time estimates, applies the surge multiplier for the pickup cell, and stores a fare quote id honoured at trip end. Surge is recomputed per cell every minute from request and supply counts.
Routing / ETA (maps question): The routing engine: driver-to-pickup ETAs for ranking candidates, and pickup-to-destination distance and time for pricing. Treated as an external dependency with a strict latency budget and a fallback (haversine × factor).
Event stream (Kafka · pings + trip events): Two families of topics: driver location pings (keyed by geo cell, huge volume, short retention) and trip events (keyed by trip id, durable). Consumers: surge computation, analytics, the trace archiver, and the rider push fan-out.
Trip DB (Postgres (sharded by city) / Spanner): Trips, their state history, fare quotes, and assignments. Sharded by city since trips never cross cities. Strong consistency for the assignment row is what backs the one-driver-one-trip guarantee.
Live state store (Redis · locks · last positions): Driver status and lock (available / offered / on-trip) with TTLs, last-known positions for fast reads, connection registry for pushes, and surge multipliers per cell.
Trace & analytics store (object storage · warehouse): Compressed trip traces and all events for receipts, disputes, and analytics. Written by stream consumers, never on the request path.
Payment system: Charges the rider at trip completion against the stored payment method, using an idempotency key derived from the trip id. Driver payouts run on a schedule from completed trips.

User flows

Driver location ingest and the geo index. The biggest stream in the system. Every online driver reports every few seconds; the index must reflect it within a second and serve nearby queries at the same time.
1. Driver app sends a location ping over its WebSocket every 4 s while online. Adaptive interval: faster (2 s) when moving toward a pickup, slower (10 s) when parked. Batched if the network was briefly down.
2. Gateway forwards to the Location service for the driver's city. City is resolved once at connect from the first fix and sticks; a driver crossing a city boundary is re-homed on the next ping.
3. Location service validates and smooths the fix, then updates the geo index. Reject impossible jumps (teleporting), snap to the road if a routing tile is handy, compute the cell id. Index update: remove driver from old cell set, add to new cell set, update driver record. In-memory, microseconds.
4. Last-known position and status are written to the live state store; the ping is published to the stream. Redis holds driver:{id} → {pos, status, ts} with a short TTL so a driver that stops pinging disappears from "available" automatically. Kafka carries the ping to surge, analytics, and the rider push fan-out.
5. Riders viewing the area receive a batched update of nearby car positions. A fan-out consumer groups pings by cell and pushes one message per rider per interval containing the cars in the rider's viewport cells. Positions are lightly obfuscated for riders not yet matched (privacy of drivers).
Rider requests a trip: price, then match. Two phases: an upfront quote the rider can decline, then a request that must find a driver within seconds. The quote id ties them together.
1. Rider enters a destination; the app asks for an upfront fare and pickup ETA.
2. Pricing gets distance and duration from routing, applies the cell's surge multiplier, and stores the quote. Fare = base + per-km × km + per-min × min, times surge, with minimums. The quote is stored with its inputs and a 5-minute expiry so the fare is honoured even if surge rises while the rider decides. Pickup ETA comes from the nearest few available drivers' ETAs, precomputed for the cell.
3. Rider confirms; Trip service creates the trip in state "requested" and asks Dispatch to match. Idempotency key on the request so a retry cannot create two trips. The trip row is written before matching starts, so a crash mid-match leaves a visible requested trip that a sweeper can resume or cancel.
4. Dispatch queries the geo index for available drivers near the pickup. Pickup cell plus its 8 neighbours at ~1 km, expanding to a second ring if fewer than N candidates. Filter to status available and a fresh timestamp. Typically 20–200 candidates in a city centre.
5. Dispatch ranks candidates by ETA to the pickup and other factors. Batch ETA request for the top candidates by straight-line distance and heading (a driver moving away is worse than one slightly farther but approaching). Secondary factors: acceptance rate, time since last trip for fairness, vehicle match. Budget 300 ms; fall back to haversine × 1.4 if routing is slow.
6. Dispatch locks the best driver and pushes the offer with a countdown. SET NX on driver:{id}:lock with a TTL slightly longer than the offer window. A driver already locked by another dispatcher is skipped. The offer carries pickup, estimated fare share, and the deadline.
Driver accepts (or declines) and the trip proceeds. The assignment is the one place where two writers race: the driver's acceptance and the offer timeout. The trip row's state guard settles it.
1. Driver taps accept within the window.
2. Trip service assigns atomically: trip requested → matched with this driver, driver lock → on_trip. UPDATE trips SET status=matched, driver_id=? WHERE id=? AND status=requested. Zero rows updated means the offer already expired or was cancelled; the driver gets a "too late" response. Then the Redis lock is converted to on_trip with no TTL. This ordering means the durable row is the authority and the lock is a fast advisory.
3. If the driver declines or the timer expires, Dispatch releases the lock and offers to the next candidate. Sequential offers keep the driver experience clean; after two or three declines, broadcast to a small batch and take the first acceptance (the UPDATE guard makes that safe). Declines lower the driver's ranking for a while. If no driver accepts within ~60 s, the trip fails with a clear message and the quote is released.
4. Both apps receive the match; the rider sees the real driver and car approaching. trip.matched event → push to both sockets via the connection registry. From now on the rider receives the specific driver's pings, un-obfuscated, at the fast interval.
5. Driver marks arrived, started, and completed; each is a guarded state transition and an event, and the trace is archived. Start and completion can also be inferred from location (rider and driver co-located and moving; arrival at destination) as a fallback when the driver forgets to tap. Completion freezes the route actually driven for fare adjustment rules.
6. Trip service charges the rider through the payment system with a trip-derived idempotency key and releases the driver. Final fare = quoted fare unless the route deviated materially or waiting time applied; adjustments are itemised. Payment failure does not block the driver's release; it goes to a retry and collections path.
Surge pricing from live supply and demand. A per-cell multiplier recomputed every minute from request counts and available drivers, smoothed so it does not whipsaw, and locked into quotes.
1. Trip requests and driver pings flow through the event stream keyed by cell. Demand signal: quotes requested and trips requested per cell per minute (including ones that did not match). Supply: distinct available drivers per cell per minute.
2. Pricing service aggregates demand and supply per cell over a sliding window. Windows of 5 minutes sliding by 1. Neighbouring cells are blended so a hotspot does not create a cliff at a street boundary. Minimum sample counts avoid surging an empty suburb because of one request.
3. Multiplier is computed from the demand-to-supply ratio and smoothed. A monotone function of ratio with steps (1.0, 1.2, 1.5, 2.0…), capped, with hysteresis so it rises quickly and falls gradually. The goal is to move supply toward demand without shocking riders with a multiplier that changes between the quote and the confirm.
4. Multipliers are written to the live store and pushed to driver apps as a heat map. Drivers see where surge is and move toward it, which is the mechanism by which surge actually increases supply. Riders see the multiplier on the quote.
5. A quote freezes the multiplier at quote time; confirmation honours it within the expiry. This is what prevents the "price changed when I tapped confirm" complaint. After expiry, the rider gets a fresh quote with the current multiplier.
Failures: driver goes offline mid-offer, dispatcher crashes, region degrades. The invariants must survive crashes at every point. Locks with TTLs, guarded state transitions, and a sweeper make the system self-healing.
1. A driver with an outstanding offer loses connectivity. The offer times out server side regardless of the client. The lock TTL expires. Dispatch moves to the next candidate. If the driver's accept arrives late, the guarded UPDATE rejects it.
2. A dispatcher instance crashes while holding a driver lock and a requested trip. The lock TTL frees the driver within seconds. A sweeper in the Trip service finds trips in "requested" older than a threshold with no active dispatcher heartbeat and restarts matching. The rider sees a slightly longer wait, not a stuck request.
3. The routing service is slow or down. Dispatch ranks by haversine distance with a heading penalty; pricing uses a distance factor and historical speeds for the cell. Quotes carry a flag that ETA is approximate. Matching continues; accuracy degrades. This is the explicit "degrade pricing before matching" decision.
4. The geo index shard for a city restarts. It rebuilds from the last-known positions in Redis (a few hundred MB) in seconds, then catches up from live pings. During the rebuild, nearby queries fall back to a Redis GEOSEARCH on the last-position set, slower but correct.
5. A whole region is degraded. Cities are isolated deployments: a failure in one region cannot slow another. Within the region, the trip database is the last thing to give up; if it is unavailable, new requests are rejected fast with a retry message rather than accepted into a state that cannot be recorded.

Deep dives

The geo index: finding nearby drivers under 1 M writes per second

How do you index millions of moving points so that "available drivers within 2 km" is a microsecond query while positions change every few seconds?

Classic spatial indexes (R-trees) are built for mostly static data; rebalancing them at a million updates per second is hopeless. Moving-object indexes use a fixed spatial grid instead: assign each point to a cell, keep a set per cell, and a nearby query is "read this cell and its neighbours". Updates are two set operations. This is the approach behind Uber's H3 and Google's S2 usage.

Cell size is the key parameter: too large and each query scans thousands of drivers; too small and a 2 km query touches hundreds of cells. About 1 km cells with a one-ring expansion, growing to two rings when candidates are scarce, works for cities.

In-memory cell grid (S2 / H3) per city, sets of drivers per cell chosen
Redis GEO (geohash sorted set) situational: smaller scale, or as the rebuild source and fallback for the in-memory index
PostGIS / database spatial index rejected
Quadtree with rebalancing situational: extremely uneven density where fixed cells are wasteful

The answer: A Location service per city holding an in-memory index: cell → set of driver ids, and driver → (cell, position, status, ts). Cells at roughly 1 km (H3 resolution 8 or S2 level 13). Pings update both maps; a nearby query reads the pickup cell plus one ring, expanding to two rings if fewer than 10 available candidates. Last-known positions are mirrored to Redis with a TTL, which is both the rebuild source after a restart and the fallback query path (GEOSEARCH) during it. Very dense cells can be subdivided by using a finer level for the query in those areas.

A driver sits exactly on a cell boundary and jitters between two cells every ping. Cost?

Two set operations per ping either way, so no extra cost to the index. The rider-facing map might flicker if positions are grouped by cell; smooth positions client side and debounce cell changes for display only, never for the index.

How do you handle a stadium letting out: 5 000 requests in one cell in two minutes?

The index is fine: reads scale with candidates, not requests. Dispatch is the pressure point: thousands of concurrent matchings competing for the same few hundred drivers. Batch matching helps here: collect requests in the hot cell for a second and solve an assignment problem (requests × drivers by ETA) rather than first come first served. Surge does the rest by pulling in supply.

Why per city and not one global index?

Isolation and locality. A city's drivers never match riders in another city, so there is no cross-city query. Per-city shards mean a bug or overload in one city cannot affect another, deployments can be regional for latency and data residency, and each shard fits comfortably in memory. Cities that border each other (a metro area) are treated as one shard.

What does the index return for a driver whose last ping was 40 seconds ago?

Nothing: the query filters by freshness (say 15 s) because a stale position means an unreliable ETA and possibly an offline driver. The Redis TTL on driver status backs this up: without pings, the driver falls out of "available" automatically.

Matching: nearest driver vs optimal assignment

Offer each request to the closest driver immediately, or wait a moment and solve the assignment across many requests and drivers?

Greedy nearest-driver matching is simple and feels instant, but it is myopic: in a busy area it can send the only nearby driver to a rider 3 minutes away when a rider 1 minute away is about to request, leaving the second rider with a 10-minute pickup. Batched matching collects requests for a short window (a second or two) and assigns drivers to minimise total pickup time, which improves the average and the tail.

The trade is latency versus quality, and driver experience: drivers dislike offers that flip. In practice the large platforms run short batch windows in dense areas and near-greedy elsewhere.

Short-window batch assignment with ETA as cost, greedy fallback chosen
Greedy nearest available driver situational: sparse areas and off-peak, where there is no contention to optimise
Broadcast offers to many drivers, first to accept wins rejected: only as a last resort after several sequential declines

The answer: Dispatch groups incoming requests by area and runs a matching tick every 1–2 seconds in busy areas (immediately when there is no contention). Each tick builds a cost matrix of ETA from candidate drivers to requests, adjusted for fairness and acceptance history, and solves the assignment (Hungarian for small matrices, a greedy approximation for large ones). The result is a proposed driver per request; offers go out sequentially with a lock and a 15 s acceptance window; declines feed back into the next tick. The trip row's guarded update is the final arbiter. Explain that "wait a second to match better" is the same principle as the matchmaking queue for games.

A driver declines three offers in a row. What happens to them and to the riders?

Each rider is re-offered to the next candidate within seconds; they never see the decline. The driver's acceptance rate drops, which lowers their ranking for a while and, on some platforms, temporarily pauses offers. Persistent decliners are a supply quality problem handled outside dispatch.

How do you decide the batch window length?

Measure pickup time and match time as a function of window length per area type. Dense areas gain from 1–3 s; sparse areas gain nothing and should match instantly. Make it adaptive: window = f(requests per second in the area), capped at a few seconds so the rider's spinner never feels long.

Two dispatchers in the same city: how do they avoid offering the same driver?

The per-driver lock in Redis (SET NX with TTL). Whoever sets it owns the driver for the offer window. Partition dispatch by area so this rarely happens in the first place; the lock handles the boundary cases.

What is the invariant and where exactly is it enforced?

One driver has at most one active trip; one trip has at most one driver. Enforced at the durable layer by the guarded UPDATE on the trip row and a unique partial index on (driver_id) WHERE status IN (matched, in_progress). The Redis lock only reduces wasted offers; correctness does not depend on it.

Real-time updates to riders and drivers

Hundreds of thousands of trips in progress, millions watching the map. How do positions and status changes reach the right phones?

Two push patterns coexist. Trip-scoped pushes (status changes, the assigned driver's position) go to exactly two people and must be reliable. Map browsing pushes (cars near you) go to many riders, are approximate, and can be lossy. Treating them the same wastes resources; treating them differently is the design.

A persistent connection per active user with a connection registry, as in the chat question, is the base. The fan-out consumer for map cars reads the ping stream by cell and pushes batched updates to riders subscribed to those cells.

WebSocket per user; trip events pushed reliably; map positions fanned out per cell, batched and lossy chosen
Polling every few seconds rejected
Push everything through one topic per user rejected

The answer: Persistent WebSocket per active rider and driver with a registry of user → gateway server. Trip status changes: Trip service emits an event; a consumer looks up both participants and pushes; missed pushes are recovered by the client fetching trip state on reconnect. Assigned-driver position: the Location service forwards that driver's pings directly to the rider's socket at the fast interval. Map cars: clients subscribe to the cells in their viewport; a fan-out consumer aggregates pings per cell every 3–4 s and pushes one message per subscribed rider with lightly obfuscated positions and rotating tokens. Everything on the map path is at-most-once by design.

A rider's phone goes through a tunnel for 30 s during a trip. What do they see after?

On reconnect the client fetches GET /trips/{id} for the authoritative state and the driver's current position, then resumes the stream. Anything pushed during the gap is irrelevant because the current state supersedes it. The app shows "reconnecting" rather than stale movement.

Why obfuscate car positions on the browse map?

Precise, continuous positions of identifiable drivers let anyone track a specific person. Rounding positions, rotating anonymous tokens per session, and showing only a few cars limits that. After matching, the rider legitimately needs the exact position of one driver, and gets it.

How many gateway servers and how do you size them?

Roughly 7 M concurrent connections at peak (drivers plus active and browsing riders) at 30–50 k per server: a few hundred servers per large region. Drivers are the constant load; riders spike with demand. Autoscale on connection count, and drain connections gracefully on deploys as in the chat design.

ETA and upfront pricing

Pickup ETA and fare are shown before the rider commits. How are they computed fast and honoured fairly?

Both depend on the routing engine, which is expensive and external to this system. Pickup ETA needs driver-to-pickup times for several candidates; fare needs pickup-to-destination distance and time plus surge. Both are shown in under a second and must be good enough that riders trust them.

Upfront pricing changes the contract: the rider agrees to a number, so the platform bears the risk of traffic and route changes. The quote must be stored with its inputs and honoured within an expiry, with a clear policy for adjustments.

Routing-based quote stored with inputs, per-cell surge frozen at quote time, adjustments only for defined deviations chosen
Metered fare (distance and time at completion) situational: regulatory requirements or as the adjustment basis for large deviations
Precomputed zone-to-zone price table situational: airport flat fares, or as the fallback when routing is down

The answer: Quote path: one routing call for distance and duration, a Redis read for the surge multiplier of the pickup cell, and a precomputed pickup ETA per cell (refreshed every few seconds from the nearest available drivers) so the quote does not wait on candidate ranking. Store quote id, inputs, multiplier, fare, and a 5-minute expiry. Trip creation references the quote and inherits its fare. At completion, compare the driven route to the quoted one; adjust only under defined rules (rider-requested stops, material detours, waiting time, tolls) and itemise them on the receipt. Fallback when routing is unavailable: haversine distance × a per-city road factor and historical speed profile, with the quote marked approximate.

The quoted fare is honoured but the driver is paid on distance and time. Who eats the difference?

The platform, by design. The quote is an estimate that is right on average; per-trip errors net out across millions of trips. The risk is systematic bias, so the ETA-versus-actual and fare-versus-metered error distributions are tracked per city and fed back into the estimation models.

How is the pickup ETA per cell precomputed?

A small job per city runs every few seconds: for each cell with recent demand, take the nearest few available drivers from the geo index and their routing ETA to the cell centre, keep the best. Cache in Redis with a short TTL. Cells with no drivers show "no cars nearby" rather than a guess.

Surge changes between quote and confirm. Which applies?

The quote's, within its expiry. That is the entire point of freezing the multiplier in the quote: the rider decides on a known price. After expiry, a fresh quote with the current multiplier, shown clearly as changed.

Trip state, invariants, and the database

Which parts of this system need strong consistency, and how do you keep them small?

Most of the system is eventually consistent and lossy by design: positions, maps, surge. The exceptions are the trip lifecycle and the assignment invariant. Those live in a relational database sharded by city, with guarded state transitions, and everything else is derived from the events the trip service emits after commit.

Keeping the strongly consistent core small is what lets the rest scale: the database sees a few hundred writes per second per city, not the million-per-second ping stream.

Relational trip DB sharded by city, guarded transitions, outbox events, Redis for advisory locks and live state chosen
Everything in Redis for speed rejected
Event-sourced trips (the event log is the truth) situational: teams already running event sourcing

The answer: A trips table per city shard with a state column, a driver_id, and a partial unique index on driver_id for active states; every transition is an UPDATE with a WHERE on the expected current state; the outbox pattern publishes trip events after commit. Redis holds the driver lock (advisory, TTL), live statuses, and last positions. A sweeper resolves trips stuck in transitional states by consulting the source that knows (dispatcher heartbeats, driver pings). The payment charge uses the trip id as its idempotency key so a retried completion cannot double charge. Name the boundary explicitly in the interview: strong consistency for trips and assignment, eventual for everything else.

A rider cancels at the same instant the driver accepts. Outcome?

Both issue guarded UPDATEs: cancel requires status=requested or matched; accept requires status=requested. The database serialises them; one succeeds and the other sees zero rows and gets a 409. Whichever won is the truth, and the events tell both apps. Cancellation fees are decided by which happened first per the recorded timestamps.

Why shard by city rather than by trip id?

Locality and isolation: dispatch, surge, and analytics all operate per city, so co-locating a city's trips makes those queries local and lets you deploy a city's stack in its region. Trip id sharding spreads one city across all shards and makes "active trips in this city" a scatter-gather. The cost is uneven shard sizes, handled by splitting the largest metros.

How would you run a migration of the trips table with 350 k trips in flight?

Additive schema changes only, applied online; dual-write for a new column during transition; never lock the table. For a resharding, move whole cities during their quiet hours with a brief write pause per city, since the shard key is the city.