Skip to content

Design Uber (LLD) with driver matching

TL;DR

  • You build the dispatch core: drivers stream positions into a grid index, a rider requests a ride, the best candidates are ranked, and one of them is leased an offer that expires.
  • Three decisions carry the interview: the index uses striped locks (per cell and per driver) instead of one global mutex, matching is an optimistic hint re-validated under the dispatch lock, and an assignment is a lease with a timeout that cascades down a shortlist.
  • Patterns that earn their place: Mediator (MatchingService), State (the trip transition table), Strategy (matching and surge), Observer (trip feed, earnings), Factory (ride types), Facade (RideHailingService).

Problem statement

"Design the core of a ride-hailing service. Drivers go online and report their position continuously. A rider asks for a ride of a given class between two points, and the system finds a nearby driver, offers them the trip, and waits for an answer. The trip then runs through arrival, start and end, and a fare is charged from base, distance, time and surge. Focus on how you find drivers quickly, how you make sure one driver is never given two trips, and what happens when a driver ignores the offer or a rider cancels mid-flight."

Requirements

Functional

  • Drivers go online, stream position updates, and go offline.
  • A rider requests a ride with a pickup, a drop-off and a ride class; a fare estimate is available before confirming.
  • Matching finds nearby eligible drivers, ranks them, and offers the trip to the best one with a deadline.
  • An offer may be accepted, declined or left to expire; declines and expiries cascade to the next candidate.
  • The trip walks a state machine through matched, arrived, in progress and completed, with cancellation branches.
  • The final fare is base plus distance plus time, multiplied by a surge factor read from the pickup's grid cell, floored at a class minimum.
  • Cancellation is free before a driver commits and inside a short grace window afterwards; then it costs a fee.
  • Ratings after completion; trip history per rider.

Non-functional and constraints

  • Position updates are the hot path and must not serialise behind dispatch.
  • One driver is never offered or assigned two trips, no matter how many riders request simultaneously.
  • A driver who stops responding must not pin a rider's request indefinitely.
  • In-memory and single-process; the clock and ID generators are injected, so every test is deterministic.

Out of scope: routing and real road distance, pooling, scheduled rides, driver onboarding, and the payment gateway beyond a captured amount.

Clarifying questions and assumptions

Question to ask Assumption taken here
How often do drivers report position, and how many are online? Every few seconds, tens of thousands per city. That is what forces a striped index rather than a lock around a dict.
Is distance road distance or straight line? Straight line, computed with an equirectangular approximation. Real routing is a service call behind the same MatchingStrategy interface.
Do we offer to one driver or broadcast to several? One at a time, with a 15-second lease. Broadcast-and-first-wins is the alternative, and the trade — faster match, more declines, unfair to slow phones — is worth saying out loud.
What if nobody accepts? The shortlist is walked once and then the trip ends in NO_DRIVER. A retry is a product decision, not a correctness one.
Is surge per city or per area? Per grid cell, using the same geometry as the index, so pricing and dispatch argue about the same coordinates.
Can the rider cancel after matching? Yes. Free for 120 seconds, then a flat fee — and the driver is always released.
Where does the fare come from? Class specs in a factory registry, so adding a new class is one dict entry, not an if in the calculator.

Core entities and relationships

  • Location — a frozen lat/lon pair that knows how to measure distance. Everything spatial goes through it.
  • DriverLocationIndex — a uniform grid over the city. It owns both striped lock arrays and is the only authority on where a driver is.
  • Driver — id, vehicle, rating, DriverStatus, and the trip they currently hold. DriverSnapshot is the immutable read of one driver that ranking sees.
  • Vehicle and RideTypeSpec — which classes a car may serve, and what each class costs. RideTypeFactory is the registry.
  • RideRequest (frozen) and Trip — the ask and the thing that happens. One trip, one request, at most one driver.
  • DriverOffer — the lease: trip, driver, expires_at, OfferStatus. At most one live offer names a given driver.
  • TripService owns trips and every transition; MatchingService is the mediator that owns drivers, the index and offers; RideHailingService is the facade.
  • MatchingStrategy (NearestDriver, FastestEta, HighestRatedNearby, FairRotation) and SurgeProvider (NoSurge, FlatSurge, ZoneSurge) are the policies; FareCalculator combines a spec and a surge into a Fare.

Multiplicities: index 1 → * cells, cell 1 → * drivers, driver 1 → 0..1 live offer, trip 1 → * offers over its life, trip 0..1 → 1 driver, trip 1 → 0..1 fare.

Class diagram

Domain: where drivers are, what a trip is, and what it costs.

classDiagram
    class Location {
        +lat: float
        +lon: float
        +distance_km(other) float
    }
    class DriverLocationIndex {
        +cell_size_km: float
        +cell_of(location) tuple
        +update(driver_id, location) tuple
        +position(driver_id) Location
        +nearby(centre, radius_km) List~str~
        +remove(driver_id)
    }
    class Vehicle {
        +plate: str
        +seats: int
        +serves(ride_type) bool
    }
    class RideTypeSpec {
        +base: Money
        +per_km: Money
        +per_minute: Money
        +minimum: Money
    }
    class RideTypeFactory {
        +spec(ride_type) RideTypeSpec
    }
    class Rider {
        +id: str
        +rating: float
    }
    class Driver {
        +id: str
        +status: DriverStatus
        +rating: float
        +trips_today: int
        +is_available() bool
    }
    class DriverSnapshot {
        +driver_id: str
        +location: Location
        +pickup_km(pickup) float
    }
    class RideRequest {
        +id: str
        +ride_type: RideType
        +straight_line_km float
    }
    class Trip {
        +id: str
        +status: TripStatus
        +driver_id: str
        +distance_km: float
        +can_move_to(target) bool
        +minutes() float
    }
    class DriverOffer {
        +id: str
        +expires_at: float
        +status: OfferStatus
        +is_live(now) bool
    }
    class Fare {
        +base: Money
        +surge_multiplier: float
        +total: Money
    }
    class Payment {
        +amount: Money
        +captured: bool
    }
    class Rating {
        +stars: int
    }
    Driver "1" *-- "1" Vehicle
    Driver --> Location
    DriverLocationIndex o-- "many" Driver : by id
    DriverSnapshot ..> Driver : frozen read of
    RideRequest --> Location
    Trip "1" *-- "1" RideRequest
    Trip --> "0..1" Driver
    Trip --> "0..1" Fare
    DriverOffer --> Trip
    DriverOffer --> Driver : leases
    RideTypeFactory ..> RideTypeSpec : creates
    Trip ..> Payment
    Trip ..> Rating
    Rider ..> RideRequest : makes

Services and policies: one mediator, one facade, two swappable rules.

