Cab Booking
medium · nearest-neighbour matching, ride lifecycle, fare
Brief-reported interview attribution (unverified): Uber, Lyft, Ola
How to approach an LLD roundRequirements
- 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 driverRules. 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
Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.
Return to the Python interpreter