Limited time: AI code review, hints, mock interviews, whiteboard analysis, and all Pro features are unlocked. Enroll
⏱️ 27 min read

Designing a Ride Matching Engine

Difficulty: Intermediate Patterns: Strategy, State, Observer Asked at: Uber, Ola, Rapido, Lyft

Functional Requirements

  1. Register drivers - drivers go online/offline, update their location in real-time
  2. Request rides - riders submit pickup and drop locations to request a ride
  3. Proximity matching - find nearest available drivers within a radius
  4. Accept/reject - matched driver can accept or reject; if rejected, offer to next
  5. Trip lifecycle - states: REQUESTED → MATCHED → EN_ROUTE → IN_PROGRESS → COMPLETED / CANCELLED
  6. Fare calculation - compute fare based on distance, time, surge multiplier

Non-Functional Requirements

  1. Thread-safety - concurrent ride requests and driver updates must not corrupt state
  2. Low-latency matching - proximity search must be fast even with many drivers
  3. Extensibility - new matching strategies (cheapest, highest-rated) without changing core

Core Entities

Entity Description
Location Latitude and longitude pair
Driver ID, name, location, status (AVAILABLE, ON_TRIP, OFFLINE)
Rider ID, name, current location
RideRequest Rider + pickup + drop + timestamp
Trip Links rider, driver, route, fare; tracks state
TripState Enum: REQUESTED, MATCHED, DRIVER_EN_ROUTE, IN_PROGRESS, COMPLETED, CANCELLED
MatchingStrategy Interface for driver selection algorithm
FareCalculator Computes fare from distance + time + surge
RideService Orchestrates matching, state transitions, notifications

Class Diagram

classDiagram
    class DriverStatus {
        <<enumeration>>
        AVAILABLE
        ON_TRIP
        OFFLINE
    }

    class TripState {
        <<enumeration>>
        REQUESTED
        MATCHED
        DRIVER_EN_ROUTE
        IN_PROGRESS
        COMPLETED
        CANCELLED
    }

    class Location {
        -double latitude
        -double longitude
        +distanceTo(Location other) double
    }

    class Driver {
        -String id
        -String name
        -Location location
        -DriverStatus status
        -double rating
        +updateLocation(Location loc)
        +goOnline()
        +goOffline()
    }

    class Rider {
        -String id
        -String name
        -Location location
    }

    class RideRequest {
        -String id
        -Rider rider
        -Location pickup
        -Location drop
        -long timestamp
    }

    class Trip {
        -String id
        -RideRequest request
        -Driver driver
        -TripState state
        -double fare
        +transitionTo(TripState newState)
        +calculateFare()
    }

    class MatchingStrategy {
        <<interface>>
        +findDriver(RideRequest, List~Driver~) Driver
    }

    class NearestDriverStrategy {
        +findDriver(RideRequest, List~Driver~) Driver
    }

    class HighestRatedStrategy {
        +findDriver(RideRequest, List~Driver~) Driver
    }

    class FareCalculator {
        -double baseFare
        -double perKmRate
        -double perMinRate
        -double surgeMultiplier
        +calculate(double distanceKm, double timeMin) double
    }

    class RideObserver {
        <<interface>>
        +onRideRequested(RideRequest)
        +onDriverMatched(Trip)
        +onTripStarted(Trip)
        +onTripCompleted(Trip)
        +onTripCancelled(Trip)
    }

    class RideService {
        -Map~String, Driver~ drivers
        -Map~String, Trip~ activeTrips
        -MatchingStrategy matchingStrategy
        -FareCalculator fareCalculator
        -List~RideObserver~ observers
        +registerDriver(Driver)
        +requestRide(RideRequest) Trip
        +acceptRide(String tripId)
        +startTrip(String tripId)
        +completeTrip(String tripId)
        +cancelTrip(String tripId)
    }

    RideService --> MatchingStrategy
    RideService --> FareCalculator
    RideService --> Trip
    RideService --> RideObserver
    Trip --> RideRequest
    Trip --> Driver
    Trip --> TripState
    RideRequest --> Rider
    RideRequest --> Location
    Driver --> Location
    Driver --> DriverStatus
    MatchingStrategy <|.. NearestDriverStrategy
    MatchingStrategy <|.. HighestRatedStrategy

Design Patterns

Pattern Where Why
Strategy MatchingStrategy with Nearest/HighestRated implementations Swap matching algorithm at runtime without changing RideService
State TripState enum governs valid transitions Prevents invalid state changes (e.g., COMPLETED → IN_PROGRESS)
Observer RideObserver notified on trip lifecycle events Decouple notifications, logging, analytics from core logic

Data Structures

Component Structure Why
Driver registry ConcurrentHashMap<String, Driver> O(1) lookup by driver ID
Available drivers List<Driver> filtered by status Linear scan acceptable for interview; real systems use geospatial index
Active trips ConcurrentHashMap<String, Trip> O(1) trip lookup by ID
Observers CopyOnWriteArrayList<RideObserver> Thread-safe iteration

How It All Fits Together

Here’s the complete ride flow from request to completion:

  1. Rider opens app → calls requestRide(pickup, drop)
  2. RideService creates a RideRequest and notifies observers
  3. MatchingStrategy.findDriver() searches available drivers within radius
  4. NearestDriverStrategy sorts by distance to pickup, returns closest
  5. Trip created in MATCHED state; driver notified
  6. Driver accepts → state transitions to DRIVER_EN_ROUTE
  7. Driver arrives at pickup → startTrip() → state = IN_PROGRESS
  8. Driver reaches drop → completeTrip()
  9. FareCalculator computes fare (baseFare + distancerate + timerate) * surge
  10. Trip state = COMPLETED; rider and driver notified with fare

If driver rejects: trip goes back to REQUESTED, next-nearest driver is tried.

Complete Code

Location and Core Models

Location uses the Haversine formula for distance calculation between two GPS coordinates.

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.locks.*;
import java.util.stream.*;

// ─── Enums ──────────────────────────────────────────────
enum DriverStatus { AVAILABLE, ON_TRIP, OFFLINE }
enum TripState { REQUESTED, MATCHED, DRIVER_EN_ROUTE, IN_PROGRESS, COMPLETED, CANCELLED }

// ─── Location ───────────────────────────────────────────
class Location {
    private final double latitude;
    private final double longitude;

    public Location(double latitude, double longitude) {
        this.latitude = latitude;
        this.longitude = longitude;
    }

    public double getLatitude() { return latitude; }
    public double getLongitude() { return longitude; }

