On this page

Design a Ride-Sharing System (LLD)

This is the final capstone of the LLD course. A ride-sharing core packs most of the earlier modules into one familiar product: a lifecycle with real business rules, two algorithm families interviewers love to swap (matching and pricing), a spatial lookup that must be fast, and two races that cost real money if you get them wrong. Everyone has used the product, so nobody needs the domain explained and design gaps show quickly.

The Uber/Lyft system design covers the distributed version: location ingestion, geospatial sharding, dispatch services. This page stays at class level: one process, in-memory state, real threads. The questions are what the classes are, who owns which invariant, and how the code stays correct when two requests arrive in the same microsecond. We follow the LLD interview framework.

1. Requirements

Clarifying questions worth asking

QuestionAnswer we assumeWhy it matters
One vehicle category or several?One to start. Categories come later as an extensionDecides whether matching needs a filter
Does the driver get to accept or decline?Yes. The trip is offered to one driver at a timeAdds a RESERVED state for drivers and a re-offer path
Can the rider cancel? When does it cost money?Free before acceptance, a flat fee afterCancel has to know which state it interrupted
How is the fare computed?Base + per km + per minute, times surge, floored at a minimumPricing must be composable
When is surge fixed?When the trip is requestedThe rider agreed to that multiplier, so the trip stores it
How is payment taken?Charged automatically on completion through a gatewayPayment is an external call that can fail
Who rates whom?Each side rates the other once per completed tripRatings feed back into matching
Pooling, scheduled rides, driver payouts?Out of scopeEach one is a separate design

Functional requirements

  1. Riders and drivers register. Drivers go online and stream their location.
  2. A rider requests a trip from a pickup to a dropoff.
  3. The system finds nearby available drivers, ranks them with a pluggable strategy and offers the trip to the best one.
  4. The driver accepts or declines. A decline moves the offer to the next-best driver. If nobody is left, the trip is cancelled.
  5. The trip moves through REQUESTED → ACCEPTED → ARRIVED → IN_PROGRESS → COMPLETED. CANCELLED is allowed from the first three states.
  6. On completion, the fare is computed and the rider is charged. A cancellation after acceptance charges a fee.
  7. After completion, rider and driver each rate the other once (1 to 5 stars).

Non-functional requirements

  • Correctness under concurrency. A driver is assigned to at most one active trip, ever. Concurrent requests, accepts and cancels must not leave a driver stuck on a dead trip.
  • Fast nearby search. Finding candidates must not scan every driver in the city.
  • Open for extension. New matching rules, fare components and vehicle categories shouldn't mean editing the trip lifecycle.
  • Testable. Payment and surge are injected, so tests run with fakes and no network.
  • Money in integer cents. Floating-point money is a classic interview red flag.

2. Core entities

EntityKindOwns
LocationValue objectx/y in km, distance
RiderEntityid, Rating
DriverEntityid, current Location, atomic DriverStatus, Rating
TripEntity, the aggregate root for one riderider, assigned driver, pickup, dropoff, locked-in surge, TripStatus, fare, payment status, who declined, rating flags
RatingValue holdercount and sum. The average is derived
GridIndexDomain servicecell to drivers buckets, nearby queries
MatchingStrategyStrategy interfaceranks candidates
FareCalculatorStrategy interface, decoratedturns TripMetrics into cents
PaymentGatewayPortcharges a rider idempotently
RideServiceFacade / application serviceorchestrates every use case and owns the registries

Three of these choices deserve a sentence aloud in the interview:

  • Trip owns the lifecycle, not Driver. A driver goes through many trips. If status lived only on the driver, you couldn't answer "what happened to trip T42?" The driver keeps a coarse availability status, and the trip keeps the rich one.
  • Surge is a field on Trip. If the fare re-read the current surge at completion, a rider who requested at 1.0x could pay 2.0x because demand spiked mid-ride.
  • Ratings are aggregates, not lists. Matching only needs the average, so we store count and sum. Keep individual reviews in a separate store if the product needs them.

Class diagram

classDiagram
    class RideService {
        +addRider(id) Rider
        +addDriver(id, location) Driver
        +updateLocation(driverId, location)
        +requestTrip(riderId, pickup, dropoff) Trip
        +accept(tripId, driverId)
        +decline(tripId, driverId)
        +arrive(tripId, driverId)
        +start(tripId, driverId)
        +complete(tripId, driverId, metrics) long
        +cancel(tripId, riderId)
        +rateDriver(tripId, stars)
        +rateRider(tripId, stars)
    }
    class Trip {
        +id
        +pickup
        +dropoff
        +surge
        -status TripStatus
        -driver Driver
        -fareCents
        -payment PaymentStatus
        -declinedBy Set
    }
    class Driver {
        +id
        -location
        -status AtomicReference
        +transition(from, to) boolean
    }
    class Rider {
        +id
    }
    class Rating {
        -count
        -sum
        +add(stars)
        +average() double
    }
    class GridIndex {
        -cells Map
        +add(driver)
        +move(driver, to)
        +nearby(point, radius) List~Driver~
    }
    class MatchingStrategy {
        <<interface>>
        +rank(candidates, pickup) List~Driver~
    }
    class NearestDriverStrategy
    class RatingWeightedStrategy
    class FareCalculator {
        <<interface>>
        +fareCents(metrics) long
    }
    class StandardFare
    class SurgeFare
    class MinimumFare
    class PaymentGateway {
        <<interface>>
        +charge(riderId, cents, key) boolean
    }
    RideService --> GridIndex
    RideService --> MatchingStrategy
    RideService --> FareCalculator
    RideService --> PaymentGateway
    RideService "1" o-- "*" Trip
    Trip --> Rider
    Trip --> Driver
    Rider *-- Rating
    Driver *-- Rating
    GridIndex o-- Driver
    MatchingStrategy <|.. NearestDriverStrategy
    MatchingStrategy <|.. RatingWeightedStrategy
    FareCalculator <|.. StandardFare
    FareCalculator <|.. SurgeFare
    FareCalculator <|.. MinimumFare
    SurgeFare o-- FareCalculator : wraps
    MinimumFare o-- FareCalculator : wraps

3. Lifecycles

Trip

stateDiagram-v2
    [*] --> REQUESTED : rider requests, driver reserved
    REQUESTED --> REQUESTED : driver declines, next driver offered
    REQUESTED --> ACCEPTED : driver accepts
    REQUESTED --> CANCELLED : rider cancels, or nobody left to offer
    ACCEPTED --> ARRIVED : driver at pickup
    ACCEPTED --> CANCELLED : rider cancels, fee
    ARRIVED --> IN_PROGRESS : rider on board
    ARRIVED --> CANCELLED : rider cancels, fee
    IN_PROGRESS --> COMPLETED : dropoff, fare charged
    COMPLETED --> [*]
    CANCELLED --> [*]

IN_PROGRESS only leads to completion. A rider stopping early gets a shorter completed trip, which removes "cancelled with the rider in the car" bugs.

Driver

stateDiagram-v2
    [*] --> OFFLINE
    OFFLINE --> AVAILABLE : goes online
    AVAILABLE --> RESERVED : trip offered, CAS
    RESERVED --> ON_TRIP : accepts
    RESERVED --> AVAILABLE : declines, or rider cancels
    ON_TRIP --> AVAILABLE : trip completed or cancelled
    AVAILABLE --> OFFLINE : goes offline

RESERVED makes atomic assignment possible: offering a trip moves the driver out of AVAILABLE with a compare-and-set, so no other request can claim them while the first waits for an answer.

4. Key flows

Request, match and accept

sequenceDiagram
    participant R as Rider app
    participant S as RideService
    participant G as GridIndex
    participant M as MatchingStrategy
    participant D as Driver
    R->>S: requestTrip r1, pickup, dropoff
    S->>S: surge = multiplierAt pickup, stored on Trip
    S->>G: nearby pickup, 3 km
    G-->>S: candidates from surrounding cells
    S->>M: rank AVAILABLE candidates
    M-->>S: ordered list
    S->>D: transition AVAILABLE to RESERVED
    D-->>S: true, claimed
    S-->>R: Trip T1, REQUESTED, offered to d1
    D->>S: accept T1
    S->>D: transition RESERVED to ON_TRIP
    S-->>D: Trip T1 ACCEPTED

If the CAS returns false, another request claimed that driver between our search and our claim. That's normal, not an error. We try the next driver in the ranked list.

Complete and pay

sequenceDiagram
    participant D as Driver app
    participant S as RideService
    participant T as Trip
    participant F as FareCalculator chain
    participant P as PaymentGateway
    D->>S: complete T1, 5 km, 12 min
    S->>T: lock, require IN_PROGRESS
    S->>F: MinimumFare over SurgeFare over StandardFare
    F-->>S: 1815 cents
    S->>T: status COMPLETED, fare 1815
    S->>D: transition ON_TRIP to AVAILABLE
    S->>T: unlock
    S->>P: charge r1, 1815, key T1 fare
    P-->>S: ok
    S->>T: payment PAID