classDiagram
    class RideHailingService {
        +estimate(pickup, dropoff, ride_type) Fare
        +request_ride(rider_id, pickup, dropoff, ride_type) Trip
        +driver_accepts(offer_id, driver_id) Trip
        +driver_declines(offer_id, driver_id) DriverOffer
        +sweep_offers() List~DriverOffer~
        +cancel_ride(trip_id) Trip
        +end_trip(trip_id, distance_km) Trip
    }
    class TripService {
        +open(request) Trip
        +transition(trip_id, target, event) Trip
        +assign_driver(trip_id, driver_id) Trip
        +finish_metering(trip_id, distance_km) Trip
        +complete(trip_id, fare) Trip
    }
    class MatchingService {
        +ping(driver_id, location)
        +shortlist(request) List~str~
        +offer_next(trip_id, request) DriverOffer
        +accept(offer_id, driver_id) DriverOffer
        +sweep() List~DriverOffer~
        +release(offer)
        +void_trip(trip_id)
    }
    class DriverLocationIndex
    class TripListener {
        <<interface>>
        +on_trip_event(trip, event)
    }
    class TripFeed {
        +timeline(trip_id) List~str~
    }
    class EarningsBoard {
        +earnings(driver_id) Money
    }
    class MatchingStrategy {
        <<interface>>
        +rank(request, candidates) List~DriverSnapshot~
    }
    class NearestDriver
    class FastestEta
    class HighestRatedNearby
    class FairRotation
    class SurgeProvider {
        <<interface>>
        +multiplier(pickup) float
    }
    class NoSurge
    class FlatSurge
    class ZoneSurge
    class FareCalculator {
        +quote(ride_type, distance_km, minutes, pickup) Fare
        +estimate(request) Fare
    }
    class CancellationPolicy {
        +fee(trip, now) Money
    }
    RideHailingService --> TripService
    RideHailingService --> MatchingService
    RideHailingService --> FareCalculator
    RideHailingService --> CancellationPolicy
    MatchingService "1" *-- "1" DriverLocationIndex
    MatchingService --> MatchingStrategy
    TripService --> "many" TripListener : notifies
    TripListener <|.. TripFeed
    TripListener <|.. EarningsBoard
    MatchingStrategy <|.. NearestDriver
    MatchingStrategy <|.. FastestEta
    MatchingStrategy <|.. HighestRatedNearby
    MatchingStrategy <|.. FairRotation
    FareCalculator --> SurgeProvider
    SurgeProvider <|.. NoSurge
    SurgeProvider <|.. FlatSurge
    SurgeProvider <|.. ZoneSurge
    ZoneSurge --> DriverLocationIndex : same cells

Design patterns applied

Pattern Where Why it earns its place
Mediator MatchingService Nothing else in the system holds both a Driver and a Trip. Riders ask it for a driver, drivers report position and answer offers to it, and it alone decides who hears about whom. Without it, Trip reaches into the driver registry and Driver reaches into trips, and you have a two-way dependency you cannot test.
State (as a table) TRIP_TRANSITIONS plus TripService.transition Seven statuses and three actors that can act at once. One dict is the machine, one method is the gate, and the state diagram below is a drawing of that dict.
Strategy MatchingStrategy, SurgeProvider The two rules that change every interview. Strategies receive frozen DriverSnapshot values, so they cannot mutate dispatch state or take a lock — swapping the ranking rule cannot introduce a race, and that is a design property, not a convention.
Observer TripListener with TripFeed and EarningsBoard TripService publishes moves and knows nothing about who listens. Listeners are notified outside the trip lock, so a slow feed cannot stall dispatch.
Factory Method RideTypeFactory.spec A request carries "xl". A registry maps it to base, per-km, per-minute and minimum. A new class is one dict entry; FareCalculator never changes.
Facade RideHailingService Nine verbs for the API layer, and the only place that knows in what order the two services must be called.
Null Object NoSurge FareCalculator never writes if surge is None. The default is an object that returns 1.0.

What was deliberately not used: a Repository per entity, and a full State class hierarchy. Repositories are the persistence seam — say "each service holds a dict today and would hold a repository protocol instead, with the trip table as the transaction boundary" and move on. State classes would be seven files whose only content is a list of successors, which the table already holds in nine lines.

Key flows

Request to fare: the index is read without the dispatch lock, and the lease is taken with it.

sequenceDiagram
    autonumber
    actor R as Rider
    participant F as RideHailingService
    participant T as TripService
    participant M as MatchingService
    participant I as DriverLocationIndex
    participant S as MatchingStrategy
    actor D as Driver
    R->>F: request_ride(pickup, dropoff, economy)
    F->>T: open(request)
    T-->>F: Trip(REQUESTED)
    F->>M: offer_next(trip_id, request)
    M->>I: nearby(pickup, 1.5 km) then 3 km then 5 km
    I-->>M: driver ids inside the radius
    M->>S: rank(request, frozen snapshots)
    S-->>M: shortlist, best first
    M->>M: under the lock, lease the first still-available driver
    M-->>D: DriverOffer valid for 15 s
    D->>F: driver_accepts(offer_id)
    F->>M: accept claims the lease
    F->>T: assign_driver, REQUESTED to MATCHED
    D->>F: arrived, start_trip, end_trip(distance)
    F->>T: finish_metering stops the meter
    F->>F: FareCalculator.quote with the pickup cell surge
    F->>T: complete(trip, fare)
    T-)R: trip completed, fare shown

The hot path and the cascade: pings never wait for dispatch, and dispatch never trusts a stale read.

sequenceDiagram
    autonumber
    actor D1 as Driver one
    actor D2 as Driver two
    participant I as DriverLocationIndex
    participant M as MatchingService
    par position stream
        D1->>I: update(d1, location) on its driver stripe
        D2->>I: update(d2, location) on a different stripe
    and dispatch
        M->>I: nearby(pickup, radius) taking cell stripes one at a time
        I-->>M: candidate ids, a hint that may already be stale
    end
    M->>M: lock, pop the next candidate, re-check availability
    alt still available
        M->>M: status AVAILABLE to OFFERED, offer created
    else leased by another request in the meantime
        M->>M: skip and try the next candidate
    end
    Note over M: 15 s later, nobody answered
    M->>M: sweep expires the offer and frees the driver
    M->>M: offer_next pops the next entry of the same shortlist
    alt shortlist exhausted
        M-->>M: None, trip ends in NO_DRIVER
    end

Trip lifecycle. This is TRIP_TRANSITIONS drawn out; nothing else enforces it.

stateDiagram-v2
    [*] --> REQUESTED : rider confirms
    REQUESTED --> MATCHED : a driver accepts the lease
    REQUESTED --> NO_DRIVER : shortlist exhausted
    REQUESTED --> CANCELLED : rider cancels, free
    MATCHED --> ARRIVED : driver reaches the pickup
    MATCHED --> CANCELLED : rider cancels, fee after the grace window
    ARRIVED --> IN_PROGRESS : rider is in the car
    ARRIVED --> CANCELLED : rider never shows
    IN_PROGRESS --> COMPLETED : meter stops, fare priced
    COMPLETED --> [*]
    CANCELLED --> [*]
    NO_DRIVER --> [*]

Driver lifecycle. OFFERED is the lease. It exists so that "is this driver free?" has one answer, held under one lock.

stateDiagram-v2
    [*] --> OFFLINE
    OFFLINE --> AVAILABLE : go_online, indexed
    AVAILABLE --> OFFERED : leased by offer_next
    OFFERED --> AVAILABLE : declined, expired, or trip voided
    OFFERED --> ON_TRIP : accept claims the lease
    ON_TRIP --> AVAILABLE : trip completed or cancelled
    AVAILABLE --> OFFLINE : go_offline, removed from the index

