LOW LEVEL DESIGN · MACHINE CODING · MEDIUM · 22 OF 42

Design a Cab Booking System Like Uber: LLD with Java Code

The ride-hailing machine coding question, solved end to end: riders, drivers and trips, a trip state machine, matching the nearest free driver as a strategy, claiming a driver with compare-and-set so two riders never share one, metered fares with surge, ratings, push updates as observers, and a full Java 17 solution with a 12-rider race.

Patterns usedObserverStrategyState

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
  42. 42
1 / 17

Press play to hear the narration, or step through at your own pace. The full Java code is below.

Full Java solution

One file, Java 17, 299 lines, with a small main() demo. Save it as CabBooking.java, then run javac CabBooking.java && java CabBooking.

import java.time.Duration;
import java.time.Instant;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Map;
import java.util.Optional;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicLong;
import java.util.concurrent.atomic.AtomicReference;
import java.util.function.Supplier;

/** Cab booking: riders request trips, the nearest free driver is claimed atomically, fares use a strategy. */
public class CabBooking {

    // ---------- the model ----------
    record Location(double x, double y) {
        double kmTo(Location o) { return Math.hypot(x - o.x, y - o.y); }
    }

    enum CabType { MINI, SEDAN, SUV }

    enum DriverStatus { OFFLINE, AVAILABLE, ON_TRIP }

    static final class Driver {
        final String id;
        final CabType type;
        private final AtomicReference<DriverStatus> status = new AtomicReference<>(DriverStatus.OFFLINE);
        private volatile Location location;
        private final AtomicLong ratingSum = new AtomicLong();
        private final AtomicLong ratings = new AtomicLong();

        Driver(String id, CabType type, Location at) {
            this.id = id;
            this.type = type;
            this.location = at;
        }

        /** Compare-and-set: two trips can never claim the same driver. */
        boolean claim() { return status.compareAndSet(DriverStatus.AVAILABLE, DriverStatus.ON_TRIP); }

        void goOnline() { status.set(DriverStatus.AVAILABLE); }

        void finishTrip(Location at) {
            location = at;
            status.set(DriverStatus.AVAILABLE);
        }

        boolean isAvailable() { return status.get() == DriverStatus.AVAILABLE; }

        Location location() { return location; }

        void rate(int stars) {
            ratingSum.addAndGet(stars);
            ratings.incrementAndGet();
        }

        double rating() { return ratings.get() == 0 ? 5.0 : (double) ratingSum.get() / ratings.get(); }
    }

    enum TripState { REQUESTED, ACCEPTED, STARTED, COMPLETED, CANCELLED }

    static final class Trip {
        final String id;
        final String rider;
        final Location from;
        final Location to;
        final CabType type;
        private TripState state = TripState.REQUESTED;
        private Driver driver;
        private Instant startedAt;
        private long fareCents;

        Trip(String id, String rider, Location from, Location to, CabType type) {
            this.id = id;
            this.rider = rider;
            this.from = from;
            this.to = to;
            this.type = type;
        }

        /** Every state change goes through here, so an illegal jump fails loudly. */
        synchronized void move(TripState from, TripState next) {
            if (state != from) throw new IllegalStateException(id + ": cannot go " + state + " -> " + next);
            state = next;
        }

        synchronized TripState state() { return state; }

        synchronized Driver driver() { return driver; }

        synchronized long fareCents() { return fareCents; }
    }

    // ---------- strategies and observers ----------
    interface MatchingStrategy { List<Driver> rank(DriverSource drivers, Trip trip); }

    /** Lets the strategy see drivers without owning the map. */
    interface DriverSource { List<Driver> all(); }

    /** Nearest free driver of the right type within a radius, ties broken by rating. */
    static final class NearestDriver implements MatchingStrategy {
        private final double radiusKm;

        NearestDriver(double radiusKm) { this.radiusKm = radiusKm; }

        @Override
        public List<Driver> rank(DriverSource drivers, Trip trip) {
            List<Driver> out = new ArrayList<>();
            for (Driver d : drivers.all()) {
                boolean near = d.location().kmTo(trip.from) <= radiusKm;
                if (d.type == trip.type && d.isAvailable() && near) out.add(d);
            }
            out.sort(Comparator.comparingDouble((Driver d) -> d.location().kmTo(trip.from))
                    .thenComparing(Comparator.comparingDouble(Driver::rating).reversed()));
            return out;
        }
    }

    interface FareStrategy { long fareCents(Trip trip, double km, Duration took); }

