How Uber matches riders to drivers in real time

The Problem Statement

Interviewer: "A rider opens the Uber app and taps 'Request Ride.' Three seconds later, they are matched with a driver. Walk me through what happens in those 3 seconds, from the rider's tap to the driver's phone ringing."

This question tests four things: your understanding of geospatial indexing and how location data is stored and queried at scale, your ability to reason about real-time matching algorithms under latency constraints, your knowledge of supply-demand economics in distributed systems, and whether you can handle the concurrency challenges of matching in a dense urban area where dozens of riders request rides simultaneously.

Most candidates describe a simple "find the nearest driver" approach. That is how Uber worked in 2012. Modern Uber uses a batch matching system that collects multiple ride requests over a short window and solves an optimization problem to match them all simultaneously, minimizing total wait time across the batch rather than greedily assigning each rider to their nearest driver.

I particularly like this question because the "obvious" answer (nearest driver) is wrong in a non-obvious way. The nearest driver to rider A might also be the nearest driver to rider B. Greedy matching gives the first request a great match and the second request a terrible one. Batch matching gives both requests good matches.

Clarifying the Scenario

You: "Before I jump in, let me make sure I understand the scope."

You: "When you say 'matching,' are we talking just about UberX (standard rides) or are we including pool rides, scheduled rides, and premium tiers?"

Interviewer: "Focus on UberX. Single rider, single driver."

You: "OK. Should I assume a dense urban area like Manhattan where there are hundreds of drivers within a few blocks, or a sparse suburban area?"

Interviewer: "Manhattan-level density. Lots of concurrent requests."

You: "Got it. And should I go into the surge pricing / supply-demand scoring, or just the matching mechanics?"

Interviewer: "Include how supply and demand affect matching. That is an important part."

You: "Last question: should I cover how the driver's location is tracked in real time? That is a prerequisite for matching."

Interviewer: "Yes, briefly."

You: "I will structure my answer in four parts: how driver locations are indexed in real time using geospatial data structures, how candidate drivers are selected for a ride request, how the scoring and matching algorithm works across a batch of requests, and how ETA estimation feeds into the scoring."

My Approach

I break this into five parts:

1. Driver location streaming: How GPS updates from drivers are ingested, processed, and indexed every 4 seconds
2. Geospatial indexing with H3: How Uber partitions the earth into hexagonal cells for fast spatial queries
3. Candidate selection: How the system narrows from "every driver in the city" to "10-20 viable candidates" for a given request
4. Batch matching and scoring: How multiple simultaneous requests are matched optimally using the Hungarian algorithm
5. ETA estimation: How the routing engine calculates real-time ETAs that feed into the matching score

The core tension in this system is speed vs optimality. A greedy algorithm (match each request to the nearest driver immediately) is fast but produces globally suboptimal assignments. A global optimization (consider every possible assignment of all riders to all drivers) produces perfect matches but is computationally infeasible at scale. Uber's trick is batching requests over a short window (2-3 seconds) and solving the optimization problem over that small batch, which is a sweet spot between speed and quality.

Here are the key latency budgets I keep in mind when discussing this system:

Every stage has been engineered to fit within its budget. If any single stage exceeds its allocation, the rider feels the delay.

The Architecture

Here is the end-to-end architecture from the rider tapping "Request" to the driver receiving the match notification:

Let me walk through the flow.

When a rider taps "Request," their app sends the pickup location, destination, and ride type to the API gateway. This request is published to Kafka and consumed by the Request Collector, which batches incoming requests over a 2-second window grouped by H3 region.

Meanwhile, every active driver's app sends GPS coordinates every 4 seconds to the Location Service, which maintains an in-memory H3 geospatial index of all available drivers.

For each batch, the Candidate Selector queries the H3 index to find the 10-20 closest available drivers for each request. The Scoring Engine then evaluates each rider-driver pair using ETA estimates and supply-demand ratios. Finally, the Batch Matcher runs the Hungarian algorithm to find the globally optimal assignment across all requests in the batch.

The matched driver receives a push notification and has 15 seconds to accept. If they decline or do not respond, the system re-matches the rider in the next batch cycle.

For your interview: the phrase "batch matching over a 2-second window" is the key insight that separates a strong answer from a naive one. It shows you understand the tension between greedy and optimal matching.

Let me call out the scale numbers here. In Manhattan at peak hours:

• ~10,000 active drivers sending GPS every 4s = 2,500 location updates/second
• ~100 ride requests per second
• Each 2-second batch: ~200 requests
• Each request × 15 candidates = 3,000 rider-driver pairs per batch
• 3,000 ETA queries per batch (must complete in < 200ms)
• One Hungarian algorithm solve per H3 region per batch