    /** Haversine distance in kilometers */
    public double distanceTo(Location other) {
        double R = 6371.0; // Earth radius in km
        double dLat = Math.toRadians(other.latitude - this.latitude);
        double dLon = Math.toRadians(other.longitude - this.longitude);
        double a = Math.sin(dLat / 2) * Math.sin(dLat / 2) +
                   Math.cos(Math.toRadians(this.latitude)) *
                   Math.cos(Math.toRadians(other.latitude)) *
                   Math.sin(dLon / 2) * Math.sin(dLon / 2);
        double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
        return R * c;
    }

    @Override
    public String toString() {
        return String.format("(%.4f, %.4f)", latitude, longitude);
    }
}

// ─── Driver ─────────────────────────────────────────────
class Driver {
    private final String id;
    private final String name;
    private volatile Location location;
    private volatile DriverStatus status;
    private final double rating;

    public Driver(String id, String name, Location location, double rating) {
        this.id = id;
        this.name = name;
        this.location = location;
        this.status = DriverStatus.OFFLINE;
        this.rating = rating;
    }

    public void updateLocation(Location loc) { this.location = loc; }
    public void goOnline() { this.status = DriverStatus.AVAILABLE; }
    public void goOffline() { this.status = DriverStatus.OFFLINE; }
    public void setStatus(DriverStatus s) { this.status = s; }

    public String getId() { return id; }
    public String getName() { return name; }
    public Location getLocation() { return location; }
    public DriverStatus getStatus() { return status; }
    public double getRating() { return rating; }

    @Override
    public String toString() {
        return "Driver[" + name + " | " + status + " | rating=" + rating + "]";
    }
}

// ─── Rider ──────────────────────────────────────────────
class Rider {
    private final String id;
    private final String name;
    private Location location;

    public Rider(String id, String name, Location location) {
        this.id = id;
        this.name = name;
        this.location = location;
    }

    public String getId() { return id; }
    public String getName() { return name; }
    public Location getLocation() { return location; }
}

// ─── Ride Request ───────────────────────────────────────
class RideRequest {
    private final String id;
    private final Rider rider;
    private final Location pickup;
    private final Location drop;
    private final long timestamp;

    public RideRequest(Rider rider, Location pickup, Location drop) {
        this.id = UUID.randomUUID().toString().substring(0, 8);
        this.rider = rider;
        this.pickup = pickup;
        this.drop = drop;
        this.timestamp = System.currentTimeMillis();
    }

    public String getId() { return id; }
    public Rider getRider() { return rider; }
    public Location getPickup() { return pickup; }
    public Location getDrop() { return drop; }
    public long getTimestamp() { return timestamp; }

    public double getTripDistanceKm() {
        return pickup.distanceTo(drop);
    }
}

// ─── Trip ───────────────────────────────────────────────
class Trip {
    private final String id;
    private final RideRequest request;
    private Driver driver;
    private TripState state;
    private double fare;
    private long startTime;
    private long endTime;

    private static final Map<TripState, Set<TripState>> VALID_TRANSITIONS = Map.of(
        TripState.REQUESTED, Set.of(TripState.MATCHED, TripState.CANCELLED),
        TripState.MATCHED, Set.of(TripState.DRIVER_EN_ROUTE, TripState.CANCELLED),
        TripState.DRIVER_EN_ROUTE, Set.of(TripState.IN_PROGRESS, TripState.CANCELLED),
        TripState.IN_PROGRESS, Set.of(TripState.COMPLETED, TripState.CANCELLED),
        TripState.COMPLETED, Set.of(),
        TripState.CANCELLED, Set.of()
    );

    public Trip(RideRequest request) {
        this.id = "TRIP-" + UUID.randomUUID().toString().substring(0, 6);
        this.request = request;
        this.state = TripState.REQUESTED;
    }

    public void transitionTo(TripState newState) {
        Set<TripState> allowed = VALID_TRANSITIONS.get(this.state);
        if (allowed == null || !allowed.contains(newState)) {
            throw new IllegalStateException(
                "Invalid transition: " + this.state + " -> " + newState);
        }
        this.state = newState;
        if (newState == TripState.IN_PROGRESS) this.startTime = System.currentTimeMillis();
        if (newState == TripState.COMPLETED) this.endTime = System.currentTimeMillis();
    }

    public String getId() { return id; }
    public RideRequest getRequest() { return request; }
    public Driver getDriver() { return driver; }
    public void setDriver(Driver d) { this.driver = d; }
    public TripState getState() { return state; }
    public double getFare() { return fare; }
    public void setFare(double f) { this.fare = f; }
    public long getStartTime() { return startTime; }
    public long getEndTime() { return endTime; }

    @Override
    public String toString() {
        return "Trip[" + id + " | " + state + " | rider=" + request.getRider().getName() +
               (driver != null ? " | driver=" + driver.getName() : "") +
               " | fare=₹" + String.format("%.2f", fare) + "]";
    }
}

// ─── Matching Strategy Interface ────────────────────────
interface MatchingStrategy {
    Driver findDriver(RideRequest request, List<Driver> availableDrivers);
    String getName();
}

// ─── Nearest Driver Strategy ────────────────────────────
class NearestDriverStrategy implements MatchingStrategy {
    private final double maxRadiusKm;

    public NearestDriverStrategy(double maxRadiusKm) {
        this.maxRadiusKm = maxRadiusKm;
    }

    @Override
    public Driver findDriver(RideRequest request, List<Driver> availableDrivers) {
        Location pickup = request.getPickup();
        return availableDrivers.stream()
            .filter(d -> d.getStatus() == DriverStatus.AVAILABLE)
            .filter(d -> d.getLocation().distanceTo(pickup) <= maxRadiusKm)
            .min(Comparator.comparingDouble(d -> d.getLocation().distanceTo(pickup)))
            .orElse(null);
    }

    @Override
    public String getName() { return "NearestDriver (radius=" + maxRadiusKm + "km)"; }
}

// ─── Highest Rated Strategy ─────────────────────────────
class HighestRatedStrategy implements MatchingStrategy {
    private final double maxRadiusKm;

    public HighestRatedStrategy(double maxRadiusKm) {
        this.maxRadiusKm = maxRadiusKm;
    }

    @Override
    public Driver findDriver(RideRequest request, List<Driver> availableDrivers) {
        Location pickup = request.getPickup();
        return availableDrivers.stream()
            .filter(d -> d.getStatus() == DriverStatus.AVAILABLE)
            .filter(d -> d.getLocation().distanceTo(pickup) <= maxRadiusKm)
            .max(Comparator.comparingDouble(Driver::getRating))
            .orElse(null);
    }

    @Override
    public String getName() { return "HighestRated (radius=" + maxRadiusKm + "km)"; }
}

// ─── Fare Calculator ────────────────────────────────────
class FareCalculator {
    private final double baseFare;
    private final double perKmRate;
    private final double perMinRate;
    private double surgeMultiplier;

