Design a Ride Sharing Service: Matching, Routing, and Real-Time State

Most ride-sharing LLD walkthroughs jump straight to the matching algorithm and call it done. That misses the harder design problems. Matching is one decision you make at the start of a trip. What’s more interesting is everything after that decision: how do you track the trip’s lifecycle through six distinct states without turning your code into a maze of booleans and if-else chains? How do you keep the driver and rider notified of each transition without coupling the trip logic to the notification mechanism?

When I reason through this problem, I find three largely independent design challenges: a state machine for the trip lifecycle, a strategy for matching, and an observer mechanism for real-time updates. Getting the boundaries between these three right is most of the work.

Requirements

Functional:

• Riders request a trip with a pickup and destination location
• The system matches the rider to an available driver using a configurable strategy (nearest, cheapest, fastest)
• The trip progresses through states: REQUESTED, ACCEPTED, DRIVER_ARRIVED, IN_PROGRESS, COMPLETED, CANCELLED
• Both driver and rider receive notifications on state transitions
• Price is calculated at completion using a configurable pricing strategy

Non-functional:

• State transitions must be validated so invalid transitions (e.g. skipping DRIVER_ARRIVED) raise an error
• Swapping the matching algorithm or pricing model should not require changing the trip or driver classes
• The notification mechanism should not couple the trip logic to any specific delivery channel

Core Entities

Location is a simple value object holding latitude and longitude. It knows how to compute the Euclidean distance to another location. Nothing else.

Driver carries a current location, a name, and an availability flag. It does not own trips. It does not calculate anything. It changes its location and availability and nothing else.

Rider is similarly minimal: a name and a current location.

RideRequest is the signal a rider sends into the system. It holds the rider, the pickup location, and the destination.

Trip is the central object. It owns the current state, the driver, the rider, the matched fare at completion, and the observer list. It exposes one method per state transition and validates that the transition is legal.

TripState is an enum with all six states. An ALLOWED_TRANSITIONS map on the Trip class encodes which transitions are valid, so the validation logic is data-driven rather than buried in conditionals.

MatchingStrategy is an abstract base class. Concrete implementations are NearestDriverStrategy, CheapestDriverStrategy, and FastestDriverStrategy. Each one takes a list of available drivers and a pickup location and returns the best driver. Callers never care which algorithm runs.

PricingStrategy is a second abstract base. PerKmPricing and SurgePricing implement it. The trip calls calculate() on the strategy when it transitions to COMPLETED.

TripObserver is an interface that anything wanting notifications must implement. DriverNotifier and RiderNotifier are concrete implementations. The trip broadcasts to all registered observers on every state change.

ASCII Class Diagram

+------------------+     +--------------------+
|   RideRequest    |     |   MatchingStrategy |  (abstract)
|------------------|     |--------------------|
| - rider: Rider   |     | + match(drivers,   |
| - pickup: Loc    |     |   pickup) -> Driver|
| - destination    |     +------+-------------+
+------------------+            |
                        +-------+-------+--------+
                        |               |        |
                  NearestDriver  CheapestDriver FastestDriver

+------------------+     +--------------------+
|   Trip           |---->|   PricingStrategy  |  (abstract)
|------------------|     |--------------------|
| - state          |     | + calculate(trip)  |
| - driver: Driver |     |   -> float         |
| - rider: Rider   |     +------+-------------+
| - observers      |            |
| + accept()       |     PerKmPricing  SurgePricing
| + driver_arrived()|
| + start()        |     +--------------------+
| + complete()     |     |   TripObserver     |  (abstract)
| + cancel()       |     |--------------------|
+------------------+     | + on_state_change  |
         |               |   (trip, new_state)|
         |               +------+-------------+
         |                      |
         +-------->  DriverNotifier  RiderNotifier

+------------------+     +------------------+
|   Driver         |     |   Rider          |
|------------------|     |------------------|
| - driver_id      |     | - rider_id       |
| - name           |     | - name           |
| - location       |     | - location       |
| - is_available   |     +------------------+
| + update_location|
+------------------+

Key Implementation

from __future__ import annotations

import math
import uuid
from abc import ABC, abstractmethod
from dataclasses import dataclass, field
from enum import Enum, auto
from typing import Optional


@dataclass
class Location:
    latitude: float
    longitude: float

    def distance_to(self, other: Location) -> float:
        """Euclidean distance — good enough for matching in LLD context."""
        return math.sqrt(
            (self.latitude - other.latitude) ** 2
            + (self.longitude - other.longitude) ** 2
        )


