Ride-Sharing: Matching, Surge, and Three State Machines

12.1Problem Statement

Design the core of a ride-hailing service — Uber or Ola stripped to its LLD skeleton. A rider requests a ride from a pickup to a drop location; the system finds a nearby available driver; the trip runs through a lifecycle from assignment to completion, with a fare computed at the end.

Functional requirements:

• Riders request a ride from a pickup to a drop location, choosing a ride type (Mini / Sedan / SUV).
• Drivers go online/offline, publish their location, and accept/reject ride offers.
• The system matches a request to a suitable nearby available driver.
• Trip lifecycle: REQUESTED → DRIVER_ASSIGNED → ARRIVED → IN_PROGRESS → COMPLETED / CANCELLED.
• Compute fare on completion (base + distance + time, with surge).
• Notify rider and driver on each state change.

Non-functional / constraints:

• Matching strategy is pluggable (nearest driver, highest-rated, least-idle).
• Pricing strategy is pluggable (normal vs. surge, based on demand/supply).
• Driver and Trip are modeled as State machines.
• Observer pattern drives rider/driver notifications.
• Concurrency: one driver must never be assigned to two trips; matching must be atomic.

Expected public interface (given, not invented — lock this down before writing a single internal):

enum class TripStatus { REQUESTED, DRIVER_ASSIGNED, ARRIVED, IN_PROGRESS, COMPLETED, CANCELLED };

class MatchingStrategy {              // Strategy
public:
    virtual Driver* match(const RideRequest&, const std::vector<Driver*>& available) = 0;
    virtual ~MatchingStrategy() = default;
};

class PricingStrategy {               // Strategy (normal / surge)
public:
    virtual double fare(const Trip&) const = 0;
    virtual ~PricingStrategy() = default;
};

class RideService {
public:
    Trip&   requestRide(const std::string& riderId, Location pickup, Location drop, RideType type);
    void    acceptRide(const std::string& driverId, const std::string& tripId);
    void    startTrip(const std::string& tripId);
    Receipt endTrip(const std::string& tripId);   // computes fare
    void    cancelTrip(const std::string& tripId, const std::string& byActor);
};

What the interviewer is really testing: multiple interacting state machines (driver availability vs. trip lifecycle) kept consistent under change; atomic matching so a driver isn't double-booked under concurrency; pluggable matching and surge-pricing Strategies; Observer notifications threaded through every state change without a missed call site.

Follow-up questions to expect:

1. Geospatial matching at scale — grid, quadtree, or geohash for "nearby drivers" instead of a linear scan.
2. Cancellation policy and fees — who cancelled, and when, changes what gets charged.
3. Pool / shared rides — multiple riders per trip.
4. Ratings, driver payout, and ETA estimation.

12.2How to Approach

Read the constraints like an interviewer wrote them, because they decide the whole design. "Driver and Trip modeled as State machines… kept consistent" means there are (at least) two machines and they must never disagree: a driver going ON_TRIP and a trip going DRIVER_ASSIGNED are the same real-world event seen from two angles. "Matching must be atomic" is the concurrency trap: selecting a driver and marking them busy must be one indivisible step, or two riders race onto the same driver. The two Strategy interfaces and the Observer requirement are handed to you outright — your job is to wire them cleanly, not invent architecture.

Why three state machines, not one shared enum

A tempting shortcut is one shared status enum slapped onto rider, driver and trip alike. It falls apart immediately: what does ON_TRIP mean for a rider who hasn't been matched yet? A driver's timeline doesn't line up 1:1 with any one trip's timeline either — a driver can be OFFLINE long before any trip exists, and AVAILABLE between trips, states no single trip ever observes. Conflating "whose perspective is this status from" produces impossible combinations. The fix is to scope each machine to what's actually true for that actor:

• Driver gets a real, stored DriverStatus { OFFLINE, AVAILABLE, ON_TRIP }, because its lifetime outlives any single trip.
• Trip gets the real, stored TripStatus lifecycle — it is the canonical record of what actually happened to this one ride.
• Rider doesn't need a third stored field at all. A rider's experience — waiting for a match, waiting for pickup, on the trip, done — is always a deterministic function of whichever trip currently references them. Derive it as a read-only view over Trip::status() instead of storing a second copy that could quietly drift out of sync.

