How would you find the nearest available drivers quickly?

Index drivers by map cell (geohash, S2 or H3) in memory. For a rider, gather drivers from their cell and the neighbouring cells (widening if too few), then sort that small set by actual distance and filter to available drivers.

How do you prevent two riders from being matched to the same driver?

Make assignment an atomic compare-and-set: set the driver's current ride only if it's empty (a conditional UPDATE ... WHERE ride_id IS NULL, or a Redis SET NX/Lua script). Exactly one request succeeds; the rest try the next driver.

Design a Ride-Hailing App — System Design Interviews, Step by Step

The question

"Design the core of a ride-hailing app: riders request a ride, nearby drivers get offers, one accepts, and both see each other's location until pickup."

Clarify the requirements

Functional: drivers share location while online; riders see nearby cars; request a ride; match with a nearby available driver; live tracking during the trip; trip history.
Scale: 5 million drivers online at peak worldwide; 20 million rides per day.
Non-functional: a match within seconds; a driver must never be assigned two rides at once; location data a few seconds old is fine; the matching flow must stay up even if analytics is down.
Out of scope: pricing and surge (mention), payments (separate lesson), maps routing.

Estimate the scale

Location updates: 5M drivers every 4 s = 1.25 million writes/s. This is the hot path; it can't go to a normal relational database row by row.
Ride requests: 20M/day ≈ 230/s, peak ~1,000/s. Matching is low volume but must be correct.
A location is small (~50 bytes) and only the latest one matters for matching: keep it in memory, partitioned by city or region; write the trail to cheap storage asynchronously for history.

API and data model

WS   driver -> server   { lat, lng, heading, status: available|busy }   every ~4 s
GET  /drivers/nearby?lat=..&lng=..          -> cars to draw on the rider's map
POST /rides  { pickup, dropoff }            -> { ride_id, status: "matching" }
WS   server -> driver   { offer: ride_id, pickup, expires_in: 15 }
POST /rides/{id}/accept                      (driver)

In memory (per region): cell_id -> set of available driver ids; driver_id -> (lat, lng, status, updated_at)
rides (DB): ride_id | rider_id | driver_id | status | pickup | dropoff | timestamps

High-level design

drivers ══ WS ══► location gateway ─► location service (in-memory geo index, sharded by region)
                                              ▲
riders ─► ride service ─► matching service ───┘   (find nearest available drivers)
              │                 │
              │                 └─► offer to driver (WS) ─► accept ─► atomic assign
              └─► rides DB                         └─► trip tracking: driver location relayed to rider

Deep dives

1. Finding nearby drivers. Divide the map into a grid of cells (geohash, S2 or H3 cells). Each driver is indexed under the cell they're in; when they move to another cell, they're moved in the index. A nearby search looks at the rider's cell and its neighbours, then sorts those few drivers by real distance.

Grid index: search the rider's cell and its neighboursTry it yourself

import math

CELL = 0.01        # degrees, roughly 1 km cells near the equator


def cell_of(lat, lng):
    return (math.floor(lat / CELL), math.floor(lng / CELL))


def km(a, b):      # good enough over a few km
    dlat = (a[0] - b[0]) * 111
    dlng = (a[1] - b[1]) * 111 * math.cos(math.radians(a[0]))
    return math.hypot(dlat, dlng)


index, where = {}, {}


def update(driver, lat, lng):
    old = where.get(driver)
    if old:
        index[cell_of(*old)].discard(driver)       # moved: leave the old cell
    where[driver] = (lat, lng)
    index.setdefault(cell_of(lat, lng), set()).add(driver)


def nearby(lat, lng, k=3):
    cx, cy = cell_of(lat, lng)
    candidates = set()
    for dx in (-1, 0, 1):
        for dy in (-1, 0, 1):
            candidates |= index.get((cx + dx, cy + dy), set())
    ranked = sorted(candidates, key=lambda d: km((lat, lng), where[d]))
    return [(d, round(km((lat, lng), where[d]), 2)) for d in ranked[:k]]


