Design a Ride Hailing System

1Clarify the requirements#

Before I draw a single box, I ask questions. The interviewer is watching whether I scope the thing or try to boil the ocean. I have seen strong coders fail this problem by jumping straight to a Trip class and never asking what the trip has to do.

Here is what I pin down, and the design call each answer locks in:

• One rider or pooling? Single-rider first, pooling as an extension. Committing to the simpler version first is itself a signal.
• Build the geo-index or assume it? I build a simple grid index myself to show spatial thinking, but keep it pluggable behind an interface so it is one swap to a production index.
• Fixed pricing or surge? Surge for sure. That is where the money logic gets interesting, and it is almost always the follow-up.
• One city or multi-region? Per-region, so the matcher does not scan the whole planet. A single nearby query touches one region's drivers, not all of them.

Functional scope:

• A rider requests a trip from a pickup to a drop location.
• The system finds nearby available drivers and offers the trip.
• A driver accepts, drives, picks up, drops off.
• We compute fare: base plus distance plus time, times a surge multiplier.
• Both parties can cancel, with rules about when a cancel is legal.

Non-functional scope:

• Fast matching. No rider staring at a spinner while we sort every driver in the city.
• No double-booking, ever. This is the concurrency crux and the thing I defend most carefully.
• Strict lifecycle. No skipping from REQUESTED straight to COMPLETED, no billing a trip that never started.

What I am and am not designing:

• I am designing the in-memory object model and its behavior, not the distributed deployment.
• That is the LLD contract, and saying it out loud keeps the interviewer from thinking I forgot about sharding.
• I did not forget. It is just not what this round is testing.

2Identify the core entities#

I name the nouns first, then give each a reason to exist. A reason-per-noun is what separates a design from a list.

• Rider and Driver: the two actors. A Driver also carries a live location and an availability status, because both feed the matcher.
• Vehicle: the car. Separate from Driver because a driver can switch cars across a shift, and vehicle type (sedan, SUV) drives pricing. Folding it into Driver would couple two things that change at different rates.
• Location: a lat/lng value object. Immutable, so a Location I hand to the matcher can never be mutated under me.
• Trip: the heart of the system. Holds rider, driver, the two locations, a status, and the fare. Everything orbits this.
• TripStatus: an enum that powers a state machine. This is not just a label; it gates what operations are legal at each step.
• DriverMatchingStrategy: pluggable logic for picking drivers. Nearest-first today, highest-rated tomorrow, both behind the same seam.
• PricingStrategy: pluggable fare math. Normal and surge are different strategies, not if-statements scattered around the service.
• LocationIndex: a spatial lookup so I do not scan every driver on earth for one request.
• RideService: the orchestrator the client calls. It wires the pieces together and owns none of the hard logic itself.

The two splits that make the interviewer nod:

• Splitting Driver from Vehicle.
• Splitting the two strategies out behind interfaces.

Both signal you have maintained a system like this, not just read about one.

3Class design#

The spine is Trip, and the front door is RideService. Keep the roles clean:

• Trip owns a TripStatus and refuses illegal transitions.
• RideService takes a request, asks the LocationIndex for candidates, hands them to a DriverMatchingStrategy, and locks a driver.
• When the trip ends, RideService asks a PricingStrategy for the fare.

Why both strategies are interfaces, on purpose:

• Surge pricing and nearest-driver matching are the parts most likely to change, so I isolate them behind seams.
• Driver carries status so the matcher can filter, and that status change is the thing I guard with a compare-and-set later.
• Everything in the diagram below serves one of two moves: isolate what changes, lock what must not break.

And here is the runtime flow for a request, which is the story I tell out loud while pointing at the board:

4Key implementation#

Start with the state machine, because it is the rule everything else obeys. I let each enum constant declare its own legal next states. No giant switch that someone can forget to update when they add a status.

public enum TripStatus {
    REQUESTED, DRIVER_ASSIGNED, EN_ROUTE, IN_PROGRESS, COMPLETED, CANCELLED;

    private static final Map<TripStatus, Set<TripStatus>> NEXT = Map.of(
        REQUESTED,       EnumSet.of(DRIVER_ASSIGNED, CANCELLED),
        DRIVER_ASSIGNED, EnumSet.of(EN_ROUTE, CANCELLED),
        EN_ROUTE,        EnumSet.of(IN_PROGRESS, CANCELLED),
        IN_PROGRESS,     EnumSet.of(COMPLETED),
        COMPLETED,       EnumSet.noneOf(TripStatus.class),
        CANCELLED,       EnumSet.noneOf(TripStatus.class)
    );

