Ride sharing: matching, trips and fares

Design a ride-sharing service. Riders request rides, the nearest free driver is matched, the trip moves through its states, and the fare depends on distance, time and a surge multiplier. Cancel rules apply.

Design the core of a ride-hailing app. Drivers have locations on a map. A rider asks for a ride from one point to another, and the system matches a driver. The trip starts and completes, and the rider pays a fare based on distance and time, higher when few drivers are free. Riders and drivers can cancel under clear rules.

Questions to ask first

  • How do we measure distance? Assume a grid, and Manhattan distance: the sum of the horizontal and vertical steps. No roads or traffic.
  • Which driver is matched? Assume the nearest free driver within 5 steps of the pickup, and the lowest driver id when two are equally near. Matching happens at once, with no offers to drivers.
  • How is time measured? Assume whole logical minutes passed in by the caller. No real clock.
  • How is the fare computed? Assume a base amount, a price per distance step and a price per minute, with a minimum fare, multiplied by a surge percent.
  • When does surge apply? Assume it is set when the ride is requested, from the number of free drivers near the pickup, and the trip keeps it.
  • Who can cancel and when? Assume either side before the trip starts. A rider who cancels late pays a small fee. After the start, no cancel.

Requirements

  • Add drivers with a location. A driver is available until matched.
  • Request a ride: find the nearest eligible driver, create a trip and mark the driver busy.
  • Move a trip through MATCHED, STARTED and COMPLETED, and reject a call that does not fit the current state.
  • Compute the fare from distance and time with a minimum, and apply the surge multiplier fixed at request time.
  • Cancel a matched trip, with a fee for a late cancel by the rider, and free the driver.
  • Refuse a second ride for a rider who already has a trip in progress.

Out of scope

  • Real maps, routes, traffic and live GPS.
  • Payments, ratings and driver offers that can be rejected (see the extensions).
  • Many cities and vehicle types.

Entities

  • Location: x, y -> distanceTo(other) is the Manhattan distance
  • Driver: id, location, available
  • Trip: id, rider, driver, pickup, drop, surgePercent, state -> moveTo(state)
  • TripState: REQUESTED, MATCHED, STARTED, COMPLETED, CANCELLED -> canMoveTo(next)
  • DriverMatcher: picks the driver -> match(pickup, eligible), with NearestDriverMatcher
  • FareStrategy: the price before surge -> fare(distance, minutes)
  • SurgePolicy: the multiplier -> percent(eligibleDrivers)
  • RideService: the entry point -> addDriver(), requestRide(), start(), complete(), cancel()

Classes in the model design

  • Location (class)
  • Driver (class)
  • Trip (class)
  • TripState (enum)
  • DriverMatcher (interface)
  • NearestDriverMatcher (class)
  • FareStrategy (interface)
  • DistanceTimeFare (class)
  • SurgePolicy (interface)
  • DemandSurgePolicy (class)
  • RideService (class)

The main use case, step by step

  1. Asha asks for a ride from (0,0) to (3,4) at minute 0. The client calls `RideService.requestRide`. Three drivers are free and near, and one is far away.
  2. The service keeps the drivers who are available and at most 5 steps from the pickup. These are the eligible drivers. A busy or far driver is skipped.
  3. It asks the `SurgePolicy` for a percent, passing the number of eligible drivers. Three or more gives 100. Fewer would give 150 or 200.
  4. It asks the `DriverMatcher` for a driver. `NearestDriverMatcher` takes the smallest distance to the pickup, and the lowest id if two are equal.
  5. The service creates a `Trip` in MATCHED, with the surge percent stored in it, marks the driver busy and returns the trip id and driver id.
  6. At minute 3, `start` moves the trip to STARTED and moves the driver to the pickup point. A `start` on a trip that is not MATCHED is refused.
  7. At minute 15, `complete` moves the trip to COMPLETED and the driver to the drop point, and frees the driver. The `FareStrategy` gives the base fare for 7 steps and 12 minutes: 30 + 70 + 24 = 124. The stored surge percent, 100, leaves it at 124.

Patterns used

  • Strategy: DriverMatcher (NearestDriverMatcher), FareStrategy (DistanceTimeFare) and SurgePolicy (DemandSurgePolicy).. Matching, base price and surge are three rules that change on their own. A new city may match by estimated time, price by zone or surge by schedule. Each is one new class, and RideService is not edited.
  • State machine: TripState lists the allowed moves in canMoveTo. Trip.moveTo throws for any other move.. A trip has a few valid orders of events. With the rules in one place, a method such as complete cannot run on a cancelled trip by mistake, and a new state means one edit to the table.
  • Value object: Location is immutable and knows its own distance rule.. Two drivers at the same point are at the same Location, and no caller can change a location by accident. The formula for distance is written once.

Key code

