Cab Booking (LLD)

Problem statement (interviewer prompt)

Design the class model for a cab booking service (Uber, Ola style). Model riders, drivers, vehicles, and a trip lifecycle. Plug in a driver-matching strategy and a pricing strategy (including surge). Discuss concurrency hot spots.

The core abstraction is a Trip that moves through a small state machine (Requested, Matched, Started, Completed, Cancelled). Around it, a MatchingStrategy picks a driver and a PricingStrategy computes the fare; both are pluggable.

classDiagram
  class User { +id, name, paymentMethod }
  class Driver {
    +id, name, rating
    +vehicle : Vehicle
    +status : DriverStatus
    +location : LatLng
  }
  class Vehicle { +plate, model, category }
  class Trip {
    +id, rider : User, driver : Driver
    +pickup, dropoff : LatLng
    +state : TripState
    +fare : Money
    +request(), match(d), start(), complete(), cancel()
  }
  class TripState {
    <<enumeration>>
    REQUESTED
    MATCHED
    STARTED
    COMPLETED
    CANCELLED
  }
  class DriverStatus {
    <<enumeration>>
    OFFLINE
    AVAILABLE
    EN_ROUTE
    ON_TRIP
  }
  class MatchingStrategy { <<interface>> +pick(trip, drivers) Driver }
  class PricingStrategy { <<interface>> +quote(trip) Money }
  Driver *-- Vehicle
  Trip --> User
  Trip --> Driver
  Trip --> TripState
  Driver --> DriverStatus
  Trip ..> MatchingStrategy
  Trip ..> PricingStrategy

The trip object is the aggregate root: every transition is an explicit method that validates the source state, mutates atomically, and emits an event (TripMatched, TripStarted). Driver state changes happen via compare-and-set so two riders cannot grab the same driver at the same instant.

A canonical LLD interview prompt: small domain, rich state machine, hot concurrency on driver allocation, and obvious pluggability for matching and pricing.

Problem statement (interviewer prompt)

Design the class model for an Uber-style cab booking service. Model users, drivers, vehicles, and trips. Cover the trip lifecycle, driver matching (nearest vs weighted), pricing (flat vs surge), driver location events, and the concurrency issues around assigning the same driver to two riders.

Requirements

Functional

• Rider requests a trip (pickup, dropoff, vehicle category).
• System matches an available driver nearby.
• Trip transitions: Requested, Matched, Started, Completed, or Cancelled at any pre-Completed state.
• Fare is quoted up-front and finalised at completion (with surge if applicable).
• Drivers send location heartbeats; their state must reflect availability.

Non-functional

• Driver allocation must be exclusive: a driver cannot be matched to two trips at once.
• Pricing and matching must be swappable without touching the trip aggregate.
• Trip lifecycle changes must be auditable.

Class design

classDiagram
  direction TB

  class User {
    +id : String
    +name : String
    +paymentMethod : PaymentMethod
  }

  class Vehicle {
    +plate : String
    +model : String
    +category : VehicleCategory
  }

  class VehicleCategory {
    <<enumeration>>
    MINI
    SEDAN
    SUV
    XL
  }

  class Driver {
    +id : String
    +name : String
    +rating : double
    +vehicle : Vehicle
    +status : DriverStatus
    +location : LatLng
    +updateLocation(p)
    +goOnline()
    +goOffline()
  }

  class DriverStatus {
    <<enumeration>>
    OFFLINE
    AVAILABLE
    EN_ROUTE
    ON_TRIP
  }

  class Trip {
    +id : String
    +rider : User
    +driver : Driver
    +pickup : LatLng
    +dropoff : LatLng
    +state : TripState
    +quote : Money
    +fare : Money
    +createdAt : Instant
    +request()
    +match(d : Driver)
    +start()
    +complete(fare : Money)
    +cancel(reason)
  }

  class TripState {
    <<enumeration>>
    REQUESTED
    MATCHED
    STARTED
    COMPLETED
    CANCELLED
  }

  class MatchingStrategy {
    <<interface>>
    +pick(trip : Trip, candidates : List~Driver~) Driver
  }
  class NearestDriverStrategy
  class WeightedDriverStrategy {
    +alpha, beta, gamma : double
  }

  class PricingStrategy {
    <<interface>>
    +quote(trip : Trip) Money
  }
  class FlatPricing {
    +base, perKm, perMin : double
  }
  class SurgePricing {
    +zoneMultiplier(p : LatLng) double
  }

  class TripService {
    -drivers : DriverRegistry
    -matcher : MatchingStrategy
    -pricer : PricingStrategy
    -events : EventBus
    +book(req) Trip
    +onLocation(driverId, p)
  }

  class DriverRegistry {
    +nearby(p : LatLng, radius) List~Driver~
    +tryReserve(d : Driver) boolean
    +release(d : Driver)
  }

  class EventBus {
    +publish(e : DomainEvent)
  }

  Driver *-- Vehicle
  Vehicle --> VehicleCategory
  Driver --> DriverStatus
  Trip --> User
  Trip --> Driver
  Trip --> TripState
  TripService ..> MatchingStrategy
  TripService ..> PricingStrategy
  TripService ..> DriverRegistry
  TripService ..> EventBus
  MatchingStrategy <|.. NearestDriverStrategy
  MatchingStrategy <|.. WeightedDriverStrategy
  PricingStrategy <|.. FlatPricing
  PricingStrategy <|.. SurgePricing