The charge happens after the lock is released. A payment call can take seconds, and holding the trip lock that long would block the rider's app from even reading the trip. The idempotency key T1:fare means a retry after a timeout can't charge twice.

Accept racing cancel

sequenceDiagram
    participant D as Driver thread
    participant T as Trip T1 lock
    participant R as Rider thread
    D->>T: acquire
    R->>T: acquire, blocks
    T-->>D: status REQUESTED, accept allowed
    D->>T: ACCEPTED, driver ON_TRIP, release
    T-->>R: acquired, status ACCEPTED
    R->>T: CANCELLED, driver ON_TRIP to AVAILABLE, fee due, release
    Note over D,R: Reverse order: cancel wins, accept sees CANCELLED and fails

5. Patterns, and why

PatternWhereRequirement it servesAlternative rejected
StrategyMatchingStrategy: nearest, rating-weightedMatching policy changes by market and experimentif (mode == ...) in requestTrip, which grows with every experiment and can't be unit-tested on its own
DecoratorSurgeFare, MinimumFare around StandardFareFare components stack, and order mattersOne calculateFare method with flags for surge, minimum and promo, which gives 2^n code paths in one function
Strategy (again)FareCalculator itselfDifferent cities or categories have different rate cardsConstants inside Trip
State machine (enum + guards)TripStatus with require(...)Lifecycle rulesFull State pattern classes, see below
FacadeRideServiceOne entry point per use case, so invariants live in one placeLetting callers mutate Trip and Driver directly
Port / dependency injectionPaymentGateway, surge providerTestability, swapping providersCalling a payment SDK from complete

Why not the full State pattern for Trip? State pays off when each state behaves differently, like a vending machine where "insert coin" means something new in every state. Here every state just allows or rejects a transition, and the real work (releasing the driver, charging a fee) depends on the transition. An enum plus a require(allowed...) guard fits on one screen. Switch to State classes when states carry their own data and behaviour, say ARRIVED running a wait-time meter.

Why a ScoredMatching base? It owns the snapshot-then-sort step, where a subtle bug lives (section 7), so each strategy writes only its scoring line.

Decorator order is a product decision, so say it aloud. MinimumFare(SurgeFare(base)) floors the fare after surge, so the minimum doesn't surge. SurgeFare(MinimumFare(base)) surges the minimum too. Both are defensible. The point is that the order is visible in one line of wiring instead of buried in arithmetic.

6. The code

All three implementations are complete and runnable. Each file ends with a main/demo that walks through the use cases and asserts the results. The Java main also runs both concurrency races. Save the Python file as ride_sharing.py, because the test file in section 9 imports it.

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;

record Location(double x, double y) {             // planar km, enough for a grid demo
    double distanceTo(Location o) { return Math.hypot(x - o.x, y - o.y); }
}

record TripMetrics(double km, double minutes) {}

enum DriverStatus { OFFLINE, AVAILABLE, RESERVED, ON_TRIP }
enum TripStatus { REQUESTED, ACCEPTED, ARRIVED, IN_PROGRESS, COMPLETED, CANCELLED }
enum PaymentStatus { NONE, PAID, FAILED }

class RideException extends RuntimeException {
    RideException(String message) { super(message); }
}

final class Rating {
    private long count, sum;                       // guarded by this
    synchronized void add(int stars) {
        if (stars < 1 || stars > 5) throw new RideException("stars must be 1..5");
        count++; sum += stars;
    }
    synchronized double average() { return count == 0 ? 5.0 : (double) sum / count; }
}

final class Rider {
    final String id; final Rating rating = new Rating();
    Rider(String id) { this.id = id; }
}

final class Driver {
    final String id; final Rating rating = new Rating();
    private final AtomicReference<DriverStatus> status = new AtomicReference<>(DriverStatus.OFFLINE);
    private volatile Location location;
    Driver(String id, Location location) { this.id = id; this.location = location; }
    DriverStatus status() { return status.get(); }
    Location location() { return location; }
    void setLocation(Location l) { location = l; }
    boolean transition(DriverStatus from, DriverStatus to) { return status.compareAndSet(from, to); }
}

final class Trip {
    final String id; final Rider rider; final Location pickup, dropoff; final double surge;
    // everything below is guarded by the Trip's own monitor
    Driver driver;
    TripStatus status = TripStatus.REQUESTED;
    PaymentStatus payment = PaymentStatus.NONE;
    long fareCents;
    boolean riderRated, driverRated;
    final Set<String> declinedBy = new HashSet<>();

    Trip(String id, Rider rider, Location pickup, Location dropoff, double surge) {
        this.id = id; this.rider = rider; this.pickup = pickup; this.dropoff = dropoff; this.surge = surge;
    }
    void require(TripStatus... allowed) {
        for (TripStatus s : allowed) if (s == status) return;
        throw new RideException("trip " + id + " is " + status);
    }
    void requireDriver(Driver d) {
        if (driver != d) throw new RideException("driver " + d.id + " is not on trip " + id);
    }
    synchronized TripStatus status() { return status; }
    synchronized Driver driver() { return driver; }
    synchronized PaymentStatus payment() { return payment; }
    synchronized long fareCents() { return fareCents; }
}

final class GridIndex {
    private final double cellKm;
    private final Map<Long, Set<Driver>> cells = new ConcurrentHashMap<>();
    GridIndex(double cellKm) { this.cellKm = cellKm; }

    private int cell(double v) { return (int) Math.floor(v / cellKm); }
    private long key(int cx, int cy) { return ((long) cx << 32) | (cy & 0xffffffffL); }
    private long keyOf(Location l) { return key(cell(l.x()), cell(l.y())); }
    private Set<Driver> bucket(long k) { return cells.computeIfAbsent(k, x -> ConcurrentHashMap.newKeySet()); }

    void add(Driver d) { bucket(keyOf(d.location())).add(d); }

    void move(Driver d, Location to) {
        synchronized (d) {                         // one driver's updates apply in order
            long from = keyOf(d.location()), next = keyOf(to);
            d.setLocation(to);
            if (from != next) { bucket(next).add(d); bucket(from).remove(d); }
        }
    }

    List<Driver> nearby(Location p, double radiusKm) {
        int r = (int) Math.ceil(radiusKm / cellKm), cx = cell(p.x()), cy = cell(p.y());
        List<Driver> out = new ArrayList<>();
        for (int x = cx - r; x <= cx + r; x++)
            for (int y = cy - r; y <= cy + r; y++)
                for (Driver d : cells.getOrDefault(key(x, y), Set.of()))
                    if (d.location().distanceTo(p) <= radiusKm) out.add(d);
        return out;
    }
}

interface MatchingStrategy { List<Driver> rank(List<Driver> candidates, Location pickup); }

abstract class ScoredMatching implements MatchingStrategy {
    abstract double score(Driver d, Location pickup);      // lower is better
    public List<Driver> rank(List<Driver> candidates, Location pickup) {
        // snapshot scores first: locations change while we sort
        Map<Driver, Double> scores = new HashMap<>();
        for (Driver d : candidates) scores.put(d, score(d, pickup));
        List<Driver> out = new ArrayList<>(candidates);
        out.sort(Comparator.comparingDouble(scores::get));
        return out;
    }
}

final class NearestDriverStrategy extends ScoredMatching {
    double score(Driver d, Location p) { return d.location().distanceTo(p); }
}

final class RatingWeightedStrategy extends ScoredMatching {
    private final double kmPerMissingStar;
    RatingWeightedStrategy(double kmPerMissingStar) { this.kmPerMissingStar = kmPerMissingStar; }
    double score(Driver d, Location p) {
        return d.location().distanceTo(p) + kmPerMissingStar * (5.0 - d.rating.average());
    }
}

interface FareCalculator { long fareCents(TripMetrics m); }

final class StandardFare implements FareCalculator {
    private final long baseCents, perKmCents, perMinuteCents;
    StandardFare(long base, long perKm, long perMinute) { baseCents = base; perKmCents = perKm; perMinuteCents = perMinute; }
    public long fareCents(TripMetrics m) {
        return baseCents + Math.round(m.km() * perKmCents) + Math.round(m.minutes() * perMinuteCents);
    }
}

final class SurgeFare implements FareCalculator {
    private final FareCalculator inner; private final double multiplier;
    SurgeFare(FareCalculator inner, double multiplier) { this.inner = inner; this.multiplier = multiplier; }
    public long fareCents(TripMetrics m) { return Math.round(inner.fareCents(m) * multiplier); }
}

final class MinimumFare implements FareCalculator {
    private final FareCalculator inner; private final long minCents;
    MinimumFare(FareCalculator inner, long minCents) { this.inner = inner; this.minCents = minCents; }
    public long fareCents(TripMetrics m) { return Math.max(minCents, inner.fareCents(m)); }
}

interface SurgeProvider { double multiplierAt(Location p); }
interface PaymentGateway { boolean charge(String riderId, long cents, String idempotencyKey); }