The atomic matching problem

The concurrency trap is a classic check-then-act race: "find an available driver" and "mark them busy" cannot be two separate steps with a gap between them, or two concurrent requestRide calls can both see the same driver as free. The fix is to make the whole sequence — snapshot available drivers, ask the matching Strategy to pick one, flip that driver to ON_TRIP, flip the trip to DRIVER_ASSIGNED — happen inside one critical section guarded by a single mutex. Nothing outside that block can observe a half-matched state. The same lock guards the release path (a trip completing or cancelling hands the driver back to AVAILABLE), so availability flips are always serialized through one gate.

The two Strategy seams and the Observer channel

MatchingStrategy::match(request, availableDrivers) and PricingStrategy::fare(trip) should be pure functions of their inputs — no shared mutable state, so a nearest-driver rule and a highest-rated rule are equally drop-in, and normal pricing vs. surge pricing can be swapped at runtime with one call. Surge is naturally a decorator over the normal fare: compute the base fare, then multiply. For notifications, resist the urge to fire an observer callback at every call site that touches a trip's status; instead route every transition through one choke point (a small helper that runs the mutation, diffs old vs. new status, and only then notifies). That guarantees no transition ever ships silently, and adding a second observer later touches zero existing call sites.

Each follow-up maps onto a seam that's already there. Geospatial scale doesn't touch MatchingStrategy at all — a grid, geohash, or quadtree just shrinks the candidate list handed to match(). Cancellation fees are a new Strategy reading (actor, status, elapsed). Pooled rides extend Trip to a list of riders and waypoints without touching the driver machine. Ratings are an Observer that updates Driver on COMPLETED, feeding straight back into a highest-rated matching Strategy.

12.3Whole Solution

One synthesized, compiling C++17 program merging every fragment above into a single consistent design: Location/RideType/Rider/RideRequest/Receipt as the immutable leaves, Driver and Trip as the two stored state machines (with RiderView as the derived third), the two Strategy interfaces with two implementations each, the Observer interface with one concrete notifier, and RideService as the orchestrator owning the atomic match. main() runs a full happy path, swaps pricing strategies live, cancels a trip, rejects an illegal transition, and shows an unmatched request when no driver is free.

// ride_sharing.cpp
// LLD: Zero to Hero -- Chapter 12: Ride-Sharing
// Three coupled state machines (rider view is derived, driver and trip are
// stored), a pluggable MatchingStrategy, a pluggable PricingStrategy, and an
// Observer channel for status-change notifications. Atomic matching is a
// single lock_guard around "pick a driver, then mark them busy."

#include <cmath>
#include <iostream>
#include <limits>
#include <memory>
#include <mutex>
#include <stdexcept>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>

// ---------------------------------------------------------------------------
// Leaves: no dependencies on anything below.
// ---------------------------------------------------------------------------

struct Location {
    double lat = 0, lng = 0;
    // Cheap planar approximation; good enough for matching/fare in an LLD.
    double distanceTo(const Location& o) const {
        double dx = lat - o.lat, dy = lng - o.lng;
        return std::sqrt(dx * dx + dy * dy);
    }
};

enum class RideType { MINI, SEDAN, SUV };

// Per-tier multiplier; a bigger car costs more per km.
inline double tierMultiplier(RideType t) {
    switch (t) {
        case RideType::MINI:  return 1.0;
        case RideType::SEDAN: return 1.3;
        case RideType::SUV:   return 1.7;
    }
    return 1.0;
}

struct Rider {
    std::string id;
    std::string name;
};

// Immutable description of an ask. Strategies read it, never mutate it.
struct RideRequest {
    std::string riderId;
    Location    pickup;
    Location    drop;
    RideType    type;
    double tripDistance() const { return pickup.distanceTo(drop); }
};

struct Receipt {
    std::string tripId;
    double      fare = 0;
    double      distance = 0;
    double      surgeMultiplier = 1.0;
};