    public FareCalculator(double baseFare, double perKmRate, double perMinRate) {
        this.baseFare = baseFare;
        this.perKmRate = perKmRate;
        this.perMinRate = perMinRate;
        this.surgeMultiplier = 1.0;
    }

    public void setSurgeMultiplier(double multiplier) {
        this.surgeMultiplier = multiplier;
    }

    public double calculate(double distanceKm, double timeMinutes) {
        double fare = baseFare + (distanceKm * perKmRate) + (timeMinutes * perMinRate);
        return Math.round(fare * surgeMultiplier * 100.0) / 100.0;
    }

    public double getSurgeMultiplier() { return surgeMultiplier; }
}

// ─── Ride Observer Interface ────────────────────────────
interface RideObserver {
    void onRideRequested(RideRequest request);
    void onDriverMatched(Trip trip);
    void onTripStarted(Trip trip);
    void onTripCompleted(Trip trip);
    void onTripCancelled(Trip trip);
}

// ─── Logging Observer ───────────────────────────────────
class RideLoggingObserver implements RideObserver {
    @Override
    public void onRideRequested(RideRequest r) {
        System.out.println("  [EVENT] Ride requested by " + r.getRider().getName());
    }
    @Override
    public void onDriverMatched(Trip t) {
        System.out.println("  [EVENT] Driver " + t.getDriver().getName() + " matched for " + t.getId());
    }
    @Override
    public void onTripStarted(Trip t) {
        System.out.println("  [EVENT] Trip " + t.getId() + " started");
    }
    @Override
    public void onTripCompleted(Trip t) {
        System.out.println("  [EVENT] Trip " + t.getId() + " completed. Fare: ₹" +
                          String.format("%.2f", t.getFare()));
    }
    @Override
    public void onTripCancelled(Trip t) {
        System.out.println("  [EVENT] Trip " + t.getId() + " cancelled");
    }
}

// ─── Ride Service ───────────────────────────────────────
class RideService {
    private final ConcurrentHashMap<String, Driver> drivers;
    private final ConcurrentHashMap<String, Trip> activeTrips;
    private MatchingStrategy matchingStrategy;
    private final FareCalculator fareCalculator;
    private final List<RideObserver> observers;
    private final ReentrantLock lock;

    public RideService(MatchingStrategy strategy, FareCalculator fareCalculator) {
        this.drivers = new ConcurrentHashMap<>();
        this.activeTrips = new ConcurrentHashMap<>();
        this.matchingStrategy = strategy;
        this.fareCalculator = fareCalculator;
        this.observers = new CopyOnWriteArrayList<>();
        this.lock = new ReentrantLock();
    }

    public void addObserver(RideObserver observer) { observers.add(observer); }

    public void setMatchingStrategy(MatchingStrategy strategy) {
        this.matchingStrategy = strategy;
    }

    public void registerDriver(Driver driver) {
        drivers.put(driver.getId(), driver);
    }

    public Trip requestRide(RideRequest request) {
        lock.lock();
        try {
            observers.forEach(o -> o.onRideRequested(request));

            List<Driver> available = new ArrayList<>(drivers.values());
            Driver matched = matchingStrategy.findDriver(request, available);

            if (matched == null) {
                throw new RuntimeException("No drivers available nearby");
            }

            Trip trip = new Trip(request);
            trip.setDriver(matched);
            trip.transitionTo(TripState.MATCHED);
            matched.setStatus(DriverStatus.ON_TRIP);
            activeTrips.put(trip.getId(), trip);

            observers.forEach(o -> o.onDriverMatched(trip));
            return trip;
        } finally {
            lock.unlock();
        }
    }

    public void acceptRide(String tripId) {
        Trip trip = getTrip(tripId);
        trip.transitionTo(TripState.DRIVER_EN_ROUTE);
    }

    public void startTrip(String tripId) {
        Trip trip = getTrip(tripId);
        trip.transitionTo(TripState.IN_PROGRESS);
        observers.forEach(o -> o.onTripStarted(trip));
    }

    public void completeTrip(String tripId) {
        lock.lock();
        try {
            Trip trip = getTrip(tripId);
            trip.transitionTo(TripState.COMPLETED);

            double distanceKm = trip.getRequest().getTripDistanceKm();
            double timeMin = (trip.getEndTime() - trip.getStartTime()) / 60000.0;
            // Minimum 5 min for demo purposes
            timeMin = Math.max(timeMin, 5.0);

            double fare = fareCalculator.calculate(distanceKm, timeMin);
            trip.setFare(fare);

            trip.getDriver().setStatus(DriverStatus.AVAILABLE);
            activeTrips.remove(tripId);

            observers.forEach(o -> o.onTripCompleted(trip));
        } finally {
            lock.unlock();
        }
    }

    public void cancelTrip(String tripId) {
        lock.lock();
        try {
            Trip trip = getTrip(tripId);
            trip.transitionTo(TripState.CANCELLED);

            if (trip.getDriver() != null) {
                trip.getDriver().setStatus(DriverStatus.AVAILABLE);
            }
            activeTrips.remove(tripId);

            observers.forEach(o -> o.onTripCancelled(trip));
        } finally {
            lock.unlock();
        }
    }

    private Trip getTrip(String tripId) {
        Trip trip = activeTrips.get(tripId);
        if (trip == null) throw new RuntimeException("Trip not found: " + tripId);
        return trip;
    }

    public int getAvailableDriverCount() {
        return (int) drivers.values().stream()
            .filter(d -> d.getStatus() == DriverStatus.AVAILABLE)
            .count();
    }

    public void displayDrivers() {
        System.out.println("\n--- Registered Drivers ---");
        drivers.values().forEach(d -> System.out.println("  " + d));
    }
}