Implementation

Write it in the order the interviewer wants: vocabulary and the transition table, then the index (which is the part they are actually testing), then the policies, then the two services and the facade.

The enums and TRIP_TRANSITIONS are the contract every service reads. CHARGEABLE_CANCEL_FROM sits next to them because "when does cancelling cost money" is a business rule, not a service detail:

code/lld/ride_sharing/models.py — statuses and the transition table
class RideType(StrEnum):
    ECONOMY = "economy"
    COMFORT = "comfort"
    XL = "xl"
    BLACK = "black"


class DriverStatus(StrEnum):
    OFFLINE = "offline"
    AVAILABLE = "available"  # in the index, can be offered a trip
    OFFERED = "offered"  # holds one live lease
    ON_TRIP = "on_trip"


class TripStatus(StrEnum):
    REQUESTED = "requested"  # matching in progress
    MATCHED = "matched"  # a driver accepted and is on the way
    ARRIVED = "arrived"  # driver is at the pickup point
    IN_PROGRESS = "in_progress"
    COMPLETED = "completed"
    CANCELLED = "cancelled"
    NO_DRIVER = "no_driver"  # the offer cascade ran out of candidates


class OfferStatus(StrEnum):
    PENDING = "pending"
    ACCEPTED = "accepted"
    DECLINED = "declined"
    EXPIRED = "expired"
    VOIDED = "voided"  # the rider cancelled underneath the offer


#: The whole trip lifecycle in one dict. ``TripService.transition`` is the only
#: caller, and the state diagram on the page is a drawing of exactly this table.
TRIP_TRANSITIONS: dict[TripStatus, frozenset[TripStatus]] = {
    TripStatus.REQUESTED: frozenset({TripStatus.MATCHED, TripStatus.CANCELLED, TripStatus.NO_DRIVER}),
    TripStatus.MATCHED: frozenset({TripStatus.ARRIVED, TripStatus.CANCELLED}),
    TripStatus.ARRIVED: frozenset({TripStatus.IN_PROGRESS, TripStatus.CANCELLED}),
    TripStatus.IN_PROGRESS: frozenset({TripStatus.COMPLETED}),
    TripStatus.COMPLETED: frozenset(),
    TripStatus.CANCELLED: frozenset(),
    TripStatus.NO_DRIVER: frozenset(),
}

#: After this point a driver has already burned fuel getting to the rider.
CHARGEABLE_CANCEL_FROM = frozenset({TripStatus.MATCHED, TripStatus.ARRIVED})

DriverSnapshot is the small idea with the biggest payoff: matching strategies receive frozen values, never live drivers.

code/lld/ride_sharing/models.py — value objects and the ride-type registry
@dataclass(frozen=True, slots=True)
class Location:
    lat: float
    lon: float

    def distance_km(self, other: Location) -> float:
        """Equirectangular approximation: accurate enough inside one city, and cheap."""
        mean_lat = radians((self.lat + other.lat) / 2)
        dx = (other.lon - self.lon) * cos(mean_lat) * KM_PER_DEGREE
        dy = (other.lat - self.lat) * KM_PER_DEGREE
        return hypot(dx, dy)


@dataclass(frozen=True, slots=True)
class RideTypeSpec:
    """The commercial rules of one ride class: what it costs and what it needs."""

    ride_type: RideType
    base: Money
    per_km: Money
    per_minute: Money
    minimum: Money
    seats: int


class RideTypeFactory:
    """Factory: a request carries the string ``"xl"``, not a pricing table."""

    _registry: dict[RideType, RideTypeSpec] = {
        RideType.ECONOMY: RideTypeSpec(
            RideType.ECONOMY, Money.of("2.00"), Money.of("0.90"), Money.of("0.20"), Money.of("4.00"), 4
        ),
        RideType.COMFORT: RideTypeSpec(
            RideType.COMFORT, Money.of("3.00"), Money.of("1.20"), Money.of("0.25"), Money.of("6.00"), 4
        ),
        RideType.XL: RideTypeSpec(
            RideType.XL, Money.of("4.00"), Money.of("1.60"), Money.of("0.30"), Money.of("8.00"), 6
        ),
        RideType.BLACK: RideTypeSpec(
            RideType.BLACK, Money.of("6.00"), Money.of("2.40"), Money.of("0.45"), Money.of("12.00"), 4
        ),
    }

    @classmethod
    def spec(cls, ride_type: RideType | str) -> RideTypeSpec:
        try:
            return cls._registry[RideType(ride_type)]
        except ValueError as exc:
            raise ValidationError(f"unknown ride type: {ride_type!r}") from exc

    @classmethod
    def all_types(cls) -> tuple[RideType, ...]:
        return tuple(cls._registry)


@dataclass(frozen=True, slots=True)
class Vehicle:
    plate: str
    model: str
    seats: int
    ride_types: frozenset[RideType]

    def serves(self, ride_type: RideType) -> bool:
        return ride_type in self.ride_types


@dataclass(frozen=True, slots=True)
class DriverSnapshot:
    """An immutable read of one driver at ranking time.

    Matching strategies see only this, never a live ``Driver``, so a strategy
    physically cannot mutate dispatch state or observe a half-written field.
    """

    driver_id: str
    location: Location
    rating: float
    trips_today: int

    def pickup_km(self, pickup: Location) -> float:
        return self.location.distance_km(pickup)


@dataclass(frozen=True, slots=True)
class Fare:
    """An itemised fare. The rider sees why the number is the number."""

    base: Money
    distance: Money
    time: Money
    surge_multiplier: float
    total: Money

    def __str__(self) -> str:
        return (
            f"{self.total} = ({self.base} base + {self.distance} distance + {self.time} time)"
            f" x {self.surge_multiplier:.2f} surge"
        )

The index is the centrepiece. Two arrays of locks, a fixed one-way order between them, and a read path that holds nothing while it computes distances:

code/lld/ride_sharing/index.py — the striped grid
class DriverLocationIndex:
    """Which drivers are near a point, kept correct under a storm of GPS pings.

    Two *striped* lock arrays, never a single global lock:

    * ``_cell_locks[i]`` guards ``_cell_members[i]``, the cell to driver-id sets
      whose cells hash to stripe ``i``. Two drivers moving in different parts of
      the city touch different stripes and never wait for each other.
    * ``_driver_locks[j]`` guards ``_driver_cells[j]`` and ``_driver_positions[j]``,
      which remember where a driver is. A driver's entry lives in exactly one of
      these dicts, so per-driver updates serialise without a global map.

    Lock order is fixed and one-way: driver stripe first, then cell stripes in
    ascending index order. Nothing ever takes them the other way round, so the
    index cannot deadlock. ``nearby`` takes only cell stripes, one at a time, and
    holds none of them while it computes distances.
    """

    def __init__(self, cell_size_km: float = 1.0, reference_lat: float = 0.0, stripes: int = 16) -> None:
        if cell_size_km <= 0 or stripes <= 0:
            raise ValueError("cell size and stripe count must be positive")
        self.cell_size_km = cell_size_km
        self._stripes = stripes
        self._lat_step = cell_size_km / KM_PER_DEGREE
        self._lon_step = cell_size_km / (KM_PER_DEGREE * max(cos(radians(reference_lat)), 0.01))
        self._cell_locks = [threading.Lock() for _ in range(stripes)]
        self._cell_members: list[dict[Cell, set[str]]] = [{} for _ in range(stripes)]
        self._driver_locks = [threading.Lock() for _ in range(stripes)]
        self._driver_cells: list[dict[str, Cell]] = [{} for _ in range(stripes)]
        self._driver_positions: list[dict[str, Location]] = [{} for _ in range(stripes)]

    def cell_of(self, location: Location) -> Cell:
        return (floor(location.lon / self._lon_step), floor(location.lat / self._lat_step))

    def update(self, driver_id: str, location: Location) -> Cell:
        """Record a GPS ping. A ping inside the current cell costs one lock and no writes."""
        new_cell = self.cell_of(location)
        stripe = self._driver_stripe(driver_id)
        with self._driver_locks[stripe]:
            self._driver_positions[stripe][driver_id] = location
            cells = self._driver_cells[stripe]
            old_cell = cells.get(driver_id)
            if old_cell == new_cell:
                return new_cell  # the common case: still in the same square, no set edits
            cells[driver_id] = new_cell
            self._move(driver_id, old_cell, new_cell)
        return new_cell

    def position(self, driver_id: str) -> Location | None:
        """The authoritative last-known position. Matching reads it, nobody else writes it."""
        stripe = self._driver_stripe(driver_id)
        with self._driver_locks[stripe]:
            return self._driver_positions[stripe].get(driver_id)

    def remove(self, driver_id: str) -> None:
        """Driver went offline. Their id must not surface in any later search."""
        stripe = self._driver_stripe(driver_id)
        with self._driver_locks[stripe]:
            self._driver_positions[stripe].pop(driver_id, None)
            old_cell = self._driver_cells[stripe].pop(driver_id, None)
            if old_cell is not None:
                self._move(driver_id, old_cell, None)

    def nearby(self, centre: Location, radius_km: float) -> list[str]:
        """Cell ring covering the radius, then an exact distance filter.

        The ring is a superset: a 1 km grid searched at 1.5 km reads a 5x5 block
        of 25 cells and throws away the corners. That is the standard trade -- a
        cheap over-read followed by exact maths, rather than an exact index.
        """
        centre_cell = self.cell_of(centre)
        rings = ceil(radius_km / self.cell_size_km)
        found: list[str] = []
        for dx in range(-rings, rings + 1):
            for dy in range(-rings, rings + 1):
                found.extend(self._members((centre_cell[0] + dx, centre_cell[1] + dy)))
        inside = []
        for driver_id in found:
            position = self.position(driver_id)
            if position is not None and position.distance_km(centre) <= radius_km:
                inside.append(driver_id)
        return inside

    def cell_population(self, cell: Cell) -> int:
        return len(self._members(cell))

    def size(self) -> int:
        return sum(len(cells) for cells in self._driver_cells)

    # -- internals ---------------------------------------------------------------
    def _driver_stripe(self, driver_id: str) -> int:
        return zlib.crc32(driver_id.encode()) % self._stripes  # stable across processes

    def _cell_stripe(self, cell: Cell) -> int:
        return hash(cell) % self._stripes

    def _members(self, cell: Cell) -> list[str]:
        with self._cell_locks[self._cell_stripe(cell)]:
            return list(self._cell_members[self._cell_stripe(cell)].get(cell, ()))

    def _move(self, driver_id: str, old_cell: Cell | None, new_cell: Cell | None) -> None:
        """Caller holds the driver stripe. Cell stripes are taken in ascending order."""
        touched = {self._cell_stripe(c) for c in (old_cell, new_cell) if c is not None}
        acquired = [self._cell_locks[i] for i in sorted(touched)]
        for lock in acquired:
            lock.acquire()
        try:
            if old_cell is not None:
                members = self._cell_members[self._cell_stripe(old_cell)]
                bucket = members.get(old_cell)
                if bucket is not None:
                    bucket.discard(driver_id)
                    if not bucket:
                        del members[old_cell]
            if new_cell is not None:
                members = self._cell_members[self._cell_stripe(new_cell)]
                members.setdefault(new_cell, set()).add(driver_id)
        finally:
            for lock in reversed(acquired):
                lock.release()

Ranking is pure. Note the rounding in FastestEta: without it, two drivers forty metres apart order by floating-point noise and the same request matches differently on every run.

code/lld/ride_sharing/strategies.py — matching
class MatchingStrategy(Protocol):
    """Ranks an already-filtered shortlist of drivers, best first.

    It receives immutable ``DriverSnapshot`` values, so a strategy cannot mutate
    dispatch state or take a lock. Swapping the ranking rule therefore cannot
    introduce a race -- that is the whole reason the snapshot type exists.
    """

    def rank(self, request: RideRequest, candidates: Sequence[DriverSnapshot]) -> list[DriverSnapshot]: ...


class NearestDriver:
    """Straight-line distance to the pickup. The answer everyone gives first."""

    def rank(self, request: RideRequest, candidates: Sequence[DriverSnapshot]) -> list[DriverSnapshot]:
        return sorted(candidates, key=lambda d: (d.pickup_km(request.pickup), d.driver_id))


class FastestEta:
    """Distance turned into minutes at an assumed city speed, rounded to 0.1 min.

    Rounding matters: without it, two drivers 40 metres apart are ordered by
    floating-point noise, and the same request ranks differently on every run.
    """

    def __init__(self, speed_kmh: float = AVERAGE_CITY_SPEED_KMH) -> None:
        self._speed = speed_kmh

    def eta_minutes(self, snapshot: DriverSnapshot, pickup: Location) -> float:
        return round(snapshot.pickup_km(pickup) / self._speed * 60.0, 1)

    def rank(self, request: RideRequest, candidates: Sequence[DriverSnapshot]) -> list[DriverSnapshot]:
        return sorted(
            candidates,
            key=lambda d: (self.eta_minutes(d, request.pickup), -d.rating, d.driver_id),
        )


class HighestRatedNearby:
    """Best rated first, distance only as a tie-break. Used for premium classes."""

    def rank(self, request: RideRequest, candidates: Sequence[DriverSnapshot]) -> list[DriverSnapshot]:
        return sorted(candidates, key=lambda d: (-d.rating, d.pickup_km(request.pickup), d.driver_id))


class FairRotation:
    """Fewest trips today first. Keeps a shift's earnings even across drivers."""

    def rank(self, request: RideRequest, candidates: Sequence[DriverSnapshot]) -> list[DriverSnapshot]:
        return sorted(candidates, key=lambda d: (d.trips_today, d.pickup_km(request.pickup), d.driver_id))
code/lld/ride_sharing/strategies.py — surge and the fare
class SurgeProvider(Protocol):
    """The multiplier applied to a fare at this pickup point, right now."""

    def multiplier(self, pickup: Location) -> float: ...


class NoSurge:
    """Null Object: the default. Pricing never branches on ``surge is None``."""

    def multiplier(self, pickup: Location) -> float:
        return 1.0


class FlatSurge:
    """One multiplier over the whole city -- a bank holiday, a storm."""

    def __init__(self, multiplier: float = 1.0) -> None:
        self._multiplier = multiplier

    def multiplier(self, pickup: Location) -> float:
        return self._multiplier