// ---------------------------------------------------------------------------
// Driver: the first state machine. Availability persists across trips and
// has a state (OFFLINE) that no trip ever sees, so it earns its own stored
// field. RideService flips it under a lock; nobody else may call
// markOnTrip()/markAvailable() directly.
// ---------------------------------------------------------------------------

enum class DriverStatus { OFFLINE, AVAILABLE, ON_TRIP };

class Driver {
public:
    Driver(std::string id, Location loc, double rating)
        : id_(std::move(id)), loc_(loc), rating_(rating) {}

    const std::string& id() const { return id_; }
    Location location() const     { return loc_; }
    double   rating() const       { return rating_; }
    DriverStatus status() const   { return status_; }

    void goOnline()  { if (status_ == DriverStatus::OFFLINE)   status_ = DriverStatus::AVAILABLE; }
    void goOffline() { if (status_ == DriverStatus::AVAILABLE) status_ = DriverStatus::OFFLINE; }

    // Driven by RideService under the matcher lock -- never call directly.
    void markOnTrip()    { status_ = DriverStatus::ON_TRIP; }
    void markAvailable() { status_ = DriverStatus::AVAILABLE; }

    void setLocation(Location l) { loc_ = l; }

private:
    std::string  id_;
    Location     loc_;
    double       rating_ = 0;
    DriverStatus status_ = DriverStatus::OFFLINE;
};

// ---------------------------------------------------------------------------
// Trip: the second state machine, and the canonical source of truth for the
// whole ride. The rider's experience -- WAITING_FOR_MATCH, WAITING_FOR_PICKUP,
// ON_TRIP, DONE -- is a *read-only derived view* over this same status (see
// riderView() below), never a second stored enum that could drift out of
// sync with it. Legal moves are guarded inside the object, so callers cannot
// corrupt the machine.
// ---------------------------------------------------------------------------

enum class TripStatus { REQUESTED, DRIVER_ASSIGNED, ARRIVED, IN_PROGRESS, COMPLETED, CANCELLED };

// The rider's third state machine. No stored field anywhere -- see Trip::riderView().
enum class RiderView { IDLE, WAITING_FOR_MATCH, WAITING_FOR_PICKUP, ON_TRIP, DONE };

class Trip {
public:
    Trip(std::string id, RideRequest req)
        : id_(std::move(id)), req_(std::move(req)) {}

    const std::string& id() const       { return id_; }
    TripStatus status() const           { return status_; }
    const RideRequest& request() const  { return req_; }
    const std::string& driverId() const { return driverId_; }
    double distance() const             { return req_.tripDistance(); }
    RideType type() const               { return req_.type; }

    double fare() const          { return fare_; }
    void   setFare(double f)     { fare_ = f; }

    // ---- guarded transitions: legal move => advance, illegal => throw ----
    void assign(const std::string& driverId) {
        expect(TripStatus::REQUESTED, "assign");
        driverId_ = driverId;
        status_   = TripStatus::DRIVER_ASSIGNED;
    }
    void arrive() {
        expect(TripStatus::DRIVER_ASSIGNED, "arrive");
        status_ = TripStatus::ARRIVED;
    }
    void start() {
        expect(TripStatus::ARRIVED, "start");
        status_ = TripStatus::IN_PROGRESS;
    }
    void complete() {
        expect(TripStatus::IN_PROGRESS, "complete");
        status_ = TripStatus::COMPLETED;
    }
    void cancel() {
        if (isTerminal())
            throw std::logic_error("trip already finished; cannot cancel");
        status_ = TripStatus::CANCELLED;
    }

    bool isTerminal() const {
        return status_ == TripStatus::COMPLETED || status_ == TripStatus::CANCELLED;
    }
    // A driver is "held" while the trip is active (assigned but not terminal).
    bool holdsDriver() const {
        return !driverId_.empty() && !isTerminal();
    }

