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
| Question | Answer we assume | Why it matters |
|---|---|---|
| One vehicle category or several? | One to start. Categories come later as an extension | Decides whether matching needs a filter |
| Does the driver get to accept or decline? | Yes. The trip is offered to one driver at a time | Adds 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 after | Cancel has to know which state it interrupted |
| How is the fare computed? | Base + per km + per minute, times surge, floored at a minimum | Pricing must be composable |
| When is surge fixed? | When the trip is requested | The rider agreed to that multiplier, so the trip stores it |
| How is payment taken? | Charged automatically on completion through a gateway | Payment is an external call that can fail |
| Who rates whom? | Each side rates the other once per completed trip | Ratings feed back into matching |
| Pooling, scheduled rides, driver payouts? | Out of scope | Each one is a separate design |
Functional requirements
- Riders and drivers register. Drivers go online and stream their location.
- A rider requests a trip from a pickup to a dropoff.
- The system finds nearby available drivers, ranks them with a pluggable strategy and offers the trip to the best one.
- The driver accepts or declines. A decline moves the offer to the next-best driver. If nobody is left, the trip is cancelled.
- The trip moves through
REQUESTED → ACCEPTED → ARRIVED → IN_PROGRESS → COMPLETED.CANCELLEDis allowed from the first three states. - On completion, the fare is computed and the rider is charged. A cancellation after acceptance charges a fee.
- 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
| Entity | Kind | Owns |
|---|---|---|
Location | Value object | x/y in km, distance |
Rider | Entity | id, Rating |
Driver | Entity | id, current Location, atomic DriverStatus, Rating |
Trip | Entity, the aggregate root for one ride | rider, assigned driver, pickup, dropoff, locked-in surge, TripStatus, fare, payment status, who declined, rating flags |
Rating | Value holder | count and sum. The average is derived |
GridIndex | Domain service | cell to drivers buckets, nearby queries |
MatchingStrategy | Strategy interface | ranks candidates |
FareCalculator | Strategy interface, decorated | turns TripMetrics into cents |
PaymentGateway | Port | charges a rider idempotently |
RideService | Facade / application service | orchestrates every use case and owns the registries |
Three of these choices deserve a sentence aloud in the interview:
Tripowns the lifecycle, notDriver. 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
| Pattern | Where | Requirement it serves | Alternative rejected |
|---|---|---|---|
| Strategy | MatchingStrategy: nearest, rating-weighted | Matching policy changes by market and experiment | if (mode == ...) in requestTrip, which grows with every experiment and can't be unit-tested on its own |
| Decorator | SurgeFare, MinimumFare around StandardFare | Fare components stack, and order matters | One calculateFare method with flags for surge, minimum and promo, which gives 2^n code paths in one function |
| Strategy (again) | FareCalculator itself | Different cities or categories have different rate cards | Constants inside Trip |
| State machine (enum + guards) | TripStatus with require(...) | Lifecycle rules | Full State pattern classes, see below |
| Facade | RideService | One entry point per use case, so invariants live in one place | Letting callers mutate Trip and Driver directly |
| Port / dependency injection | PaymentGateway, surge provider | Testability, swapping providers | Calling 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
| State | Written by | Protection |
|---|---|---|
Driver.status | request (claim), accept, decline, cancel, complete | AtomicReference CAS in Java, a small lock in Python, synchronous code in TS |
Driver.location | location updates (very frequent) | volatile, plus a per-driver lock for the index move |
GridIndex cells | location updates, nearby reads | ConcurrentHashMap of concurrent sets in Java, one lock in Python |
Trip fields | accept, decline, arrive, start, complete, cancel, rate, payment result | the trip's own monitor (per-trip lock) |
Rating | rate methods | its own monitor |
| registries | add, request | ConcurrentHashMap |
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:
- Accept reads
status == REQUESTED. OK. - Cancel reads
status == REQUESTED, releases the driver (RESERVED → AVAILABLE) and writesCANCELLED. - Accept writes
ACCEPTEDand triesRESERVED → 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 findsACCEPTED, charges the fee and releases the driver fromON_TRIP. - Cancel first: the trip becomes
CANCELLED, and accept findsCANCELLEDand 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_PROGRESSforever 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.
FakeGatewayhas real idempotency, so tests check outcomes (one charge per key), not call counts.
10. Common mistakes
- Assigning a driver with check-then-set.
if (d.status == AVAILABLE) d.status = RESERVEDacross two statements is the bug this whole problem is built around. - Status only on the driver. You lose trip history, and cancellation can't tell what it interrupted.
- Reading surge at completion. The rider pays a price they never saw.
- Doubles for money. Use integer cents, and round once per decorator step.
- 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.
- 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.
- 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.
- 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.