// ─── Main Demo ──────────────────────────────────────────
public class RideMatchingDemo {
    public static void main(String[] args) {
        System.out.println("═══════════════════════════════════════");
        System.out.println("     RIDE MATCHING - LLD DEMO         ");
        System.out.println("═══════════════════════════════════════\n");

        // Setup
        FareCalculator fareCalc = new FareCalculator(50, 12, 2); // base=50, 12/km, 2/min
        MatchingStrategy strategy = new NearestDriverStrategy(5.0); // 5km radius
        RideService service = new RideService(strategy, fareCalc);
        service.addObserver(new RideLoggingObserver());

        // Register drivers near Bangalore
        Location koramangala = new Location(12.9352, 77.6245);
        Location indiranagar = new Location(12.9716, 77.6412);
        Location whitefield = new Location(12.9698, 77.7500);
        Location hsr = new Location(12.9116, 77.6389);

        Driver d1 = new Driver("D1", "Raju", koramangala, 4.5);
        Driver d2 = new Driver("D2", "Kumar", indiranagar, 4.8);
        Driver d3 = new Driver("D3", "Suresh", whitefield, 4.2);
        Driver d4 = new Driver("D4", "Ganesh", hsr, 4.9);

        service.registerDriver(d1);
        service.registerDriver(d2);
        service.registerDriver(d3);
        service.registerDriver(d4);

        d1.goOnline(); d2.goOnline(); d3.goOnline(); d4.goOnline();
        service.displayDrivers();

        // ─── Request Ride 1: Near Koramangala ───────────────
        System.out.println("\n--- Ride Request 1: Koramangala to Indiranagar ---");
        Rider rider1 = new Rider("R1", "Priya", koramangala);
        Location pickup1 = new Location(12.9340, 77.6260);
        Location drop1 = indiranagar;

        RideRequest req1 = new RideRequest(rider1, pickup1, drop1);
        System.out.println("  Distance: " + String.format("%.2f", req1.getTripDistanceKm()) + " km");

        Trip trip1 = service.requestRide(req1);
        System.out.println("  Matched: " + trip1);

        service.acceptRide(trip1.getId());
        service.startTrip(trip1.getId());
        service.completeTrip(trip1.getId());
        System.out.println("  Final: " + trip1);

        // ─── Request Ride 2: With Surge ─────────────────────
        System.out.println("\n--- Ride Request 2: With 1.5x Surge ---");
        fareCalc.setSurgeMultiplier(1.5);

        Rider rider2 = new Rider("R2", "Arjun", hsr);
        Location pickup2 = new Location(12.9120, 77.6400);
        Location drop2 = whitefield;

        RideRequest req2 = new RideRequest(rider2, pickup2, drop2);
        System.out.println("  Distance: " + String.format("%.2f", req2.getTripDistanceKm()) + " km");

        Trip trip2 = service.requestRide(req2);
        service.acceptRide(trip2.getId());
        service.startTrip(trip2.getId());
        service.completeTrip(trip2.getId());
        System.out.println("  Final: " + trip2);

        // ─── Cancel a Ride ──────────────────────────────────
        System.out.println("\n--- Ride Request 3: Cancelled ---");
        fareCalc.setSurgeMultiplier(1.0);

        Rider rider3 = new Rider("R3", "Meera", indiranagar);
        RideRequest req3 = new RideRequest(rider3, indiranagar, koramangala);

        Trip trip3 = service.requestRide(req3);
        service.cancelTrip(trip3.getId());
        System.out.println("  Status: " + trip3.getState());

        // ─── Switch to Highest Rated Strategy ───────────────
        System.out.println("\n--- Switch to Highest Rated Strategy ---");
        service.setMatchingStrategy(new HighestRatedStrategy(10.0));

        Rider rider4 = new Rider("R4", "Vikram", koramangala);
        RideRequest req4 = new RideRequest(rider4, koramangala, whitefield);
        Trip trip4 = service.requestRide(req4);
        System.out.println("  Matched driver (highest rated): " + trip4.getDriver());
        service.cancelTrip(trip4.getId());

        // ─── No Driver Available ────────────────────────────
        System.out.println("\n--- No Driver Available Test ---");
        d1.goOffline(); d2.goOffline(); d3.goOffline(); d4.goOffline();
        try {
            Rider rider5 = new Rider("R5", "Anil", koramangala);
            service.requestRide(new RideRequest(rider5, koramangala, hsr));
        } catch (RuntimeException e) {
            System.out.println("  Expected: " + e.getMessage());
        }

        // ─── Invalid State Transition ───────────────────────
        System.out.println("\n--- Invalid State Transition ---");
        d1.goOnline();
        Rider rider6 = new Rider("R6", "Rahul", koramangala);
        Trip trip6 = service.requestRide(new RideRequest(rider6, koramangala, hsr));
        try {
            service.startTrip(trip6.getId()); // skip EN_ROUTE - invalid
        } catch (IllegalStateException e) {
            System.out.println("  Expected: " + e.getMessage());
        }
        service.cancelTrip(trip6.getId());

        System.out.println("\nAvailable drivers: " + service.getAvailableDriverCount());

        System.out.println("\n═══════════════════════════════════════");
        System.out.println("           DEMO COMPLETE               ");
        System.out.println("═══════════════════════════════════════");
    }
}
import math
import uuid
import threading
from abc import ABC, abstractmethod
from enum import Enum
from typing import Optional

# ─── Enums ──────────────────────────────────────────────
class DriverStatus(Enum):
    AVAILABLE = "AVAILABLE"
    ON_TRIP = "ON_TRIP"
    OFFLINE = "OFFLINE"

class TripState(Enum):
    REQUESTED = "REQUESTED"
    MATCHED = "MATCHED"
    DRIVER_EN_ROUTE = "DRIVER_EN_ROUTE"
    IN_PROGRESS = "IN_PROGRESS"
    COMPLETED = "COMPLETED"
    CANCELLED = "CANCELLED"

# Valid state transitions
VALID_TRANSITIONS = {
    TripState.REQUESTED: {TripState.MATCHED, TripState.CANCELLED},
    TripState.MATCHED: {TripState.DRIVER_EN_ROUTE, TripState.CANCELLED},
    TripState.DRIVER_EN_ROUTE: {TripState.IN_PROGRESS, TripState.CANCELLED},
    TripState.IN_PROGRESS: {TripState.COMPLETED, TripState.CANCELLED},
    TripState.COMPLETED: set(),
    TripState.CANCELLED: set(),
}

# ─── Location ───────────────────────────────────────────
class Location:
    def __init__(self, latitude: float, longitude: float):
        self.latitude = latitude
        self.longitude = longitude

    def distance_to(self, other: "Location") -> float:
        """Haversine distance in kilometers."""
        R = 6371.0
        d_lat = math.radians(other.latitude - self.latitude)
        d_lon = math.radians(other.longitude - self.longitude)
        a = (math.sin(d_lat / 2) ** 2 +
             math.cos(math.radians(self.latitude)) *
             math.cos(math.radians(other.latitude)) *
             math.sin(d_lon / 2) ** 2)
        c = 2 * math.atan2(math.sqrt(a), math.sqrt(1 - a))
        return R * c

    def __str__(self) -> str:
        return f"({self.latitude:.4f}, {self.longitude:.4f})"

# ─── Driver ─────────────────────────────────────────────
class Driver:
    def __init__(self, driver_id: str, name: str, location: Location, rating: float):
        self.id = driver_id
        self.name = name
        self.location = location
        self.status = DriverStatus.OFFLINE
        self.rating = rating

    def update_location(self, loc: Location): self.location = loc
    def go_online(self): self.status = DriverStatus.AVAILABLE
    def go_offline(self): self.status = DriverStatus.OFFLINE

    def __str__(self) -> str:
        return f"Driver[{self.name} | {self.status.value} | rating={self.rating}]"