    // The rider's derived view -- computed on demand, always in lockstep.
    RiderView riderView() const {
        switch (status_) {
            case TripStatus::REQUESTED:       return RiderView::WAITING_FOR_MATCH;
            case TripStatus::DRIVER_ASSIGNED:
            case TripStatus::ARRIVED:         return RiderView::WAITING_FOR_PICKUP;
            case TripStatus::IN_PROGRESS:     return RiderView::ON_TRIP;
            case TripStatus::COMPLETED:
            case TripStatus::CANCELLED:       return RiderView::DONE;
        }
        return RiderView::IDLE;
    }

private:
    void expect(TripStatus s, const char* op) const {
        if (status_ != s)
            throw std::logic_error(std::string("illegal transition: ") + op);
    }

    std::string id_;
    RideRequest req_;
    std::string driverId_;
    TripStatus  status_ = TripStatus::REQUESTED;
    double      fare_   = 0;
};

inline const char* riderViewName(RiderView v) {
    switch (v) {
        case RiderView::IDLE:               return "IDLE";
        case RiderView::WAITING_FOR_MATCH:  return "WAITING_FOR_MATCH";
        case RiderView::WAITING_FOR_PICKUP: return "WAITING_FOR_PICKUP";
        case RiderView::ON_TRIP:            return "ON_TRIP";
        case RiderView::DONE:               return "DONE";
    }
    return "?";
}

// ---------------------------------------------------------------------------
// Strategy seam #1: matching. A pure function of (request, candidates) --
// no shared mutable state, so it is trivially swappable and testable alone.
// ---------------------------------------------------------------------------

class MatchingStrategy {
public:
    virtual ~MatchingStrategy() = default;
    // Pick a driver from `available`, or nullptr if none is suitable.
    virtual Driver* match(const RideRequest& req,
                           const std::vector<Driver*>& available) = 0;
};

// Closest driver to the pickup point.
class NearestDriverStrategy : public MatchingStrategy {
public:
    Driver* match(const RideRequest& req,
                   const std::vector<Driver*>& available) override {
        Driver* best = nullptr;
        double  bestDist = std::numeric_limits<double>::max();
        for (Driver* d : available) {
            double dist = d->location().distanceTo(req.pickup);
            if (dist < bestDist) { bestDist = dist; best = d; }
        }
        return best;
    }
};

// Highest-rated driver (tie-break: first one seen). Drop-in replacement --
// RideService never needs to change to use this instead.
class HighestRatedStrategy : public MatchingStrategy {
public:
    Driver* match(const RideRequest&,
                   const std::vector<Driver*>& available) override {
        Driver* best = nullptr;
        for (Driver* d : available)
            if (!best || d->rating() > best->rating()) best = d;
        return best;
    }
};

// ---------------------------------------------------------------------------
// Strategy seam #2: pricing. A pure function of a Trip; surge just wraps
// the normal fare with a multiplier (decorator-ish, but kept as a Strategy
// so RideService can swap it at runtime with one call).
// ---------------------------------------------------------------------------

class PricingStrategy {
public:
    virtual ~PricingStrategy() = default;
    virtual double fare(const Trip&) const = 0;
};

// base + per-km + per-tier multiplier.
class NormalPricing : public PricingStrategy {
public:
    double fare(const Trip& t) const override {
        const double base = 50.0, perKm = 12.0;
        return (base + perKm * t.distance()) * tierMultiplier(t.type());
    }
};

class SurgePricing : public PricingStrategy {
public:
    explicit SurgePricing(double multiplier) : surge_(multiplier) {}
    double fare(const Trip& t) const override {
        return base_.fare(t) * surge_;
    }
    double surge() const { return surge_; }
private:
    NormalPricing base_;
    double        surge_ = 1.0;
};

// ---------------------------------------------------------------------------
// Observer seam: fired from exactly one choke point inside RideService
// (see transition() below), never from scattered call sites, so no
// transition can ship without notifying every subscriber.
// ---------------------------------------------------------------------------

class TripObserver {
public:
    virtual ~TripObserver() = default;
    virtual void onStatusChange(const Trip& trip, TripStatus from, TripStatus to) = 0;
};

