Episode 9 — System Design / 9.6 — LLD Problem Solving

9.6.e — Uber/Ola (Ride Sharing System)

Problem: Design a ride-sharing system where riders request trips, the system matches them with nearby available drivers, tracks the trip lifecycle, calculates fares, and maintains ratings.

Requirements
Entities and Enums
Class Diagram
Trip Lifecycle
Sequence Flow
Complete Implementation
Usage Walkthrough
Edge Cases
Key Takeaways

Requirements

Functional Requirements

Riders can request a trip by providing pickup and drop locations.
The system finds the nearest available driver within a radius.
The driver can accept or decline the request.
Once accepted, the trip moves through states: REQUESTED -> ACCEPTED -> IN_PROGRESS -> COMPLETED.
Fare is calculated based on distance, time, and ride type (base fare + per-km + per-min).
Both rider and driver can rate each other (1-5 stars).
Riders and drivers can view their trip history.

Non-Functional Requirements

Driver matching should find the closest available driver.
Fare calculation should be extensible (surge pricing, promo codes).

Out of Scope

Real GPS tracking (we simulate with coordinates).
Payment processing.
Ride pooling / shared rides.
Mapping and route optimization.

Entities and Enums

┌────────────────────┐    ┌────────────────────┐    ┌────────────────────┐
│    TripStatus       │    │   DriverStatus      │    │    RideType         │
│────────────────────│    │────────────────────│    │────────────────────│
│  REQUESTED          │    │  AVAILABLE          │    │  ECONOMY            │
│  ACCEPTED           │    │  ON_TRIP            │    │  PREMIUM            │
│  IN_PROGRESS        │    │  OFFLINE            │    │  SUV                │
│  COMPLETED          │    └────────────────────┘    └────────────────────┘
│  CANCELLED          │
└────────────────────┘

Class Diagram

┌──────────────────────────────────┐       ┌──────────────────────────────┐
│           Rider                   │       │          Driver               │
│──────────────────────────────────│       │──────────────────────────────│
│ - id: string                      │       │ - id: string                  │
│ - name: string                    │       │ - name: string                │
│ - phone: string                   │       │ - phone: string               │
│ - location: Location              │       │ - location: Location          │
│ - rating: RatingTracker           │       │ - status: DriverStatus        │
│ - tripHistory: Trip[]             │       │ - vehicleNumber: string       │
│──────────────────────────────────│       │ - rideType: RideType          │
│ + requestTrip(pickup, drop): Trip │       │ - rating: RatingTracker       │
│ + rateDriver(trip, score): void   │       │ - tripHistory: Trip[]         │
└──────────────────────────────────┘       │──────────────────────────────│
                                            │ + accept(trip): void          │
                                            │ + decline(trip): void         │
                                            │ + startTrip(trip): void       │
                                            │ + completeTrip(trip): void    │
                                            │ + rateRider(trip, score): void│
                                            │ + goOnline(): void            │
                                            │ + goOffline(): void           │
                                            └──────────────────────────────┘

┌──────────────────────────────────┐       ┌──────────────────────────────┐
│          Location                 │       │       RatingTracker           │
│──────────────────────────────────│       │──────────────────────────────│
│ - latitude: number                │       │ - totalScore: number          │
│ - longitude: number               │       │ - count: number               │
│──────────────────────────────────│       │──────────────────────────────│
│ + distanceTo(other): number       │       │ + addRating(score): void      │
│                                   │       │ + getAverage(): number        │
└──────────────────────────────────┘       └──────────────────────────────┘

┌──────────────────────────────────┐       ┌──────────────────────────────┐
│            Trip                   │       │   FareCalculator (iface)      │
│──────────────────────────────────│       │──────────────────────────────│
│ - id: string                      │       │ + calculate(trip): number     │
│ - rider: Rider                    │       └──────────┬───────────────────┘
│ - driver: Driver | null           │                  │ implemented by
│ - pickup: Location                │       ┌──────────┴──────────┐
│ - drop: Location                  │       ▼                     ▼
│ - status: TripStatus              │  StandardFare         SurgeFare
│ - rideType: RideType              │
│ - fare: number                    │
│ - distance: number                │
│ - requestedAt: Date               │
│ - startedAt: Date | null          │
│ - completedAt: Date | null        │
│ - riderRating: number | null      │
│ - driverRating: number | null     │
└──────────────────────────────────┘