Trip state machine

stateDiagram-v2
  [*] --> REQUESTED : rider books
  REQUESTED --> MATCHED : driver accepts
  REQUESTED --> CANCELLED : rider cancels or no driver
  MATCHED --> STARTED : driver picks up rider
  MATCHED --> CANCELLED : rider or driver cancels
  STARTED --> COMPLETED : dropoff reached
  STARTED --> CANCELLED : aborted mid-trip
  COMPLETED --> [*]
  CANCELLED --> [*]

Each transition is a guarded method on Trip. Invalid transitions throw IllegalStateException rather than silently no-op, so bugs surface immediately in tests.

Core booking flow

sequenceDiagram
  actor R as Rider
  participant S as TripService
  participant DR as DriverRegistry
  participant M as MatchingStrategy
  participant P as PricingStrategy
  participant D as Driver

  R->>S: book(pickup, dropoff, category)
  S->>P: quote(trip)
  P-->>S: estimated fare
  S->>DR: nearby(pickup, radius)
  DR-->>S: candidates
  S->>M: pick(trip, candidates)
  M-->>S: driver
  S->>DR: tryReserve(driver)
  alt reservation wins CAS
    DR-->>S: ok
    S->>D: notify(trip)
    S-->>R: trip MATCHED
  else lost CAS
    DR-->>S: busy
    S->>M: pick next candidate
  end

The reservation step is the crux: tryReserve is a CAS that flips DriverStatus from AVAILABLE to EN_ROUTE. If two trips race for the same driver, exactly one CAS wins.

Code (Java)

public enum TripState { REQUESTED, MATCHED, STARTED, COMPLETED, CANCELLED }
public enum DriverStatus { OFFLINE, AVAILABLE, EN_ROUTE, ON_TRIP }

public class Trip {
    private final String id;
    private final User rider;
    private final LatLng pickup, dropoff;
    private Driver driver;
    private TripState state = TripState.REQUESTED;
    private Money quote, fare;

    public synchronized void match(Driver d) {
        require(state == TripState.REQUESTED, "expected REQUESTED");
        this.driver = d;
        this.state = TripState.MATCHED;
        Events.publish(new TripMatched(id, d.getId()));
    }

    public synchronized void start() {
        require(state == TripState.MATCHED, "expected MATCHED");
        this.state = TripState.STARTED;
        Events.publish(new TripStarted(id));
    }

    public synchronized void complete(Money finalFare) {
        require(state == TripState.STARTED, "expected STARTED");
        this.fare = finalFare;
        this.state = TripState.COMPLETED;
        Events.publish(new TripCompleted(id, finalFare));
    }

    public synchronized void cancel(String reason) {
        require(state != TripState.COMPLETED && state != TripState.CANCELLED,
                "cannot cancel from " + state);
        this.state = TripState.CANCELLED;
        Events.publish(new TripCancelled(id, reason));
    }