    /** Base + per km + per minute, by cab type, times a surge multiplier. */
    static final class MeteredFare implements FareStrategy {
        private final Map<CabType, long[]> rates = Map.of(   // base, per km, per minute (paise)
                CabType.MINI, new long[] { 5000, 1200, 150 },
                CabType.SEDAN, new long[] { 7000, 1500, 200 },
                CabType.SUV, new long[] { 9000, 2000, 250 });
        private final Supplier<Double> surge;

        MeteredFare(Supplier<Double> surge) { this.surge = surge; }

        @Override
        public long fareCents(Trip trip, double km, Duration took) {
            long[] r = rates.get(trip.type);
            double raw = r[0] + r[1] * km + r[2] * took.toMinutes();
            return Math.round(raw * surge.get());
        }
    }

    interface TripListener { void onChange(Trip trip, TripState state); }

    // ---------- the service ----------
    private final Map<String, Driver> drivers = new ConcurrentHashMap<>();
    private final Map<String, Trip> trips = new ConcurrentHashMap<>();
    private final List<TripListener> listeners = new CopyOnWriteArrayList<>();
    private final AtomicLong ids = new AtomicLong();
    private final MatchingStrategy matching;
    private final FareStrategy fares;
    private final Supplier<Instant> clock;

    CabBooking(MatchingStrategy matching, FareStrategy fares, Supplier<Instant> clock) {
        this.matching = matching;
        this.fares = fares;
        this.clock = clock;
    }

    void addDriver(Driver d) { drivers.put(d.id, d); }

    void subscribe(TripListener l) { listeners.add(l); }

    /** Ask the strategy for candidates in order and claim the first one that is still free. */
    Optional<Trip> request(String rider, Location from, Location to, CabType type) {
        Trip trip = new Trip("T" + ids.incrementAndGet(), rider, from, to, type);
        for (Driver d : matching.rank(() -> new ArrayList<>(drivers.values()), trip)) {
            if (!d.claim()) continue;              // another trip got this driver first
            synchronized (trip) { trip.driver = d; }
            trip.move(TripState.REQUESTED, TripState.ACCEPTED);
            trips.put(trip.id, trip);
            publish(trip);
            return Optional.of(trip);
        }
        return Optional.empty();                   // no cab nearby
    }

    void start(String tripId) {
        Trip t = trip(tripId);
        t.move(TripState.ACCEPTED, TripState.STARTED);
        synchronized (t) { t.startedAt = clock.get(); }
        publish(t);
    }

    long complete(String tripId) {
        Trip t = trip(tripId);
        t.move(TripState.STARTED, TripState.COMPLETED);
        long fare;
        synchronized (t) {
            Duration took = Duration.between(t.startedAt, clock.get());
            t.fareCents = fares.fareCents(t, t.from.kmTo(t.to), took);
            fare = t.fareCents;
        }
        t.driver().finishTrip(t.to);
        publish(t);
        return fare;
    }

    /** A rider can cancel before the trip starts; the driver becomes free again. */
    void cancel(String tripId) {
        Trip t = trip(tripId);
        t.move(TripState.ACCEPTED, TripState.CANCELLED);
        t.driver().finishTrip(t.driver().location());
        publish(t);
    }

    void rate(String tripId, int stars) {
        Trip t = trip(tripId);
        if (t.state() != TripState.COMPLETED) throw new IllegalStateException("rate only completed trips");
        t.driver().rate(stars);
    }

    private Trip trip(String id) {
        Trip t = trips.get(id);
        if (t == null) throw new IllegalArgumentException("no trip " + id);
        return t;
    }

    private void publish(Trip t) {
        TripState s = t.state();
        for (TripListener l : listeners) l.onChange(t, s);
    }

    // ---------- demo ----------
    static String rupees(long paise) { return String.format("%d.%02d", paise / 100, paise % 100); }