final class RideService {
    static final double SEARCH_RADIUS_KM = 3.0;
    static final long CANCEL_FEE_CENTS = 300, MIN_FARE_CENTS = 500;

    private final Map<String, Rider> riders = new ConcurrentHashMap<>();
    private final Map<String, Driver> drivers = new ConcurrentHashMap<>();
    private final Map<String, Trip> trips = new ConcurrentHashMap<>();
    private final AtomicLong ids = new AtomicLong();
    private final GridIndex index = new GridIndex(1.0);
    private final MatchingStrategy matcher; private final FareCalculator baseFare;
    private final SurgeProvider surge; private final PaymentGateway payments;

    RideService(MatchingStrategy matcher, FareCalculator baseFare, SurgeProvider surge, PaymentGateway payments) {
        this.matcher = matcher; this.baseFare = baseFare; this.surge = surge; this.payments = payments;
    }

    Rider addRider(String id) { Rider r = new Rider(id); riders.put(id, r); return r; }

    Driver addDriver(String id, Location at) {
        Driver d = new Driver(id, at);
        drivers.put(id, d); index.add(d); d.transition(DriverStatus.OFFLINE, DriverStatus.AVAILABLE);
        return d;
    }

    void updateLocation(String driverId, Location to) { index.move(get(drivers, driverId), to); }

    Trip requestTrip(String riderId, Location pickup, Location dropoff) {
        Rider rider = get(riders, riderId);
        Trip t = new Trip("T" + ids.incrementAndGet(), rider, pickup, dropoff, surge.multiplierAt(pickup));
        synchronized (t) {
            if (!offerToNextDriver(t)) throw new RideException("no driver available");
        }
        trips.put(t.id, t);
        return t;
    }

    // caller holds t's monitor, so the trip cannot be cancelled while we reserve
    private boolean offerToNextDriver(Trip t) {
        List<Driver> free = new ArrayList<>();
        for (Driver d : index.nearby(t.pickup, SEARCH_RADIUS_KM))
            if (d.status() == DriverStatus.AVAILABLE && !t.declinedBy.contains(d.id)) free.add(d);
        for (Driver d : matcher.rank(free, t.pickup)) {
            if (d.transition(DriverStatus.AVAILABLE, DriverStatus.RESERVED)) {  // atomic claim
                t.driver = d;
                return true;
            }
        }
        t.driver = null;
        return false;
    }

    void accept(String tripId, String driverId) {
        Trip t = get(trips, tripId); Driver d = get(drivers, driverId);
        synchronized (t) {
            t.require(TripStatus.REQUESTED); t.requireDriver(d);
            if (!d.transition(DriverStatus.RESERVED, DriverStatus.ON_TRIP)) throw new RideException("driver not reserved");
            t.status = TripStatus.ACCEPTED;
        }
    }

    void decline(String tripId, String driverId) {
        Trip t = get(trips, tripId); Driver d = get(drivers, driverId);
        synchronized (t) {
            t.require(TripStatus.REQUESTED); t.requireDriver(d);
            d.transition(DriverStatus.RESERVED, DriverStatus.AVAILABLE);
            t.declinedBy.add(d.id);
            if (!offerToNextDriver(t)) t.status = TripStatus.CANCELLED;
        }
    }

    void arrive(String tripId, String driverId) { advance(tripId, driverId, TripStatus.ACCEPTED, TripStatus.ARRIVED); }
    void start(String tripId, String driverId) { advance(tripId, driverId, TripStatus.ARRIVED, TripStatus.IN_PROGRESS); }

    private void advance(String tripId, String driverId, TripStatus from, TripStatus to) {
        Trip t = get(trips, tripId);
        synchronized (t) { t.require(from); t.requireDriver(get(drivers, driverId)); t.status = to; }
    }

    long complete(String tripId, String driverId, TripMetrics metrics) {
        Trip t = get(trips, tripId); Driver d = get(drivers, driverId);
        long fare;
        synchronized (t) {
            t.require(TripStatus.IN_PROGRESS); t.requireDriver(d);
            FareCalculator calc = new MinimumFare(new SurgeFare(baseFare, t.surge), MIN_FARE_CENTS);
            fare = calc.fareCents(metrics);
            t.fareCents = fare;
            t.status = TripStatus.COMPLETED;
            d.transition(DriverStatus.ON_TRIP, DriverStatus.AVAILABLE);
        }
        charge(t, fare, t.id + ":fare");             // network call outside the lock
        return fare;
    }

    void cancel(String tripId, String riderId) {
        Trip t = get(trips, tripId);
        boolean fee;
        synchronized (t) {
            if (t.rider != get(riders, riderId)) throw new RideException("not your trip");
            t.require(TripStatus.REQUESTED, TripStatus.ACCEPTED, TripStatus.ARRIVED);
            fee = t.status != TripStatus.REQUESTED;
            if (t.driver != null)
                t.driver.transition(fee ? DriverStatus.ON_TRIP : DriverStatus.RESERVED, DriverStatus.AVAILABLE);
            t.status = TripStatus.CANCELLED;
        }
        if (fee) charge(t, CANCEL_FEE_CENTS, t.id + ":cancel");
    }

    void rateDriver(String tripId, int stars) {
        Trip t = get(trips, tripId);
        synchronized (t) {
            t.require(TripStatus.COMPLETED);
            if (t.driverRated) throw new RideException("driver already rated");
            t.driver.rating.add(stars); t.driverRated = true;
        }
    }

    void rateRider(String tripId, int stars) {
        Trip t = get(trips, tripId);
        synchronized (t) {
            t.require(TripStatus.COMPLETED);
            if (t.riderRated) throw new RideException("rider already rated");
            t.rider.rating.add(stars); t.riderRated = true;
        }
    }

    private void charge(Trip t, long cents, String key) {
        boolean ok = payments.charge(t.rider.id, cents, key);
        synchronized (t) { t.payment = ok ? PaymentStatus.PAID : PaymentStatus.FAILED; }
    }

    private static <T> T get(Map<String, T> m, String id) {
        T v = m.get(id);
        if (v == null) throw new RideException("unknown id " + id);
        return v;
    }
}

final class FakeGateway implements PaymentGateway {
    final Map<String, Long> charges = new ConcurrentHashMap<>();
    volatile boolean fail;
    public boolean charge(String riderId, long cents, String key) {
        if (fail) return false;
        charges.putIfAbsent(key, cents);             // idempotent by key
        return true;
    }
}

public class Main {
    static RideService service(MatchingStrategy m, FakeGateway g) {
        return new RideService(m, new StandardFare(250, 120, 30), p -> 1.5, g);
    }

    static void check(boolean ok, String what) { if (!ok) throw new AssertionError(what); }

    public static void main(String[] args) throws Exception {
        FakeGateway g = new FakeGateway();
        RideService s = service(new NearestDriverStrategy(), g);
        s.addRider("r1");
        s.addDriver("near", new Location(0.5, 0.5));
        s.addDriver("far", new Location(2.0, 1.5));

        // happy path: nearest driver, full lifecycle, surge fare, payment, ratings
        Trip t = s.requestTrip("r1", new Location(0, 0), new Location(5, 0));
        check(t.driver().id.equals("near"), "nearest driver offered");
        s.accept(t.id, "near"); s.arrive(t.id, "near"); s.start(t.id, "near");
        long fare = s.complete(t.id, "near", new TripMetrics(5, 12));
        check(fare == 1815, "fare (250 + 600 + 360) * 1.5 = 1815, got " + fare);
        check(t.payment() == PaymentStatus.PAID && g.charges.get(t.id + ":fare") == 1815, "charged");
        s.rateDriver(t.id, 4); s.rateRider(t.id, 5);
        try { s.rateDriver(t.id, 5); check(false, "double rating"); } catch (RideException expected) {}

        // decline re-offers to the next driver
        Trip t2 = s.requestTrip("r1", new Location(0, 0), new Location(1, 1));
        s.decline(t2.id, "near");
        check(t2.driver().id.equals("far") && t2.status() == TripStatus.REQUESTED, "re-offered");
        s.cancel(t2.id, "r1");
        check(g.charges.get(t2.id + ":cancel") == null, "no fee before acceptance");

        // rating-weighted: one star costs 2 km, so a 4.0 driver 0.7 km away loses to a 5.0 driver 2.5 km away
        RideService w = service(new RatingWeightedStrategy(2.0), new FakeGateway());
        w.addRider("r");
        Driver meh = w.addDriver("meh", new Location(0.7, 0)); meh.rating.add(4);
        w.addDriver("star", new Location(2.5, 0));
        check(w.requestTrip("r", new Location(0, 0), new Location(1, 0)).driver().id.equals("star"), "rating-weighted");

        twoRidersNeverShareADriver();
        acceptRacingCancel();
        System.out.println("ride-sharing: all checks passed");
    }