    public boolean canMoveTo(TripStatus next) {
        return NEXT.getOrDefault(this, Set.of()).contains(next);
    }
}

Trip holds that status and enforces it. The important property:

• One method, transitionTo, is the only way status ever changes.
• So there is exactly one place to audit when a transition bug shows up.
• assign routes through the same method, so even assignment cannot skip the rules.

public class Trip {
    private final String id;
    private final Rider rider;
    private volatile Driver driver;
    private volatile TripStatus status = TripStatus.REQUESTED;
    private final Location pickup;
    private final Location drop;
    private double fare;

    public Trip(String id, Rider rider, Location pickup, Location drop) {
        this.id = id;
        this.rider = rider;
        this.pickup = pickup;
        this.drop = drop;
    }

    public synchronized void transitionTo(TripStatus next) {
        if (!status.canMoveTo(next)) {
            throw new IllegalStateException(
                "Illegal trip transition " + status + " -> " + next);
        }
        this.status = next;
    }

    public synchronized void assign(Driver d) {
        this.driver = d;
        transitionTo(TripStatus.DRIVER_ASSIGNED);
    }

    // getters for pickup, drop, status, driver omitted
}

Now the Driver, which has to be reservable without two riders grabbing it at once. I use an atomic compare-and-set on status so the winner is decided by the CPU, not by a prayer and a timing window.

public class Driver {
    private final String id;
    private volatile Location location;
    private final Vehicle vehicle;
    private final AtomicReference<DriverStatus> status =
        new AtomicReference<>(DriverStatus.AVAILABLE);

    public boolean tryReserve() {
        return status.compareAndSet(DriverStatus.AVAILABLE, DriverStatus.ON_TRIP);
    }

    public void release() {
        status.set(DriverStatus.AVAILABLE);
    }

    public Location getLocation() { return location; }
    public void setLocation(Location l) { this.location = l; }
}

Strategies next. The matcher does one clever thing worth saying out loud:

• It returns the first candidate it can actually lock, so it never hands back a driver who is already gone.
• The filter(Driver::tryReserve) line does double duty: it filters and it reserves in one pass.
• That one pass is the whole trick. Sorting by distance and locking by availability happen together, not in two round trips.

public interface DriverMatchingStrategy {
    Optional<Driver> selectDriver(List<Driver> candidates, Trip trip);
}

public class NearestDriverStrategy implements DriverMatchingStrategy {
    public Optional<Driver> selectDriver(List<Driver> candidates, Trip trip) {
        return candidates.stream()
            .sorted(Comparator.comparingDouble(
                d -> d.getLocation().distanceTo(trip.getPickup())))
            .filter(Driver::tryReserve)   // lock as we go, take the first win
            .findFirst();
    }
}

Pricing is where surge lives. The fare model:

• Normal is base plus distance plus time: 50 base, 12 per km, 2 per minute.
• Surge multiplies the whole thing by a demand factor the service feeds in.

public interface PricingStrategy {
    double price(Trip trip);
}

public class NormalPricingStrategy implements PricingStrategy {
    private static final double BASE = 50;
    private static final double PER_KM = 12;
    private static final double PER_MIN = 2;

    public double price(Trip trip) {
        double km = trip.getPickup().distanceTo(trip.getDrop());
        double mins = km * 2;  // rough ETA model
        return BASE + km * PER_KM + mins * PER_MIN;
    }
}

public class SurgePricingStrategy implements PricingStrategy {
    private final PricingStrategy base;
    private final double multiplier;

    public SurgePricingStrategy(PricingStrategy base, double multiplier) {
        this.base = base;
        this.multiplier = multiplier;
    }

    public double price(Trip trip) {
        return base.price(trip) * multiplier;
    }
}

Why SurgePricingStrategy wraps another strategy:

• That is a decorator.
• Surge works on top of any base pricing I plug in later, airport flat fares included.
• I never have to fork the fare math to add a multiplier.

Finally the orchestrator, kept thin on purpose. It coordinates; it does not compute.

• If the interviewer sees fare math or distance sorting inside RideService, I have leaked logic that belonged in a strategy.
• Everything hard (matching, pricing, the lifecycle) lives in the piece that owns it. The service just wires them.

public class RideService {
    private final LocationIndex index;
    private final DriverMatchingStrategy matcher;
    private final Map<String, Trip> trips = new ConcurrentHashMap<>();

    public RideService(LocationIndex index, DriverMatchingStrategy matcher) {
        this.index = index;
        this.matcher = matcher;
    }