# ─── Rider ──────────────────────────────────────────────
class Rider:
    def __init__(self, rider_id: str, name: str, location: Location):
        self.id = rider_id
        self.name = name
        self.location = location

# ─── Ride Request ───────────────────────────────────────
class RideRequest:
    def __init__(self, rider: Rider, pickup: Location, drop: Location):
        self.id = uuid.uuid4().hex[:8]
        self.rider = rider
        self.pickup = pickup
        self.drop = drop
        self.timestamp = 0

    @property
    def trip_distance_km(self) -> float:
        return self.pickup.distance_to(self.drop)

# ─── Trip ───────────────────────────────────────────────
class Trip:
    def __init__(self, request: RideRequest):
        self.id = f"TRIP-{uuid.uuid4().hex[:6]}"
        self.request = request
        self.driver: Optional[Driver] = None
        self.state = TripState.REQUESTED
        self.fare = 0.0
        self.start_time = 0
        self.end_time = 0

    def transition_to(self, new_state: TripState):
        allowed = VALID_TRANSITIONS.get(self.state, set())
        if new_state not in allowed:
            raise RuntimeError(f"Invalid transition: {self.state.value} -> {new_state.value}")
        self.state = new_state
        import time
        if new_state == TripState.IN_PROGRESS:
            self.start_time = time.time()
        if new_state == TripState.COMPLETED:
            self.end_time = time.time()

    def __str__(self) -> str:
        driver_info = f" | driver={self.driver.name}" if self.driver else ""
        return (f"Trip[{self.id} | {self.state.value} | "
                f"rider={self.request.rider.name}{driver_info} | fare=Rs{self.fare:.2f}]")

# ─── Matching Strategy ──────────────────────────────────
class MatchingStrategy(ABC):
    @abstractmethod
    def find_driver(self, request: RideRequest, available_drivers: list[Driver]) -> Optional[Driver]:
        pass

    @abstractmethod
    def name(self) -> str: pass

class NearestDriverStrategy(MatchingStrategy):
    def __init__(self, max_radius_km: float):
        self._max_radius = max_radius_km

    def find_driver(self, request: RideRequest, available_drivers: list[Driver]) -> Optional[Driver]:
        pickup = request.pickup
        candidates = [
            d for d in available_drivers
            if d.status == DriverStatus.AVAILABLE
            and d.location.distance_to(pickup) <= self._max_radius
        ]
        if not candidates:
            return None
        return min(candidates, key=lambda d: d.location.distance_to(pickup))

    def name(self) -> str:
        return f"NearestDriver (radius={self._max_radius}km)"

class HighestRatedStrategy(MatchingStrategy):
    def __init__(self, max_radius_km: float):
        self._max_radius = max_radius_km

    def find_driver(self, request: RideRequest, available_drivers: list[Driver]) -> Optional[Driver]:
        pickup = request.pickup
        candidates = [
            d for d in available_drivers
            if d.status == DriverStatus.AVAILABLE
            and d.location.distance_to(pickup) <= self._max_radius
        ]
        if not candidates:
            return None
        return max(candidates, key=lambda d: d.rating)

    def name(self) -> str:
        return f"HighestRated (radius={self._max_radius}km)"

# ─── Fare Calculator ────────────────────────────────────
class FareCalculator:
    def __init__(self, base_fare: float, per_km_rate: float, per_min_rate: float):
        self.base_fare = base_fare
        self.per_km_rate = per_km_rate
        self.per_min_rate = per_min_rate
        self.surge_multiplier = 1.0

    def calculate(self, distance_km: float, time_minutes: float) -> float:
        fare = self.base_fare + (distance_km * self.per_km_rate) + (time_minutes * self.per_min_rate)
        return round(fare * self.surge_multiplier, 2)

# ─── Ride Observer ──────────────────────────────────────
class RideObserver(ABC):
    @abstractmethod
    def on_ride_requested(self, request: RideRequest): pass
    @abstractmethod
    def on_driver_matched(self, trip: Trip): pass
    @abstractmethod
    def on_trip_started(self, trip: Trip): pass
    @abstractmethod
    def on_trip_completed(self, trip: Trip): pass
    @abstractmethod
    def on_trip_cancelled(self, trip: Trip): pass

class LoggingObserver(RideObserver):
    def on_ride_requested(self, r): print(f"  [EVENT] Ride requested by {r.rider.name}")
    def on_driver_matched(self, t): print(f"  [EVENT] Driver {t.driver.name} matched for {t.id}")
    def on_trip_started(self, t): print(f"  [EVENT] Trip {t.id} started")
    def on_trip_completed(self, t): print(f"  [EVENT] Trip {t.id} completed. Fare: Rs{t.fare:.2f}")
    def on_trip_cancelled(self, t): print(f"  [EVENT] Trip {t.id} cancelled")

# ─── Ride Service ───────────────────────────────────────
class RideService:
    def __init__(self, strategy: MatchingStrategy, fare_calculator: FareCalculator):
        self._drivers: dict[str, Driver] = {}
        self._active_trips: dict[str, Trip] = {}
        self._matching_strategy = strategy
        self._fare_calculator = fare_calculator
        self._observers: list[RideObserver] = []
        self._lock = threading.Lock()

    def add_observer(self, observer: RideObserver):
        self._observers.append(observer)

    def set_matching_strategy(self, strategy: MatchingStrategy):
        self._matching_strategy = strategy

    def register_driver(self, driver: Driver):
        self._drivers[driver.id] = driver

    def request_ride(self, request: RideRequest) -> Trip:
        with self._lock:
            for obs in self._observers:
                obs.on_ride_requested(request)

            available = list(self._drivers.values())
            matched = self._matching_strategy.find_driver(request, available)

            if matched is None:
                raise RuntimeError("No drivers available nearby")

            trip = Trip(request)
            trip.driver = matched
            trip.transition_to(TripState.MATCHED)
            matched.status = DriverStatus.ON_TRIP
            self._active_trips[trip.id] = trip

            for obs in self._observers:
                obs.on_driver_matched(trip)
            return trip

    def accept_ride(self, trip_id: str):
        trip = self._get_trip(trip_id)
        trip.transition_to(TripState.DRIVER_EN_ROUTE)

    def start_trip(self, trip_id: str):
        trip = self._get_trip(trip_id)
        trip.transition_to(TripState.IN_PROGRESS)
        for obs in self._observers:
            obs.on_trip_started(trip)

    def complete_trip(self, trip_id: str):
        with self._lock:
            trip = self._get_trip(trip_id)
            trip.transition_to(TripState.COMPLETED)

            distance_km = trip.request.trip_distance_km
            time_min = max(5.0, (trip.end_time - trip.start_time) / 60.0)

            fare = self._fare_calculator.calculate(distance_km, time_min)
            trip.fare = fare
            trip.driver.status = DriverStatus.AVAILABLE
            del self._active_trips[trip_id]

            for obs in self._observers:
                obs.on_trip_completed(trip)

    def cancel_trip(self, trip_id: str):
        with self._lock:
            trip = self._get_trip(trip_id)
            trip.transition_to(TripState.CANCELLED)
            if trip.driver:
                trip.driver.status = DriverStatus.AVAILABLE
            del self._active_trips[trip_id]
            for obs in self._observers:
                obs.on_trip_cancelled(trip)

    def _get_trip(self, trip_id: str) -> Trip:
        trip = self._active_trips.get(trip_id)
        if not trip:
            raise RuntimeError(f"Trip not found: {trip_id}")
        return trip

    def get_available_driver_count(self) -> int:
        return sum(1 for d in self._drivers.values() if d.status == DriverStatus.AVAILABLE)

    def display_drivers(self):
        print("\n--- Registered Drivers ---")
        for d in self._drivers.values():
            print(f"  {d}")