@dataclass
class Driver:
    driver_id: str
    name: str
    location: Location
    is_available: bool = True
    base_rate: float = 1.0  # dollars per km, used by CheapestDriverStrategy

    def update_location(self, location: Location) -> None:
        self.location = location

    def set_available(self, available: bool) -> None:
        self.is_available = available


@dataclass
class Rider:
    rider_id: str
    name: str
    location: Location


@dataclass
class RideRequest:
    rider: Rider
    pickup: Location
    destination: Location


class TripState(Enum):
    REQUESTED = auto()
    ACCEPTED = auto()
    DRIVER_ARRIVED = auto()
    IN_PROGRESS = auto()
    COMPLETED = auto()
    CANCELLED = auto()


# Valid transitions: maps each state to the set of states it can move to.
ALLOWED_TRANSITIONS: dict[TripState, set[TripState]] = {
    TripState.REQUESTED: {TripState.ACCEPTED, TripState.CANCELLED},
    TripState.ACCEPTED: {TripState.DRIVER_ARRIVED, TripState.CANCELLED},
    TripState.DRIVER_ARRIVED: {TripState.IN_PROGRESS, TripState.CANCELLED},
    TripState.IN_PROGRESS: {TripState.COMPLETED},
    TripState.COMPLETED: set(),
    TripState.CANCELLED: set(),
}


class TripObserver(ABC):
    @abstractmethod
    def on_state_change(self, trip: Trip, new_state: TripState) -> None:
        pass


class DriverNotifier(TripObserver):
    def on_state_change(self, trip: Trip, new_state: TripState) -> None:
        print(
            f"[Driver {trip.driver.name}] Trip {trip.trip_id[:8]}: "
            f"state is now {new_state.name}"
        )


class RiderNotifier(TripObserver):
    def on_state_change(self, trip: Trip, new_state: TripState) -> None:
        print(
            f"[Rider {trip.rider.name}] Trip {trip.trip_id[:8]}: "
            f"state is now {new_state.name}"
        )


class PricingStrategy(ABC):
    @abstractmethod
    def calculate(self, trip: Trip) -> float:
        pass


class PerKmPricing(PricingStrategy):
    def __init__(self, rate_per_km: float) -> None:
        self._rate = rate_per_km

    def calculate(self, trip: Trip) -> float:
        dist = trip.request.pickup.distance_to(trip.request.destination)
        return round(dist * self._rate, 2)


class SurgePricing(PricingStrategy):
    def __init__(self, base_rate: float, surge_multiplier: float) -> None:
        self._base = base_rate
        self._multiplier = surge_multiplier

    def calculate(self, trip: Trip) -> float:
        dist = trip.request.pickup.distance_to(trip.request.destination)
        return round(dist * self._base * self._multiplier, 2)


class Trip:
    def __init__(
        self,
        request: RideRequest,
        driver: Driver,
        pricing: PricingStrategy,
    ) -> None:
        self.trip_id = str(uuid.uuid4())
        self.request = request
        self.rider = request.rider
        self.driver = driver
        self._pricing = pricing
        self.state = TripState.REQUESTED
        self._observers: list[TripObserver] = []
        self.fare: Optional[float] = None

    def add_observer(self, observer: TripObserver) -> None:
        self._observers.append(observer)

    def _transition(self, new_state: TripState) -> None:
        allowed = ALLOWED_TRANSITIONS[self.state]
        if new_state not in allowed:
            raise ValueError(
                f"Cannot transition from {self.state.name} to {new_state.name}."
            )
        self.state = new_state
        for observer in self._observers:
            observer.on_state_change(self, new_state)

    def accept(self) -> None:
        self.driver.set_available(False)
        self._transition(TripState.ACCEPTED)

    def driver_arrived(self) -> None:
        self._transition(TripState.DRIVER_ARRIVED)

    def start(self) -> None:
        self._transition(TripState.IN_PROGRESS)

    def complete(self) -> None:
        self.fare = self._pricing.calculate(self)
        self._transition(TripState.COMPLETED)
        self.driver.set_available(True)

    def cancel(self) -> None:
        self._transition(TripState.CANCELLED)
        self.driver.set_available(True)


class MatchingStrategy(ABC):
    @abstractmethod
    def match(
        self, drivers: list[Driver], pickup: Location
    ) -> Optional[Driver]:
        pass