class ZoneSurge:
    """Per-cell multipliers, read off the same grid dispatch already uses.

    Reusing the index geometry is the point: a surge zone is a set of cells, so
    the pricing team and the dispatch team argue about the same coordinates.
    """

    def __init__(self, index: DriverLocationIndex, zones: dict[Cell, float], default: float = 1.0) -> None:
        self._index = index
        self._zones = dict(zones)
        self._default = default

    def multiplier(self, pickup: Location) -> float:
        return self._zones.get(self._index.cell_of(pickup), self._default)


class FareCalculator:
    """base + per km + per minute, multiplied by surge, floored at the minimum."""

    def __init__(self, surge: SurgeProvider | None = None) -> None:
        self._surge = surge or NoSurge()

    def quote(self, ride_type: RideType, distance_km: float, minutes: float, pickup: Location) -> Fare:
        spec = RideTypeFactory.spec(ride_type)
        multiplier = self._surge.multiplier(pickup)
        distance = spec.per_km * Decimal(str(round(max(distance_km, 0.0), 2)))
        time = spec.per_minute * Decimal(str(round(max(minutes, 0.0), 2)))
        raw = (spec.base + distance + time) * Decimal(str(multiplier))
        return Fare(spec.base, distance, time, multiplier, max(raw, spec.minimum))

    def estimate(self, request: RideRequest, speed_kmh: float = AVERAGE_CITY_SPEED_KMH) -> Fare:
        """The number shown before the rider confirms: straight line at city speed."""
        distance = request.straight_line_km
        return self.quote(request.ride_type, distance, distance / speed_kmh * 60.0, request.pickup)


class CancellationPolicy:
    """Free before a driver commits, and free for a short grace window after."""

    FEE = Money.of("3.00")
    GRACE_SECONDS = 120.0

    def fee(self, trip: Trip, now: float) -> Money:
        if trip.status not in CHARGEABLE_CANCEL_FROM or trip.matched_at is None:
            return Money(0)
        if now - trip.matched_at <= self.GRACE_SECONDS:
            return Money(0)
        return self.FEE

TripService owns one lock and every write to a trip. finish_metering exists so the fare can be priced with no lock held and committed afterwards:

code/lld/ride_sharing/services.py — TripService
class TripService:
    """Owns the trip registry and every status change. One lock over both.

    ``transition`` is a check-and-flip against ``TRIP_TRANSITIONS``; listeners are
    notified *outside* the lock so a slow observer cannot stall dispatch.
    """

    def __init__(self, clock: Clock | None = None, ids: IdGenerator | None = None) -> None:
        self._clock = clock or SystemClock()
        self._ids = ids or SequentialIdGenerator("T")
        self._trips: dict[str, Trip] = {}
        self._listeners: list[TripListener] = []
        self._lock = threading.Lock()

    def subscribe(self, listener: TripListener) -> None:
        self._listeners.append(listener)

    def open(self, request: RideRequest) -> Trip:
        trip = Trip(id=self._ids.next_id(), request=request)
        with self._lock:
            self._trips[trip.id] = trip
        self._notify(trip, "requested")
        return trip

    def trip(self, trip_id: str) -> Trip:
        with self._lock:
            try:
                return self._trips[trip_id]
            except KeyError:
                raise UnknownTripError(f"unknown trip {trip_id}") from None

    def history(self, rider_id: str) -> list[Trip]:
        with self._lock:
            return [t for t in self._trips.values() if t.request.rider_id == rider_id]

    def transition(self, trip_id: str, target: TripStatus, event: str | None = None) -> Trip:
        with self._lock:
            trip = self._require(trip_id, target)
            trip.status = target
        self._notify(trip, event or str(target))
        return trip

    def assign_driver(self, trip_id: str, driver_id: str) -> Trip:
        """REQUESTED to MATCHED, atomically. A cancelled trip refuses the driver."""
        with self._lock:
            trip = self._require(trip_id, TripStatus.MATCHED)
            trip.status = TripStatus.MATCHED
            trip.driver_id = driver_id
            trip.matched_at = self._clock.now()
        self._notify(trip, "matched")
        return trip

    def start(self, trip_id: str) -> Trip:
        with self._lock:
            trip = self._require(trip_id, TripStatus.IN_PROGRESS)
            trip.status = TripStatus.IN_PROGRESS
            trip.started_at = self._clock.now()
        self._notify(trip, "in_progress")
        return trip

    def finish_metering(self, trip_id: str, distance_km: float) -> Trip:
        """Stop the meter without ending the trip, so the fare can be priced under no lock."""
        with self._lock:
            trip = self._require(trip_id, TripStatus.COMPLETED)
            trip.ended_at = self._clock.now()
            trip.distance_km = distance_km
            return trip

    def complete(self, trip_id: str, fare: Fare) -> Trip:
        with self._lock:
            trip = self._require(trip_id, TripStatus.COMPLETED)
            trip.fare = fare
            trip.status = TripStatus.COMPLETED
        self._notify(trip, "completed")
        return trip

    def cancel(self, trip_id: str, fee: Money) -> Trip:
        with self._lock:
            trip = self._require(trip_id, TripStatus.CANCELLED)
            trip.status = TripStatus.CANCELLED
            trip.cancellation_fee = fee
        self._notify(trip, "cancelled")
        return trip

    def _require(self, trip_id: str, target: TripStatus) -> Trip:
        """Caller holds the lock. Fetch the trip and assert the move is legal."""
        trip = self._trips.get(trip_id)
        if trip is None:
            raise UnknownTripError(f"unknown trip {trip_id}")
        if not trip.can_move_to(target):
            raise TripStateError(f"trip {trip_id} cannot move {trip.status} to {target}")
        return trip

    def _notify(self, trip: Trip, event: str) -> None:
        for listener in self._listeners:  # outside the lock, on purpose
            listener.on_trip_event(trip, event)

MatchingService is the mediator and the lease-holder. Read offer_next carefully — the shortlist is computed outside the lock and every candidate is re-checked inside it:

code/lld/ride_sharing/services.py — MatchingService
class MatchingService:
    """Mediator between riders, drivers and the location index.

    Nothing else in the system holds both a ``Driver`` and a ``Trip``. Riders ask
    it for a driver, drivers report position and answer offers to it, and it is
    the only object that decides who is told about whom.

    One lock guards driver statuses, the offer registry and the per-trip
    shortlist. The *index* has its own striped locks and is queried without this
    lock held: the shortlist it produces is a hint, re-validated when the lease
    is taken -- the same optimistic pattern a parking lot uses to claim a spot.
    """

    OFFER_TIMEOUT_SECONDS = 15.0
    SEARCH_RADII_KM = (1.5, 3.0, 5.0)
    SHORTLIST_SIZE = 5

    def __init__(
        self,
        drivers: Iterable[Driver],
        index: DriverLocationIndex | None = None,
        strategy: MatchingStrategy | None = None,
        clock: Clock | None = None,
        ids: IdGenerator | None = None,
        offer_timeout: float = OFFER_TIMEOUT_SECONDS,
    ) -> None:
        self._drivers = {d.id: d for d in drivers}
        self.index = index or DriverLocationIndex()
        self._strategy = strategy or FastestEta()
        self._clock = clock or SystemClock()
        self._ids = ids or SequentialIdGenerator("OF")
        self._timeout = offer_timeout
        self._offers: dict[str, DriverOffer] = {}
        self._shortlists: dict[str, list[str]] = {}
        self._lock = threading.Lock()

    def driver(self, driver_id: str) -> Driver:
        try:
            return self._drivers[driver_id]
        except KeyError:
            raise UnknownDriverError(f"no driver {driver_id}") from None

    def go_online(self, driver_id: str, location: Location | None = None) -> Driver:
        with self._lock:
            driver = self.driver(driver_id)
            driver.location = location or driver.location
            driver.status = DriverStatus.AVAILABLE
        self.index.update(driver_id, driver.location)
        return driver

    def go_offline(self, driver_id: str) -> Driver:
        self.index.remove(driver_id)
        with self._lock:
            driver = self.driver(driver_id)
            driver.status = DriverStatus.OFFLINE
            return driver

    def ping(self, driver_id: str, location: Location) -> None:
        """The hot path: thousands per second, and it never touches the dispatch lock."""
        self.index.update(driver_id, location)

    def shortlist(self, request: RideRequest) -> list[str]:
        """Expanding-radius index read plus a ranking. No dispatch lock is held."""
        for radius in self.SEARCH_RADII_KM:
            snapshots = self._snapshots(self.index.nearby(request.pickup, radius), request)
            if snapshots:
                ranked = self._strategy.rank(request, snapshots)
                return [s.driver_id for s in ranked[: self.SHORTLIST_SIZE]]
        return []

    def offer_next(self, trip_id: str, request: RideRequest) -> DriverOffer | None:
        """Lease the next candidate. Idempotent while an offer for the trip is live."""
        now = self._clock.now()
        with self._lock:
            live = [o for o in self._offers.values() if o.trip_id == trip_id and o.is_live(now)]
            if live:
                return live[0]
            queue = self._shortlists.get(trip_id)
        if queue is None:
            candidates = self.shortlist(request)  # index read, dispatch lock released
            with self._lock:
                queue = self._shortlists.setdefault(trip_id, candidates)
        with self._lock:
            while queue:
                driver = self._drivers.get(queue.pop(0))
                if driver is None or not driver.is_available():
                    continue  # the hint went stale between the index read and here
                offer = DriverOffer(self._ids.next_id(), trip_id, driver.id, now, now + self._timeout)
                driver.status = DriverStatus.OFFERED
                driver.current_trip_id = trip_id
                self._offers[offer.id] = offer
                return offer
            return None

    def accept(self, offer_id: str, driver_id: str) -> DriverOffer:
        """Claim the lease. Exactly one caller moves an offer out of PENDING."""
        with self._lock:
            offer = self._offers.get(offer_id)
            if offer is None or offer.driver_id != driver_id:
                raise OfferStateError(f"offer {offer_id} is not addressed to {driver_id}")
            if not offer.is_live(self._clock.now()):
                raise OfferStateError(f"offer {offer_id} is {offer.status} or expired")
            offer.status = OfferStatus.ACCEPTED
            self.driver(driver_id).status = DriverStatus.ON_TRIP
            return offer

    def decline(self, offer_id: str, driver_id: str) -> DriverOffer:
        with self._lock:
            offer = self._offers.get(offer_id)
            if offer is None or offer.driver_id != driver_id:
                raise OfferStateError(f"offer {offer_id} is not addressed to {driver_id}")
            if offer.status is not OfferStatus.PENDING:
                raise OfferStateError(f"offer {offer_id} is already {offer.status}")
            self._retire(offer, OfferStatus.DECLINED)
            return offer

    def sweep(self) -> list[DriverOffer]:
        """Expire every lease past its deadline and free those drivers."""
        now = self._clock.now()
        with self._lock:
            stale = [o for o in self._offers.values() if o.status is OfferStatus.PENDING and now >= o.expires_at]
            for offer in stale:
                self._retire(offer, OfferStatus.EXPIRED)
            return stale

    def release(self, offer: DriverOffer) -> None:
        """Undo a claim because the trip moved under the driver."""
        with self._lock:
            self._retire(offer, OfferStatus.VOIDED)

    def void_trip(self, trip_id: str) -> None:
        with self._lock:
            for offer in self._offers.values():
                if offer.trip_id == trip_id and offer.status in (OfferStatus.PENDING, OfferStatus.ACCEPTED):
                    self._retire(offer, OfferStatus.VOIDED)
            self._shortlists.pop(trip_id, None)

    def finish(self, driver_id: str) -> Driver:
        with self._lock:
            driver = self.driver(driver_id)
            driver.status = DriverStatus.AVAILABLE
            driver.current_trip_id = None
            driver.trips_today += 1
        self.index.update(driver_id, driver.location)
        return driver

    def offers_for(self, trip_id: str) -> list[DriverOffer]:
        with self._lock:
            return [o for o in self._offers.values() if o.trip_id == trip_id]

    def _snapshots(self, driver_ids: Iterable[str], request: RideRequest) -> list[DriverSnapshot]:
        """Freeze the eligible drivers. Availability here is a hint, not a promise."""
        out: list[DriverSnapshot] = []
        for driver_id in driver_ids:
            driver = self._drivers.get(driver_id)
            position = self.index.position(driver_id)
            if driver is None or position is None or not driver.is_available():
                continue
            if not driver.vehicle.serves(request.ride_type):
                continue
            out.append(DriverSnapshot(driver.id, position, driver.rating, driver.trips_today))
        return out

    def _retire(self, offer: DriverOffer, status: OfferStatus) -> None:
        """Caller holds the lock. The single place a leased driver is freed."""
        offer.status = status
        driver = self._drivers.get(offer.driver_id)
        if driver is not None and driver.status is not DriverStatus.OFFLINE:
            driver.status = DriverStatus.AVAILABLE
            driver.current_trip_id = None

The facade sequences and reverts:

code/lld/ride_sharing/facade.py — RideHailingService
class RideHailingService:
    """Facade over trips, matching and money. It sequences; it never computes.

    Every cross-service step is *claim, act, revert*: ``driver_accepts`` claims
    the lease inside ``MatchingService``, then matches the trip inside
    ``TripService``, and releases the lease if the trip has moved on. No method
    ever holds two service locks, so there is no lock order to get wrong.
    """

    def __init__(
        self,
        riders: Iterable[Rider],
        drivers: Iterable[Driver],
        index: DriverLocationIndex | None = None,
        strategy: MatchingStrategy | None = None,
        surge: SurgeProvider | None = None,
        clock: Clock | None = None,
        ids: IdGenerator | None = None,
        request_ids: IdGenerator | None = None,
        offer_timeout: float = MatchingService.OFFER_TIMEOUT_SECONDS,
    ) -> None:
        self._clock = clock or SystemClock()
        self._ids = ids or SequentialIdGenerator("T")
        self._request_ids = request_ids or SequentialIdGenerator("RQ")
        self._riders = {r.id: r for r in riders}
        self.trips = TripService(clock=self._clock, ids=self._ids)
        self.matching = MatchingService(
            drivers, index=index, strategy=strategy, clock=self._clock, offer_timeout=offer_timeout
        )
        self.fares = FareCalculator(surge)
        self.cancellation = CancellationPolicy()
        self.feed = TripFeed()
        self.earnings = EarningsBoard()
        self.trips.subscribe(self.feed)
        self.trips.subscribe(self.earnings)
        self._payments: dict[str, Payment] = {}
        self._ratings: list[Rating] = []
        self._lock = threading.Lock()

    # -- rider ------------------------------------------------------------------
    def estimate(self, pickup: Location, dropoff: Location, ride_type: RideType) -> Fare:
        request = RideRequest("estimate", "-", pickup, dropoff, RideType(ride_type), self._clock.now())
        return self.fares.estimate(request)

    def request_ride(self, rider_id: str, pickup: Location, dropoff: Location, ride_type: RideType) -> Trip:
        """Open a trip, then offer it to the best candidate the index knows about."""
        if rider_id not in self._riders:
            raise TripStateError(f"unknown rider {rider_id}")
        request = RideRequest(
            id=self._request_ids.next_id(),
            rider_id=rider_id,
            pickup=pickup,
            dropoff=dropoff,
            ride_type=RideType(ride_type),
            requested_at=self._clock.now(),
        )
        trip = self.trips.open(request)
        self._offer_next(trip)
        return trip

    def cancel_ride(self, trip_id: str) -> Trip:
        """Flip the trip first, so a driver accepting at the same instant loses."""
        trip = self.trips.trip(trip_id)
        fee = self.cancellation.fee(trip, self._clock.now())
        cancelled = self.trips.cancel(trip_id, fee)
        self.matching.void_trip(trip_id)
        return cancelled

    def history(self, rider_id: str) -> list[Trip]:
        return self.trips.history(rider_id)

    # -- driver -----------------------------------------------------------------
    def driver_accepts(self, offer_id: str, driver_id: str) -> Trip:
        offer = self.matching.accept(offer_id, driver_id)  # claim the lease
        try:
            return self.trips.assign_driver(offer.trip_id, driver_id)
        except TripStateError:
            self.matching.release(offer)  # the rider cancelled underneath
            raise

    def driver_declines(self, offer_id: str, driver_id: str) -> DriverOffer | None:
        offer = self.matching.decline(offer_id, driver_id)
        return self._offer_next(self.trips.trip(offer.trip_id))

    def sweep_offers(self) -> list[DriverOffer]:
        """Expire stale leases, then push each waiting trip down its shortlist."""
        expired = self.matching.sweep()
        for offer in expired:
            self._offer_next(self.trips.trip(offer.trip_id))
        return expired

    def driver_arrived(self, trip_id: str) -> Trip:
        return self.trips.transition(trip_id, TripStatus.ARRIVED, "arrived")

    def start_trip(self, trip_id: str) -> Trip:
        return self.trips.start(trip_id)

    def end_trip(self, trip_id: str, distance_km: float | None = None) -> Trip:
        """Stop the meter, price the fare outside every lock, then commit it."""
        trip = self.trips.trip(trip_id)
        metered = distance_km if distance_km is not None else trip.request.straight_line_km
        trip = self.trips.finish_metering(trip_id, metered)
        fare = self.fares.quote(trip.request.ride_type, trip.distance_km, trip.minutes(), trip.request.pickup)
        completed = self.trips.complete(trip_id, fare)
        if completed.driver_id:
            self.matching.finish(completed.driver_id)
        return completed

    # -- money and reputation ---------------------------------------------------
    def pay(self, trip_id: str) -> Payment:
        trip = self.trips.trip(trip_id)
        amount = trip.fare.total if trip.fare else (trip.cancellation_fee or Money(0))
        if trip.status not in (TripStatus.COMPLETED, TripStatus.CANCELLED):
            raise TripStateError(f"trip {trip_id} is {trip.status}, nothing to charge")
        payment = Payment(f"PAY-{trip_id}", trip_id, amount, captured=True)
        with self._lock:
            self._payments[trip_id] = payment
        return payment

    def rate_driver(self, trip_id: str, stars: int, comment: str = "") -> Rating:
        trip = self.trips.trip(trip_id)
        if trip.status is not TripStatus.COMPLETED or trip.driver_id is None:
            raise TripStateError(f"trip {trip_id} was not completed")
        rating = Rating(trip_id, trip.driver_id, stars, comment)
        driver = self.matching.driver(trip.driver_id)
        with self._lock:
            self._ratings.append(rating)
            total = driver.rating * driver.ratings_count + stars
            driver.ratings_count += 1
            driver.rating = round(total / driver.ratings_count, 2)
        return rating

    def _offer_next(self, trip: Trip) -> DriverOffer | None:
        """Offer to the next candidate, or declare the cascade exhausted."""
        if trip.status is not TripStatus.REQUESTED:
            return None
        offer = self.matching.offer_next(trip.id, trip.request)
        if offer is None:
            self.trips.transition(trip.id, TripStatus.NO_DRIVER, "no_driver")
        return offer

Running python -m lld.ride_sharing.demo walks a timeout, a decline, an accept and a surged fare:

6 drivers online; pickup cell (8393, 1439) holds 2
within 1.5 km of the pickup: ['d1', 'd2', 'd3', 'd5', 'd6']
economy estimate: 12.74 USD = (2.00 USD base + 4.56 USD distance + 2.54 USD time) x 1.40 surge
T-1 requested; shortlist ranked by ETA, OF-1 offered to d1 for 15 s
OF-1 expired; cascaded to d2, who declines
OF-3 offered to d3, who accepts
T-1 completed after 6.4 km in 18 min
fare: 15.90 USD = (2.00 USD base + 5.76 USD distance + 3.60 USD time) x 1.40 surge
PAY-T-1 captured 15.90 USD; Chetan now rated 4.73 with 15.90 USD earned
timeline: requested -> matched -> arrived -> in_progress -> completed

Concurrency and edge cases

Which lock protects what. Two families, and no method holds locks from both at once:

  1. Inside the index, _cell_locks[i] guards the cell-to-drivers map for cells hashing to stripe i, and _driver_locks[j] guards where a driver currently is. Lock order is one-way — driver stripe first, then cell stripes in ascending index order — so a driver crossing a boundary takes at most three locks in a provable order and the index cannot deadlock.
  2. MatchingService._lock guards driver statuses, the offer registry and the per-trip shortlist. TripService._lock guards the trip registry and every transition. Cross-service work is claim, act, revert.

Why striping is worth the extra code. Position updates dominate. A city with 30,000 drivers online pinging every 4 seconds is 30,000 / 4 = 7,500 updates per second. A single lock would serialise all of them behind one critical section; sixteen stripes spread it to roughly 7,500 / 16 ≈ 470 per stripe, and drivers who stay inside their cell — the common case — do no set edits at all. The lock itself is not the cost: an uncontended acquire is about 17 ns, so 7,500 of them is 0.13 ms of pure locking per second. What you are buying is parallel progress on the writes inside. For scale reference, a single Redis instance sustains about 100k ops/s, so this shape of workload fits one node comfortably until the fleet is an order of magnitude larger.