    static void twoRidersNeverShareADriver() throws Exception {
        RideService s = service(new NearestDriverStrategy(), new FakeGateway());
        for (int i = 0; i < 5; i++) s.addDriver("d" + i, new Location(i * 0.1, 0));
        for (int i = 0; i < 20; i++) s.addRider("r" + i);
        ExecutorService pool = Executors.newFixedThreadPool(20);
        CountDownLatch go = new CountDownLatch(1);
        List<Future<String>> results = new ArrayList<>();
        for (int i = 0; i < 20; i++) {
            String rider = "r" + i;
            results.add(pool.submit(() -> {
                go.await();
                try { return s.requestTrip(rider, new Location(0, 0), new Location(1, 1)).driver().id; }
                catch (RideException e) { return null; }
            }));
        }
        go.countDown();
        List<String> got = new ArrayList<>();
        for (Future<String> f : results) if (f.get() != null) got.add(f.get());
        pool.shutdown();
        check(got.size() == 5 && new HashSet<>(got).size() == 5, "5 trips, 5 distinct drivers: " + got);
    }

    static void acceptRacingCancel() throws Exception {
        ExecutorService pool = Executors.newFixedThreadPool(2);
        for (int i = 0; i < 300; i++) {
            FakeGateway g = new FakeGateway();
            RideService s = service(new NearestDriverStrategy(), g);
            s.addRider("r"); Driver d = s.addDriver("d", new Location(0, 0));
            Trip t = s.requestTrip("r", new Location(0, 0), new Location(1, 0));
            CyclicBarrier barrier = new CyclicBarrier(2);
            Future<Boolean> accepted = pool.submit(() -> {
                barrier.await();
                try { s.accept(t.id, "d"); return true; } catch (RideException e) { return false; }
            });
            Future<?> cancelled = pool.submit(() -> { barrier.await(); s.cancel(t.id, "r"); return null; });
            cancelled.get();
            boolean acceptWon = accepted.get();
            check(t.status() == TripStatus.CANCELLED, "trip ends cancelled");
            check(d.status() == DriverStatus.AVAILABLE, "driver released, never stuck ON_TRIP");
            check(g.charges.containsKey(t.id + ":cancel") == acceptWon, "fee only if accept won");
        }
        pool.shutdown();
    }
}
from __future__ import annotations

import math
import threading
from dataclasses import dataclass, field
from enum import Enum
from itertools import count
from typing import Callable, Protocol


@dataclass(frozen=True)
class Location:              # planar km, enough for a grid demo
    x: float
    y: float

    def distance_to(self, o: Location) -> float:
        return math.hypot(self.x - o.x, self.y - o.y)


@dataclass(frozen=True)
class TripMetrics:
    km: float
    minutes: float


class DriverStatus(Enum):
    OFFLINE = 1; AVAILABLE = 2; RESERVED = 3; ON_TRIP = 4


class TripStatus(Enum):
    REQUESTED = 1; ACCEPTED = 2; ARRIVED = 3; IN_PROGRESS = 4; COMPLETED = 5; CANCELLED = 6


class PaymentStatus(Enum):
    NONE = 1; PAID = 2; FAILED = 3


class RideError(Exception):
    pass


class Rating:
    def __init__(self) -> None:
        self._lock = threading.Lock()
        self._count = 0
        self._sum = 0

    def add(self, stars: int) -> None:
        if not 1 <= stars <= 5:
            raise RideError("stars must be 1..5")
        with self._lock:
            self._count += 1
            self._sum += stars

    def average(self) -> float:
        with self._lock:
            return 5.0 if self._count == 0 else self._sum / self._count


class Rider:
    def __init__(self, id: str) -> None:
        self.id = id
        self.rating = Rating()


class Driver:
    def __init__(self, id: str, location: Location) -> None:
        self.id = id
        self.location = location
        self.rating = Rating()
        self._status = DriverStatus.OFFLINE
        self._status_lock = threading.Lock()

    @property
    def status(self) -> DriverStatus:
        return self._status

    def transition(self, frm: DriverStatus, to: DriverStatus) -> bool:
        """Compare-and-set: succeeds only if the status is still `frm`."""
        with self._status_lock:
            if self._status is not frm:
                return False
            self._status = to
            return True


@dataclass(eq=False)
class Trip:
    id: str
    rider: Rider
    pickup: Location
    dropoff: Location
    surge: float
    # everything below is guarded by `lock`
    driver: Driver | None = None
    status: TripStatus = TripStatus.REQUESTED
    payment: PaymentStatus = PaymentStatus.NONE
    fare_cents: int = 0
    rider_rated: bool = False
    driver_rated: bool = False
    declined_by: set[str] = field(default_factory=set)
    lock: threading.RLock = field(default_factory=threading.RLock)

    def require(self, *allowed: TripStatus) -> None:
        if self.status not in allowed:
            raise RideError(f"trip {self.id} is {self.status.name}")

    def require_driver(self, d: Driver) -> None:
        if self.driver is not d:
            raise RideError(f"driver {d.id} is not on trip {self.id}")


class GridIndex:
    def __init__(self, cell_km: float) -> None:
        self._cell_km = cell_km
        self._cells: dict[tuple[int, int], set[Driver]] = {}
        self._lock = threading.Lock()   # Python sets are not safe to iterate while mutated

    def _key(self, p: Location) -> tuple[int, int]:
        return (math.floor(p.x / self._cell_km), math.floor(p.y / self._cell_km))

    def add(self, d: Driver) -> None:
        with self._lock:
            self._cells.setdefault(self._key(d.location), set()).add(d)

    def move(self, d: Driver, to: Location) -> None:
        with self._lock:
            old, new = self._key(d.location), self._key(to)
            d.location = to
            if old != new:
                self._cells.setdefault(new, set()).add(d)
                self._cells[old].discard(d)

    def nearby(self, p: Location, radius_km: float) -> list[Driver]:
        r = math.ceil(radius_km / self._cell_km)
        cx, cy = self._key(p)
        with self._lock:
            return [d for x in range(cx - r, cx + r + 1) for y in range(cy - r, cy + r + 1)
                    for d in self._cells.get((x, y), ()) if d.location.distance_to(p) <= radius_km]


class MatchingStrategy(Protocol):
    def rank(self, candidates: list[Driver], pickup: Location) -> list[Driver]: ...


class NearestDriverStrategy:
    def rank(self, candidates: list[Driver], pickup: Location) -> list[Driver]:
        return sorted(candidates, key=lambda d: d.location.distance_to(pickup))


class RatingWeightedStrategy:
    def __init__(self, km_per_missing_star: float) -> None:
        self._k = km_per_missing_star

    def rank(self, candidates: list[Driver], pickup: Location) -> list[Driver]:
        # sorted() computes each key once, so scores are a consistent snapshot
        return sorted(candidates, key=lambda d: d.location.distance_to(pickup)
                      + self._k * (5.0 - d.rating.average()))


class FareCalculator(Protocol):
    def fare_cents(self, m: TripMetrics) -> int: ...


class StandardFare:
    def __init__(self, base: int, per_km: int, per_minute: int) -> None:
        self._base, self._per_km, self._per_minute = base, per_km, per_minute

    def fare_cents(self, m: TripMetrics) -> int:
        return self._base + round(m.km * self._per_km) + round(m.minutes * self._per_minute)


class SurgeFare:
    def __init__(self, inner: FareCalculator, multiplier: float) -> None:
        self._inner, self._multiplier = inner, multiplier

    def fare_cents(self, m: TripMetrics) -> int:
        return round(self._inner.fare_cents(m) * self._multiplier)


class MinimumFare:
    def __init__(self, inner: FareCalculator, min_cents: int) -> None:
        self._inner, self._min = inner, min_cents

    def fare_cents(self, m: TripMetrics) -> int:
        return max(self._min, self._inner.fare_cents(m))


class PaymentGateway(Protocol):
    def charge(self, rider_id: str, cents: int, idempotency_key: str) -> bool: ...