class NearestDriverStrategy(MatchingStrategy):
    def match(
        self, drivers: list[Driver], pickup: Location
    ) -> Optional[Driver]:
        available = [d for d in drivers if d.is_available]
        if not available:
            return None
        return min(available, key=lambda d: d.location.distance_to(pickup))


class CheapestDriverStrategy(MatchingStrategy):
    """Picks the driver with the lowest base rate per km."""

    def match(
        self, drivers: list[Driver], pickup: Location
    ) -> Optional[Driver]:
        available = [d for d in drivers if d.is_available]
        if not available:
            return None
        return min(available, key=lambda d: d.base_rate)


class FastestDriverStrategy(MatchingStrategy):
    """
    'Fastest' is approximated by nearest driver.
    A real implementation would call a routing API with live traffic data.
    """

    def match(
        self, drivers: list[Driver], pickup: Location
    ) -> Optional[Driver]:
        return NearestDriverStrategy().match(drivers, pickup)


class RideSharingService:
    def __init__(
        self,
        matching_strategy: MatchingStrategy,
        pricing_strategy: PricingStrategy,
    ) -> None:
        self._drivers: list[Driver] = []
        self._matching = matching_strategy
        self._pricing = pricing_strategy

    def register_driver(self, driver: Driver) -> None:
        self._drivers.append(driver)

    def request_ride(self, request: RideRequest) -> Trip:
        driver = self._matching.match(self._drivers, request.pickup)
        if driver is None:
            raise RuntimeError("No drivers available.")
        trip = Trip(request=request, driver=driver, pricing=self._pricing)
        trip.add_observer(DriverNotifier())
        trip.add_observer(RiderNotifier())
        trip.accept()
        return trip

Design Decisions and Trade-offs

State pattern vs. enum plus transition table.

The full State pattern (a class per state, each responsible for its own transition logic) is powerful when states have meaningfully different behavior. Here, each state mostly differs in which transitions are legal. The logic does not vary per state, only the permission set does. Using an ALLOWED_TRANSITIONS dict with an enum keeps the machine flat, readable, and easy to modify. Adding a new state is one enum value and one dict entry. With the full State pattern it would be a new class plus wiring. The enum approach is the right choice here.

Observer for notifications.

The trip does not know whether notifications go to push notifications, SMS, WebSocket broadcasts, or logs. It just calls on_state_change() on each registered observer. This means the notification channel is a plug-in. In a test you register a mock observer that records calls. In production you register real notifiers. The trip class never changes. This is the canonical Observer pattern motivation: decouple event producers from event consumers.

Driver availability as a flag on Driver.

A driver’s availability is set to False on accept() and reset to True on complete() or cancel(). This is a simple flag mutation and it is intentional. The alternative, storing availability in the service and keeping Driver immutable, makes it harder for the matching strategy to inspect availability since it only receives Driver objects. Keeping the flag on Driver keeps the matching logic clean.

FastestDriverStrategy delegating to NearestDriverStrategy.

This is honest about what the LLD model can actually compute. True ETA requires a routing API with live traffic data, which is out of scope for this class design. The comment in the code says so explicitly. The strategy exists as a placeholder so that the interface is complete and a real implementation can replace the internals later without any changes to RideSharingService or Trip.

Why calculate fare at completion, not at request time?

Fare calculation at request time is an estimate. The actual trip might take a different route, encounter surge pricing conditions that change mid-ride, or be cancelled before starting. Calculating at complete() means the fare is based on the actual trip, not a prediction. PricingStrategy.calculate() receives the whole Trip object, so it has access to whatever data it needs: request locations, driver, timestamps if you add them.

Real-time location updates.

The update_location() method on Driver is the entry point for GPS updates. In a real system, location updates arrive continuously from the driver’s mobile app. The matching strategy runs against the latest snapshot of driver locations. This LLD does not model the update frequency or the data pipeline behind it because that is a distributed systems concern, not a class design concern. The key point is that the class model supports location updates without any structural change.

What I’d Extend Next

A TripHistory that records every state transition with a timestamp, a RatingService that allows riders and drivers to rate each other after completion, and a CancellationPolicy that determines whether a cancellation fee applies based on how far through the trip lifecycle the cancellation happened. Each of these is a clean addition that plugs in around the existing boundaries.

---

If you’d approach the state machine differently or want to argue about where driver availability should live, I’d genuinely like to hear it. Reach out on Twitter or LinkedIn.