    public static void main(String[] args) throws InterruptedException {
        Instant[] now = { Instant.parse("2026-11-20T09:00:00Z") };
        double[] surge = { 1.0 };
        CabBooking app = new CabBooking(new NearestDriver(8), new MeteredFare(() -> surge[0]), () -> now[0]);
        app.subscribe((t, s) -> {
            if (s == TripState.ACCEPTED || s == TripState.COMPLETED) {
                System.out.println("  [push] " + t.rider + ": " + t.id + " " + s);
            }
        });

        Driver d1 = new Driver("D1", CabType.SEDAN, new Location(1, 1));
        Driver d2 = new Driver("D2", CabType.SEDAN, new Location(4, 4));
        Driver d3 = new Driver("D3", CabType.MINI, new Location(0, 1));
        for (Driver d : List.of(d1, d2, d3)) {
            app.addDriver(d);
            d.goOnline();
        }

        Trip t1 = app.request("asha", new Location(0, 0), new Location(6, 8), CabType.SEDAN).orElseThrow();
        System.out.println("asha matched with " + t1.driver().id + " (nearest sedan)");
        now[0] = now[0].plus(Duration.ofMinutes(4));
        app.start(t1.id);
        now[0] = now[0].plus(Duration.ofMinutes(20));
        System.out.println("asha fare for 10 km, 20 min: " + rupees(app.complete(t1.id)));
        app.rate(t1.id, 5);

        Trip t2 = app.request("ravi", new Location(0, 0), new Location(3, 4), CabType.SEDAN).orElseThrow();
        System.out.println("ravi matched with " + t2.driver().id);
        app.cancel(t2.id);
        System.out.println("ravi cancelled, " + t2.driver().id + " free again: " + t2.driver().isAvailable());
        try {
            app.start(t2.id);
        } catch (IllegalStateException e) {
            System.out.println("start after cancel: " + e.getMessage());
        }

        surge[0] = 1.5;
        Trip t3 = app.request("meera", new Location(0, 0), new Location(3, 4), CabType.MINI).orElseThrow();
        app.start(t3.id);
        now[0] = now[0].plus(Duration.ofMinutes(10));
        System.out.println("meera mini, 5 km, 10 min, surge 1.5x: " + rupees(app.complete(t3.id)));

        // Race: 12 riders ask for a sedan at once; only 2 sedans exist, so exactly 2 get one.
        ExecutorService pool = Executors.newFixedThreadPool(8);
        CountDownLatch go = new CountDownLatch(1);
        AtomicInteger matched = new AtomicInteger();
        Map<String, String> byDriver = new ConcurrentHashMap<>();
        for (int i = 0; i < 12; i++) {
            String rider = "r" + i;
            pool.submit(() -> {
                try {
                    go.await();
                    app.request(rider, new Location(2, 2), new Location(5, 5), CabType.SEDAN).ifPresent(t -> {
                        matched.incrementAndGet();
                        String prev = byDriver.putIfAbsent(t.driver().id, rider);
                        if (prev != null) throw new AssertionError("driver shared");
                    });
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
            });
        }
        go.countDown();
        pool.shutdown();
        pool.awaitTermination(5, TimeUnit.SECONDS);
        System.out.println("Race: 12 riders, 2 sedans, matched " + matched.get()
                + ", drivers " + new java.util.TreeSet<>(byDriver.keySet()));
        if (matched.get() != 2) throw new AssertionError("a driver was double booked");
    }
}

Notes

Requirements

Fix the scope. A rider requests a trip with a pickup, a drop and a cab type. We match the nearest free driver of that type. The driver starts and ends the trip, and the fare is a base plus a rate per kilometre and per minute, times a surge multiplier at peak times. The rider can cancel before the trip starts and rate the driver after. Both sides get live updates. Real maps and payment are out of scope.

Ask what changes the code. How far do we look for drivers? Eight kilometres. Does the driver accept, or do we assign automatically? Auto-assign for now, with accept as a follow-up. Two drivers at the same distance? The higher rating wins. Can a rider cancel after the trip starts? No. Each answer lands in exactly one class, which shows the interviewer you think in responsibilities.

Requirements
  • rider requests: pickup, drop,
  • cab type (mini, sedan, SUV)
  • match the nearest free driver
  • driver starts and ends the trip
  • fare: base + per km + per minute
  • surge multiplier at peak times
  • rider can cancel before start
  • rate the driver after the trip
  • live updates to both sides
  • out of scope: maps, payments
Clarify first
  • how far to look for drivers?
  • within 8 km
  • driver must accept, or auto?
  • auto-assign for now
  • tie on distance?
  • higher rating wins
  • cancel after the trip starts?
  • no
  • pool rides?
  • later, as an extension

Entities

Underline the nouns: rider, driver, trip, location. A location is an immutable record with a distance method. A driver has a cab type, a status of offline, available or on trip, a current location and a rating. A trip has the rider, pickup and drop, the cab type, a state, the assigned driver and the fare. A rider needs no class of its own yet; an id is enough until profiles or wallets appear.

The model
record Location(double x, double y)
enum CabType { MINI, SEDAN, SUV }
enum DriverStatus { OFFLINE,
                   AVAILABLE, ON_TRIP }
class Driver: id, type, status,
  location, rating
class Trip: id, rider, from, to,
  type, state, driver, fare

State machine

The trip is a state machine. Requested becomes accepted when a driver is matched. Accepted becomes started at pickup, or cancelled if the rider cancels. Started becomes completed at the drop. Nothing else is allowed. Write it as one move method that takes the expected current state and the next one, and throws on anything else, so a bug like starting a cancelled trip fails loudly instead of corrupting data.

Here is that method. It is synchronized, so a driver tapping start and a rider tapping cancel at the same moment cannot both succeed: whichever runs first changes the state, and the other sees the wrong current state and gets a clear error. Every public action, start, complete and cancel, is a single call to move with its expected from-state.

Trip states
  • REQUESTED
  • -> ACCEPTED (driver matched)
  • ACCEPTED
  • -> STARTED (rider picked up)
  • -> CANCELLED (rider cancels)
  • STARTED
  • -> COMPLETED (drop reached)
  • anything else: throw
Trip.move()
synchronized void move(TripState from,
                       TripState next) {
  if (state != from)
    throw new IllegalStateException(
      id + ": cannot go " + state
         + " -> " + next);
  state = next;
}

start(): move(ACCEPTED, STARTED)

Strategy: matching

Which driver gets the ride is a business policy that will change, so it sits behind an interface: the Strategy pattern. Our default filters to free drivers of the right type within eight kilometres, sorts by distance and breaks ties by rating. Later the business may want road travel time, acceptance rate or fairness so every driver gets work. Each is a new class; the booking service never changes.

MatchingStrategy
interface MatchingStrategy {
  List<Driver> rank(DriverSource d,
                    Trip trip);
}
NearestDriver: right type, free,
  within 8 km, nearest first,
  then higher rating
later: ETA by road, acceptance
  rate, driver fairness

Flow: request

The request flow. Create the trip, ask the strategy for ranked candidates, and try to claim each driver in order. If a claim fails because another rider just took that driver, move to the next. On success, attach the driver, move the trip to accepted, store it and tell listeners. If nobody is free, return empty so the app can show no cabs nearby instead of throwing an exception for an everyday case.

request(...)
Trip trip = new Trip(nextId(), ...)
for (Driver d : matching.rank(..)) {
  if (!d.claim()) continue;
  trip.driver = d;
  trip.move(REQUESTED, ACCEPTED);
  trips.put(trip.id, trip);
  publish(trip);
  return Optional.of(trip);
}
return Optional.empty(); // no cab

Concurrency

Now the key concurrency point. Two riders standing on the same corner both rank driver D1 first. If claiming were check the status, then set it, both could win and one driver would get two trips. Instead the status is an atomic reference and claiming is a compare-and-set from available to on trip. Exactly one rider wins; the other simply tries the next driver in their list. No global lock, so riders never wait on each other.

No driver booked twice
AtomicReference<DriverStatus> status

boolean claim() {
  return status.compareAndSet(
    AVAILABLE, ON_TRIP);
}

A and B both rank D1 first
A: AVAILABLE -> ON_TRIP, true
B: expected AVAILABLE, false

Strategy: fare

The fare is a second strategy. Metered fare charges a base, a rate per kilometre and a rate per minute for the cab type, times the surge multiplier. A ten kilometre, twenty minute sedan ride is two hundred and sixty. Flat airport fares or subscriptions are new classes. Surge comes from a supplier, so a test can set it directly, and money stays as whole paise in a long, never a floating point number.

MeteredFare
fare = (base + perKm * km
        + perMin * minutes) * surge

sedan: 70 + 15/km + 2/min
  10 km, 20 min = 260.00
mini at 1.5x surge:
  5 km, 10 min = 187.50

surge is a Supplier<Double>,
  so tests set it directly

Observer: updates

Live updates use the Observer pattern. Each interested part registers a trip listener: the rider's push notifications, the driver's app, the receipt emailer, analytics. After every state change the service publishes the trip and its new state. Adding a new subscriber never touches the booking code, and a copy-on-write list lets subscribers join while trips are running.

TripListener
interface TripListener {
  void onChange(Trip t, TripState s);
}
listeners = new CopyOnWriteArrayList

subscribers: rider push, driver
  app, receipts, analytics

Flow: finish

Finishing a trip moves it from started to completed, prices it from the distance and the time taken, and frees the driver at the drop point so the next match uses their new location. Cancel moves accepted to cancelled and frees the driver where they stand. Rating is allowed only on a completed trip, and the driver keeps a running sum and count so the average is cheap to read.

complete() and cancel()
complete(id):
  move(STARTED, COMPLETED)
  fare = fares.fareCents(t, km, took)
  driver.finishTrip(t.to)
cancel(id):
  move(ACCEPTED, CANCELLED)
  driver back to AVAILABLE
rate(id, stars):
  only on a COMPLETED trip

Concurrency

Go through every shared field. Driver status is atomic and claimed with compare-and-set. Driver location is volatile so a new position is visible to the matcher at once. Trip state changes only inside the synchronized move method. Drivers and trips live in concurrent hash maps, ids come from an atomic counter, ratings are two atomic longs, and listeners sit in a copy-on-write list.

Thread safety checklist
  • driver status: AtomicReference
  • claimed with compare-and-set
  • driver location: volatile
  • trip state: synchronized move()
  • trips, drivers: ConcurrentHashMap
  • trip ids: AtomicLong
  • ratings: AtomicLong sum + count
  • listeners: CopyOnWriteArrayList
  • records: immutable

Extensibility

Now the follow-ups. Drivers accept or decline? Add an offered state with a timeout, and on decline try the next driver. Pool rides? A trip with several stops. Scheduled rides? Run the matcher ten minutes before pickup. Too many drivers to scan? Index them by grid cell or geohash and search only nearby cells. Payments listen for completed trips. Almost every change is a new state, a new strategy or a new listener.

Extension points
  • driver accepts or declines:
  • OFFERED state, timeout, next
  • pool rides: a Trip with stops
  • scheduled rides: matcher runs
  • 10 minutes before pickup
  • fast nearest search: grid or
  • geohash cells, not a full scan
  • payments, wallet: on COMPLETED,
  • via a listener
  • many cities: one app per city

Testing

The full code is below the player. The demo matches the nearest sedan and prices a ten kilometre ride with a fake clock, cancels a trip and shows the driver is free again, proves a cancelled trip cannot start, applies a one and a half times surge, and finally lets twelve riders request a sedan at once when only two exist. Exactly two are matched, to two different drivers, every run.

Run it
asha matched with D1 (nearest)
asha fare 10 km, 20 min: 260.00
ravi matched with D2, cancels
  D2 free again: true
start after cancel:
  cannot go CANCELLED -> STARTED
mini, surge 1.5x: 187.50
Race: 12 riders, 2 sedans,
  matched 2, drivers [D1, D2]

Say it like this

Here is the version to say out loud. Riders request trips, and a trip is a state machine with one guarded move method. Matching and fares are strategies, and live updates are observers. A driver is claimed with a compare-and-set on its status, so two riders never get the same driver, and the loser simply tries the next one.

In the interview
  • "Riders request trips; a Trip is
  • a state machine with one guarded
  • move(). Matching and fares are
  • strategies; updates are
  • observers. A driver is claimed
  • with compare-and-set on its
  • status, so two riders never get
  • the same driver."

Interview questions

How do you make sure two riders never get the same driver?

Claiming is atomic. Each driver keeps its status in an AtomicReference and the service claims with compareAndSet(AVAILABLE, ON_TRIP). Only one rider can win; the other moves on to the next driver in its ranked list, with no global lock.

Why model the trip as a state machine?

A trip has a small set of legal moves: requested, accepted, started, completed, or cancelled before start. One guarded move(from, next) method enforces them, so an illegal action like starting a cancelled trip throws instead of corrupting data.

What happens if the rider cancels just as the driver taps start?

Both actions go through the synchronized move method with an expected from-state. Whichever runs first wins; the other sees the trip is no longer ACCEPTED and gets a clear error, so the trip is never both started and cancelled.

Why is matching a strategy?

Choosing a driver is a business policy that changes: nearest, best ETA, acceptance rate, fairness. Behind a MatchingStrategy interface each version is a new class and the booking service stays closed for modification.

How would you find nearby drivers quickly with a million drivers?

Do not scan them all. Index drivers by grid cell or geohash, update the index when they move, and search the rider cell plus its neighbours, widening the ring until enough candidates are found.

How do you calculate the fare and surge?

A FareStrategy computes base plus per-km plus per-minute rates for the cab type, multiplied by a surge factor supplied from outside. Money is kept in whole paise in a long so there are no rounding errors.

How do rider and driver apps get live updates?

Observer pattern: listeners subscribe to trip changes and the service publishes after every transition. Push notifications, driver apps, receipts and analytics are all listeners, so adding one never changes the core.

How would you add driver accept or decline?

Add an OFFERED state. The service claims the best driver, offers the trip with a timeout, and on decline or timeout frees that driver and offers the next one. On accept the trip moves to ACCEPTED as before.