class NotificationService : public TripObserver {
public:
    void onStatusChange(const Trip& trip, TripStatus from, TripStatus to) override {
        std::cout << "[notify] trip " << trip.id()
                  << " : " << name(from) << " -> " << name(to) << "\n";
    }
private:
    static const char* name(TripStatus s) {
        switch (s) {
            case TripStatus::REQUESTED:       return "REQUESTED";
            case TripStatus::DRIVER_ASSIGNED: return "DRIVER_ASSIGNED";
            case TripStatus::ARRIVED:         return "ARRIVED";
            case TripStatus::IN_PROGRESS:     return "IN_PROGRESS";
            case TripStatus::COMPLETED:       return "COMPLETED";
            case TripStatus::CANCELLED:       return "CANCELLED";
        }
        return "?";
    }
};

// ---------------------------------------------------------------------------
// RideService: the orchestrator. Owns atomic matching (the concurrency
// trap named in the prompt) and the single choke point where the driver
// and trip machines flip together and observers fire.
// ---------------------------------------------------------------------------

class RideService {
public:
    RideService(std::unique_ptr<MatchingStrategy> matcher,
                std::unique_ptr<PricingStrategy>  pricing)
        : matcher_(std::move(matcher)), pricing_(std::move(pricing)) {}

    void addDriver(Driver* d)                            { drivers_.push_back(d); }
    void setPricing(std::unique_ptr<PricingStrategy> p)  { pricing_ = std::move(p); }
    void subscribe(TripObserver* o)                      { observers_.push_back(o); }

    Trip& requestRide(const std::string& riderId, Location pickup,
                       Location drop, RideType type) {
        RideRequest req{riderId, pickup, drop, type};
        std::string tripId = "T" + std::to_string(++counter_);
        auto trip = std::make_unique<Trip>(tripId, req);
        Trip& ref = *trip;
        trips_[tripId] = std::move(trip);

        // ---- ATOMIC: snapshot available drivers, pick one, lock him in ----
        {
            std::lock_guard<std::mutex> guard(matchMutex_);
            std::vector<Driver*> available;
            for (Driver* d : drivers_)
                if (d->status() == DriverStatus::AVAILABLE) available.push_back(d);

            Driver* chosen = matcher_->match(req, available);
            if (chosen) {
                chosen->markOnTrip();                                // (1) flip driver  } both
                transition(ref, [&] { ref.assign(chosen->id()); });  // (2) flip trip    } inside
            }                                                        //     the same lock
        }
        return ref;   // REQUESTED if no driver was free, else DRIVER_ASSIGNED
    }

    void acceptRide(const std::string& driverId, const std::string& tripId) {
        // In a pure offer/accept model the driver confirms here. With the
        // synchronous matcher above the assignment already happened; this
        // method exists for the explicit-handshake variant of the design.
        (void)driverId; (void)tripId;
    }

    void arrive(const std::string& tripId) {
        Trip& t = trip(tripId);
        transition(t, [&] { t.arrive(); });
    }

    void startTrip(const std::string& tripId) {
        Trip& t = trip(tripId);
        transition(t, [&] { t.start(); });
    }

    Receipt endTrip(const std::string& tripId) {
        Trip& t = trip(tripId);
        double f = pricing_->fare(t);           // Strategy decides the fare
        t.setFare(f);
        transition(t, [&] { t.complete(); });
        releaseDriver(t);                        // driver back to AVAILABLE
        return Receipt{tripId, f, t.distance(), surgeOf()};
    }

    void cancelTrip(const std::string& tripId, const std::string& byActor) {
        Trip& t = trip(tripId);
        std::cout << "[cancel] " << tripId << " by " << byActor << "\n";
        transition(t, [&] { t.cancel(); });
        releaseDriver(t);                        // free the held driver, if any
    }

private:
    // Single choke point: run the mutation, then fire observers with from/to.
    template <typename Fn>
    void transition(Trip& t, Fn&& mutate) {
        TripStatus from = t.status();
        mutate();
        TripStatus to = t.status();
        if (from != to)
            for (TripObserver* o : observers_) o->onStatusChange(t, from, to);
    }

    void releaseDriver(Trip& t) {
        std::lock_guard<std::mutex> guard(matchMutex_);
        for (Driver* d : drivers_)
            if (d->id() == t.driverId()) { d->markAvailable(); break; }
    }