Location, trip state and the trip

public record Location(int x, int y) {
    public int distanceTo(Location other) { return Math.abs(x - other.x) + Math.abs(y - other.y); }
}

public enum TripState {
    REQUESTED, MATCHED, STARTED, COMPLETED, CANCELLED;

    /** The allowed moves are written once, here. */
    public boolean canMoveTo(TripState next) {
        switch (this) {
            case REQUESTED: return next == MATCHED;
            case MATCHED: return next == STARTED || next == CANCELLED;
            case STARTED: return next == COMPLETED;
            default: return false;
        }
    }
}

public final class Trip {
    private final String id, rider;
    private final Driver driver;
    private final Location pickup, drop;
    private final int requestMinute;
    private final int surgePercent;          // fixed when the ride was requested
    private TripState state = TripState.REQUESTED;
    private int startMinute;

    public Trip(String id, String rider, Driver driver, Location pickup, Location drop, int requestMinute, int surgePercent) {
        this.id = id; this.rider = rider; this.driver = driver; this.pickup = pickup; this.drop = drop;
        this.requestMinute = requestMinute; this.surgePercent = surgePercent;
        moveTo(TripState.MATCHED);
    }

    public void moveTo(TripState next) {
        if (!state.canMoveTo(next)) throw new IllegalStateException(state + " -> " + next);
        state = next;
    }
}

Matching, fare and surge strategies

public interface DriverMatcher {
    Optional<Driver> match(Location pickup, Collection<Driver> eligible);
}

public final class NearestDriverMatcher implements DriverMatcher {
    @Override public Optional<Driver> match(Location pickup, Collection<Driver> eligible) {
        return eligible.stream().min(Comparator
            .comparingInt((Driver d) -> d.location().distanceTo(pickup))
            .thenComparing(Driver::id));              // equally near: the lowest id
    }
}

public interface FareStrategy { int fare(int distance, int minutes); }

public final class DistanceTimeFare implements FareStrategy {
    @Override public int fare(int distance, int minutes) {
        return Math.max(50, 30 + 10 * distance + 2 * minutes);   // minimum before surge
    }
}

public interface SurgePolicy { int percent(int eligibleDrivers); }

public final class DemandSurgePolicy implements SurgePolicy {
    @Override public int percent(int eligibleDrivers) {
        if (eligibleDrivers >= 3) return 100;
        return eligibleDrivers == 2 ? 150 : 200;
    }
}

Request, complete and cancel in the service

public class RideService {
    public synchronized RideOffer requestRide(String rider, Location pickup, Location drop, int minute) {
        if (trips.values().stream().anyMatch(t -> t.rider().equals(rider) && t.isActive())) {
            return new RideOffer("BUSY", null, null, 0);              // one trip at a time per rider
        }
        List<Driver> eligible = drivers.values().stream()
            .filter(d -> d.isAvailable() && d.location().distanceTo(pickup) <= RADIUS)
            .collect(Collectors.toList());
        Optional<Driver> chosen = matcher.match(pickup, eligible);
        if (chosen.isEmpty()) return new RideOffer("NO_DRIVER", null, null, 0);
        int percent = surge.percent(eligible.size());                // eligible drivers before the match
        Trip trip = new Trip("T" + ++tripCount, rider, chosen.get(), pickup, drop, minute, percent);
        chosen.get().setAvailable(false);
        trips.put(trip.id(), trip);
        return new RideOffer("MATCHED", trip.id(), chosen.get().id(), percent);
    }

    public synchronized int complete(String tripId, int minute) {
        Trip t = trips.get(tripId);
        if (t == null || t.state() != TripState.STARTED) return -1;
        t.moveTo(TripState.COMPLETED);
        t.driver().moveTo(t.drop());
        t.driver().setAvailable(true);
        int base = fares.fare(t.pickup().distanceTo(t.drop()), minute - t.startMinute());
        return base * t.surgePercent() / 100;                         // whole rupees, rounded down
    }

    public synchronized int cancel(String tripId, String by, int minute) {
        Trip t = trips.get(tripId);
        if (t == null || t.state() != TripState.MATCHED) return -1;   // no cancel after the start
        t.moveTo(TripState.CANCELLED);
        t.driver().setAvailable(true);
        boolean late = minute - t.requestMinute() > FREE_CANCEL_MINUTES;
        return by.equals("RIDER") && late ? LATE_CANCEL_FEE : 0;
    }
}

Deep dives

Matching a rider with a driver

Weak: Put the loop inside requestRide: for each driver compute the distance, keep the smallest. It works, but the rule is tied to the service, the busy check is mixed in with it, and a tie gives a different answer each time the map is iterated.