update("d1", 51.5074, -0.1278)     # central London
update("d2", 51.5101, -0.1340)
update("d3", 51.5000, -0.1200)
update("d4", 51.5500, -0.2000)     # far away: not in neighbouring cells
update("d2", 51.5080, -0.1290)     # d2 drives closer

print("drivers near the rider:", nearby(51.5072, -0.1275))
print("cells holding drivers:", len([c for c, s in index.items() if s]))

import math

CELL = 0.01        # degrees, roughly 1 km cells near the equator

def cell_of(lat, lng):
    return (math.floor(lat / CELL), math.floor(lng / CELL))

def km(a, b):      # good enough over a few km
    dlat = (a[0] - b[0]) * 111
    dlng = (a[1] - b[1]) * 111 * math.cos(math.radians(a[0]))
    return math.hypot(dlat, dlng)

index, where = {}, {}

def update(driver, lat, lng):
    old = where.get(driver)
    if old:
        index[cell_of(*old)].discard(driver)       # moved: leave the old cell
    where[driver] = (lat, lng)
    index.setdefault(cell_of(lat, lng), set()).add(driver)

def nearby(lat, lng, k=3):
    cx, cy = cell_of(lat, lng)
    candidates = set()
    for dx in (-1, 0, 1):
        for dy in (-1, 0, 1):
            candidates |= index.get((cx + dx, cy + dy), set())
    ranked = sorted(candidates, key=lambda d: km((lat, lng), where[d]))
    return [(d, round(km((lat, lng), where[d]), 2)) for d in ranked[:k]]

update("d1", 51.5074, -0.1278)     # central London
update("d2", 51.5101, -0.1340)
update("d3", 51.5000, -0.1200)
update("d4", 51.5500, -0.2000)     # far away: not in neighbouring cells
update("d2", 51.5080, -0.1290)     # d2 drives closer

print("drivers near the rider:", nearby(51.5072, -0.1275))
print("cells holding drivers:", len([c for c, s in index.items() if s]))

Output

drivers near the rider: [('d1', 0.03), ('d2', 0.14), ('d3', 0.95)]
cells holding drivers: 3

2. Never double-assigning a driver. Several ride requests may offer the same driver at once. The accept step must be atomic: a conditional update such as UPDATE drivers SET ride_id = ? WHERE driver_id = ? AND ride_id IS NULL, or a compare-and-set in Redis. Only one request wins; the others move on to the next driver.

3. Matching flow. Find the nearest few available drivers, offer the ride to the best one with a 15-second timeout, and move to the next if they decline or time out. Batching requests in a short window (a second or two) and solving them together gives better overall matches in busy areas.

4. Scaling the location firehose. Partition the in-memory index by region (a city rarely needs another city's drivers); each partition is replicated. Drivers write to their region's node; the raw location trail flows to a log for trip history and analytics, off the hot path.

Trade-offs

Cell size: small cells mean fewer candidates per lookup but more cell changes as drivers move; search neighbouring rings when a cell is empty.
In-memory vs database for locations: memory handles a million writes per second; losing a few seconds of locations on a node failure is acceptable because drivers resend them.
Nearest-first vs batched matching: simple and fast vs better global efficiency.
Consistency: location can be eventually consistent; ride assignment must be strongly consistent.

What interviewers look for

Recognising the 1M+/s location write load and keeping it in memory.
A geospatial index (grid, geohash, quadtree) and a neighbour search.
Atomic driver assignment.
Separating the real-time path from history and analytics.

Key points

Latest driver locations live in memory, partitioned by region.
Grid cells (geohash/S2/H3): search the rider's cell and its neighbours, then rank by distance.
Assign drivers with an atomic conditional update.
Offer → timeout → next driver; batch matching in busy areas.