    private static void require(boolean cond, String msg) {
        if (!cond) throw new IllegalStateException(msg);
    }
}

public interface MatchingStrategy {
    Driver pick(Trip trip, List<Driver> candidates);
}

public class NearestDriverStrategy implements MatchingStrategy {
    @Override public Driver pick(Trip trip, List<Driver> candidates) {
        return candidates.stream()
            .min(Comparator.comparingDouble(d -> Geo.distance(d.getLocation(), trip.getPickup())))
            .orElse(null);
    }
}

public class WeightedDriverStrategy implements MatchingStrategy {
    private final double alpha, beta, gamma;
    public WeightedDriverStrategy(double a, double b, double g) {
        this.alpha = a; this.beta = b; this.gamma = g;
    }
    @Override public Driver pick(Trip trip, List<Driver> candidates) {
        return candidates.stream()
            .min(Comparator.comparingDouble(d ->
                alpha * Geo.distance(d.getLocation(), trip.getPickup())
              - beta * d.getRating()
              + gamma * d.acceptanceLatency()))
            .orElse(null);
    }
}

public interface PricingStrategy { Money quote(Trip t); }

public class FlatPricing implements PricingStrategy {
    private final double base, perKm, perMin;
    public FlatPricing(double b, double k, double m) {
        this.base = b; this.perKm = k; this.perMin = m;
    }
    @Override public Money quote(Trip t) {
        double km = Geo.distance(t.getPickup(), t.getDropoff());
        double min = Geo.eta(t.getPickup(), t.getDropoff());
        return Money.of(base + km * perKm + min * perMin);
    }
}

public class SurgePricing implements PricingStrategy {
    private final PricingStrategy delegate;
    private final SurgeIndex index;
    public SurgePricing(PricingStrategy d, SurgeIndex i) {
        this.delegate = d; this.index = i;
    }
    @Override public Money quote(Trip t) {
        double mult = index.multiplierFor(t.getPickup());
        return delegate.quote(t).times(mult);
    }
}

SurgePricing is a decorator over FlatPricing. Composition keeps the surge logic separable.

Concurrency

The two hot spots:

1. Driver allocation: two trips can simultaneously pick the same driver as their best match. Resolve with a CAS on DriverStatus. The CAS lives in DriverRegistry.tryReserve, backed by either an in-memory AtomicReference or a SQL UPDATE driver SET status='EN_ROUTE' WHERE id=? AND status='AVAILABLE' returning rows-affected.
2. Trip state transitions: a rider may cancel exactly as the driver presses Start. Synchronise transitions on the trip aggregate, or use optimistic locking with a version column.

Driver location heartbeats arrive at high frequency. Process them on a separate thread pool and persist asynchronously; the live in-memory index is what nearby() reads.

Edge cases

• No driver found within radius: expand radius once, then transition the trip to CANCELLED(NO_SUPPLY).
• Driver declines: release the reservation, loop to the next candidate (bounded retries).
• Rider double-tap on Book: idempotency key on book(req); second call returns the same trip.
• Cancellation after start: end the trip with partial fare and a cancellation fee.
• Network drop mid-trip: heartbeats continue from driver; resume on reconnect using last known state.

Extensions

• Pooling / shared rides: a Trip is composed of multiple legs and the matcher picks a driver compatible with the existing route.
• Scheduled bookings: persist a ScheduledTrip and a worker promotes it to a live Trip at the right time.
• Driver incentives: an event listener on TripCompleted accumulates streak bonuses.
• Geo-fenced surge zones: SurgeIndex consumes demand and supply counts per H3 cell.

Where Cab Booking LLD fits

flowchart TB
  CAB((Cab Booking<br/>LLD))
  SM[State machines<br/>Trip lifecycle]
  BP[Behavioral patterns<br/>Strategy and Decorator]
  UBER[Uber HLD<br/>system-design sibling]
  CONC[Concurrency primitives<br/>CAS on driver state]
  SM --> CAB
  BP --> CAB
  CAB -. complement .- UBER
  CONC --> CAB

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class CAB service;
    class SM,BP,UBER,CONC datastore;