class RideService:
    SEARCH_RADIUS_KM = 3.0
    CANCEL_FEE_CENTS = 300
    MIN_FARE_CENTS = 500

    def __init__(self, matcher: MatchingStrategy, base_fare: FareCalculator,
                 surge: Callable[[Location], float], payments: PaymentGateway) -> None:
        self._matcher, self._base_fare, self._surge, self._payments = matcher, base_fare, surge, payments
        self._riders: dict[str, Rider] = {}
        self._drivers: dict[str, Driver] = {}
        self._trips: dict[str, Trip] = {}
        self._index = GridIndex(1.0)
        self._ids = count(1)

    def add_rider(self, id: str) -> Rider:
        self._riders[id] = Rider(id)
        return self._riders[id]

    def add_driver(self, id: str, at: Location) -> Driver:
        d = Driver(id, at)
        self._drivers[id] = d
        self._index.add(d)
        d.transition(DriverStatus.OFFLINE, DriverStatus.AVAILABLE)
        return d

    def update_location(self, driver_id: str, to: Location) -> None:
        self._index.move(self._get(self._drivers, driver_id), to)

    def request_trip(self, rider_id: str, pickup: Location, dropoff: Location) -> Trip:
        rider = self._get(self._riders, rider_id)
        t = Trip(f"T{next(self._ids)}", rider, pickup, dropoff, self._surge(pickup))
        with t.lock:
            if not self._offer_to_next_driver(t):
                raise RideError("no driver available")
        self._trips[t.id] = t
        return t

    def _offer_to_next_driver(self, t: Trip) -> bool:
        """Caller holds t.lock, so the trip cannot be cancelled while we reserve."""
        free = [d for d in self._index.nearby(t.pickup, self.SEARCH_RADIUS_KM)
                if d.status is DriverStatus.AVAILABLE and d.id not in t.declined_by]
        for d in self._matcher.rank(free, t.pickup):
            if d.transition(DriverStatus.AVAILABLE, DriverStatus.RESERVED):  # atomic claim
                t.driver = d
                return True
        t.driver = None
        return False

    def accept(self, trip_id: str, driver_id: str) -> None:
        t, d = self._get(self._trips, trip_id), self._get(self._drivers, driver_id)
        with t.lock:
            t.require(TripStatus.REQUESTED)
            t.require_driver(d)
            if not d.transition(DriverStatus.RESERVED, DriverStatus.ON_TRIP):
                raise RideError("driver not reserved")
            t.status = TripStatus.ACCEPTED

    def decline(self, trip_id: str, driver_id: str) -> None:
        t, d = self._get(self._trips, trip_id), self._get(self._drivers, driver_id)
        with t.lock:
            t.require(TripStatus.REQUESTED)
            t.require_driver(d)
            d.transition(DriverStatus.RESERVED, DriverStatus.AVAILABLE)
            t.declined_by.add(d.id)
            if not self._offer_to_next_driver(t):
                t.status = TripStatus.CANCELLED

    def arrive(self, trip_id: str, driver_id: str) -> None:
        self._advance(trip_id, driver_id, TripStatus.ACCEPTED, TripStatus.ARRIVED)

    def start(self, trip_id: str, driver_id: str) -> None:
        self._advance(trip_id, driver_id, TripStatus.ARRIVED, TripStatus.IN_PROGRESS)

    def _advance(self, trip_id: str, driver_id: str, frm: TripStatus, to: TripStatus) -> None:
        t = self._get(self._trips, trip_id)
        with t.lock:
            t.require(frm)
            t.require_driver(self._get(self._drivers, driver_id))
            t.status = to

    def complete(self, trip_id: str, driver_id: str, metrics: TripMetrics) -> int:
        t, d = self._get(self._trips, trip_id), self._get(self._drivers, driver_id)
        with t.lock:
            t.require(TripStatus.IN_PROGRESS)
            t.require_driver(d)
            calc = MinimumFare(SurgeFare(self._base_fare, t.surge), self.MIN_FARE_CENTS)
            t.fare_cents = calc.fare_cents(metrics)
            t.status = TripStatus.COMPLETED
            d.transition(DriverStatus.ON_TRIP, DriverStatus.AVAILABLE)
        self._charge(t, t.fare_cents, f"{t.id}:fare")   # network call outside the lock
        return t.fare_cents

    def cancel(self, trip_id: str, rider_id: str) -> None:
        t = self._get(self._trips, trip_id)
        with t.lock:
            if t.rider is not self._get(self._riders, rider_id):
                raise RideError("not your trip")
            t.require(TripStatus.REQUESTED, TripStatus.ACCEPTED, TripStatus.ARRIVED)
            fee = t.status is not TripStatus.REQUESTED
            if t.driver is not None:
                t.driver.transition(DriverStatus.ON_TRIP if fee else DriverStatus.RESERVED,
                                    DriverStatus.AVAILABLE)
            t.status = TripStatus.CANCELLED
        if fee:
            self._charge(t, self.CANCEL_FEE_CENTS, f"{t.id}:cancel")

    def rate_driver(self, trip_id: str, stars: int) -> None:
        t = self._get(self._trips, trip_id)
        with t.lock:
            t.require(TripStatus.COMPLETED)
            if t.driver_rated:
                raise RideError("driver already rated")
            assert t.driver is not None
            t.driver.rating.add(stars)
            t.driver_rated = True

    def rate_rider(self, trip_id: str, stars: int) -> None:
        t = self._get(self._trips, trip_id)
        with t.lock:
            t.require(TripStatus.COMPLETED)
            if t.rider_rated:
                raise RideError("rider already rated")
            t.rider.rating.add(stars)
            t.rider_rated = True

    def _charge(self, t: Trip, cents: int, key: str) -> None:
        ok = self._payments.charge(t.rider.id, cents, key)
        with t.lock:
            t.payment = PaymentStatus.PAID if ok else PaymentStatus.FAILED

    @staticmethod
    def _get(m: dict, id: str):
        if id not in m:
            raise RideError(f"unknown id {id}")
        return m[id]


class FakeGateway:
    def __init__(self) -> None:
        self.charges: dict[str, int] = {}
        self.fail = False
        self._lock = threading.Lock()

    def charge(self, rider_id: str, cents: int, idempotency_key: str) -> bool:
        if self.fail:
            return False
        with self._lock:
            self.charges.setdefault(idempotency_key, cents)   # idempotent by key
        return True


def make_service(matcher: MatchingStrategy, gateway: FakeGateway) -> RideService:
    return RideService(matcher, StandardFare(250, 120, 30), lambda p: 1.5, gateway)


def demo() -> None:
    g = FakeGateway()
    s = make_service(NearestDriverStrategy(), g)
    s.add_rider("r1")
    s.add_driver("near", Location(0.5, 0.5))
    s.add_driver("far", Location(2.0, 1.5))

    t = s.request_trip("r1", Location(0, 0), Location(5, 0))
    assert t.driver is not None and t.driver.id == "near"
    s.accept(t.id, "near"); s.arrive(t.id, "near"); s.start(t.id, "near")
    assert s.complete(t.id, "near", TripMetrics(5, 12)) == 1815   # (250 + 600 + 360) * 1.5
    assert t.payment is PaymentStatus.PAID and g.charges[f"{t.id}:fare"] == 1815
    s.rate_driver(t.id, 4); s.rate_rider(t.id, 5)
    try:
        s.rate_driver(t.id, 5)
        raise AssertionError("double rating allowed")
    except RideError:
        pass

    t2 = s.request_trip("r1", Location(0, 0), Location(1, 1))
    s.decline(t2.id, "near")
    assert t2.driver is not None and t2.driver.id == "far" and t2.status is TripStatus.REQUESTED
    s.cancel(t2.id, "r1")
    assert f"{t2.id}:cancel" not in g.charges

    w = make_service(RatingWeightedStrategy(2.0), FakeGateway())
    w.add_rider("r")
    w.add_driver("meh", Location(0.7, 0)).rating.add(4)
    w.add_driver("star", Location(2.5, 0))
    trip = w.request_trip("r", Location(0, 0), Location(1, 0))
    assert trip.driver is not None and trip.driver.id == "star"
    print("ride-sharing: demo checks passed")


if __name__ == "__main__":
    demo()
// ride-sharing.ts — run with: npx tsx ride-sharing.ts
class Location {
  constructor(readonly x: number, readonly y: number) {} // planar km
  distanceTo(o: Location): number { return Math.hypot(this.x - o.x, this.y - o.y); }
}

interface TripMetrics { km: number; minutes: number }

enum DriverStatus { OFFLINE = "OFFLINE", AVAILABLE = "AVAILABLE", RESERVED = "RESERVED", ON_TRIP = "ON_TRIP" }
enum TripStatus {
  REQUESTED = "REQUESTED", ACCEPTED = "ACCEPTED", ARRIVED = "ARRIVED",
  IN_PROGRESS = "IN_PROGRESS", COMPLETED = "COMPLETED", CANCELLED = "CANCELLED",
}
enum PaymentStatus { NONE = "NONE", PAID = "PAID", FAILED = "FAILED" }

class RideError extends Error {}

class Rating {
  private count = 0;
  private sum = 0;
  add(stars: number): void {
    if (!Number.isInteger(stars) || stars < 1 || stars > 5) throw new RideError("stars must be 1..5");
    this.count++; this.sum += stars;
  }
  average(): number { return this.count === 0 ? 5 : this.sum / this.count; }
}

class Rider {
  readonly rating = new Rating();
  constructor(readonly id: string) {}
}

class Driver {
  readonly rating = new Rating();
  private _status = DriverStatus.OFFLINE;
  constructor(readonly id: string, public location: Location) {}
  get status(): DriverStatus { return this._status; }
  /** Compare-and-set. Synchronous, so no other task can run between the check and the write. */
  transition(from: DriverStatus, to: DriverStatus): boolean {
    if (this._status !== from) return false;
    this._status = to;
    return true;
  }
}