┌──────────────────────────────────────────────────────────────────────┐
│                          RideService                                  │
│──────────────────────────────────────────────────────────────────────│
│ - riders: Map<id, Rider>                                              │
│ - drivers: Map<id, Driver>                                            │
│ - trips: Map<id, Trip>                                                │
│ - fareCalculator: FareCalculator                                      │
│ - maxSearchRadiusKm: number                                           │
│──────────────────────────────────────────────────────────────────────│
│ + registerRider(name, phone): Rider                                   │
│ + registerDriver(name, phone, vehicleNum, rideType): Driver           │
│ + requestTrip(riderId, pickup, drop, rideType): Trip                  │
│ + findNearestDriver(location, rideType): Driver | null                │
│ + acceptTrip(driverId, tripId): void                                  │
│ + startTrip(tripId): void                                             │
│ + completeTrip(tripId): { fare, distance, duration }                  │
│ + cancelTrip(tripId): void                                            │
│ + rateTripByRider(tripId, score): void                                │
│ + rateTripByDriver(tripId, score): void                               │
└──────────────────────────────────────────────────────────────────────┘

Trip Lifecycle

  ┌────────────┐     driver found     ┌────────────┐
  │ REQUESTED  │ ──────────────────► │  ACCEPTED   │
  └─────┬──────┘                      └─────┬──────┘
        │                                    │
        │ no driver / rider cancels          │ driver starts ride
        │                                    │
        ▼                                    ▼
  ┌────────────┐                      ┌────────────┐
  │ CANCELLED  │                      │ IN_PROGRESS │
  └────────────┘                      └─────┬──────┘
                                             │
                                             │ driver completes ride
                                             │ (fare calculated)
                                             ▼
                                      ┌────────────┐
                                      │ COMPLETED   │
                                      └────────────┘

Sequence Flow

Complete Trip Flow

  Rider         RideService       DriverMatcher        Driver           FareCalc
    │                │                  │                  │                │
    │── requestTrip()►│                  │                  │                │
    │                │── findNearest() ─►│                  │                │
    │                │                  │── sort by dist ──►│               │
    │                │◄── driver ────────│                  │                │
    │                │── notify driver ────────────────────►│                │
    │◄── trip        │                  │                  │                │
    │   (REQUESTED)  │                  │                  │                │
    │                │                  │                  │                │
    │                │◄── acceptTrip() ────────────────────│                │
    │◄── ACCEPTED ───│                  │                  │                │
    │                │                  │                  │                │
    │                │◄── startTrip() ─────────────────────│                │
    │◄── IN_PROGRESS │                  │                  │                │
    │                │                  │                  │                │
    │                │◄── completeTrip() ──────────────────│                │
    │                │── calculate() ──────────────────────────────────────►│
    │                │◄── fare ────────────────────────────────────────────│
    │◄── COMPLETED   │                  │                  │                │
    │   { fare }     │                  │                  │                │
    │                │                  │                  │                │
    │── rateDriver() ►│                  │                  │                │
    │                │◄── rateRider() ─────────────────────│                │

Complete Implementation

Enums and Supporting Classes

// ─── Enums ──────────────────────────────────────────────

const TripStatus = Object.freeze({
  REQUESTED: 'REQUESTED',
  ACCEPTED: 'ACCEPTED',
  IN_PROGRESS: 'IN_PROGRESS',
  COMPLETED: 'COMPLETED',
  CANCELLED: 'CANCELLED',
});

const DriverStatus = Object.freeze({
  AVAILABLE: 'AVAILABLE',
  ON_TRIP: 'ON_TRIP',
  OFFLINE: 'OFFLINE',
});

const RideType = Object.freeze({
  ECONOMY: 'ECONOMY',
  PREMIUM: 'PREMIUM',
  SUV: 'SUV',
});

Location

// ─── Location ───────────────────────────────────────────

class Location {
  constructor(latitude, longitude) {
    this.latitude = latitude;
    this.longitude = longitude;
  }

