Design a Cab Booking System
Riders, drivers, trip lifecycle, surge pricing, and nearest-driver matching — Uber/Ola in objects.
Problem Statement
Design the object model for a cab booking system like Uber or Ola. Riders request trips from pickup to drop, nearby available drivers are matched, the fare is estimated with surge, the trip moves through Requested -> Assigned -> Started -> Completed / Cancelled, and rider plus driver receive lifecycle notifications.
The focus is matching and trip lifecycle: who owns live location, who reserves a driver, who computes price, and who prevents invalid state transitions.
Business context
Cab booking is a high-signal marketplace LLD problem because it combines live actors, location-aware dispatch, dynamic pricing, explicit state transitions, and notification side effects. Weak answers become a giant service full of if-else blocks. Strong answers separate policies from orchestration and make the trip aggregate protect its own lifecycle.
Interviewers usually probe the exact request path: filter available drivers, choose the nearest one, quote fare with surge, mark that driver unavailable, assign the trip, then move safely through start, completion, or cancellation.
Functional Requirements
Register riders and drivers with identity and current live location.
Let drivers update location and toggle availability.
Allow a rider to request a trip with pickup and drop locations.
Match a request to the nearest available driver through a pluggable strategy.
Estimate fare through a pricing strategy that can apply surge using demand and supply.
Create a trip and move it through Requested, Assigned, Started, Completed, and Cancelled states.
Reject invalid transitions such as completing a trip before it starts.
Notify rider and driver on assignment, start, completion, and cancellation.
Release the driver back to available after completion or eligible cancellation.
Non-Functional Requirements
Low-latency matching
A ride request should find a nearby driver quickly. The interview version can scan in memory; production can replace that with a geospatial index behind the same strategy.
Lifecycle correctness
The trip must reject impossible transitions instead of letting any caller assign an arbitrary status.
Extensible policies
Matching and pricing change by city, vehicle type, and experiment. They should be interfaces, not hard-coded branches in the service.
Timely notifications
Rider and driver apps need prompt lifecycle updates. The domain should publish events through observers and keep push or SMS delivery outside the trip entity.
Concurrency safety
Two riders must not receive the same driver. Driver selection and marking unavailable form one critical section.
Requirement Clarification
QDo we need real road routing and ETA?
No. Use a simple Location.distanceTo estimate. Real maps, traffic, and ETA providers are adapters that can feed matching and pricing later.
QCan a driver reject an assigned ride?
Not in the base flow. Driver acceptance can be added as an Offered state before Assigned, with timeout and retry matching.
QWhen is a driver made unavailable?
Immediately after the service chooses the driver and before returning the assigned trip, inside the same synchronized request flow.
QWhich cancellations are supported?
Requested, Assigned, and Started trips can cancel in the base model. Completed and Cancelled are terminal.
QWho sends notifications?
The Trip emits lifecycle messages to TripObserver instances. Concrete push, SMS, or email adapters can subscribe outside the core model.
UML Class Diagram
Sequence Diagram
Entity Identification
Rider
Customer actor with current location. It requests trips and receives lifecycle messages as an observer.
Driver
Supply actor with live location and availability. The service reserves the driver by flipping availability during assignment.
Location
Immutable latitude-longitude value object shared by matching and pricing.
Trip
Aggregate for one ride. It stores pickup, dropoff, rider, driver, fare, current status, state object, and observers.
TripStatus / TripState
Visible enum plus behavior objects that enforce legal lifecycle transitions.
MatchingStrategy
Driver-selection policy. The base implementation chooses the nearest available driver.
PricingStrategy
Fare-estimation policy. The base implementation combines base fare, distance fare, and surge multiplier.
TripObserver
Notification seam implemented by rider and driver. Production push or SMS adapters can implement the same interface.
RideService
Singleton facade that registers actors, performs atomic match-and-assign, stores trips, and delegates lifecycle operations.
Design Patterns Used
MatchingStrategy and PricingStrategy isolate policies that vary by city, category, demand, and experiment while the service flow stays stable.
TripState moves transition rules out of if-else chains. Requested can assign or cancel, Assigned can start or cancel, Started can complete or cancel, and terminal states reject changes.
TripObserver lets rider, driver, and future notification adapters subscribe to lifecycle updates without coupling Trip to delivery channels.
RideService.getInstance gives the in-memory interview solution one coordinator for rider, driver, and trip maps, making the critical section easy to explain.
Step-by-Step Design
1Model the lifecycle first
Start from the state chain. Every request begins as Requested, must be Assigned before Started, and ends as Completed or Cancelled.
enum TripStatus { REQUESTED, ASSIGNED, STARTED, COMPLETED, CANCELLED }2Represent pickup and driver positions as values
Location is immutable and owns distance calculation so matching and pricing do not duplicate coordinate math.
public double distanceTo(Location other) { double dLat = latitude - other.latitude; double dLon = longitude - other.longitude; return Math.sqrt(dLat * dLat + dLon * dLon) * 111.0; }3Select drivers through a strategy
The base policy is nearest available driver, but the service depends only on MatchingStrategy.
return drivers.stream() .filter(Driver::isAvailable) .min(Comparator.comparingDouble(d -> d.getCurrentLocation().distanceTo(pickup)));4Compute surge through a strategy
PricingStrategy receives pickup, dropoff, available-driver count, and active-request count. The trip stores the quote returned by the strategy.
5Make match-and-assign atomic
The synchronized requestTrip method selects a driver, marks the driver unavailable, assigns the trip, and stores it before returning.
6Notify from state transitions
The service wires rider and driver as TripObserver instances. The trip broadcasts assignment, start, completion, and cancellation from transition methods.
Complete Java Implementation
Explanation of Every Class
Location
Immutable value object for latitude and longitude. distanceTo gives matching and pricing one shared distance estimate.
Rider
Customer actor that stores current location and implements TripObserver for lifecycle notifications.
Driver
Supply actor with live location and availability. The service reserves and releases the driver around the trip lifecycle.
Trip
Ride aggregate and state-machine host. Concrete states in the same file enforce assignment, start, completion, and cancellation rules.
MatchingStrategy
Driver-selection seam. NearestAvailableMatchingStrategy chooses the available driver closest to pickup.
PricingStrategy
Fare-estimation seam. SurgePricingStrategy combines base fare, distance fare, and a demand-supply multiplier.
RideService
Singleton facade and critical section for registration, match-and-assign, trip storage, and driver release.
Main
Demo that registers actors, requests a trip, starts it, completes it, and prints notifications.
Dry Run
Sample input
Rider R1 requests Indiranagar to Koramangala. Drivers: D1 is 0.6 km away and available; D2 is 5.2 km away and available. Base fare 50, per-km 18, one active request, two available drivers.
| Step | Action | Driver pool | Trip status | Notifications | Result |
|---|---|---|---|---|---|
| 1 | requestTrip(R1) | D1:0.6 km free, D2:5.2 km free | REQUESTED | none yet | D1 chosen as nearest available |
| 2 | estimateFare | available=2, activeRequests=1 | REQUESTED | none yet | base + distance fare with 1.0 surge |
| 3 | assign D1 | D1 marked unavailable | ASSIGNED | rider and D1 receive assigned | Trip TRIP-1 stored |
| 4 | startTrip(TRIP-1) | D1 busy | STARTED | rider and D1 receive started | Trip moves out of pickup phase |
| 5 | completeTrip(TRIP-1) | D1 released | COMPLETED | rider and D1 receive completed | Trip terminal, fare retained |
Step 3 is the key invariant: D1 is selected and marked unavailable in the same service call, so another rider cannot receive the same driver.
Complexity Analysis
| Operation | Time | Space | Note |
|---|---|---|---|
| requestTrip with linear scan | O(D) | O(1) | D is the number of registered drivers scanned by the nearest-available strategy. |
| fare estimate | O(1) | O(1) | Distance and surge multiplier are constant-time in this interview model. |
| startTrip / completeTrip / cancelTrip | O(1) | O(1) | Map lookup, one state transition, and a small observer broadcast. |
| location update | O(1) | O(1) | The actor replaces one immutable Location value. |
The hot path is matching. Replace the O(D) scan with geohash, S2, H3, or another spatial index while keeping MatchingStrategy unchanged.
Extensibility
ETA-aware matching
Add a strategy that ranks by road ETA, rating, acceptance probability, and fairness instead of pure straight-line distance.
City-specific pricing
Add a pricing strategy that reads city rates, vehicle category, weather, events, tolls, and cancellation fees.
Driver acceptance
Insert Offered and OfferExpired states before Assigned, then retry matching when an offer times out or is rejected.
Notification channels
Attach observers for push, SMS, email, or WhatsApp without changing Trip transition logic.
Persistence
Replace in-memory maps with repositories and keep service methods as transaction boundaries.
Alternative Designs
Geospatial driver index
Maintain available drivers in cells and expand around pickup until enough candidates are found, then rank candidates with the matching strategy.
Tradeoffs
Fast at scale, but driver location updates must keep the index consistent and cell expansion becomes a separate algorithm.
Event-sourced trip lifecycle
Persist events such as TripRequested, DriverAssigned, TripStarted, TripCompleted, and TripCancelled, then derive status from the stream.
Tradeoffs
Excellent auditability, but usually too heavy for the base LLD unless disputes or compliance are central follow-ups.
Dedicated dispatch service
Move driver discovery and reservation into DriverDispatchService, leaving RideService focused on trip lifecycle.
Tradeoffs
Cleaner at large scale, but adds network failure modes and is more HLD than core LLD.
Common Mistakes
- ×
Putting matching, pricing, state transitions, and notifications inside one huge method.
- ×
Using a mutable status enum without transition guards.
- ×
Forgetting to mark the driver unavailable atomically with assignment.
- ×
Hard-coding nearest-driver logic so ETA or vehicle-category matching requires editing the service.
- ×
Hard-coding surge math in Trip instead of a pricing strategy.
- ×
Letting notification delivery failures roll back the trip state.
- ×
Allowing terminal trips to be completed or cancelled again.
Follow-up Interview Questions
QHow would you scale nearest-driver matching?
Index available drivers by geospatial cells, search the pickup cell first, expand neighboring cells, and run MatchingStrategy on that candidate set.
QHow do you prevent two riders from getting one driver?
Make reservation atomic. The sample synchronizes requestTrip; production would use a compare-and-set or row lock on driver availability.
QWhere does driver acceptance fit?
Add Offered and OfferExpired states. Assignment happens only after the driver accepts before timeout.
QHow would you handle cancellation after start?
Let StartedState.cancel transition to Cancelled, compute any fee through pricing, release the driver, and notify both parties.
QHow do notifications become reliable?
Write lifecycle events to an outbox in the same transaction as the trip state change, then retry delivery asynchronously.
Production Considerations
Geospatial indexing
Use geohash, S2, H3, or a search backend for nearby-driver lookup, with TTL for fast-changing locations.
Atomic reservation
Reserve a driver with compare-and-set or a database row lock. If it fails, retry with the next candidate.
Pricing audit
Persist fare quote, distance estimate, surge multiplier, and policy version used at assignment time.
Reliable notification
Use an outbox and idempotent workers so push provider failures do not corrupt trip state.
Observability
Track match latency, no-driver rate, driver utilization, cancellation rate, surge distribution, and transition failures.
What Interviewers Look For
Did you separate matching, pricing, lifecycle, and notifications?
Is nearest-driver matching a swappable strategy rather than service glue?
Does the state machine reject invalid transitions clearly?
Is driver reservation atomic with trip assignment?
Can the design evolve to acceptance, geospatial indexing, and reliable notifications without rewriting the model?
Quiz
0/5 answered
1.Why should nearest-driver selection live behind **MatchingStrategy**?
2.What is the purpose of **TripState**?
3.When should a matched driver become unavailable?
4.Why use Observer for notifications?
5.What does Singleton represent here?
Practice Variants
Add driver acceptance timeout
AdvancedIntroduce Offered and OfferExpired states, notify the driver, and retry matching when the offer times out.
Support vehicle categories
IntermediateAdd Auto, Mini, Sedan, and SUV categories to drivers and rider requests. Update matching and pricing strategies without changing trip transitions.
Replace scan with geohash buckets
AdvancedMaintain available drivers by geohash cell and expand around pickup while preserving the MatchingStrategy contract.
Flashcards
Cheat Sheet
Entities: Rider, Driver, Location, Trip, TripStatus/TripState, MatchingStrategy, PricingStrategy, TripObserver, RideService.
Patterns: Strategy for matching and pricing; State for trip lifecycle; Observer for rider/driver notifications; Singleton for the in-memory service facade.
Flow: requestTrip = load rider -> find nearest available driver -> estimate surge fare -> create trip -> attach observers -> reserve driver -> assign trip.
Lifecycle: Requested -> Assigned -> Started -> Completed. Cancelled is terminal and can be reached from non-terminal states in the base design.
Invariant: one available driver can be assigned to at most one active trip; invalid state transitions throw immediately.
Complexity: linear scan matching O(D), lifecycle transitions O(1), notification broadcast O(observers).
Scale path: geospatial index, transactional driver reservation, persistent trip and fare quote, outbox-backed notifications.
References
- BookDesigning Data-Intensive Applications — Martin Kleppmann
- DocsRefactoring Guru — Strategy, State, and Observer Patterns
- BlogUber Engineering — Marketplace Reliability Engineering — Uber Engineering