class Trip {
  driver: Driver | null = null;
  status = TripStatus.REQUESTED;
  payment = PaymentStatus.NONE;
  fareCents = 0;
  riderRated = false;
  driverRated = false;
  readonly declinedBy = new Set<string>();
  constructor(readonly id: string, readonly rider: Rider, readonly pickup: Location,
              readonly dropoff: Location, readonly surge: number) {}
  require(...allowed: TripStatus[]): void {
    if (!allowed.includes(this.status)) throw new RideError(`trip ${this.id} is ${this.status}`);
  }
  requireDriver(d: Driver): void {
    if (this.driver !== d) throw new RideError(`driver ${d.id} is not on trip ${this.id}`);
  }
}

class GridIndex {
  private readonly cells = new Map<string, Set<Driver>>();
  constructor(private readonly cellKm: number) {}
  private cell(v: number): number { return Math.floor(v / this.cellKm); }
  private key(cx: number, cy: number): string { return `${cx}:${cy}`; }
  private keyOf(p: Location): string { return this.key(this.cell(p.x), this.cell(p.y)); }
  private bucket(k: string): Set<Driver> {
    let s = this.cells.get(k);
    if (!s) { s = new Set(); this.cells.set(k, s); }
    return s;
  }
  add(d: Driver): void { this.bucket(this.keyOf(d.location)).add(d); }
  move(d: Driver, to: Location): void {
    const from = this.keyOf(d.location), next = this.keyOf(to);
    d.location = to;
    if (from !== next) { this.bucket(next).add(d); this.bucket(from).delete(d); }
  }
  nearby(p: Location, radiusKm: number): Driver[] {
    const r = Math.ceil(radiusKm / this.cellKm), cx = this.cell(p.x), cy = this.cell(p.y);
    const out: Driver[] = [];
    for (let x = cx - r; x <= cx + r; x++)
      for (let y = cy - r; y <= cy + r; y++)
        for (const d of this.cells.get(this.key(x, y)) ?? [])
          if (d.location.distanceTo(p) <= radiusKm) out.push(d);
    return out;
  }
}

interface MatchingStrategy { rank(candidates: Driver[], pickup: Location): Driver[] }

function rankBy(candidates: Driver[], score: (d: Driver) => number): Driver[] {
  const scored = candidates.map((d) => ({ d, s: score(d) })); // snapshot, then sort
  return scored.sort((a, b) => a.s - b.s).map((e) => e.d);
}

class NearestDriverStrategy implements MatchingStrategy {
  rank(c: Driver[], p: Location): Driver[] { return rankBy(c, (d) => d.location.distanceTo(p)); }
}

class RatingWeightedStrategy implements MatchingStrategy {
  constructor(private readonly kmPerMissingStar: number) {}
  rank(c: Driver[], p: Location): Driver[] {
    return rankBy(c, (d) => d.location.distanceTo(p) + this.kmPerMissingStar * (5 - d.rating.average()));
  }
}

interface FareCalculator { fareCents(m: TripMetrics): number }

class StandardFare implements FareCalculator {
  constructor(private base: number, private perKm: number, private perMinute: number) {}
  fareCents(m: TripMetrics): number {
    return this.base + Math.round(m.km * this.perKm) + Math.round(m.minutes * this.perMinute);
  }
}

class SurgeFare implements FareCalculator {
  constructor(private inner: FareCalculator, private multiplier: number) {}
  fareCents(m: TripMetrics): number { return Math.round(this.inner.fareCents(m) * this.multiplier); }
}

class MinimumFare implements FareCalculator {
  constructor(private inner: FareCalculator, private minCents: number) {}
  fareCents(m: TripMetrics): number { return Math.max(this.minCents, this.inner.fareCents(m)); }
}

type SurgeProvider = (p: Location) => Promise<number>; // a remote pricing call
interface PaymentGateway { charge(riderId: string, cents: number, idempotencyKey: string): Promise<boolean> }

class RideService {
  static readonly SEARCH_RADIUS_KM = 3;
  static readonly CANCEL_FEE_CENTS = 300;
  static readonly MIN_FARE_CENTS = 500;
  private readonly riders = new Map<string, Rider>();
  private readonly drivers = new Map<string, Driver>();
  private readonly trips = new Map<string, Trip>();
  private readonly index = new GridIndex(1);
  private nextId = 1;

  constructor(private matcher: MatchingStrategy, private baseFare: FareCalculator,
              private surge: SurgeProvider, private payments: PaymentGateway) {}

  addRider(id: string): Rider { const r = new Rider(id); this.riders.set(id, r); return r; }

  addDriver(id: string, at: Location): Driver {
    const d = new Driver(id, at);
    this.drivers.set(id, d); this.index.add(d); d.transition(DriverStatus.OFFLINE, DriverStatus.AVAILABLE);
    return d;
  }

  updateLocation(driverId: string, to: Location): void { this.index.move(get(this.drivers, driverId), to); }

  async requestTrip(riderId: string, pickup: Location, dropoff: Location): Promise<Trip> {
    const rider = get(this.riders, riderId);
    const surge = await this.surge(pickup); // other requests run during this await
    const t = new Trip(`T${this.nextId++}`, rider, pickup, dropoff, surge);
    if (!this.offerToNextDriver(t)) throw new RideError("no driver available");
    this.trips.set(t.id, t);
    return t;
  }

  // synchronous from candidate search to claim: nothing can interleave
  private offerToNextDriver(t: Trip): boolean {
    const free = this.index.nearby(t.pickup, RideService.SEARCH_RADIUS_KM)
      .filter((d) => d.status === DriverStatus.AVAILABLE && !t.declinedBy.has(d.id));
    for (const d of this.matcher.rank(free, t.pickup)) {
      if (d.transition(DriverStatus.AVAILABLE, DriverStatus.RESERVED)) { t.driver = d; return true; }
    }
    t.driver = null;
    return false;
  }

  accept(tripId: string, driverId: string): void {
    const t = get(this.trips, tripId), d = get(this.drivers, driverId);
    t.require(TripStatus.REQUESTED); t.requireDriver(d);
    if (!d.transition(DriverStatus.RESERVED, DriverStatus.ON_TRIP)) throw new RideError("driver not reserved");
    t.status = TripStatus.ACCEPTED;
  }

  decline(tripId: string, driverId: string): void {
    const t = get(this.trips, tripId), d = get(this.drivers, driverId);
    t.require(TripStatus.REQUESTED); t.requireDriver(d);
    d.transition(DriverStatus.RESERVED, DriverStatus.AVAILABLE);
    t.declinedBy.add(d.id);
    if (!this.offerToNextDriver(t)) t.status = TripStatus.CANCELLED;
  }

  arrive(tripId: string, driverId: string): void { this.advance(tripId, driverId, TripStatus.ACCEPTED, TripStatus.ARRIVED); }
  start(tripId: string, driverId: string): void { this.advance(tripId, driverId, TripStatus.ARRIVED, TripStatus.IN_PROGRESS); }

  private advance(tripId: string, driverId: string, from: TripStatus, to: TripStatus): void {
    const t = get(this.trips, tripId);
    t.require(from); t.requireDriver(get(this.drivers, driverId));
    t.status = to;
  }

  async complete(tripId: string, driverId: string, metrics: TripMetrics): Promise<number> {
    const t = get(this.trips, tripId), d = get(this.drivers, driverId);
    t.require(TripStatus.IN_PROGRESS); t.requireDriver(d);
    const calc = new MinimumFare(new SurgeFare(this.baseFare, t.surge), RideService.MIN_FARE_CENTS);
    t.fareCents = calc.fareCents(metrics);
    t.status = TripStatus.COMPLETED; // state is final before the first await
    d.transition(DriverStatus.ON_TRIP, DriverStatus.AVAILABLE);
    await this.charge(t, t.fareCents, `${t.id}:fare`);
    return t.fareCents;
  }

  async cancel(tripId: string, riderId: string): Promise<void> {
    const t = get(this.trips, tripId);
    if (t.rider !== get(this.riders, riderId)) throw new RideError("not your trip");
    t.require(TripStatus.REQUESTED, TripStatus.ACCEPTED, TripStatus.ARRIVED);
    const fee = t.status !== TripStatus.REQUESTED;
    t.driver?.transition(fee ? DriverStatus.ON_TRIP : DriverStatus.RESERVED, DriverStatus.AVAILABLE);
    t.status = TripStatus.CANCELLED;
    if (fee) await this.charge(t, RideService.CANCEL_FEE_CENTS, `${t.id}:cancel`);
  }

  rateDriver(tripId: string, stars: number): void {
    const t = get(this.trips, tripId);
    t.require(TripStatus.COMPLETED);
    if (t.driverRated) throw new RideError("driver already rated");
    t.driver!.rating.add(stars); t.driverRated = true;
  }

  rateRider(tripId: string, stars: number): void {
    const t = get(this.trips, tripId);
    t.require(TripStatus.COMPLETED);
    if (t.riderRated) throw new RideError("rider already rated");
    t.rider.rating.add(stars); t.riderRated = true;
  }

  private async charge(t: Trip, cents: number, key: string): Promise<void> {
    const ok = await this.payments.charge(t.rider.id, cents, key);
    t.payment = ok ? PaymentStatus.PAID : PaymentStatus.FAILED;
  }
}

