5. Ride-Sharing (Uber) Advanced + Geospatial

A. Realistic Interview Prompt

This problem introduces a dimension none of the previous four have: geography. Every prior design point (fanout, routing, ordering) assumed identity-based lookups (a user ID, a client ID); here the fundamental query is "who/what is physically near this point," which a standard database index cannot answer efficiently at all. The second, equally load-bearing idea is that matching a rider to a driver is a genuine race for a single, physical, exclusive resource — two riders cannot be assigned the same driver, which forces a real consistency decision in a system that would otherwise lean entirely eventual.

B. Difficulty

Advanced + a genuinely distinct sub-domain (geospatial indexing) that most candidates haven't touched in other systems. Similar in spirit to Chat System in that there's no purely "naive but functional" V1 — even the most basic version requires picking a way to index location, because a naive full-scan-and-filter approach (P below) fails obviously and immediately, not just at scale.

C. What This Problem Tests

• Whether you know that "find things near a point" needs a specialized spatial index (geohash/quadtree/S2/H3), not a plain B-tree index or a linear scan with a distance filter
• Recognition that a match is a check-then-act race for an exclusive resource — the same class of bug named explicitly in Rate Limiter (N) and the LLD Parking Lot problem, now expressed as "assign this driver," and requiring a genuinely atomic compare-and-swap
• Judgment about where strong consistency is actually necessary (the assignment step) versus where it's not (location updates, ETA estimates) — an unusually narrow island of strong consistency inside an otherwise eventually-consistent system
• Comfort with "overwrite, don't accumulate" as the right model for a rapidly-changing, low-value-per-update stream (location pings) — a deliberately different data-lifecycle decision than message/post history
• Awareness that a long-running, multi-step process (request → match → accept → pickup → trip) benefits from a durable workflow/orchestration pattern rather than being modeled as a single synchronous call

D. Requirements

Functional

1. A rider can request a trip from a pickup location to a destination and get matched with a nearby available driver
2. A driver can accept or decline a match offer; on decline (or timeout), the system retries with the next-best driver
3. Both rider and driver can see the other's live location during an active trip
4. Drivers continuously report their current location while online

Non-Functional

• Low matching latency — a rider should be matched with a driver in <10 seconds; this is the entire product experience, not a background job
• High-frequency location updates at massive scale — this document uses 5M drivers reporting location every ~4 seconds as the standard illustrative input
• Strong consistency for the assignment step specifically — exactly one rider must end up matched to a given driver at a given time; this is the one place in the whole design where "eventually consistent" is not acceptable
• High availability for location tracking and search — a brief delay in seeing a driver's dot move is a minor UX issue; failing to find any driver at all is a much bigger one

Out of scope: payments, pricing computation itself (surge is discussed at a conceptual level only, S), driver background checks/onboarding.

E. Clarifying Questions

F. Assumptions