    public Trip requestTrip(Rider rider, Location from, Location to) {
        Trip trip = new Trip(UUID.randomUUID().toString(), rider, from, to);
        trips.put(trip.getId(), trip);

        List<Driver> candidates = index.nearby(from, 3.0);
        Optional<Driver> matched = matcher.selectDriver(candidates, trip);

        matched.ifPresentOrElse(
            trip::assign,
            () -> { throw new NoDriverAvailableException(trip.getId()); });
        return trip;
    }

    public double endTrip(String tripId, PricingStrategy pricing) {
        Trip trip = trips.get(tripId);
        trip.transitionTo(TripStatus.COMPLETED);
        double fare = pricing.price(trip);
        trip.getDriver().release();
        return fare;
    }
}

5Design decisions and patterns used#

Five patterns, each earning its place:

• State pattern, via the enum machine. Trip transitions are centralized and illegal jumps throw. The interviewer specifically wants to see you stop a REQUESTED trip from becoming COMPLETED, and the NEXT map does exactly that in one readable place.
• Strategy pattern for both matching and pricing. These are the volatile parts, so I isolate them behind interfaces. Swapping nearest-driver for highest-rated is a one-line change at construction time, nowhere else.
• Decorator for surge. SurgePricingStrategy wraps a base strategy instead of forking the pricing code. Clean layering, and surge composes with any future base.
• Factory (implied) when the service picks which pricing strategy to apply based on current demand. I would add a PricingStrategyFactory that returns surge above a demand threshold and normal below, so the decision lives in one testable spot.
• Observer for notifications. When a trip transitions, riders and drivers get pinged. I keep it out of the core classes so Trip does not know about push notifications or SMS, which keeps the lifecycle code honest.

The parts that change often live behind interfaces; the part that must never break is locked down tight. Say that sentence and you have handed the interviewer the headline of your design.

6Handling edge cases and concurrency#

This is where the problem earns its Hard rating, and where I spend the most breath without being asked.

• Double-booking. Two riders request at the same instant and the matcher offers the same driver. My tryReserve uses compareAndSet, so exactly one thread flips AVAILABLE to ON_TRIP. The loser's filter skips that driver and moves to the next candidate. No locks held across the network, no race, no two riders in one back seat.
• No driver found. The nearby list comes back empty or everyone is taken. I throw a typed NoDriverAvailableException that the client turns into "expanding your search," and I would widen the radius past the initial 3 km on retry.
• Cancellation after assignment. Rider cancels while the driver is EN_ROUTE. The state machine allows DRIVER_ASSIGNED and EN_ROUTE to go to CANCELLED, and on cancel I always call driver.release() so the driver returns to the pool. The rule I never break: releasing the driver is part of the same path as cancelling, never a separate call someone can forget.
• Driver accepts but goes offline. I would add a reservation timeout. If the driver does not move the trip to EN_ROUTE within N seconds, a reaper releases the driver and rematches. That keeps a flaky driver from freezing a rider on the spinner forever.
• Stale location. The index holds last-known positions. A driver who went dark should not be matched, so I timestamp every update and the index filters out positions older than a threshold before it ever returns a candidate.
• Fare consistency. I compute surge at request time and freeze the multiplier on the trip, otherwise a rider gets a nasty surprise if demand spikes mid-ride. Quote the number, honor the number. This is a product rule, not just a code rule, and calling it out shows you think past the compiler.

7Extensions and follow-ups#

When the interviewer pushes, here is where I go.

• Pooling. One trip, multiple riders. Trip holds a list of stops and the matcher optimizes a route. Pricing splits across riders by distance share.
• Better geo-index. My grid of cells is fine for the interview. In production I would reach for a geohash or an H3 hex grid so radius queries hit a handful of cells, not a scan. The LocationIndex interface means that swap touches zero other classes.
• Ratings and preferences. A new HighestRatedStrategy that implements the same interface. Zero changes anywhere else, which is the whole point of the Strategy seam.
• Scheduled rides. A booking queued for later. The service holds it and runs matching at T minus a few minutes.
• ETA and routing. Plug a routing service behind an interface so pricing's mins is a real estimate, not my km * 2 stand-in.

8What the interviewer is really checking#

Two things, and they are the whole game:

• Can you find the seams? The exercise is spotting that matching and pricing will change, that the trip lifecycle must not, and drawing the line between them. Hardcode surge into an if and skip the state machine, and you have missed the point even if the code runs.
• Are you concurrency-honest? Ride hailing is a shared-resource problem wearing a product costume. The driver is the contended resource. Talk through compareAndSet and reservation timeouts without being asked and you have shown you have actually run one of these. That is the signal that gets you the yes.

If you liked the state machine here, try the LLD for an Elevator System or a Vending Machine. For the strategy and decorator layering, the Pricing Engine and Notification Service problems are close cousins.