function get<T>(m: Map<string, T>, id: string): T {
  const v = m.get(id);
  if (v === undefined) throw new RideError(`unknown id ${id}`);
  return v;
}

class FakeGateway implements PaymentGateway {
  readonly charges = new Map<string, number>();
  fail = false;
  async charge(_riderId: string, cents: number, key: string): Promise<boolean> {
    if (this.fail) return false;
    if (!this.charges.has(key)) this.charges.set(key, cents); // idempotent by key
    return true;
  }
}

function assert(cond: unknown, msg: string): asserts cond { if (!cond) throw new Error("FAILED: " + msg); }

const tick = () => new Promise<void>((r) => setTimeout(r, 0));
function makeService(m: MatchingStrategy, g: FakeGateway): RideService {
  return new RideService(m, new StandardFare(250, 120, 30), async () => { await tick(); return 1.5; }, g);
}

async function main(): Promise<void> {
  const g = new FakeGateway();
  const s = makeService(new NearestDriverStrategy(), g);
  s.addRider("r1");
  s.addDriver("near", new Location(0.5, 0.5));
  s.addDriver("far", new Location(2, 1.5));

  const t = await s.requestTrip("r1", new Location(0, 0), new Location(5, 0));
  assert(t.driver?.id === "near", "nearest driver offered");
  s.accept(t.id, "near"); s.arrive(t.id, "near"); s.start(t.id, "near");
  assert((await s.complete(t.id, "near", { km: 5, minutes: 12 })) === 1815, "surge fare");
  assert(t.payment === PaymentStatus.PAID && g.charges.get(`${t.id}:fare`) === 1815, "charged");
  s.rateDriver(t.id, 4); s.rateRider(t.id, 5);
  let threw = false;
  try { s.rateDriver(t.id, 5); } catch { threw = true; }
  assert(threw, "double rating rejected");

  const t2 = await s.requestTrip("r1", new Location(0, 0), new Location(1, 1));
  s.decline(t2.id, "near");
  assert(t2.driver?.id === "far" && t2.status === TripStatus.REQUESTED, "re-offered");
  await s.cancel(t2.id, "r1");
  assert(!g.charges.has(`${t2.id}:cancel`), "no fee before acceptance");

  const w = makeService(new RatingWeightedStrategy(2), new FakeGateway());
  w.addRider("r");
  w.addDriver("meh", new Location(0.7, 0)).rating.add(4);
  w.addDriver("star", new Location(2.5, 0));
  assert((await w.requestTrip("r", new Location(0, 0), new Location(1, 0))).driver?.id === "star", "weighted");

  // 20 concurrent requests for 5 drivers: every request awaits the surge call, then claims
  const c = makeService(new NearestDriverStrategy(), new FakeGateway());
  for (let i = 0; i < 5; i++) c.addDriver(`d${i}`, new Location(i * 0.1, 0));
  for (let i = 0; i < 20; i++) c.addRider(`r${i}`);
  const results = await Promise.allSettled(
    Array.from({ length: 20 }, (_, i) => c.requestTrip(`r${i}`, new Location(0, 0), new Location(1, 1))));
  const ids = results.flatMap((r) => (r.status === "fulfilled" ? [r.value.driver!.id] : []));
  assert(ids.length === 5 && new Set(ids).size === 5, "5 trips, 5 distinct drivers");
  console.log("ride-sharing: all checks passed");
}

main();
export {}; // makes this file a module, so names do not clash with DOM globals

Run them with javac -d out Main.java && java -ea -cp out Main, python ride_sharing.py, and npx tsx ride-sharing.ts (the TypeScript also passes tsc --strict).

7. Concurrency

What's shared

StateWritten byProtection
Driver.statusrequest (claim), accept, decline, cancel, completeAtomicReference CAS in Java, a small lock in Python, synchronous code in TS
Driver.locationlocation updates (very frequent)volatile, plus a per-driver lock for the index move
GridIndex cellslocation updates, nearby readsConcurrentHashMap of concurrent sets in Java, one lock in Python
Trip fieldsaccept, decline, arrive, start, complete, cancel, rate, payment resultthe trip's own monitor (per-trip lock)
Ratingrate methodsits own monitor
registriesadd, requestConcurrentHashMap

Race 1: two riders, one driver

Two riders request at the same moment and the nearest driver is the same for both. Both read AVAILABLE during the search. Without the CAS, both would write RESERVED, both trips would point at the driver, and one rider would wait forever for a car that's driving someone else.

With compareAndSet(AVAILABLE, RESERVED), exactly one call succeeds. The loser's loop continues to its second-ranked driver. There's no lock on the driver, so matching for different areas never contends. The Java twoRidersNeverShareADriver check runs 20 riders against 5 drivers from a common start latch and asserts exactly 5 trips with 5 distinct drivers. The Python test repeats that 50 times with a tiny thread switch interval.

A global lock around requestTrip is also correct and an acceptable first answer, if you say the cost: every request in the city serialises, nearby search included. Per-driver CAS shrinks the critical section to one word.

Race 2: driver accepts while the rider cancels

This is the race interviewers actually probe. Without a per-trip lock, the interleaving below leaves a "zombie" trip:

  1. Accept reads status == REQUESTED. OK.
  2. Cancel reads status == REQUESTED, releases the driver (RESERVED → AVAILABLE) and writes CANCELLED.
  3. Accept writes ACCEPTED and tries RESERVED → ON_TRIP.

Depending on the exact interleaving you get a trip marked ACCEPTED after the rider cancelled, or a driver marked ON_TRIP for a cancelled trip and invisible to matching forever. Both are real money: a stranded rider or an idle driver.

The fix is to make each transition a single critical section on the trip: check the status, update the trip, update the driver, all under synchronized (t). Then there are only two serial orders, and both are valid:

  • Accept first: the trip becomes ACCEPTED, then cancel finds ACCEPTED, charges the fee and releases the driver from ON_TRIP.
  • Cancel first: the trip becomes CANCELLED, and accept finds CANCELLED and throws.

The test asserts the invariant that holds in both orders. The trip ends CANCELLED, the driver ends AVAILABLE, and a fee exists if and only if accept won. It repeats 300 times with a barrier so the two threads really do collide.

Lock ordering and deadlock

The only nested acquisition is trip lock, then driver CAS. A CAS never blocks, so there's no cycle and no deadlock. If you later add a lock that's taken before a trip lock (a per-rider lock to stop a rider from holding two active trips, for example), always take rider before trip, everywhere.

The sorting bug nobody sees in review

Locations change while you sort. A comparator that reads d.location() on every comparison can see a driver at 1.2 km in one comparison and 0.8 km in the next. Java's TimSort can then throw IllegalArgumentException: Comparison method violates its general contract. That doesn't happen in a demo, but it will happen on a busy Friday night. ScoredMatching.rank computes every score once into a map and sorts by that snapshot. Python's sorted(key=...) and the TS rankBy helper do the same by construction.

TypeScript is different

Node runs your code on one thread, so transition needs no lock: nothing can run between its check and its write. The danger is await. requestTrip awaits the surge provider, and during that await other requests run. The design stays correct because everything from the candidate search to the claim is synchronous and comes after the await. The TS main fires 20 concurrent requestTrip calls against 5 drivers and gets 5 distinct assignments. Even if an await crept in between rank and transition, the CAS would still re-check the status at the moment of the claim.

For the general toolkit, see thread-safe class design and booking and inventory concurrency. The driver claim is the same problem as reserving the last seat in movie booking.

8. The interviewer adds...

"Add promo codes: 20% off, capped at $3"

This is one new decorator. Nothing in Trip's lifecycle changes. The only edit is one line in the wiring inside complete.

final class PromoDiscount implements FareCalculator {
    private final FareCalculator inner; private final int percentOff; private final long capCents;
    PromoDiscount(FareCalculator inner, int percentOff, long capCents) {
        this.inner = inner; this.percentOff = percentOff; this.capCents = capCents;
    }
    public long fareCents(TripMetrics m) {
        long full = inner.fareCents(m);
        return full - Math.min(capCents, full * percentOff / 100);
    }
}
// in RideService.complete, wrap the chain when the trip carries a promo:
// FareCalculator calc = new MinimumFare(new SurgeFare(baseFare, t.surge), MIN_FARE_CENTS);
// if (t.promo != null) calc = new PromoDiscount(calc, t.promo.percentOff(), t.promo.capCents());

Tested: on the 1815-cent fare, 20% is 363, so the cap applies and the rider pays 1515. Because the promo sits outside MinimumFare, it can take a fare below the minimum. If the business disagrees, swap two wrappers.

"Riders can choose GO or XL"

Matching gets a filter that wraps any existing strategy. This is Decorator applied to a Strategy, and neither built-in strategy changes:

from typing import Callable