  // Haversine formula for distance in km
  distanceTo(other) {
    const R = 6371; // Earth radius in km
    const dLat = this._toRad(other.latitude - this.latitude);
    const dLon = this._toRad(other.longitude - this.longitude);
    const a =
      Math.sin(dLat / 2) * Math.sin(dLat / 2) +
      Math.cos(this._toRad(this.latitude)) *
        Math.cos(this._toRad(other.latitude)) *
        Math.sin(dLon / 2) *
        Math.sin(dLon / 2);
    const c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
    return R * c;
  }

  _toRad(deg) {
    return (deg * Math.PI) / 180;
  }

  toString() {
    return `(${this.latitude.toFixed(4)}, ${this.longitude.toFixed(4)})`;
  }
}

RatingTracker

// ─── RatingTracker ──────────────────────────────────────

class RatingTracker {
  constructor() {
    this.totalScore = 0;
    this.count = 0;
  }

  addRating(score) {
    if (score < 1 || score > 5) {
      throw new Error('Rating must be between 1 and 5.');
    }
    this.totalScore += score;
    this.count++;
  }

  getAverage() {
    if (this.count === 0) return 0;
    return Math.round((this.totalScore / this.count) * 100) / 100;
  }
}

Rider and Driver

// ─── Rider ──────────────────────────────────────────────

class Rider {
  static _counter = 0;

  constructor(name, phone) {
    this.id = `RIDER-${++Rider._counter}`;
    this.name = name;
    this.phone = phone;
    this.location = null;
    this.rating = new RatingTracker();
    this.tripHistory = [];
  }

  setLocation(location) {
    this.location = location;
  }
}

// ─── Driver ─────────────────────────────────────────────

class Driver {
  static _counter = 0;

  constructor(name, phone, vehicleNumber, rideType) {
    this.id = `DRIVER-${++Driver._counter}`;
    this.name = name;
    this.phone = phone;
    this.vehicleNumber = vehicleNumber;
    this.rideType = rideType; // RideType enum
    this.location = null;
    this.status = DriverStatus.OFFLINE;
    this.rating = new RatingTracker();
    this.tripHistory = [];
  }

  setLocation(location) {
    this.location = location;
  }

  goOnline() {
    this.status = DriverStatus.AVAILABLE;
  }

  goOffline() {
    if (this.status === DriverStatus.ON_TRIP) {
      throw new Error('Cannot go offline while on a trip.');
    }
    this.status = DriverStatus.OFFLINE;
  }
}

Trip

// ─── Trip ───────────────────────────────────────────────

class Trip {
  static _counter = 0;

  constructor(rider, pickup, drop, rideType) {
    this.id = `TRIP-${++Trip._counter}`;
    this.rider = rider;
    this.driver = null;
    this.pickup = pickup;
    this.drop = drop;
    this.rideType = rideType;
    this.status = TripStatus.REQUESTED;
    this.fare = 0;
    this.distance = pickup.distanceTo(drop);
    this.requestedAt = new Date();
    this.startedAt = null;
    this.completedAt = null;
    this.riderRating = null;   // Rating given BY rider (to driver)
    this.driverRating = null;  // Rating given BY driver (to rider)
  }
}

Fare Calculators (Strategy Pattern)

// ─── Fare Calculators ───────────────────────────────────

// Rate config per ride type
const FARE_RATES = Object.freeze({
  [RideType.ECONOMY]: { baseFare: 30, perKm: 8, perMin: 1.5 },
  [RideType.PREMIUM]: { baseFare: 50, perKm: 14, perMin: 2.5 },
  [RideType.SUV]: { baseFare: 80, perKm: 18, perMin: 3.0 },
});

class StandardFareCalculator {
  calculate(trip) {
    const rates = FARE_RATES[trip.rideType];
    if (!rates) throw new Error(`Unknown ride type: ${trip.rideType}`);

    const distanceKm = trip.distance;
    const durationMin = trip.completedAt && trip.startedAt
      ? (trip.completedAt - trip.startedAt) / (1000 * 60)
      : 0;

    const fare = rates.baseFare + rates.perKm * distanceKm + rates.perMin * durationMin;
    return Math.round(fare * 100) / 100;
  }
}

class SurgeFareCalculator {
  constructor(surgeMultiplier = 1.5) {
    this.surgeMultiplier = surgeMultiplier;
    this.standard = new StandardFareCalculator();
  }