This is not a toy problem. The entire pipeline must complete in under 3 seconds, and every millisecond of added latency means a rider is staring at a loading screen.

Geospatial Indexing with H3 Hexagons

The first challenge is: how do you answer the question "which drivers are near this pickup location?" when you have 50,000 active drivers in Manhattan? You cannot iterate through all 50,000 and compute distances. You need a spatial index.

Uber uses H3, a hexagonal hierarchical spatial index developed in-house and open-sourced. The key idea: the entire earth's surface is divided into hexagonal cells at multiple resolutions. Each cell has a unique 64-bit ID. Converting a lat/lng to an H3 cell ID is O(1). Finding neighboring cells is O(1). This turns "find drivers within 2km" into "find drivers in these 7-19 H3 cells."

Why hexagons instead of squares or rectangles? Two reasons.

Uniform distance: The center of a hexagon is equidistant from the centers of all its neighbors. With square grids, diagonal neighbors are ~1.41x farther than cardinal neighbors. This means ring-based expansion gives consistent distance guarantees with hexagons.

No gaps or overlaps: Hexagons tile perfectly. You can expand outward ring by ring without any coverage gaps. This matters when the candidate search says "give me all drivers within 3 rings of the pickup."

The H3 index is stored in memory (Redis or a custom in-memory store) with the cell ID as the key and a list of driver IDs as the value. When a driver moves and their GPS update crosses a cell boundary, the Location Service removes them from the old cell's list and adds them to the new cell's list. This happens roughly every 4 seconds per driver.

The Dispatch Scoring and Matching Pipeline

Once we have 10-20 candidate drivers for each ride request, the system needs to decide which driver gets which ride. This is where the magic happens, and where most candidates give a weak answer.

The naive approach is "assign each rider to their nearest driver." This is a greedy algorithm: process requests in arrival order, and for each request, pick the closest available driver. The problem is that it is globally suboptimal.

Imagine two riders (A and B) and two drivers (D1 and D2). D1 is 2 minutes from A and 5 minutes from B. D2 is 3 minutes from A and 2 minutes from B. Greedy matching processes A first, assigns D1 (2 min), then assigns D2 to B (2 min). Total wait: 4 minutes. But what if we swapped? A→D2 (3 min), B→D1 (5 min) = 8 min total. Here greedy won. But consider a different scenario: D1 is 1 min from A and 10 min from B. D2 is 2 min from both. Greedy: A→D1 (1), B→D2 (2) = 3 total. Optimal: same. These small examples often look fine, but at scale with 50 riders and 50 drivers, greedy consistently produces 10-20% worse total wait time because it locks in early locally-good assignments that block globally-better ones later.

The scoring function combines multiple signals:

ETA (40% weight): How quickly the driver can reach the pickup. This is the most important factor because riders care most about wait time. The ETA is not straight-line distance; it comes from Uber's routing engine, which accounts for real-time traffic, turn restrictions, and road closures.

Supply-demand ratio (30% weight): The ratio of available drivers to active requests in the pickup's H3 region. In a surge zone with few drivers, the system might assign a slightly farther driver to avoid leaving the zone completely empty for the next request. This is where matching and surge pricing interact.

Driver preference (20% weight): Drivers who are heading toward the pickup area (based on heading and recent trajectory) score higher than drivers who would need to make a U-turn. A driver 2km away driving toward you is better than a driver 1km away driving away from you.

Trip value (10% weight): Longer trips generate more revenue. In some versions of the algorithm, the system slightly favors assigning high-rated, experienced drivers to longer trips to ensure a good experience. This is controversial internally but is a real signal.

Real-Time ETA Estimation

ETA estimation is the foundation of the entire matching system. If the ETA is wrong by 3 minutes, the matching algorithm assigns the wrong driver. If the routing engine is slow, the entire dispatch pipeline misses the 3-second latency budget. This is why Uber built their own routing engine instead of using Google Maps.

The ETA challenge has three aspects:

Graph representation: The road network is a directed graph with ~100 million edges (road segments) globally. Each edge has time-variable weights based on traffic conditions. Rush hour in Manhattan means a 200-meter block might take 5 minutes, while the same block at 3 AM takes 20 seconds.

Real-time traffic: Every driver's GPS trace is a traffic probe. When 200 drivers on a road segment go from 30 mph to 5 mph, the system knows there is congestion within 30 seconds. These speed observations update the edge weights in the routing graph continuously.