class CategoryFilter:
    """Wraps any MatchingStrategy and drops drivers whose vehicle is the wrong category."""

    def __init__(self, inner: MatchingStrategy, category_of: Callable[[Driver], str], wanted: str) -> None:
        self._inner, self._category_of, self._wanted = inner, category_of, wanted

    def rank(self, candidates: list[Driver], pickup: Location) -> list[Driver]:
        return self._inner.rank([d for d in candidates if self._category_of(d) == self._wanted], pickup)


# RideService keeps one matcher per category, chosen by the rider's request:
# self._matchers = {c: CategoryFilter(NearestDriverStrategy(), vehicles.category_of, c) for c in ("GO", "XL")}

Tested: with a small car 0.1 km away and a van 2 km away, an XL request gets the van. The fare side is symmetrical: each category gets its own StandardFare rate card.

"If a driver ignores an offer for 15 seconds, move on"

The core already has a safe "move on" path: decline. A timeout is a decline that nobody pressed. So the extension is a small collaborator that remembers when each offer was made and calls decline when it expires. Time is passed in as an argument, so tests don't sleep (see designing for testability).

/** Re-offers a trip when the driver ignores it. Time comes in as an argument, so tests control it. */
class OfferExpiry {
  private readonly offeredAt = new Map<Trip, { driver: Driver; at: number }>();
  constructor(private readonly service: RideService, private readonly timeoutMs: number) {}

  track(t: Trip, nowMs: number): void {
    if (t.driver) this.offeredAt.set(t, { driver: t.driver, at: nowMs });
  }

  sweep(nowMs: number): void {
    for (const [t, offer] of [...this.offeredAt]) {
      if (t.status !== TripStatus.REQUESTED || t.driver !== offer.driver) { this.offeredAt.delete(t); continue; }
      if (nowMs - offer.at < this.timeoutMs) continue;
      this.service.decline(t.id, offer.driver.id); // same path as an explicit "no"
      this.offeredAt.delete(t);
      this.track(t, nowMs);                       // the next driver gets a fresh window
    }
  }
}

Tested: at 10 s the offer stays with driver a, at 15 s it moves to b, and at 31 s, with nobody left, the trip is CANCELLED. In Java or Python, run sweep from a scheduled executor. A late accept is safe, because decline re-checks REQUESTED and the current driver under the trip lock.

9. Tests

The test suite targets the rules most likely to break: illegal transitions, the minimum fare with a failing gateway, the grid index after moves, and both races. It needs no framework (run python test_ride_sharing.py), and it's also valid pytest.

import sys
import threading
from concurrent.futures import ThreadPoolExecutor

from ride_sharing import (DriverStatus, FakeGateway, Location, NearestDriverStrategy,
                          RideError, TripMetrics, TripStatus, make_service)

sys.setswitchinterval(1e-6)   # switch threads as often as possible to shake out races


def test_illegal_transitions_are_rejected():
    s = make_service(NearestDriverStrategy(), FakeGateway())
    s.add_rider("r"); s.add_driver("d", Location(0, 0))
    t = s.request_trip("r", Location(0, 0), Location(1, 0))
    for bad in (lambda: s.start(t.id, "d"), lambda: s.complete(t.id, "d", TripMetrics(1, 1)),
                lambda: s.rate_driver(t.id, 5)):
        try:
            bad()
            raise AssertionError("illegal transition allowed")
        except RideError:
            pass
    assert t.status is TripStatus.REQUESTED


def test_minimum_fare_and_failed_payment():
    g = FakeGateway()
    s = make_service(NearestDriverStrategy(), g)
    s.add_rider("r"); s.add_driver("d", Location(0, 0))
    t = s.request_trip("r", Location(0, 0), Location(0.1, 0))
    s.accept(t.id, "d"); s.arrive(t.id, "d"); s.start(t.id, "d")
    g.fail = True
    assert s.complete(t.id, "d", TripMetrics(0.1, 1)) == 500     # 438 after surge, floored to 500
    assert t.status is TripStatus.COMPLETED and t.payment.name == "FAILED"


def test_grid_index_follows_moves():
    s = make_service(NearestDriverStrategy(), FakeGateway())
    s.add_rider("r"); s.add_driver("d", Location(50, 50))
    try:
        s.request_trip("r", Location(0, 0), Location(1, 0))
        raise AssertionError("driver 70 km away matched")
    except RideError:
        pass
    s.update_location("d", Location(1.2, 0.4))
    assert s.request_trip("r", Location(0, 0), Location(1, 0)).driver.id == "d"


def test_two_riders_never_share_a_driver():
    for _ in range(50):
        s = make_service(NearestDriverStrategy(), FakeGateway())
        for i in range(5):
            s.add_driver(f"d{i}", Location(i * 0.1, 0))
        for i in range(20):
            s.add_rider(f"r{i}")
        barrier = threading.Barrier(20)

        def ride(i: int):
            barrier.wait()
            try:
                return s.request_trip(f"r{i}", Location(0, 0), Location(1, 1)).driver.id
            except RideError:
                return None

        with ThreadPoolExecutor(20) as pool:
            got = [d for d in pool.map(ride, range(20)) if d]
        assert len(got) == 5 and len(set(got)) == 5, got


def test_accept_racing_cancel():
    for _ in range(300):
        g = FakeGateway()
        s = make_service(NearestDriverStrategy(), g)
        s.add_rider("r"); d = s.add_driver("d", Location(0, 0))
        t = s.request_trip("r", Location(0, 0), Location(1, 0))
        barrier = threading.Barrier(2)
        won = []

        def accept():
            barrier.wait()
            try:
                s.accept(t.id, "d"); won.append(True)
            except RideError:
                pass

        def cancel():
            barrier.wait()
            s.cancel(t.id, "r")

        threads = [threading.Thread(target=accept), threading.Thread(target=cancel)]
        for th in threads: th.start()
        for th in threads: th.join()
        assert t.status is TripStatus.CANCELLED
        assert d.status is DriverStatus.AVAILABLE
        assert (f"{t.id}:cancel" in g.charges) == bool(won)


if __name__ == "__main__":
    for name, fn in list(globals().items()):
        if name.startswith("test_"):
            fn()
            print("ok", name)
  • Illegal transitions are the business logic, so each gets a test.
  • Payment failure doesn't undo the trip. It's easy to leave a trip IN_PROGRESS forever on an exception.
  • Assert invariants, not schedules. Don't assert "accept wins". Assert what holds whichever thread wins, hundreds of times behind a barrier.
  • Fakes over mocks. FakeGateway has real idempotency, so tests check outcomes (one charge per key), not call counts.

10. Common mistakes

  1. Assigning a driver with check-then-set. if (d.status == AVAILABLE) d.status = RESERVED across two statements is the bug this whole problem is built around.
  2. Status only on the driver. You lose trip history, and cancellation can't tell what it interrupted.
  3. Reading surge at completion. The rider pays a price they never saw.
  4. Doubles for money. Use integer cents, and round once per decorator step.
  5. Holding a lock across the payment call. It's correct, but it freezes every reader of the trip for the length of a network timeout.
  6. Scanning all drivers. At 50,000 online drivers, a linear scan per request is the first thing to fall over. A grid with cells about the size of the search radius checks 9 to 25 cells.
  7. The full State pattern by reflex. Six classes that each say "not allowed" for most events is ceremony, not design. Justify it or skip it.
  8. Forgetting declined drivers. Without declinedBy, a driver who just declined is often still the nearest and gets the same offer again.

11. Interview follow-ups

How would you choose the grid cell size? Make it about the typical search radius. Smaller cells mean more cells to visit per query. Larger cells mean more drivers to distance-check in each one. With cell = radius, a query touches 9 cells (more if it rounds up). Production systems use geohash or S2 cells at several resolutions and widen the radius in steps when the first ring comes back empty.

Why rank by distance and not ETA? Straight-line distance ignores rivers and one-way streets. ETA is better, and it fits as a third MatchingStrategy that calls a routing service. Because that call is slow, you'd rank the top 10 by distance first, then re-rank those by ETA, all before the claim step.

What if the matching process crashes after reserving a driver but before telling anyone? In one process, a crash loses everything anyway. In a distributed version, the reservation needs a lease: RESERVED with an expiry, cleared by a sweeper, which is the offer-timeout extension again. That's the bridge to the system design version.

How does a rider avoid booking two trips at once? Add an activeTrip reference on Rider, claimed with CAS from null the same way drivers are claimed. Claim the rider first, then the driver, and release the rider if no driver is found.

How would batch matching work? Instead of matching each request greedily, collect requests for 2 seconds and solve an assignment problem (minimise total pickup distance). Greedy can give rider A the driver that was the only option for rider B. The batch matcher is a different collaborator that produces (trip, driver) pairs and then uses the same transition claim, so correctness is unchanged.

What would you persist first if this became a real service? The trip with a version column. Every transition becomes UPDATE trips SET status=?, version=version+1 WHERE id=? AND version=?. That's the database form of the per-trip lock, and the driver claim becomes UPDATE drivers SET status='RESERVED' WHERE id=? AND status='AVAILABLE', checking that one row changed.