  calculate(trip) {
    const baseFare = this.standard.calculate(trip);
    return Math.round(baseFare * this.surgeMultiplier * 100) / 100;
  }
}

RideService (Controller)

// ─── RideService ────────────────────────────────────────

class RideService {
  constructor() {
    this.riders = new Map();    // riderId -> Rider
    this.drivers = new Map();   // driverId -> Driver
    this.trips = new Map();     // tripId -> Trip
    this.fareCalculator = new StandardFareCalculator();
    this.maxSearchRadiusKm = 10;
  }

  // ── Registration ──────────────────────────────────────

  registerRider(name, phone) {
    const rider = new Rider(name, phone);
    this.riders.set(rider.id, rider);
    console.log(`[REGISTER] Rider: ${rider.name} (${rider.id})`);
    return rider;
  }

  registerDriver(name, phone, vehicleNumber, rideType) {
    const driver = new Driver(name, phone, vehicleNumber, rideType);
    this.drivers.set(driver.id, driver);
    console.log(`[REGISTER] Driver: ${driver.name} (${driver.id}) - ${rideType}`);
    return driver;
  }

  // ── Driver matching ───────────────────────────────────

  findNearestDriver(pickupLocation, rideType) {
    let nearest = null;
    let minDistance = Infinity;

    for (const [, driver] of this.drivers) {
      if (driver.status !== DriverStatus.AVAILABLE) continue;
      if (driver.rideType !== rideType) continue;
      if (!driver.location) continue;

      const dist = driver.location.distanceTo(pickupLocation);
      if (dist <= this.maxSearchRadiusKm && dist < minDistance) {
        minDistance = dist;
        nearest = driver;
      }
    }

    return nearest;
  }

  // ── Trip lifecycle ────────────────────────────────────

  requestTrip(riderId, pickup, drop, rideType) {
    const rider = this.riders.get(riderId);
    if (!rider) throw new Error(`Rider ${riderId} not found.`);

    const trip = new Trip(rider, pickup, drop, rideType);

    // Find nearest driver
    const driver = this.findNearestDriver(pickup, rideType);
    if (!driver) {
      trip.status = TripStatus.CANCELLED;
      console.log(`[TRIP] ${trip.id} - No drivers available. Cancelled.`);
      return trip;
    }

    // Assign driver (auto-accept for simplicity; in real system driver gets a notification)
    trip.driver = driver;
    this.trips.set(trip.id, trip);

    console.log(
      `[TRIP] ${trip.id} requested by ${rider.name}. ` +
      `Matched with ${driver.name}. Distance: ${trip.distance.toFixed(2)} km`
    );

    return trip;
  }

  acceptTrip(driverId, tripId) {
    const trip = this.trips.get(tripId);
    if (!trip) throw new Error(`Trip ${tripId} not found.`);
    if (trip.status !== TripStatus.REQUESTED) {
      throw new Error(`Trip is ${trip.status}, cannot accept.`);
    }

    const driver = this.drivers.get(driverId);
    if (!driver) throw new Error(`Driver ${driverId} not found.`);
    if (trip.driver.id !== driverId) {
      throw new Error('This trip is not assigned to you.');
    }

    trip.status = TripStatus.ACCEPTED;
    driver.status = DriverStatus.ON_TRIP;

    console.log(`[TRIP] ${trip.id} ACCEPTED by ${driver.name}`);
  }

  startTrip(tripId) {
    const trip = this.trips.get(tripId);
    if (!trip) throw new Error(`Trip ${tripId} not found.`);
    if (trip.status !== TripStatus.ACCEPTED) {
      throw new Error(`Trip is ${trip.status}, cannot start.`);
    }

    trip.status = TripStatus.IN_PROGRESS;
    trip.startedAt = new Date();

    console.log(`[TRIP] ${trip.id} IN_PROGRESS. Rider: ${trip.rider.name}`);
  }