# ─── Main Demo ──────────────────────────────────────────
def main():
    print("═══════════════════════════════════════")
    print("     RIDE MATCHING - LLD DEMO         ")
    print("═══════════════════════════════════════\n")

    fare_calc = FareCalculator(50, 12, 2)
    strategy = NearestDriverStrategy(5.0)
    service = RideService(strategy, fare_calc)
    service.add_observer(LoggingObserver())

    koramangala = Location(12.9352, 77.6245)
    indiranagar = Location(12.9716, 77.6412)
    whitefield = Location(12.9698, 77.7500)
    hsr = Location(12.9116, 77.6389)

    d1 = Driver("D1", "Raju", koramangala, 4.5)
    d2 = Driver("D2", "Kumar", indiranagar, 4.8)
    d3 = Driver("D3", "Suresh", whitefield, 4.2)
    d4 = Driver("D4", "Ganesh", hsr, 4.9)

    for d in [d1, d2, d3, d4]:
        service.register_driver(d)
        d.go_online()

    service.display_drivers()

    print("\n--- Ride Request 1: Koramangala to Indiranagar ---")
    rider1 = Rider("R1", "Priya", koramangala)
    req1 = RideRequest(rider1, Location(12.9340, 77.6260), indiranagar)
    print(f"  Distance: {req1.trip_distance_km:.2f} km")

    trip1 = service.request_ride(req1)
    print(f"  Matched: {trip1}")
    service.accept_ride(trip1.id)
    service.start_trip(trip1.id)
    service.complete_trip(trip1.id)
    print(f"  Final: {trip1}")

    print("\n--- Ride Request 2: With 1.5x Surge ---")
    fare_calc.surge_multiplier = 1.5
    rider2 = Rider("R2", "Arjun", hsr)
    req2 = RideRequest(rider2, Location(12.9120, 77.6400), whitefield)
    print(f"  Distance: {req2.trip_distance_km:.2f} km")

    trip2 = service.request_ride(req2)
    service.accept_ride(trip2.id)
    service.start_trip(trip2.id)
    service.complete_trip(trip2.id)
    print(f"  Final: {trip2}")

    print("\n--- Ride Request 3: Cancelled ---")
    fare_calc.surge_multiplier = 1.0
    rider3 = Rider("R3", "Meera", indiranagar)
    trip3 = service.request_ride(RideRequest(rider3, indiranagar, koramangala))
    service.cancel_trip(trip3.id)
    print(f"  Status: {trip3.state.value}")

    print("\n--- Switch to Highest Rated Strategy ---")
    service.set_matching_strategy(HighestRatedStrategy(10.0))
    rider4 = Rider("R4", "Vikram", koramangala)
    trip4 = service.request_ride(RideRequest(rider4, koramangala, whitefield))
    print(f"  Matched driver (highest rated): {trip4.driver}")
    service.cancel_trip(trip4.id)

    print("\n--- No Driver Available Test ---")
    d1.go_offline(); d2.go_offline(); d3.go_offline(); d4.go_offline()
    try:
        rider5 = Rider("R5", "Anil", koramangala)
        service.request_ride(RideRequest(rider5, koramangala, hsr))
    except RuntimeError as e:
        print(f"  Expected: {e}")

    print(f"\nAvailable drivers: {service.get_available_driver_count()}")

    print("\n═══════════════════════════════════════")
    print("           DEMO COMPLETE               ")
    print("═══════════════════════════════════════")

if __name__ == "__main__":
    main()
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
#include <mutex>
#include <memory>
#include <algorithm>
#include <cmath>
#include <set>
#include <chrono>
#include <iomanip>
#include <sstream>
#include <random>
#include <stdexcept>

// ─── Enums ──────────────────────────────────────────────
enum class DriverStatus { AVAILABLE, ON_TRIP, OFFLINE };
enum class TripState { REQUESTED, MATCHED, DRIVER_EN_ROUTE, IN_PROGRESS, COMPLETED, CANCELLED };

std::string tripStateStr(TripState s) {
    switch (s) {
        case TripState::REQUESTED: return "REQUESTED";
        case TripState::MATCHED: return "MATCHED";
        case TripState::DRIVER_EN_ROUTE: return "DRIVER_EN_ROUTE";
        case TripState::IN_PROGRESS: return "IN_PROGRESS";
        case TripState::COMPLETED: return "COMPLETED";
        case TripState::CANCELLED: return "CANCELLED";
    }
    return "UNKNOWN";
}

std::string generateTripId() {
    static std::mt19937 gen(std::random_device{}());
    static std::uniform_int_distribution<int> dist(0, 15);
    static const char* hex = "0123456789abcdef";
    std::string id = "TRIP-";
    for (int i = 0; i < 6; ++i) id += hex[dist(gen)];
    return id;
}

// ─── Location ───────────────────────────────────────────
class Location {
    double lat, lon;
public:
    Location(double lat = 0, double lon = 0) : lat(lat), lon(lon) {}
    double getLatitude() const { return lat; }
    double getLongitude() const { return lon; }

    double distanceTo(const Location& other) const {
        double R = 6371.0;
        double dLat = (other.lat - lat) * M_PI / 180.0;
        double dLon = (other.lon - lon) * M_PI / 180.0;
        double a = sin(dLat/2)*sin(dLat/2) +
                   cos(lat*M_PI/180)*cos(other.lat*M_PI/180)*
                   sin(dLon/2)*sin(dLon/2);
        return R * 2 * atan2(sqrt(a), sqrt(1-a));
    }
};

// ─── Driver ─────────────────────────────────────────────
class Driver {
public:
    std::string id, name;
    Location location;
    DriverStatus status;
    double rating;