The read is a hint, the lease is the truth. shortlist queries the index and ranks without the dispatch lock, because ranking five candidates should not block every other request in the city. By the time offer_next runs, a candidate may already be leased — so it re-checks driver.is_available() under the lock and skips to the next entry. This is exactly the parking lot's "choose without the lock, claim under it" loop, and saying that out loud connects two problems in the interviewer's head.

No double assignment. Only offer_next moves a driver AVAILABLE → OFFERED, and only inside the lock. Two riders whose shortlists both start with the same driver cannot both lease them: the loser sees a non-available driver and moves down its own list. offer_next is also idempotent — a live offer for the trip is returned rather than a second driver being leased.

Search cost. nearby reads a square ring of cells and then filters exactly. A 1 km grid searched at 1.5 km reads a 5x5 block: 25 cells, of which the corners are 2.1 km away and get discarded by the distance filter. That over-read is the deliberate trade — a cheap superset from the grid, then exact arithmetic — and it is why the radius expands 1.5 km, 3 km, 5 km rather than starting wide.

Cancel during an offer. cancel_ride flips the trip first and then voids the offer, so a driver accepting at the same instant either loses at assign_driver (and their lease is released in the except branch) or has already won and is released by void_trip. Either way the driver ends AVAILABLE — that is the invariant the test asserts, rather than "exactly one call wins".

Edge cases handled: a driver leaving the index while a shortlist that names them is in flight, a ride class no online driver serves, the cascade running out and ending in NO_DRIVER, an expired offer being accepted, an offer accepted by the wrong driver, cancelling inside and outside the grace window, rating a trip that never completed, and a driver going offline mid-lease.

Common mistake

Holding one lock around "find nearby drivers, rank them, and assign the best one". It is correct and it is also a city-wide mutex: every rider in the city queues behind one ranking pass, and every GPS ping queues behind those. Split it the way the code does — a striped index for position, a short critical section for the lease, and an explicit re-check because the read in between was only a hint.

Extensibility and follow-ups

  • Pooling: Driver gains a seat budget and DriverOffer names a list of trips. MatchingStrategy keeps working unchanged because it only reads snapshots; what changes is the eligibility filter and the fare split.
  • Surge from live supply and demand: a DemandSurge(index, requests_per_cell) implementing SurgeProvider, reading the same cells the index already maintains. Nothing else changes — that is the payoff of ZoneSurge sharing the index's geometry.
  • Scheduled rides: a queue keyed by departure time that calls request_ride at the right moment; the state machine gains a SCHEDULED state before REQUESTED.
  • Broadcast matching: offer to the top three at once and let the first accept win. offer_next becomes offer_batch, and the lease invariant becomes "a driver holds at most one live offer" instead of "a trip has at most one".
  • Real ETAs: replace the straight line with a routing service behind MatchingStrategy. The ranking call becomes network-bound, which is precisely why it must stay outside the dispatch lock.
  • Better geometry: swap the uniform grid for geohash prefixes, S2 cells or H3 hexagons. The interface is three methods — update, remove, nearby — so the swap is contained. See Geospatial indexing for the trade-offs.

Interview tip

Draw the grid before you draw any class. Put four dots in cells, circle the 3x3 block around the pickup, and say "this is the read path, and it is striped so pings do not queue". Interviewers grade this problem on whether you understand that position updates outnumber ride requests by orders of magnitude — everything else in your design follows from that sentence.

Tests

tests/test_ride_sharing.py has 20 cases. Two concurrency tests carry the design. The first hammers the index with 480 pings from twelve threads, deliberately letting two threads ping the same driver — the interleaving that duplicates a driver across cells in a naive implementation:

code/lld/ride_sharing/tests/test_ride_sharing.py — index under contention and no double assignment
def test_concurrent_pings_never_leave_a_driver_in_two_cells() -> None:
    index = DriverLocationIndex(cell_size_km=1.0, reference_lat=12.97, stripes=8)
    ids = [f"d{i}" for i in range(12)]
    rng = random.Random(42)
    # Two threads ping the *same* driver, which is the interleaving that corrupts
    # a naive index: one thread adds to the new cell while the other is removing.
    pings = [(driver_id, Location(PICKUP.lat + rng.uniform(-0.02, 0.02), PICKUP.lon + rng.uniform(-0.02, 0.02)))
             for driver_id in ids for _ in range(40)]
    rng.shuffle(pings)

    with ThreadPoolExecutor(max_workers=12) as pool:
        list(pool.map(lambda p: index.update(*p), pings))
    for driver_id in ids:  # settle every driver on a known point
        index.update(driver_id, PICKUP)

    found = index.nearby(PICKUP, 5.0)
    assert sorted(found) == sorted(ids)  # equal length means no driver was duplicated or lost
    assert index.cell_population(index.cell_of(PICKUP)) == len(ids)


def test_concurrent_requests_never_offer_one_driver_two_trips(clock: FakeClock) -> None:
    service = build(clock, [make_driver(i) for i in range(1, 4)])

    def request(i: int) -> str | None:
        trip = service.request_ride("r1", PICKUP, DROPOFF, RideType.ECONOMY)
        offers = service.matching.offers_for(trip.id)
        return offers[0].driver_id if offers else None

    with ThreadPoolExecutor(max_workers=8) as pool:
        leased = [d for d in pool.map(request, range(8)) if d is not None]

    assert len(leased) == 3 and len(set(leased)) == 3  # three drivers, three leases
    assert all(service.matching.driver(d).status is DriverStatus.OFFERED for d in leased)
    no_driver = [t for t in service.history("r1") if t.status is TripStatus.NO_DRIVER]
    assert len(no_driver) == 5  # the other five riders are told nobody is free

The second half of that snippet races eight ride requests at three drivers and asserts three distinct leases plus five NO_DRIVER trips — no silent over-assignment and no lost requests.

The rest cover: the end-to-end trip with a surged fare, the observer timeline and the earnings board; the index moving a driver between cells and emptying the old one; twelve threads racing to accept one offer with exactly one winner; a cancel during an offer freeing the driver and killing the offer; the timeout walking the shortlist and then giving up with NO_DRIVER; the transition table through a six-case parametrize; ride-class eligibility filtering the shortlist; the four matching strategies each picking a different driver from the same three snapshots; the cancellation fee inside and outside the grace window; and rating an unfinished trip being rejected while a finished one moves the running average. Run them with uv run pytest code/lld/ride_sharing -q.

45-minute pacing

Minutes What to do What to say or write
0–5 Clarify How many drivers, how often do they ping? One offer or a broadcast? Straight line or routing? Out of scope: pooling, scheduling, real maps.
5–12 The index Draw the grid, the 3x3 read, the expanding radius. Write cell_of and nearby. Say "pings outnumber requests by orders of magnitude".
12–20 Entities and states Trip statuses as a table, driver statuses as a four-state lease. Then the class diagram with MatchingService in the middle.
20–34 Code DriverLocationIndex.update with the two stripe families → shortlist → offer_next with the re-check → accept → assign_driver with the revert.
34–40 Concurrency The lock order, the hint-versus-truth split, the timeout sweep, and why cancel-versus-accept is judged on the driver's final state.
40–45 Extensions Pooling, demand-based surge, broadcast offers, and the swap to H3 — then hand off to the HLD version.