Glossary & fundamentals

Tag	Concept	What it is	Page
LLD	State machines	Trip lifecycle as an explicit FSM	state-machines
LLD	Behavioral patterns	Strategy for matching and pricing	behavioral-patterns
LLD	Concurrency primitives	CAS for driver allocation	concurrency-primitives
HLD	Uber	the system-design sibling	uber

Quick reference

Classes

• User, Driver, Vehicle (with VehicleCategory)
• Trip (aggregate root, holds state)
• TripState: REQUESTED, MATCHED, STARTED, COMPLETED, CANCELLED
• DriverStatus: OFFLINE, AVAILABLE, EN_ROUTE, ON_TRIP
• MatchingStrategy: NearestDriverStrategy, WeightedDriverStrategy
• PricingStrategy: FlatPricing, SurgePricing (decorator)
• DriverRegistry (spatial index + reservation CAS)
• TripService (orchestrator)
• EventBus (TripMatched, TripStarted, TripCompleted)

State machine

• REQUESTED to MATCHED or CANCELLED
• MATCHED to STARTED or CANCELLED
• STARTED to COMPLETED or CANCELLED
• Every transition validates source state and emits a domain event.

Matching

• Nearest: pure distance.
• Weighted: alpha * distance - beta * rating + gamma * acceptanceLatency.
• Always over available drivers from the spatial index.

Pricing

• Flat: base + perKm * km + perMin * min.
• Surge: decorator multiplies by a zone factor.
• Quote at booking, finalise at completion.

Concurrency

• Driver allocation race: two trips pick the same driver. Resolve with CAS on DriverStatus (in-mem AtomicReference or SQL UPDATE WHERE status='AVAILABLE').
• Trip state race: synchronise transitions on the trip aggregate, or use optimistic locking with a version column.
• Location heartbeats handled on a separate executor; the in-memory index is the live read source.

Edge cases

• No supply in radius: cancel with reason NO_SUPPLY.
• Driver declines: release and retry with the next candidate.
• Idempotency: book() takes an idempotency key.
• Cancellation after start: partial fare plus cancellation fee.

Interview tricks

• Open with the state machine diagram first; everything else hangs off it.
• Call out that surge is a decorator over base pricing, not a separate hierarchy.
• The matching/pricing interfaces are the obvious Strategy demo: state the GoF name explicitly.
• For concurrency, explicitly say "CAS on driver state" instead of vague "use a lock".

Complexity

• nearby() lookup: O(log N) with R-tree or H3 cell scan.
• pick() candidates: O(K) over the radius candidates.
• Trip transitions: O(1).

Refs

• Uber engineering blog: dispatch, H3 cells
• Designing Uber LLD (educative)
• Designing Data-Intensive Applications (Kleppmann): event-driven design

FAQ

How do you design Uber in LLD?

Model User, Driver, Vehicle, and Trip as core classes. Trip holds a state machine (Requested, Matched, Started, Completed, Cancelled). Plug in a MatchingStrategy and a PricingStrategy for driver assignment and fare.

Why use the Strategy pattern for matching?

Matching rules differ by product (Pool, Premium, Auto). The Strategy pattern lets you swap algorithms without touching Trip or Driver, and makes A/B testing of new rules trivial.

How is the Trip state machine designed?

Each Trip method (request, match, start, complete, cancel) validates the current state and transitions to the next. Invalid transitions raise an exception so half-baked trips cannot reach checkout.

How is surge pricing modeled?

PricingStrategy is an interface; a SurgePricing implementation multiplies base fare by a region-time multiplier computed from supply/demand. Surge can be swapped per market or time of day.

What are the concurrency hot spots in cab booking?

Driver assignment is the main race: two riders can try to claim the same nearby driver. Use a single-writer queue per region or an atomic compare-and-set on driver status to keep matches consistent.

Related Topics

• State Machines: the trip lifecycle is the canonical example
• Behavioral Patterns: Strategy keeps matching and pricing pluggable
• Uber (HLD): the system-design view of the same problem

Video walkthrough

Cab/Taxi Booking like Uber/Ola: Low Level Design : via System Design Walkthrough