Batch ETA queries: The scoring engine needs ETAs for 300-500 rider-driver pairs per batch. That is 300-500 routing queries that must complete within 200ms total. Uber uses a pre-computed hierarchy (Contraction Hierarchies or similar) that answers single-pair queries in 1-2ms, making batch queries feasible.

I want to highlight the feedback loop here. Driver GPS traces create traffic data, which updates the routing graph, which improves ETA estimates, which improves matching quality, which reduces driver idle time, which puts more drivers on the road, which generates more GPS probes. This is a virtuous cycle that benefits from scale. More drivers means better traffic data, which means better matching, which means more riders, which means more drivers.

The accuracy requirements are strict. Uber's internal benchmarks target ETAs within 20% of actual travel time for 90% of requests. Missing this target means the matching algorithm makes suboptimal assignments, riders get frustrated by inaccurate wait times, and surge pricing calculations are wrong (because surge is based on the ratio of estimated demand to estimated supply-time-to-pickup).

For roads with no recent driver data (a suburban cul-de-sac at 3 AM, for example), the system falls back through three layers: historical speed for that road at this time-of-day, average speed for that road class (residential, arterial, highway) in the city, and finally a conservative default speed based on the speed limit. This cascading fallback ensures the system always returns an ETA, even if the confidence is lower.

The Tricky Parts

1. Concurrent assignment races. Two batching windows might overlap in a way that both select the same driver as a candidate. If both matchers assign that driver, one of the assignments fails. The system handles this with optimistic locking: the match is only confirmed when the driver's status is atomically changed from "available" to "assigned." If the CAS (compare-and-swap) fails, the request goes back into the next batch cycle.

2. Cold start in new cities. When Uber launches in a new city, there are very few drivers and no historical traffic data. The H3 index is sparse (big cells have zero drivers), the ETA engine has no real-time data, and the matching algorithm degenerates to greedy because batches contain only 1-2 requests. Uber bootstraps by using map provider data for initial ETAs and running promotions to build driver supply before advertising to riders.

3. The airport queue problem. Airports have a fixed queue of drivers waiting in a staging lot. The matching system must balance between the queue (FIFO fairness for waiting drivers) and nearby street drivers who might be closer to the terminal. Most airports have regulatory requirements that airport rides must go to queued drivers, which overrides the optimization algorithm entirely.

4. Driver location staleness. GPS updates arrive every 4 seconds. A driver moving at 30 mph travels about 55 meters between updates. In dense areas, 55 meters can mean the driver is on a completely different street. The system interpolates between GPS points using the road graph (map-matched trajectory), but there is inherent uncertainty in the driver's exact position.

5. Surge pricing interaction. High surge zones attract drivers from neighboring areas, which drains supply from those areas, potentially creating secondary surge zones. The matching system must account for this cascade effect. If you aggressively match all drivers into a surge zone, you create a supply desert in the surrounding areas that triggers new surges.

6. Driver-side accept rate. Not every matched driver accepts the ride. Some drivers decline low-value short trips, some are about to go offline, and some are in areas with poor network connectivity and miss the notification. Uber tracks per-driver accept rates and factors them into the matching score. A driver with a 95% accept rate is more valuable as a match than one with a 60% accept rate, because the latter is likely to decline and force a re-match cycle.

What Most People Get Wrong

How I Would Communicate This in an Interview

Here is how I would actually say this:

"When a rider requests a ride, the system does not just find the nearest driver. It uses a three-stage pipeline that completes in under 3 seconds.

First, candidate selection. Uber uses an H3 hexagonal grid to index driver locations. Every active driver is mapped to an H3 cell, and the system expands outward ring by ring from the pickup location until it has 15-20 candidate drivers. This ring expansion on hexagons is O(1) per cell and avoids the edge effects of rectangular grids.

Second, scoring. For each rider-driver pair, the system scores based on four signals: ETA from a routing engine with real-time traffic (40% weight), supply-demand ratio in the area (30%), driver heading relative to the pickup (20%), and estimated trip value (10%). The ETA comes from Uber's own routing engine, which uses driver GPS traces as traffic probes to update road segment speeds every 30 seconds.

Third, batch matching. Instead of matching each request greedily, the system batches all requests in a 2-second window and solves the assignment problem using the Hungarian algorithm. This finds the globally optimal assignment that minimizes total wait time across the batch. For 30 requests, the Hungarian algorithm takes about 2ms.

The key insight is that greedy nearest-driver matching is locally optimal but globally suboptimal. Batch matching trades a tiny amount of latency (2s batching window) for significantly better outcomes across all riders. Uber reports that batch matching reduces average wait times by 10-20% compared to greedy matching."