• Confirmed: request → match → accept/decline → live-tracking as the core functional loop.
• Assumption: straight-line/geospatial-proximity matching is an acceptable first approximation for "nearby," refined by ETA in the ranking step (O) — the standard simplification every major source makes before introducing a full routing engine.
• Assumption: location updates are pure "current state," with no requirement to retain a full location history for matching purposes (E's clarifying question 2) — this is the assumption that unlocks the overwrite-based model in N.
• Assumption: concurrent match offers on the same driver are possible and must be handled correctly (E's clarifying question 4) — the more interesting, more commonly-asked version of this problem, and what forces the atomic-assignment deep dive (P).
• Assumption: surge pricing is discussed conceptually as an extension (S) but not designed as a full pricing engine — mirrors Rate Limiter's ranking-style "layer, not rearchitecture" treatment of a hard extension.

G. Capacity Estimation

H. Core Entities

I. API Design

POST /v1/trip-requests          { rider_id, pickup, destination } -> { request_id }
GET  /v1/trip-requests/{id}     -> { status, driver_info? }
POST /v1/drivers/location       { driver_id, lat, lng } -> 200          (called every ~4s, N)
POST /v1/match-offers/{id}/respond   { accept: bool }                   (driver's response, Q)
GET  /v1/trips/{id}/location    -> { lat, lng, eta }                    (polled or WebSocket, R)

Why the match offer is a distinct resource from the trip request itself: a single trip request can generate a sequence of offers to different drivers if earlier ones decline or time out (Q) — modeling the offer separately from the request lets that retry loop be expressed cleanly as "create a new offer" rather than mutating the request's state machine in place for every attempt.

J. Basic / Naive High-Level Design (V1)

The simplest thing that satisfies the functional requirement in isolation: store every driver's last known location in a normal relational table, and on a trip request, scan for drivers within a bounding box using a plain WHERE lat BETWEEN... AND lng BETWEEN... query.

V1 — a plain range scan over lat/lng columns. Correct in a small dataset; catastrophic at real scale.

Why this breaks immediately, not eventually: a standard B-tree index on lat and lng independently cannot efficiently answer a 2D "near this point" query — indexing each dimension separately still forces a scan across a huge, non-contiguous set of rows once the table holds millions of drivers (a B-tree's ordering only helps one dimension at a time). This isn't a "gets slow at scale" problem, it's a wrong-tool-for-the-job problem from the very first realistic dataset size — exactly why M's specialized geospatial index isn't an optimization, it's the actual solution to the actual query.

K. Data Model & Store Choice

Live driver location: an in-memory geospatial index (M) — e.g. Redis with its native GEOADD/GEOSEARCH commands (internally a geohash-sorted set), or a custom in-memory quadtree/S2/H3-bucketed structure — chosen for the same reason Rate Limiter chose Redis for counters: the access pattern (extremely frequent overwrite + frequent proximity read) matches an in-memory store's strengths, and losing the very latest location on a restart is harmless (the next ~4-second update replaces it, N).

Trips, trip requests, driver/rider profiles: a standard relational or wide-column durable store — this is the data that must survive restarts and support the request/accept/complete state machine (Q), a fundamentally different durability requirement than the ephemeral location index.

L. End-to-End Flow — Trip Request to Match

M. Deep Dive 1 — The Geospatial Index

Requirement this addresses: directly fixes V1's fatal flaw (J) — efficient "who is near this point" queries are the foundation everything else in this problem is built on.

Why hexagonal cells specifically solve a real problem square grids have: in a square grid, the four diagonal neighbors are ~41% farther away than the four edge-adjacent neighbors, distorting "nearby" queries right at cell boundaries; every one of a hexagon's six neighbors is equidistant, making neighbor expansion (checking one ring further out if too few drivers are found) uniform and predictable — precisely the operation the matching flow (L) performs repeatedly.

Recommendation: H3 as the specific, real-world-grounded answer (it's literally Uber's own open-sourced library for exactly this problem) — geohash is an entirely acceptable, simpler alternative to name if H3's specifics aren't recalled, as long as its boundary-distortion weakness is acknowledged.

N. Deep Dive 2 — High-Frequency Location Ingestion

Requirement this addresses: the ~1.25M updates/sec load from G — by far the largest sustained throughput number in this entire design, dwarfing trip-request volume.

Why "overwrite," not "append," is the correct model: per F's assumption, only the driver's current position matters for matching — there's no requirement to reconstruct a driver's full location history for the matching use case. This means each update is a write to the same key (driver_id's cell/coordinate in the geospatial index, K) rather than an ever-growing log — the exact opposite lifecycle decision from a chat message (Chat System, K) or a post (News Feed, K), both of which must be durably retained forever. Recognizing which category a given piece of data falls into — durable history vs. disposable latest-state — is itself a meaningful piece of design judgment.

Why this still needs careful scaling despite being "just an overwrite": 1.25M overwrites/sec, each also potentially requiring a geospatial index update (moving a driver from one H3 cell to a neighboring one as they drive), must be sharded across many index instances/partitions — the same consistent-hashing-style sharding reasoning from Rate Limiter's scaling deep dive, here partitioned by geographic region/cell rather than by client ID.

A cheap but meaningful optimization: if a driver's reported position hasn't moved out of their current geospatial cell since the last update, the index update itself can be skipped (only the raw lat/lng is refreshed) — cutting a meaningful fraction of the expensive index-restructuring work without affecting matching correctness at all, since matching only cares about which cell a driver is in.

O. Deep Dive 3 — Matching & Ranking Candidates

Requirement this addresses: the <10 second matching-latency NFR (D) — the geospatial search (M) finds candidates; this decides which candidate is actually best.

Why straight-line distance alone is an incomplete ranking signal: the nearest driver by straight-line distance might be on the opposite side of a river, a highway median, or one-way streets that make their actual driving ETA much worse than a driver who's slightly farther in a straight line but has a clear route. A full solution refines the geospatial candidate set (a cheap, coarse first pass) with a call to a routing/ETA engine for the top few candidates only — expensive per-call, so deliberately not run against every driver in the city, only the short list M's index already narrowed things down to.

Why this two-stage funnel (coarse geospatial filter → expensive ETA refinement on a short list), not one or the other alone: pure geospatial ranking is cheap but occasionally wrong in exactly the way described above; pure ETA-engine ranking (calling the routing engine against every driver in a city) is accurate but far too expensive to run at 600+ requests/sec against potentially thousands of drivers each. The funnel gets the accuracy of the expensive computation at a small fraction of its cost by only ever running it against a handful of pre-filtered candidates.

P. Deep Dive 4 — Atomic Driver Assignment

Requirement this addresses: the strong-consistency NFR from D — this is the one place in the entire design where "eventually consistent" is explicitly not good enough, and the single highest-signal deep dive in this problem.

The race, explicitly: two riders' requests can both identify the same driver as their best candidate within the same few-hundred-millisecond window (especially in a sparse area with few available drivers). If both matching attempts read "driver is available" and both then proceed to send an offer, the driver could end up double-booked — the same check-then-act race named explicitly in Rate Limiter's atomicity deep dive (N) and the LLD Parking Lot's last-spot race, here with a human being as the contested resource instead of a counter or a parking spot.

The fix — an atomic compare-and-swap (CAS) on the driver's status, executed as a single atomic operation (e.g. a Redis WATCH/MULTI transaction, an atomic Lua script analogous to Rate Limiter's N, or a conditional update in a store that supports it natively): "set driver's status to pending_offer for request X, only if it is currently available." Whichever matching attempt's CAS lands first wins the driver; the loser's CAS fails cleanly and immediately falls through to the next-best candidate (Q) — no separate locking service required, and no window where both attempts believe they've succeeded.

Why this is the narrow exception to an otherwise eventually-consistent system: location updates (N), ETA ranking (O), and trip tracking (R) all tolerate staleness measured in seconds with no real product harm — but "two riders assigned the same driver" is a directly visible, trust-breaking product failure with no acceptable staleness window at all. Naming this contrast explicitly — this design is eventually consistent everywhere except this one atomic step — is a stronger answer than either "everything is eventually consistent" (misses this) or "everything needs strong consistency" (needlessly slow and complex for location/ETA data that doesn't need it).

Q. Deep Dive 5 — Match Offer Reliability & Retries

Requirement this addresses: the accept/decline/timeout functional requirement (D) — what happens after P's atomic assignment succeeds but the driver doesn't actually confirm.

Why this needs a durable, retry-aware workflow rather than a single synchronous function call: the full request→match→accept sequence can span multiple offer/decline cycles, each with its own timeout, potentially taking several seconds — exactly the kind of long-running, multi-step, failure-prone process that a durable workflow orchestration engine (e.g. Temporal, or an equivalent state-machine-as-infrastructure approach) is built for, rather than a single request handler holding state in memory for the whole sequence. If the matching service instance handling a request crashes mid-retry-loop, a durable workflow resumes exactly where it left off; a plain in-memory retry loop would lose all of that state and leave the rider stuck with no match and no explanation.

R. Deep Dive 6 — Live Trip Tracking

Requirement this addresses: the live-location-sharing functional requirement (D) — a distinct problem from N's ingestion, since this is about broadcasting one driver's position to specifically the matched rider (and vice versa) throughout an active trip.

Why this rhymes with the Chat System's connection/routing problem: once matched, the rider and driver need low-latency, bidirectional updates — the same WebSocket-based push model from Chat System's connection tier (M), with the "who is this update for" question answered trivially here (the trip ID directly identifies the other party), unlike chat's harder cross-server user routing problem. Location pushes during a trip reuse N's already-updated position data — no separate ingestion pipeline is needed, just a subscription from the trip's WebSocket channel to the same location stream.

Why polling is a reasonable, simpler fallback here specifically (unlike Chat System, where it was ruled out entirely): a rider watching a driver's dot move tolerates a few seconds of staleness far more gracefully than a chat message would — so a lower-frequency poll (matching N's own ~4-second update cadence) is a defensible, simpler alternative to a full WebSocket push for this one feature, even though WebSockets remain the better choice if the product wants smoother, more frequent visual updates.

S. Deep Dive 7 — Supply/Demand Imbalance (Surge, Conceptual)

Discussed at the level this interview typically expects — the conceptual shape of the problem and how it plugs into the existing design, not a full pricing-engine derivation.

Why this is a natural extension of the existing geospatial structure, not a new system: the same geospatial cells already used for matching (M) are the natural unit for measuring local supply (available drivers per cell) versus demand (open trip requests per cell) — a simple ratio per cell, recomputed on a short interval, is enough to identify an imbalanced area without building new geospatial machinery. A high demand:supply ratio in a cell is both the trigger for surge pricing (out of scope in detail, per D) and a useful signal to widen the matching search radius for requests originating in that cell (a direct, in-scope tie-back to M's neighbor-expansion behavior).

T. Full Solution at Scale — Final Architecture

Everything above is the composition of M through S — no new component introduced here.

U. Design Evolution

• V1 — plain relational lat/lng range scan (J): the wrong tool for a 2D proximity query from the first realistic dataset size.
• V2 — dedicated geospatial index (H3/geohash): makes "nearby" queries actually efficient (M).
• V3 — sharded, overwrite-based location ingestion: sustains the ~1.25M updates/sec load (N).
• V4 — two-stage geospatial-filter + ETA-engine ranking: fixes straight-line distance's real-world inaccuracy (O).
• V5 — atomic CAS-based assignment: eliminates the double-booking race, the single most important correctness fix in the design (P).
• V6 — durable workflow-based offer/retry loop: survives failures mid-match instead of losing state (Q).
• V7 — WebSocket/poll-based live tracking off the existing location stream: extends the design to in-trip visibility (R).
• V8 — per-cell supply/demand monitoring: plugs surge and search-radius widening into the same geospatial structure (S).

What stays stable throughout: the POST /trip-requests and POST /drivers/location contracts from I — every version underneath changes without either app needing to change.

V. Consistency Model

This is the most consistency-bifurcated design in the whole document: location updates (N), ETA ranking (O), and live tracking (R) are all deliberately eventually consistent — a few seconds of staleness in any of them causes no real harm and buys significant scalability. Driver assignment (P) is the one deliberately strongly-consistent island — a single atomic compare-and-swap that must never allow two riders to win the same driver. This is a sharper, more explicit version of Rate Limiter's "eventual everywhere except one atomic step" model (V in that section) — here the stakes of getting the one strong-consistency step wrong are a visibly broken product experience (a driver arriving for the wrong rider), not just a barely-noticeable over-count.

W. Failure Scenarios

• Two matching attempts race for the same driver: P's atomic CAS ensures exactly one wins; the loser falls through to its next-best candidate with no double-booking window (P, O).
• The matching service crashes mid-offer-retry-loop: the durable workflow (Q) resumes from its last durable checkpoint rather than losing the rider's in-progress match entirely.
• A driver's location update is dropped or delayed: harmless in isolation — the next ~4-second update overwrites stale state (N); a driver silently going stale for too long can be aged out of "available" status defensively.
• The routing/ETA engine is temporarily unavailable: matching degrades to pure geospatial-distance ranking (M) rather than failing entirely — a graceful accuracy degradation, not an outage (O).
• A geospatial shard for one region is overloaded (e.g. a major event causing a local demand spike): the region-sharded design (N) contains the impact to that region's shard rather than degrading the global system, and S's supply/demand signal can trigger widening the search radius as a release valve.

X. Bottlenecks & Scaling Boundary

Y. Design Trade-Offs

Z. Common Bad Designs

• Plain relational range queries on lat/lng with no spatial index. Works on a tiny dataset in a demo; is the wrong data structure for the query pattern from the first realistic dataset size — the most common mistake specifically on this problem.
• Treating driver assignment as eventually consistent "like everything else." Misses the one genuinely load-bearing strong-consistency requirement in the whole design — leads directly to a double-booking bug if two matching attempts race.
• A separate read-then-write for assignment (check availability, then set status in two calls) instead of one atomic CAS — the identical check-then-act race named in Rate Limiter's atomicity deep dive, recurring here with a driver instead of a counter (P).
• Appending every location update to a growing history table when only the latest position is actually needed for matching — unnecessarily inflates storage and write cost for data whose value is disposable after the next update (N).
• Modeling the offer/accept/retry sequence as a single synchronous function call with in-memory state — silently loses the rider's in-progress match if the handling instance crashes mid-sequence (Q).

AA. Interviewer Follow-Ups

AB. Interviewer Evaluation Rubric

• Weak candidate: proposes a plain SQL range query on lat/lng with no awareness that this is the wrong index structure for the query pattern; no mention of the double-booking race at all.
• Mid-level: correctly identifies the need for a geospatial index by name, but doesn't yet flag the assignment race or the durability of the offer/retry loop.
• Senior: proactively names the double-booking race and proposes an atomic CAS-style fix unprompted; distinguishes the strong-consistency requirement for assignment from the eventual-consistency tolerance everywhere else in the system.
• Staff+: reasons about the two-stage geospatial-filter/ETA-refinement funnel as a deliberate cost/accuracy trade-off; discusses durable workflow orchestration for the multi-step match process; connects supply/demand monitoring back to the same geospatial structure rather than treating it as an unrelated new system.

AC. Interview Simulation

AD. Online Solution Comparison

AE. Interview Cheat Sheet