Good: Split two questions. Who may be matched? The service decides: available, and within a radius. Who is chosen? A DriverMatcher strategy decides, and NearestDriverMatcher breaks ties by driver id so the result is always the same. Keep the drivers in a sorted map so a replay gives the same answer.

Great: Make the match and the "mark busy" step one atomic action, under one lock or with a compare-and-set on the driver. Without it, two riders can both be matched to the same last free driver. For a large city, keep drivers in a grid of cells, so a request looks at the nearby cells and not at every driver.

Trade-off: Nearest by straight distance is simple and fast, but the nearest driver may be across a river or facing the wrong way. Matching by estimated arrival time is fairer to riders and needs a map service. Say which one you chose and why. The strategy interface is what lets you swap.

Fare, surge and rounding

Weak: Put the numbers inside complete(): fare = 30 + 10 * d + 2 * m, and read a global surgeMultiplier at that moment. If surge changes during a long trip, two riders on the same route pay differently for no clear reason. A double multiplier also makes rounding vary.

Good: Move the fare into a FareStrategy, and store the surge percent on the trip when it is requested. The rider saw that price at booking, and it cannot change under them. Use whole rupees and an integer percent, and say how you round.

Great: Make surge its own SurgePolicy, driven by supply: the number of eligible free drivers near the pickup. Apply the minimum fare before the surge, and say so, so that a short trip is not charged less than a floor. Write the rule down in a sentence, then write tests for each edge: exactly the minimum, one driver, two drivers, three.

Trade-off: Locking surge at request time is fair to the rider and may under-charge when the trip takes much longer than expected. Charging by live surge at the end is closer to the cost, but riders dislike a price that moves. Most apps lock the price at booking and only change it if the rider changes the trip.

Trip states and cancel rules

Weak: Use flags: isStarted, isCancelled, isCompleted. Four booleans allow sixteen combinations and only a few are valid. A driver cancels a trip that is already complete, and nobody notices until a fare is charged twice.

Good: Use a TripState enum and an if in each method: start requires MATCHED, complete requires STARTED. The invalid combinations are gone. The risk is that every method repeats its own check, and one forgets.

Great: Let the enum own the allowed moves with canMoveTo, and let Trip.moveTo throw for any other move. The service checks the state first to return a clear code, and the trip still protects itself. Put every side effect of a move, such as freeing the driver, in one place per move, so a cancel and a complete cannot leave the driver busy.

Trade-off: An enum with a table is the smallest design and is right while states only differ in what moves are allowed. When each state needs its own behaviour, such as different fares or different messages, the State pattern with one class per state is cleaner, but it adds classes. Start with the enum and say when you would change.

Now add one more feature

  • Now let a driver decline or ignore a request. What changes? Matching becomes a loop: offer the trip to the nearest driver, wait for the answer with a timeout, and move to the next nearest on a decline. `Trip` gets an OFFERED state. The `DriverMatcher` returns an ordered list of candidates and not one driver.
  • Now add ride pooling, where two riders share a car. What changes? A `Trip` becomes a `Ride` with a list of stops, and the matcher also looks at rides already in progress with a free seat. Each rider's fare is split by a new `FareStrategy`. The state machine stays the same per rider.
  • Now add vehicle types, such as bike, auto and car. What changes? Drivers get a type, and a request names one. The eligible filter checks the type, and the service picks a `FareStrategy` from a map by type. No existing strategy changes.
  • Now notify the rider and the driver on every state change. What changes? Add listeners, the Observer pattern, that `Trip.moveTo` or the service calls after a successful move. The state rules stay where they are.
  • Now handle thousands of drivers sending a new location every few seconds. What changes? Replace the scan with a grid index of drivers by cell. `moveDriver` updates one cell. A request looks at its own cell and the next ring of cells, and widens only if it finds nobody.

What each level is expected to show

SDE-1: Drivers with locations, a trip with named states, nearest-driver matching, a fare from distance and time, and the cancel rule. Return clear codes for bad calls. A `main` that replays one ride from request to completion is enough.

SDE-2: Everything at SDE-1, plus separate strategies for matching, fare and surge, a state table that rejects invalid moves, surge locked in at request time, an atomic match and busy step, and integer money with the rounding rule stated. Discuss driver offers, pooling and a spatial index as extensions.

Common mistakes

  • Putting matching, fare and surge in one long method, so a change to any rule means editing the service.
  • Using boolean flags for the trip's state, which allows combinations that should be impossible, such as started and cancelled.
  • Reading a changing surge value at completion, so two riders on the same trip pay different amounts.
  • Leaving the driver busy after a cancel, or free during a trip, because the busy flag is changed in several places.
  • Matching without a tie rule, so equal distances give a different driver on each run.
  • Using `double` for fares and percentages, so totals differ by a paisa between runs and machines.
  • Matching and marking the driver busy in two separate steps, so two riders can get the same driver.

Lessons behind this answer