  completeTrip(tripId) {
    const trip = this.trips.get(tripId);
    if (!trip) throw new Error(`Trip ${tripId} not found.`);
    if (trip.status !== TripStatus.IN_PROGRESS) {
      throw new Error(`Trip is ${trip.status}, cannot complete.`);
    }

    trip.status = TripStatus.COMPLETED;
    trip.completedAt = new Date();

    // Calculate fare
    trip.fare = this.fareCalculator.calculate(trip);

    // Update driver status
    trip.driver.status = DriverStatus.AVAILABLE;

    // Add to trip history
    trip.rider.tripHistory.push(trip);
    trip.driver.tripHistory.push(trip);

    console.log(
      `[TRIP] ${trip.id} COMPLETED. ` +
      `Distance: ${trip.distance.toFixed(2)} km | Fare: $${trip.fare}`
    );

    return {
      tripId: trip.id,
      fare: trip.fare,
      distance: parseFloat(trip.distance.toFixed(2)),
      durationMin: trip.startedAt
        ? parseFloat(((trip.completedAt - trip.startedAt) / 60000).toFixed(2))
        : 0,
    };
  }

  cancelTrip(tripId) {
    const trip = this.trips.get(tripId);
    if (!trip) throw new Error(`Trip ${tripId} not found.`);
    if (trip.status === TripStatus.COMPLETED || trip.status === TripStatus.CANCELLED) {
      throw new Error(`Trip is already ${trip.status}.`);
    }

    trip.status = TripStatus.CANCELLED;

    if (trip.driver) {
      trip.driver.status = DriverStatus.AVAILABLE;
    }

    console.log(`[TRIP] ${trip.id} CANCELLED`);
  }

  // ── Ratings ───────────────────────────────────────────

  rateTripByRider(tripId, score) {
    const trip = this.trips.get(tripId);
    if (!trip) throw new Error(`Trip ${tripId} not found.`);
    if (trip.status !== TripStatus.COMPLETED) {
      throw new Error('Can only rate completed trips.');
    }
    if (trip.riderRating !== null) {
      throw new Error('Rider has already rated this trip.');
    }

    trip.riderRating = score;
    trip.driver.rating.addRating(score);

    console.log(
      `[RATING] ${trip.rider.name} rated ${trip.driver.name}: ${score}/5 ` +
      `(avg: ${trip.driver.rating.getAverage()})`
    );
  }

  rateTripByDriver(tripId, score) {
    const trip = this.trips.get(tripId);
    if (!trip) throw new Error(`Trip ${tripId} not found.`);
    if (trip.status !== TripStatus.COMPLETED) {
      throw new Error('Can only rate completed trips.');
    }
    if (trip.driverRating !== null) {
      throw new Error('Driver has already rated this trip.');
    }

    trip.driverRating = score;
    trip.rider.rating.addRating(score);

    console.log(
      `[RATING] ${trip.driver.name} rated ${trip.rider.name}: ${score}/5 ` +
      `(avg: ${trip.rider.rating.getAverage()})`
    );
  }

  // ── Fare strategy ─────────────────────────────────────

  setFareCalculator(calculator) {
    this.fareCalculator = calculator;
  }

  // ── Queries ───────────────────────────────────────────

  getRiderHistory(riderId) {
    const rider = this.riders.get(riderId);
    return rider ? rider.tripHistory : [];
  }

  getDriverHistory(driverId) {
    const driver = this.drivers.get(driverId);
    return driver ? driver.tripHistory : [];
  }
}

Usage Walkthrough

// ─── Demo ───────────────────────────────────────────────

const service = new RideService();

// Register riders and drivers
const alice = service.registerRider('Alice', '111-0001');
const bob = service.registerRider('Bob', '111-0002');

const driverRaj = service.registerDriver('Raj', '222-0001', 'KA01AB1234', RideType.ECONOMY);
const driverPriya = service.registerDriver('Priya', '222-0002', 'KA01CD5678', RideType.PREMIUM);
const driverVik = service.registerDriver('Vik', '222-0003', 'KA01EF9012', RideType.ECONOMY);

// Drivers go online and set locations
driverRaj.goOnline();
driverRaj.setLocation(new Location(12.9716, 77.5946));   // Bangalore center

driverPriya.goOnline();
driverPriya.setLocation(new Location(12.9750, 77.5900)); // Nearby

driverVik.goOnline();
driverVik.setLocation(new Location(12.9800, 77.6000));   // Slightly farther