    Trip& trip(const std::string& id) {
        auto it = trips_.find(id);
        if (it == trips_.end()) throw std::invalid_argument("no such trip: " + id);
        return *it->second;
    }

    double surgeOf() const {
        if (auto* s = dynamic_cast<SurgePricing*>(pricing_.get())) return s->surge();
        return 1.0;
    }

    std::unique_ptr<MatchingStrategy> matcher_;
    std::unique_ptr<PricingStrategy>  pricing_;
    std::vector<Driver*>              drivers_;    // not owned here
    std::unordered_map<std::string, std::unique_ptr<Trip>> trips_;
    std::vector<TripObserver*>        observers_;
    std::mutex                        matchMutex_;
    int                                counter_ = 0;
};

// ---------------------------------------------------------------------------
// main: happy path, a live Strategy swap, a cancellation, an illegal
// transition, and an unmatched request -- proves all three state machines,
// both Strategy seams, and the guard rails together.
// ---------------------------------------------------------------------------

int main() {
    Driver alice("D1", {0.0, 0.0}, 4.9);
    Driver bob  ("D2", {5.0, 5.0}, 4.5);
    alice.goOnline();
    bob.goOnline();

    RideService svc(std::make_unique<NearestDriverStrategy>(),
                     std::make_unique<NormalPricing>());
    NotificationService notifier;
    svc.subscribe(&notifier);
    svc.addDriver(&alice);
    svc.addDriver(&bob);

    // --- Trip 1: rider near (0,0). NearestDriverStrategy should pick Alice.
    Trip& trip1 = svc.requestRide("R1", {0.1, 0.1}, {3.0, 4.0}, RideType::SEDAN);
    std::cout << "trip1 assigned driver: " << trip1.driverId() << "\n";           // D1
    std::cout << "trip1 rider view: " << riderViewName(trip1.riderView()) << "\n"; // WAITING_FOR_PICKUP

    svc.arrive(trip1.id());       // DRIVER_ASSIGNED -> ARRIVED
    svc.startTrip(trip1.id());    // ARRIVED -> IN_PROGRESS
    std::cout << "trip1 rider view: " << riderViewName(trip1.riderView()) << "\n"; // ON_TRIP

    // Swap to surge before completing -- a runtime Strategy swap.
    svc.setPricing(std::make_unique<SurgePricing>(1.8));
    Receipt r1 = svc.endTrip(trip1.id());   // IN_PROGRESS -> COMPLETED
    std::cout << "trip1 fare: " << r1.fare << " (surge x" << r1.surgeMultiplier << ")\n";
    std::cout << "trip1 rider view: " << riderViewName(trip1.riderView()) << "\n"; // DONE
    std::cout << "alice available again? "
              << (alice.status() == DriverStatus::AVAILABLE) << "\n";

    // --- Trip 2: rider near (5,5). Alice is free again but far away, so
    // NearestDriverStrategy should now pick Bob.
    Trip& trip2 = svc.requestRide("R2", {5.1, 5.0}, {6.0, 6.0}, RideType::MINI);
    std::cout << "trip2 assigned driver: " << trip2.driverId() << "\n";   // D2

    // Rider cancels before pickup -- Bob must be released, invariant held.
    svc.cancelTrip(trip2.id(), "rider:R2");
    std::cout << "bob available again? "
              << (bob.status() == DriverStatus::AVAILABLE) << "\n";

    // --- Illegal transition: a completed trip cannot be started again.
    try {
        svc.startTrip(trip1.id());
    } catch (const std::exception& e) {
        std::cout << "rejected: " << e.what() << "\n";
    }

    // --- No driver available: both go offline, request should stay unmatched.
    alice.goOffline();
    bob.goOffline();
    Trip& trip3 = svc.requestRide("R3", {1.0, 1.0}, {2.0, 2.0}, RideType::MINI);
    std::cout << "trip3 rider view (no driver): " << riderViewName(trip3.riderView()) << "\n"; // WAITING_FOR_MATCH

    return 0;
}