Build a Cab Booking System

Difficulty: Hard · Category: Booking System · Languages: Java 17, Python 3.11, Go 1.22, Node.js 20, TypeScript 5.x

Cab Booking System

Background

Ride-hailing platforms like Uber, Ola, and Lyft connect riders with nearby drivers in real time. At the core of every such platform lies a booking engine that handles cab registration, ride matching, state management, geospatial queries, and fare computation — all under concurrent load.

In this problem you will build the backend logic for a simplified cab booking system that manages the full ride lifecycle.

Your Task

Implement the CabBookingContract interface. Your implementation must:

1. Register cabs with driver details, vehicle info, and GPS coordinates
2. Accept ride requests from riders with pickup/drop-off locations
3. Match rides to cabs — ensuring only one cab can accept a given ride
4. Track ride state through a strict state machine (REQUESTED → ACCEPTED → COMPLETED or REQUESTED → CANCELLED)
5. Search nearby cabs using geographic distance (Haversine formula)
6. Calculate fares based on the great-circle distance between pickup and drop-off
7. Persist all data in a PostgreSQL database

Recommended infrastructure: postgres — relational storage with row-level locking suits this booking-heavy problem.

How It Works

The platform injects your chosen infrastructure SDK(s) via constructor. For example, if you select PostgreSQL:

public class MyCabBooking implements CabBookingContract {
    private final PostgresClient db;

    public MyCabBooking(PostgresClient db) {
        this.db = db;
    }

    // ... implement methods using db.*
}

See the SDK Docs tab for the full API reference of your chosen system.

Interface

public interface CabBookingContract {
    String registerCab(String driverName, String vehicleNumber,
                       String vehicleType, double currentLat, double currentLng);
    String requestRide(String riderName,
                       double pickupLat, double pickupLng,
                       double dropLat, double dropLng);
    boolean acceptRide(String rideId, String cabId);
    boolean completeRide(String rideId);
    boolean cancelRide(String rideId);
    Map<String, Object> getRideDetails(String rideId);
    boolean updateCabLocation(String cabId, double lat, double lng);
    List<Map<String, Object>> findAvailableCabs(double lat, double lng,
                                                double radiusKm);
    List<Map<String, Object>> getDriverHistory(String cabId);
    double calculateFare(String rideId);
}

Method Details

Constraints

• Cab and ride IDs must be unique (UUIDs recommended)
• Latitude: -90.0 to 90.0; Longitude: -180.0 to 180.0
• Search radius must be > 0 (kilometres)
• A ride can only be cancelled while in REQUESTED state
• A ride can only be completed while in ACCEPTED state
• Concurrent accept attempts on the same ride must be safe — exactly one succeeds
• A cab that is BUSY (has an accepted, in-progress ride) must not appear in findAvailableCabs results

Ride State Machine

REQUESTED ──→ ACCEPTED ──→ COMPLETED
    │
    └──────→ CANCELLED

Fare Calculation

fare = baseFare + (distanceKm × perKmRate)
     = 50.0    + (distanceKm × 15.0)

Distance is the great-circle distance (Haversine formula) between pickup and drop-off coordinates.

Example Walkthrough

// 1. Register a cab in Bangalore
String cabId = registerCab("Raj", "KA-01-1234", "SEDAN", 12.9716, 77.5946);

// 2. Rider requests a ride from Bangalore to Mysore
String rideId = requestRide("Alice", 12.9716, 77.5946, 12.2958, 76.6394);

// 3. Cab accepts the ride
acceptRide(rideId, cabId);   // → true

// 4. Ride completes
completeRide(rideId);        // → true

// 5. Calculate fare (~145 km)
calculateFare(rideId);       // → 50 + (145 × 15) ≈ 2225.0

// 6. Find nearby available cabs (cab is now AVAILABLE again)
findAvailableCabs(12.9716, 77.5946, 5.0);  // → [{ cabId, driverName, ... }]

Hints

1. Haversine formula — use it to compute the great-circle distance between two (lat, lng) pairs:

   a = sin²(Δlat/2) + cos(lat1) × cos(lat2) × sin²(Δlng/2)
   c = 2 × atan2(√a, √(1−a))
   distance = R × c   (R = 6371 km)

2. State machine — model ride status explicitly and validate every transition before mutating data
3. Concurrency — use row-level locking or an equivalent optimistic/pessimistic locking strategy to guarantee that only one cab can accept a given ride
4. Cab availability — toggle cab status between AVAILABLE and BUSY in sync with ride acceptance and completion
5. Indexing — add database indexes on status columns for efficient availability queries

Infrastructure your code runs against

• PostgreSQL 16

How your solution is graded

Your score combines functional correctness (40%), performance (40%) and code quality (20%).

• Target throughput: 2,500 operations/second
• Target p99 latency: 20 ms
• Load test concurrency: 4 concurrent clients
• Load test duration: 10 seconds
• Maximum error rate: 0.1%

Practice this problem

• Solve Build a Cab Booking System in the browser
• Read the walkthrough

Related LLD problems

• Build a Railway Reservation System
• Build a Load Balancer
• Build a URL Shortener