Cab Booking

medium · nearest-neighbour matching, ride lifecycle, fare

Brief-reported interview attribution (unverified): Uber, Lyft, Ola

How to approach an LLD round

Requirements

  • Functional: register drivers and riders, match the nearest available driver (ties to the lowest driver id), start/complete/cancel a ride, fare = $5 + $2 per unit of straight-line distance.
  • Non-functional: a driver must never be matched to two rides at once; the fare rule must be replaceable without touching the matching.
  • Out of scope: surge pricing, payments, real maps/routing.

Statement

Design a ride-hailing system. Drivers and riders have (x, y) coordinates. request_ride matches the nearest available driver to the rider (Euclidean distance; ties break to the lowest driver id). A ride moves through "requested" → "ongoing" → "completed" (or "cancelled" from "requested" only). Fare is $5 + $2 × distance(pickup, destination), rounded to 2 decimals. On completion the driver becomes available at the destination.

class RideHailing:
    def __init__(self):
    def add_driver(self, driver_id, x, y):
    def add_rider(self, rider_id, x, y):
    def request_ride(self, rider_id, dest_x, dest_y):
        # -> ride id (int, starting at 1), or None if the rider is unknown or
        #    no driver is available
    def start_ride(self, ride_id):
        # -> True if the ride was "requested" and is now "ongoing", False otherwise
    def complete_ride(self, ride_id):
        # -> fare (float) if the ride was "ongoing", None otherwise
    def cancel_ride(self, ride_id):
        # -> True if the ride was "requested" and is now cancelled, False otherwise
    def ride_status(self, ride_id):
        # -> "requested" | "ongoing" | "completed" | "cancelled" | "unknown"
    def driver_location(self, driver_id):
        # -> (x, y), or None for an unknown driver

Rules. A driver is busy from the moment a ride is requested until it is completed or cancelled; a busy driver is never matched. Cancelling frees the driver at their current location (unchanged). Fares use the pickup location recorded at request time.

Money units: fares are dollars, rounded to two decimal places; a distance of 4 returns 13.0.

Tests use explicit inputs and injected clocks/callbacks. No network, real threads or application-server execution is involved.

Class design (SOLID)

Driver (location + availability; SRP). Rider (location; SRP). Ride (rider, driver, pickup, destination, status; SRP). FareCalculator (ABC interface; the shared distance helper lives on it) + StandardFareCalculator (base + per-unit; OCP — surge pricing swaps in). RideHailing orchestrates and takes the fare calculator as a constructor argument (DIP). Pattern: Strategy (fare).

Public demo

# Public demo: run after implementing the class API above.
r = RideHailing()
r.add_driver('D1', 0, 0)
r.add_driver('D2', 10, 0)
r.add_rider('R1', 3, 0)
print(r.request_ride('R1', 3, 4))
print(r.ride_status(1))

Reference solution and hidden tests

Locked. Open the interactive editor and attempt the problem; the reference, hidden test descriptions, pattern explanation and complexity are available only after an explicit reveal.

Concurrency

Two riders requesting at once must not get the same driver: the find-nearest + mark-busy step must be atomic — one lock around request_ride (or per-driver locks taken in id order). The reference is single-threaded; the lock is described here.

Trade-offs & extensions

Straight-line distance is a simplification; real routing needs a map service behind the same FareCalculator interface. Extending: a MatchingStrategy (nearest vs fewest-cancellations) and a DriverLocation feed.

Starter code

import math
from abc import ABC, abstractmethod

class Driver:

    def __init__(self, driver_id, x, y):
        """Initialize the state described in the problem."""
        pass

class Rider:

    def __init__(self, rider_id, x, y):
        """Initialize the state described in the problem."""
        pass

class Ride:

    def __init__(self, ride_id, rider, driver, pickup, dest):
        """Initialize the state described in the problem."""
        pass

class FareCalculator(ABC):

    @staticmethod
    def distance(p1, p2):
        """Implement the return value and rules in the API contract."""
        pass

    @abstractmethod
    def fare(self, pickup, dest):
        """Implement the return value and rules in the API contract."""
        pass

class StandardFareCalculator(FareCalculator):

    def fare(self, pickup, dest):
        """Implement the return value and rules in the API contract."""
        pass

class RideHailing:

    def __init__(self, fares=None):
        """Initialize the state described in the problem."""
        pass

    def add_driver(self, driver_id, x, y):
        """Implement the return value and rules in the API contract."""
        pass

    def add_rider(self, rider_id, x, y):
        """Implement the return value and rules in the API contract."""
        pass

    def request_ride(self, rider_id, dest_x, dest_y):
        """-> ride id (int, starting at 1), or None if the rider is unknown or no driver is available"""
        pass

    def start_ride(self, ride_id):
        """-> True if the ride was "requested" and is now "ongoing", False otherwise"""
        pass

    def complete_ride(self, ride_id):
        """-> fare (float) if the ride was "ongoing", None otherwise"""
        pass

    def cancel_ride(self, ride_id):
        """-> True if the ride was "requested" and is now cancelled, False otherwise"""
        pass

    def ride_status(self, ride_id):
        '''-> "requested" | "ongoing" | "completed" | "cancelled" | "unknown"'''
        pass

    def driver_location(self, driver_id):
        """-> (x, y), or None for an unknown driver"""
        pass
Loading editor…

Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.

Return to the Python interpreter

3 comments

Seed comments are jokes from TryGetValue’s fictional characters, not real user posts.

Your posts stay in this browser, for this problem only. They are not shared with other visitors.

  1. InterviewerCharacter joke · No posting date

    Great approach. Now solve it without using the thing you just used.

  2. AntyCharacter joke · No posting date

    This problem has 8 hidden tests. I found 9 ways to fail them.

  3. The GraderCharacter joke · No posting date

    Edge case? Never met her.