// ── Trip 1: Alice requests economy ride ─────────────────

const pickup = new Location(12.9720, 77.5950);  // Near Raj
const drop = new Location(12.9350, 77.6150);    // ~5 km away

const trip1 = service.requestTrip(alice.id, pickup, drop, RideType.ECONOMY);
// Matched with Raj (nearest ECONOMY driver)

service.acceptTrip(driverRaj.id, trip1.id);
// [TRIP] TRIP-1 ACCEPTED by Raj

service.startTrip(trip1.id);
// [TRIP] TRIP-1 IN_PROGRESS

// ... some time passes ...

const result = service.completeTrip(trip1.id);
// [TRIP] TRIP-1 COMPLETED. Distance: 4.85 km | Fare: $68.80
console.log(result);

// Ratings
service.rateTripByRider(trip1.id, 5);
// Alice rated Raj: 5/5

service.rateTripByDriver(trip1.id, 4);
// Raj rated Alice: 4/5

// ── Trip 2: Bob requests premium ride ───────────────────

const trip2 = service.requestTrip(
  bob.id,
  new Location(12.9730, 77.5940),
  new Location(12.9500, 77.6300),
  RideType.PREMIUM
);
// Matched with Priya (only PREMIUM driver)

service.acceptTrip(driverPriya.id, trip2.id);
service.startTrip(trip2.id);
const result2 = service.completeTrip(trip2.id);
console.log(result2);

// ── Enable surge pricing ────────────────────────────────

service.setFareCalculator(new SurgeFareCalculator(2.0));

const trip3 = service.requestTrip(
  alice.id,
  new Location(12.9720, 77.5950),
  new Location(12.9350, 77.6150),
  RideType.ECONOMY
);
// Raj is now AVAILABLE again
service.acceptTrip(driverRaj.id, trip3.id);
service.startTrip(trip3.id);
const result3 = service.completeTrip(trip3.id);
console.log('Surge fare:', result3.fare); // ~2x the normal fare

// ── Trip history ────────────────────────────────────────

console.log('Alice trips:', service.getRiderHistory(alice.id).length);   // 2
console.log('Raj trips:', service.getDriverHistory(driverRaj.id).length); // 2
console.log('Raj rating:', driverRaj.rating.getAverage());               // 5.0

Edge Cases

Edge Case	How It Is Handled
No drivers available in radius	`requestTrip()` sets trip to CANCELLED
Driver goes offline during matching	`findNearestDriver()` checks AVAILABLE status
Driver tries to accept wrong trip	`acceptTrip()` validates driver assignment
Cancel after trip started	`cancelTrip()` works for any non-completed/non-cancelled trip
Rating outside 1-5 range	`RatingTracker.addRating()` throws error
Double rating by same party	Trip checks if `riderRating`/`driverRating` is already set
Zero-distance trip	Fare is just the base fare (perKm component is 0)
Driver goes offline while ON_TRIP	`goOffline()` throws error

Key Takeaways

Driver matching is the core algorithm: find the nearest available driver of the right type within a radius. In production, this uses spatial indexes (R-trees, geohashing).
Trip lifecycle is a state machine: REQUESTED -> ACCEPTED -> IN_PROGRESS -> COMPLETED, with CANCELLED as an escape state from any pre-completed state.
Strategy Pattern for fare calculation makes it trivial to add surge pricing, promotional discounts, or subscription-based pricing.
Rating system uses a simple running average tracker. In production, you might use weighted averages (recent trips count more).
Location uses the Haversine formula for real distance calculation — interviewers appreciate this level of detail.
The RideService orchestrates the entire flow, keeping Rider, Driver, and Trip as relatively simple data holders with minimal logic.

Next -> 9.6.f — Elevator System

Cohart

9.6.e — Uber/Ola (Ride Sharing System)

Table of Contents

Requirements

Functional Requirements

Non-Functional Requirements

Out of Scope

Entities and Enums

Class Diagram

Trip Lifecycle

Sequence Flow

Complete Trip Flow

Complete Implementation

Enums and Supporting Classes

Location

RatingTracker

Rider and Driver

Trip

Fare Calculators (Strategy Pattern)

RideService (Controller)

Usage Walkthrough

Edge Cases

Key Takeaways