I would then pause and ask: "Would you like me to go deeper on the geospatial indexing, the Hungarian algorithm, or the ETA estimation?" This lets the interviewer guide the conversation to whatever aspect they care about most.

Notice I did not mention Kafka, Redis, or any specific infrastructure in the overview. Infrastructure details are important but secondary. Lead with the algorithm and architecture, not the tech stack. If the interviewer asks "how do you actually implement this," then you bring in H3, Redis, Kafka, and Contraction Hierarchies.

Interview Cheat Sheet

• Trigger: "How does Uber find nearby drivers?" Say: "H3 hexagonal geospatial index. Ring expansion from the pickup cell. O(1) per cell lookup, resolution 9 gives ~175m edges."
• Trigger: "Why hexagons?" Say: "Uniform neighbor distance (equidistant centers), no edge effects, clean ring expansion. Better than squares or geohashes for distance-based queries."
• Trigger: "Why not just find the nearest driver?" Say: "Greedy matching is globally suboptimal. The nearest driver to rider A might also be nearest to rider B. Batch matching solves the assignment problem optimally."
• Trigger: "What algorithm for matching?" Say: "Hungarian algorithm (Kuhn-Munkres). O(n³) on the batch size, typically 30-50 requests. Takes 2-5ms. For larger batches, use approximation algorithms."
• Trigger: "How does ETA work?" Say: "Contraction Hierarchies on the road graph, with edge weights updated every 30 seconds using real-time speed data from driver GPS traces."
• Trigger: "How often do drivers send location?" Say: "GPS update every 4 seconds. Location Service updates the H3 index atomically. Map-matching interpolates between updates."
• Trigger: "How does surge affect matching?" Say: "Supply-demand ratio is 30% of the matching score. High surge attracts drivers from neighboring cells, so matching accounts for not draining adjacent supply."
• Trigger: "What about concurrency?" Say: "Batching eliminates most contention. Residual races are handled by optimistic locking on driver status. Failed CAS means the request goes into the next batch."
• Trigger: "How fast is the whole pipeline?" Say: "2s batching window + 200ms candidate selection + 200ms ETA queries + 5ms Hungarian solve = under 3 seconds end to end."
• Trigger: "Scale numbers?" Say: "500K+ active drivers sending GPS every 4s = 125K location updates/sec. 100+ ride requests/sec in a single city. ~10M ETA queries/minute globally."

Test Your Understanding

---

---

---

---

---

---

---

Quick Recap

1. Uber indexes driver locations using H3 hexagonal cells for O(1) spatial lookups with uniform neighbor distances.
2. The candidate selector expands H3 rings outward from the pickup location to find 10-20 nearby available drivers.
3. Each rider-driver pair is scored on ETA (40%), supply-demand ratio (30%), driver heading (20%), and trip value (10%).
4. Requests are batched over a 2-second window, and the Hungarian algorithm finds the globally optimal assignment across the batch.
5. ETA estimation uses Contraction Hierarchies on the road graph with edge weights updated every 30 seconds from driver GPS traces.
6. Driver GPS updates arrive every 4 seconds, and map-matching infers the trajectory between updates.
7. Concurrent assignment races are resolved with optimistic locking on driver status (CAS on available to assigned).
8. Batch matching reduces average wait times by 10-20% compared to greedy nearest-driver assignment.
9. Surge pricing interacts with matching by shifting driver supply toward high-demand areas, changing the candidate pool before matching even begins.
10. Chained dispatching includes drivers who are about to finish their current trip, scoring them by current-trip ETA plus pickup ETA.

Related Concepts

• How geospatial indexing works: H3 is one approach to spatial indexing. Others include R-trees, quadtrees, and S2 cells (used by Google). Understanding the tradeoffs between these structures helps you reason about when each is appropriate.
• How real-time event streaming works: The driver location pipeline is a classic streaming architecture: high-volume GPS events ingested via Kafka, processed in real time, and materialized into an in-memory index.
• How CDN cache invalidation works: The H3 index is conceptually similar to a distributed cache that must be kept consistent as driver locations change. The "invalidation" is the cell-boundary crossing that moves a driver from one cell to another.
• How push notifications work: The driver match notification is a time-critical push message. If the notification is delayed by even 5 seconds, the driver might have moved, changing the ETA and potentially invalidating the match.
• How rate limiting works: The batching window in the dispatch pipeline is conceptually similar to a sliding window: requests accumulate over a fixed interval before being processed as a group.