    Driver(std::string id, std::string name, Location loc, double rating)
        : id(std::move(id)), name(std::move(name)), location(loc),
          status(DriverStatus::OFFLINE), rating(rating) {}

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

// ─── Rider ──────────────────────────────────────────────
struct Rider {
    std::string id, name;
    Location location;
};

// ─── Ride Request ───────────────────────────────────────
struct RideRequest {
    std::string id;
    Rider rider;
    Location pickup, drop;

    double tripDistanceKm() const { return pickup.distanceTo(drop); }
};

// ─── Trip ───────────────────────────────────────────────
class Trip {
public:
    std::string id;
    RideRequest request;
    Driver* driver = nullptr;
    TripState state = TripState::REQUESTED;
    double fare = 0;
    long long startTime = 0, endTime = 0;

    Trip(const RideRequest& req) : id(generateTripId()), request(req) {}

    void transitionTo(TripState newState) {
        // Simplified validation
        static std::unordered_map<int, std::set<int>> valid = {
            {0, {1, 5}}, {1, {2, 5}}, {2, {3, 5}}, {3, {4, 5}}, {4, {}}, {5, {}}
        };
        auto& allowed = valid[static_cast<int>(state)];
        if (allowed.find(static_cast<int>(newState)) == allowed.end()) {
            throw std::runtime_error("Invalid transition: " + tripStateStr(state) +
                                     " -> " + tripStateStr(newState));
        }
        state = newState;
        auto now = std::chrono::system_clock::now().time_since_epoch();
        auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(now).count();
        if (newState == TripState::IN_PROGRESS) startTime = ms;
        if (newState == TripState::COMPLETED) endTime = ms;
    }
};

// ─── Matching Strategy ──────────────────────────────────
class MatchingStrategy {
public:
    virtual ~MatchingStrategy() = default;
    virtual Driver* findDriver(const RideRequest& req, std::vector<Driver*>& drivers) = 0;
    virtual std::string getName() = 0;
};

class NearestDriverStrategy : public MatchingStrategy {
    double maxRadius;
public:
    NearestDriverStrategy(double radius) : maxRadius(radius) {}

    Driver* findDriver(const RideRequest& req, std::vector<Driver*>& drivers) override {
        Driver* best = nullptr;
        double bestDist = maxRadius + 1;
        for (auto* d : drivers) {
            if (d->status != DriverStatus::AVAILABLE) continue;
            double dist = d->location.distanceTo(req.pickup);
            if (dist <= maxRadius && dist < bestDist) {
                bestDist = dist;
                best = d;
            }
        }
        return best;
    }

    std::string getName() override { return "NearestDriver"; }
};

class HighestRatedStrategy : public MatchingStrategy {
    double maxRadius;
public:
    HighestRatedStrategy(double radius) : maxRadius(radius) {}

    Driver* findDriver(const RideRequest& req, std::vector<Driver*>& drivers) override {
        Driver* best = nullptr;
        for (auto* d : drivers) {
            if (d->status != DriverStatus::AVAILABLE) continue;
            if (d->location.distanceTo(req.pickup) > maxRadius) continue;
            if (!best || d->rating > best->rating) best = d;
        }
        return best;
    }

    std::string getName() override { return "HighestRated"; }
};

// ─── Fare Calculator ────────────────────────────────────
class FareCalculator {
    double baseFare, perKmRate, perMinRate;
public:
    double surgeMultiplier = 1.0;

    FareCalculator(double base, double perKm, double perMin)
        : baseFare(base), perKmRate(perKm), perMinRate(perMin) {}

    double calculate(double distKm, double timeMin) {
        double fare = baseFare + distKm * perKmRate + timeMin * perMinRate;
        return std::round(fare * surgeMultiplier * 100.0) / 100.0;
    }
};

// ─── Ride Service ───────────────────────────────────────
class RideService {
    std::unordered_map<std::string, std::unique_ptr<Driver>> drivers;
    std::unordered_map<std::string, std::unique_ptr<Trip>> activeTrips;
    std::shared_ptr<MatchingStrategy> strategy;
    FareCalculator& fareCalc;
    std::mutex mtx;

public:
    RideService(std::shared_ptr<MatchingStrategy> strat, FareCalculator& fc)
        : strategy(std::move(strat)), fareCalc(fc) {}

    void setMatchingStrategy(std::shared_ptr<MatchingStrategy> s) { strategy = std::move(s); }

    Driver* registerDriver(std::string id, std::string name, Location loc, double rating) {
        auto d = std::make_unique<Driver>(id, name, loc, rating);
        Driver* ptr = d.get();
        drivers[id] = std::move(d);
        return ptr;
    }

    Trip* requestRide(const RideRequest& req) {
        std::lock_guard<std::mutex> lock(mtx);
        std::vector<Driver*> available;
        for (auto& [_, d] : drivers) available.push_back(d.get());

        Driver* matched = strategy->findDriver(req, available);
        if (!matched) throw std::runtime_error("No drivers available nearby");

        auto trip = std::make_unique<Trip>(req);
        trip->driver = matched;
        trip->transitionTo(TripState::MATCHED);
        matched->status = DriverStatus::ON_TRIP;

        Trip* ptr = trip.get();
        activeTrips[trip->id] = std::move(trip);
        std::cout << "  [EVENT] Driver " << matched->name << " matched\n";
        return ptr;
    }

    void acceptRide(const std::string& tripId) {
        auto* trip = getTrip(tripId);
        trip->transitionTo(TripState::DRIVER_EN_ROUTE);
    }

    void startTrip(const std::string& tripId) {
        auto* trip = getTrip(tripId);
        trip->transitionTo(TripState::IN_PROGRESS);
        std::cout << "  [EVENT] Trip " << tripId << " started\n";
    }

    void completeTrip(const std::string& tripId) {
        std::lock_guard<std::mutex> lock(mtx);
        auto* trip = getTrip(tripId);
        trip->transitionTo(TripState::COMPLETED);

        double dist = trip->request.tripDistanceKm();
        double timeMin = std::max(5.0, (trip->endTime - trip->startTime) / 60000.0);
        trip->fare = fareCalc.calculate(dist, timeMin);
        trip->driver->status = DriverStatus::AVAILABLE;

        std::cout << "  [EVENT] Trip completed. Fare: Rs" << std::fixed
                  << std::setprecision(2) << trip->fare << "\n";
        activeTrips.erase(tripId);
    }

    void cancelTrip(const std::string& tripId) {
        std::lock_guard<std::mutex> lock(mtx);
        auto* trip = getTrip(tripId);
        trip->transitionTo(TripState::CANCELLED);
        if (trip->driver) trip->driver->status = DriverStatus::AVAILABLE;
        std::cout << "  [EVENT] Trip " << tripId << " cancelled\n";
        activeTrips.erase(tripId);
    }

private:
    Trip* getTrip(const std::string& id) {
        auto it = activeTrips.find(id);
        if (it == activeTrips.end()) throw std::runtime_error("Trip not found: " + id);
        return it->second.get();
    }
};

// ─── Main Demo ──────────────────────────────────────────
int main() {
    std::cout << "=======================================\n";
    std::cout << "     RIDE MATCHING - LLD DEMO         \n";
    std::cout << "=======================================\n\n";

    FareCalculator fareCalc(50, 12, 2);
    auto strategy = std::make_shared<NearestDriverStrategy>(5.0);
    RideService service(strategy, fareCalc);

    Location koramangala(12.9352, 77.6245);
    Location indiranagar(12.9716, 77.6412);
    Location whitefield(12.9698, 77.7500);
    Location hsr(12.9116, 77.6389);

    auto* d1 = service.registerDriver("D1", "Raju", koramangala, 4.5);
    auto* d2 = service.registerDriver("D2", "Kumar", indiranagar, 4.8);
    auto* d3 = service.registerDriver("D3", "Suresh", whitefield, 4.2);
    auto* d4 = service.registerDriver("D4", "Ganesh", hsr, 4.9);

    d1->goOnline(); d2->goOnline(); d3->goOnline(); d4->goOnline();

    std::cout << "--- Ride Request 1: Koramangala to Indiranagar ---\n";
    RideRequest req1{"R1", {"R1", "Priya", koramangala}, Location(12.934, 77.626), indiranagar};
    std::cout << "  Distance: " << std::fixed << std::setprecision(2)
              << req1.tripDistanceKm() << " km\n";

    auto* trip1 = service.requestRide(req1);
    service.acceptRide(trip1->id);
    service.startTrip(trip1->id);
    service.completeTrip(trip1->id);

    std::cout << "\n--- Ride Request 2: With 1.5x Surge ---\n";
    fareCalc.surgeMultiplier = 1.5;
    RideRequest req2{"R2", {"R2", "Arjun", hsr}, Location(12.912, 77.640), whitefield};
    std::cout << "  Distance: " << req2.tripDistanceKm() << " km\n";
    auto* trip2 = service.requestRide(req2);
    service.acceptRide(trip2->id);
    service.startTrip(trip2->id);
    service.completeTrip(trip2->id);

    std::cout << "\n--- Ride Request 3: Cancelled ---\n";
    fareCalc.surgeMultiplier = 1.0;
    RideRequest req3{"R3", {"R3", "Meera", indiranagar}, indiranagar, koramangala};
    auto* trip3 = service.requestRide(req3);
    service.cancelTrip(trip3->id);

    std::cout << "\n--- Switch to Highest Rated Strategy ---\n";
    service.setMatchingStrategy(std::make_shared<HighestRatedStrategy>(10.0));
    RideRequest req4{"R4", {"R4", "Vikram", koramangala}, koramangala, whitefield};
    auto* trip4 = service.requestRide(req4);
    std::cout << "  Matched: " << trip4->driver->name << " (rating=" << trip4->driver->rating << ")\n";
    service.cancelTrip(trip4->id);

    std::cout << "\n--- No Driver Available Test ---\n";
    d1->goOffline(); d2->goOffline(); d3->goOffline(); d4->goOffline();
    try {
        RideRequest req5{"R5", {"R5", "Anil", koramangala}, koramangala, hsr};
        service.requestRide(req5);
    } catch (const std::runtime_error& e) {
        std::cout << "  Expected: " << e.what() << "\n";
    }

    std::cout << "\n=======================================\n";
    std::cout << "           DEMO COMPLETE               \n";
    std::cout << "=======================================\n";
    return 0;
}

State Transitions

stateDiagram-v2
    [*] --> REQUESTED
    REQUESTED --> MATCHED : driver found
    REQUESTED --> CANCELLED : rider cancels
    MATCHED --> DRIVER_EN_ROUTE : driver accepts
    MATCHED --> CANCELLED : driver rejects or timeout
    DRIVER_EN_ROUTE --> IN_PROGRESS : driver arrives at pickup
    DRIVER_EN_ROUTE --> CANCELLED : rider cancels
    IN_PROGRESS --> COMPLETED : reached drop
    IN_PROGRESS --> CANCELLED : emergency cancel
    COMPLETED --> [*]
    CANCELLED --> [*]

Sequence Diagram - Complete Ride Flow

sequenceDiagram
    participant Rider
    participant RS as RideService
    participant MS as MatchingStrategy
    participant Driver
    participant FC as FareCalculator

    Rider->>RS: requestRide(pickup, drop)
    RS->>MS: findDriver(request, availableDrivers)
    MS-->>RS: nearest Driver
    RS->>Driver: notify match
    RS-->>Rider: Trip (MATCHED)

    Driver->>RS: acceptRide(tripId)
    RS-->>Rider: driver en route

    Driver->>RS: startTrip(tripId)
    RS-->>Rider: trip in progress

    Driver->>RS: completeTrip(tripId)
    RS->>FC: calculate(distance, time)
    FC-->>RS: fare amount
    RS-->>Rider: trip completed with fare
    RS-->>Driver: trip completed

How to Extend

Extension Implementation
Ride sharing / pooling New PooledMatchingStrategy that groups riders going same direction
Driver ratings After trip completion, rider rates driver; update running average
ETA calculation Use real-time traffic data + distance to estimate arrival time
Geospatial index Replace linear scan with QuadTree or geohash for O(log n) proximity
Ride scheduling Allow booking a ride for future time; scheduler picks it up
Dynamic surge Compute surge from (demand / supply) ratio in each zone
Payment integration Strategy pattern for payment method (card, wallet, cash)

What Interviewers Look For

  1. ✅ Strategy pattern for matching - nearest, highest-rated, cheapest swappable
  2. ✅ State machine with valid transitions enforced
  3. ✅ Haversine formula for real distance calculation
  4. ✅ Thread-safety on ride requests and state transitions
  5. ✅ Observer pattern for lifecycle notifications
  6. ✅ Surge pricing cleanly separated in FareCalculator
  7. ✅ Error handling - no drivers, invalid transitions
  8. ✅ Clean separation - matching logic doesn’t live in RideService

Scale this design past a single process and these are the concepts it runs into:

Discussion

Newest first
You
0 / 2000

Free system design + DSA prep. If it helped you crack an interview, consider supporting.

SensAI SensAI
Beta
Listening...
Tap mic to stop voice mode

Shape what we build next

Every piece of feedback is read by the team and directly influences our roadmap.

What type of feedback?

Install SystemCraft

Add to your home screen for instant access, offline reading, and a distraction-free experience.

Offline reading Faster loads No browser tabs App-like feel

Unlock AI Features

One click to activate - no payment, no credit card. Just sign in and you're in.

AI code review and hints
SensAI chat assistant
AI mock interviews
Whiteboard analysis
100% free during early access