39 — LLD: Car Rental System

Understanding the Problem

A car rental system manages a fleet of cars, lets customers book by date, and computes a final invoice based on actual usage (base rate plus per-km plus late fees). It looks similar to movie booking on the surface but the pricing logic is richer and the consistency boundary sits at the level of an individual car, not a "show".

What is a Car Rental System?

Think Avis, Hertz, Zipcar. Customers pick a car and a date range; the system reserves the car for those dates; at return time it reconciles actual usage against the reservation and issues an invoice.

Requirements

Clarifying Questions

You: Full-day granularity for bookings, or hourly?

Interviewer: Full days for booking. Late return is hourly in the invoice.

Booking index keys by LocalDate. Late fee calculation uses hour-level precision.

You: Can a customer drop off at a different location?

Interviewer: Return to pickup location only.

Single-location model. No inter-location balancing.

You: Cancellation policy?

Interviewer: Free up to 24 hours before; 20% cancellation fee after that.

We will factor cancellation into a strategy so the rule can evolve.

Final Requirements

search(location, from, to, carType) -> List<Car> — available cars in that range and location.
book(userId, carId, from, to) -> Reservation — reserve the car for all days in [from, to).
closeTrip(reservationId, actualKm, returnDate) -> Invoice — compute fee (base + per-km + late fee).
Thread-safe under concurrent reservations on the same car.

Out of scope: Maintenance scheduling, insurance, fuel charges, multi-location fleet rebalancing.

Deferred tradeoff: Day-level granularity keeps the interval structure simple; upgrading to hour-level would require an interval tree.

Core Entities and Relationships

A Car is the consistency boundary. Two users booking the same car compete; two users booking different cars run in parallel. The pricing logic wants to be extracted — hourly late fees, different rates per car type, and future discount stacking all belong behind a strategy.

Entity	Responsibility
`Car`	id, type, location, rates, status, day-level booking schedule.
`Reservation`	id, userId, carId, from, to, deposit.
`PricingStrategy`	Compute fee given duration + km + late hours.
`CancellationPolicy`	Compute cancellation fee given the cancel timestamp.
`RentalService`	Facade — search, book, closeTrip, cancel.
`Invoice`	ticketId, total, breakdown.

Why a day-level TreeMap<LocalDate, reservationId> on each car? Because overlap checks for whole-day bookings become an O(K) membership check over the requested range. Simple to reason about. An interval tree would be faster but is overkill for this scope.

Design is iterative. If hourly bookings land, the day map gets upgraded to an interval-tree structure keyed on (start, end).

Class Design

Car

State:

id, type, location, dailyRate, perKmRate, status (AVAILABLE/RESERVED/IN_TRIP/MAINTENANCE).
bookedDays: TreeMap<LocalDate, String> — date → reservationId.
Implicit lock (synchronized(this) or a ReentrantLock).

Reservation (value object)

id, userId, carId, from, to, deposit.

PricingStrategy

BigDecimal compute(Car car, Reservation r, int actualKm, long lateHours)

CancellationPolicy

BigDecimal computeCancellationFee(Reservation r, Instant cancelAt)

RentalService

cars: Map<String, Car>.
reservations: ConcurrentHashMap<String, Reservation>.
pricing: PricingStrategy, cancellation: CancellationPolicy.
Methods: search, book, cancel, closeTrip.

JavaC++TypeScript

java

public enum CarType { ECONOMY, SEDAN, SUV, LUXURY, EV }
public enum CarStatus { AVAILABLE, RESERVED, IN_TRIP, MAINTENANCE }

public class Car {
    public final String id;
    public final CarType type;
    public final String location;
    public final BigDecimal dailyRate;
    public final BigDecimal perKmRate;
    volatile CarStatus status = CarStatus.AVAILABLE;
    final TreeMap<LocalDate, String> bookedDays = new TreeMap<>();
    public Car(String id, CarType t, String loc, BigDecimal daily, BigDecimal perKm) {
        this.id=id; this.type=t; this.location=loc; this.dailyRate=daily; this.perKmRate=perKm;
    }
}

public record Reservation(String id, String userId, String carId, LocalDate from, LocalDate to, BigDecimal deposit) {}
public record Invoice(String reservationId, BigDecimal amount, int km, long lateHours) {}

public interface PricingStrategy {
    BigDecimal compute(Car car, Reservation r, int actualKm, long lateHours);
}

public class StandardPricing implements PricingStrategy {
    public BigDecimal compute(Car car, Reservation r, int km, long lateHours) {
        long days = ChronoUnit.DAYS.between(r.from(), r.to());
        BigDecimal base = car.dailyRate.multiply(BigDecimal.valueOf(days));
        BigDecimal kmCost = car.perKmRate.multiply(BigDecimal.valueOf(km));
        BigDecimal lateFee = BigDecimal.valueOf(lateHours)
            .multiply(car.dailyRate.divide(BigDecimal.valueOf(24), RoundingMode.HALF_UP));
        return base.add(kmCost).add(lateFee);
    }
}

public class RentalService {
    private final Map<String, Car> cars;
    private final Map<String, Reservation> reservations = new ConcurrentHashMap<>();
    private final PricingStrategy pricing;
    // ...

    public Optional<Reservation> book(String userId, String carId, LocalDate from, LocalDate to) { /* ... */ }
    public Invoice closeTrip(String reservationId, int actualKm, LocalDate returnDate) { /* ... */ }
}

cpp

enum class CarStatus { AVAILABLE, RESERVED, IN_TRIP, MAINTENANCE };

struct Car {
    std::string id, location;
    double dailyRate, perKmRate;
    CarStatus status = CarStatus::AVAILABLE;
    std::map<long, std::string> bookedDays;
    std::mutex mtx;
};

struct Reservation { std::string id, userId, carId; long from, to; double deposit; };

typescript

export enum CarStatus { AVAILABLE, RESERVED, IN_TRIP, MAINTENANCE }

export interface Car {
  id: string; type: string; location: string;
  dailyRate: number; perKmRate: number;
  status: CarStatus;
  bookedDays: Map<string, string>;  // ISO date -> reservationId
}

export interface Reservation { id: string; userId: string; carId: string; from: string; to: string; deposit: number; }
export interface Invoice { reservationId: string; amount: number; km: number; lateHours: number; }

export interface PricingStrategy {
  compute(car: Car, r: Reservation, actualKm: number, lateHours: number): number;
}

Design principles at play:

Strategy: PricingStrategy and CancellationPolicy — open for extension, closed for modification.
State pattern (lightweight): CarStatus transitions tracked but enforced procedurally.
Lock-per-aggregate: one lock per Car — two cars never contend.

Implementation

Core Logic: book

Validate input (from < to).
Look up the car. Reject if missing or in maintenance.
Acquire the car lock.
Walk dates from from to to - 1. If any day is already in bookedDays, abort.
Otherwise, insert all days with the new reservation id.
Create the Reservation, record it, return.

Core Logic: closeTrip

Look up the reservation. Look up the car.
Compute lateHours = max(0, hours between reservation.to and returnDate).
Compute fee via pricing strategy.
Acquire the car lock.
Remove the reservation's days from bookedDays. Reset status to AVAILABLE.
Release lock, emit invoice.

Core Logic: cancel

Look up the reservation.
Compute the cancellation fee via the policy.
Acquire the car lock.
Remove the reservation's days.
Remove the reservation from the map.
Return the fee for downstream billing.

Implementations

JavaC++TypeScript

java

public Optional<Reservation> book(String userId, String carId, LocalDate from, LocalDate to) {
    if (!from.isBefore(to)) return Optional.empty();
    Car car = cars.get(carId);
    if (car == null || car.status == CarStatus.MAINTENANCE) return Optional.empty();
    synchronized (car) {
        LocalDate d = from;
        while (d.isBefore(to)) {
            if (car.bookedDays.containsKey(d)) return Optional.empty();
            d = d.plusDays(1);
        }
        String resId = UUID.randomUUID().toString();
        Reservation r = new Reservation(resId, userId, carId, from, to, computeDeposit(car, from, to));
        d = from;
        while (d.isBefore(to)) {
            car.bookedDays.put(d, resId);
            d = d.plusDays(1);
        }
        reservations.put(resId, r);
        return Optional.of(r);
    }
}

public Invoice closeTrip(String reservationId, int actualKm, LocalDate returnDate) {
    Reservation r = reservations.get(reservationId);
    if (r == null) throw new NoSuchElementException();
    Car car = cars.get(r.carId());
    long lateHours = Math.max(0,
        ChronoUnit.HOURS.between(r.to().atStartOfDay(), returnDate.atStartOfDay()));
    BigDecimal fee = pricing.compute(car, r, actualKm, lateHours);
    synchronized (car) {
        LocalDate d = r.from();
        while (d.isBefore(r.to())) {
            car.bookedDays.remove(d);
            d = d.plusDays(1);
        }
        car.status = CarStatus.AVAILABLE;
    }
    return new Invoice(reservationId, fee, actualKm, lateHours);
}

cpp

std::optional<Reservation> RentalService::book(
    const std::string& userId, const std::string& carId, long from, long to) {
    auto it = cars.find(carId);
    if (it == cars.end() || from >= to) return std::nullopt;
    auto& car = it->second;
    std::lock_guard<std::mutex> lk(car.mtx);
    for (long d = from; d < to; d += SECONDS_PER_DAY) {
        if (car.bookedDays.count(d)) return std::nullopt;
    }
    Reservation r{newUuid(), userId, carId, from, to, computeDeposit(car, from, to)};
    for (long d = from; d < to; d += SECONDS_PER_DAY) car.bookedDays[d] = r.id;
    reservations[r.id] = r;
    return r;
}

typescript

book(userId: string, carId: string, from: Date, to: Date): Reservation | null {
  if (from >= to) return null;
  const car = this.cars.get(carId);
  if (!car) return null;
  // JS is single-threaded per tick — sync mutations are atomic.
  const days: string[] = [];
  for (let d = new Date(from); d < to; d.setDate(d.getDate() + 1)) {
    const key = d.toISOString().slice(0, 10);
    if (car.bookedDays.has(key)) return null;
    days.push(key);
  }
  const r: Reservation = {
    id: crypto.randomUUID(), userId, carId,
    from: from.toISOString(), to: to.toISOString(),
    deposit: this.computeDeposit(car, from, to),
  };
  for (const k of days) car.bookedDays.set(k, r.id);
  this.reservations.set(r.id, r);
  return r;
}

Thread Safety

Per-car lock (synchronized(car) in Java, std::mutex in C++, JS event loop in TypeScript). No cross-car operations, so two cars never compete.

For distributed scale, hash by carId onto a shard — a car never lives on two hosts. Cancellation is just a reverse of book — delete the bookedDays entries under the same lock.

Verification

Two users try to book car C1 from 2026-04-20 to 2026-04-22 concurrently:

Time	U1	U2	Car state
t=0	acquires car lock	blocks	bookedDays: `{}`
t=1	20,21 both free → writes `{20→R1, 21→R1}` → releases	-	bookedDays: `{20→R1, 21→R1}`
t=2	-	acquires lock, sees 20 present → returns empty	unchanged

closeTrip trace with late return:

Reservation: from=2026-04-20, to=2026-04-22.
Actual return: 2026-04-22 at 14:00 UTC (late by 14 hours).
lateHours = 14.
Fee = 2 × dailyRate + km × perKmRate + 14 × (dailyRate / 24).

Complete Code Implementation

JavaC++TypeScript

java

import java.math.BigDecimal;
import java.math.RoundingMode;
import java.time.*;
import java.time.temporal.ChronoUnit;
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;

public enum CarType { ECONOMY, SEDAN, SUV, LUXURY, EV }
public enum CarStatus { AVAILABLE, RESERVED, IN_TRIP, MAINTENANCE }

public class Car {
    public final String id;
    public final CarType type;
    public final String location;
    public final BigDecimal dailyRate, perKmRate;
    volatile CarStatus status = CarStatus.AVAILABLE;
    final TreeMap<LocalDate, String> bookedDays = new TreeMap<>();
    public Car(String id, CarType t, String loc, BigDecimal d, BigDecimal km) {
        this.id=id; this.type=t; this.location=loc; this.dailyRate=d; this.perKmRate=km;
    }
}

public record Reservation(String id, String userId, String carId, LocalDate from, LocalDate to, BigDecimal deposit) {}
public record Invoice(String reservationId, BigDecimal amount, int km, long lateHours) {}

public interface PricingStrategy {
    BigDecimal compute(Car car, Reservation r, int actualKm, long lateHours);
}

public class StandardPricing implements PricingStrategy {
    public BigDecimal compute(Car car, Reservation r, int km, long lateHours) {
        long days = ChronoUnit.DAYS.between(r.from(), r.to());
        BigDecimal base = car.dailyRate.multiply(BigDecimal.valueOf(days));
        BigDecimal kmCost = car.perKmRate.multiply(BigDecimal.valueOf(km));
        BigDecimal hourlyRate = car.dailyRate.divide(BigDecimal.valueOf(24), 2, RoundingMode.HALF_UP);
        BigDecimal lateFee = BigDecimal.valueOf(lateHours).multiply(hourlyRate);
        return base.add(kmCost).add(lateFee).setScale(2, RoundingMode.HALF_UP);
    }
}

public interface CancellationPolicy {
    BigDecimal fee(Reservation r, Instant cancelAt);
}

public class StandardCancellationPolicy implements CancellationPolicy {
    private final BigDecimal feePct = new BigDecimal("0.20");
    public BigDecimal fee(Reservation r, Instant cancelAt) {
        Instant pickupInstant = r.from().atStartOfDay(ZoneOffset.UTC).toInstant();
        long hoursBefore = ChronoUnit.HOURS.between(cancelAt, pickupInstant);
        if (hoursBefore >= 24) return BigDecimal.ZERO;
        return r.deposit().multiply(feePct);
    }
}

public class RentalService {
    private final Map<String, Car> cars;
    private final Map<String, Reservation> reservations = new ConcurrentHashMap<>();
    private final PricingStrategy pricing;
    private final CancellationPolicy cancellationPolicy;

    public RentalService(Map<String, Car> cars, PricingStrategy p, CancellationPolicy c) {
        this.cars = cars; this.pricing = p; this.cancellationPolicy = c;
    }

    public List<Car> search(String location, LocalDate from, LocalDate to, CarType type) {
        List<Car> out = new ArrayList<>();
        for (Car c : cars.values()) {
            if (!c.location.equals(location) || c.type != type) continue;
            synchronized (c) {
                boolean free = true;
                LocalDate d = from;
                while (d.isBefore(to)) {
                    if (c.bookedDays.containsKey(d)) { free = false; break; }
                    d = d.plusDays(1);
                }
                if (free) out.add(c);
            }
        }
        return out;
    }

    public Optional<Reservation> book(String userId, String carId, LocalDate from, LocalDate to) {
        if (!from.isBefore(to)) return Optional.empty();
        Car car = cars.get(carId);
        if (car == null || car.status == CarStatus.MAINTENANCE) return Optional.empty();
        synchronized (car) {
            LocalDate d = from;
            while (d.isBefore(to)) {
                if (car.bookedDays.containsKey(d)) return Optional.empty();
                d = d.plusDays(1);
            }
            String resId = UUID.randomUUID().toString();
            BigDecimal deposit = computeDeposit(car, from, to);
            Reservation r = new Reservation(resId, userId, carId, from, to, deposit);
            d = from;
            while (d.isBefore(to)) {
                car.bookedDays.put(d, resId);
                d = d.plusDays(1);
            }
            reservations.put(resId, r);
            return Optional.of(r);
        }
    }

    public Invoice closeTrip(String reservationId, int actualKm, LocalDate returnDate) {
        Reservation r = reservations.remove(reservationId);
        if (r == null) throw new NoSuchElementException();
        Car car = cars.get(r.carId());
        long lateHours = Math.max(0,
            ChronoUnit.HOURS.between(r.to().atStartOfDay(), returnDate.atStartOfDay()));
        BigDecimal fee = pricing.compute(car, r, actualKm, lateHours);
        synchronized (car) {
            LocalDate d = r.from();
            while (d.isBefore(r.to())) {
                car.bookedDays.remove(d);
                d = d.plusDays(1);
            }
            car.status = CarStatus.AVAILABLE;
        }
        return new Invoice(reservationId, fee, actualKm, lateHours);
    }

    public BigDecimal cancel(String reservationId, Instant cancelAt) {
        Reservation r = reservations.remove(reservationId);
        if (r == null) throw new NoSuchElementException();
        Car car = cars.get(r.carId());
        synchronized (car) {
            LocalDate d = r.from();
            while (d.isBefore(r.to())) { car.bookedDays.remove(d); d = d.plusDays(1); }
        }
        return cancellationPolicy.fee(r, cancelAt);
    }

    private BigDecimal computeDeposit(Car c, LocalDate from, LocalDate to) {
        long days = ChronoUnit.DAYS.between(from, to);
        return c.dailyRate.multiply(BigDecimal.valueOf(days));
    }
}

cpp

#include <chrono>
#include <map>
#include <memory>
#include <mutex>
#include <optional>
#include <string>
#include <unordered_map>

enum class CarStatus { AVAILABLE, RESERVED, IN_TRIP, MAINTENANCE };

struct Car {
    std::string id, location;
    double dailyRate, perKmRate;
    CarStatus status = CarStatus::AVAILABLE;
    std::map<long, std::string> bookedDays;  // epoch day -> reservationId
    std::mutex mtx;
};

struct Reservation { std::string id, userId, carId; long from, to; double deposit; };
struct Invoice { std::string reservationId; double amount; int km; long lateHours; };

class PricingStrategy {
public:
    virtual double compute(const Car& car, const Reservation& r, int km, long lateHours) = 0;
    virtual ~PricingStrategy() = default;
};

class StandardPricing : public PricingStrategy {
public:
    double compute(const Car& car, const Reservation& r, int km, long lateHours) override {
        long days = (r.to - r.from) / 86400;
        double hourly = car.dailyRate / 24.0;
        return days * car.dailyRate + km * car.perKmRate + lateHours * hourly;
    }
};

class RentalService {
    std::unordered_map<std::string, std::shared_ptr<Car>> cars;
    std::unordered_map<std::string, Reservation> reservations;
    std::mutex reservationsMtx;
    std::unique_ptr<PricingStrategy> pricing;
public:
    std::optional<Reservation> book(const std::string& u, const std::string& cid, long from, long to) {
        if (from >= to) return std::nullopt;
        auto it = cars.find(cid);
        if (it == cars.end()) return std::nullopt;
        auto& car = *it->second;
        std::lock_guard<std::mutex> lk(car.mtx);
        for (long d = from; d < to; d += 86400) if (car.bookedDays.count(d)) return std::nullopt;
        Reservation r{newUuid(), u, cid, from, to, car.dailyRate * ((to - from) / 86400)};
        for (long d = from; d < to; d += 86400) car.bookedDays[d] = r.id;
        { std::lock_guard<std::mutex> rl(reservationsMtx); reservations[r.id] = r; }
        return r;
    }
};

typescript

export class RentalService {
  private reservations = new Map<string, Reservation>();

  constructor(
    private cars: Map<string, Car>,
    private pricing: PricingStrategy,
  ) {}

  book(userId: string, carId: string, from: Date, to: Date): Reservation | null {
    if (from >= to) return null;
    const car = this.cars.get(carId);
    if (!car || car.status === CarStatus.MAINTENANCE) return null;
    const days: string[] = [];
    for (let d = new Date(from); d < to; d.setDate(d.getDate() + 1)) {
      const key = d.toISOString().slice(0, 10);
      if (car.bookedDays.has(key)) return null;
      days.push(key);
    }
    const daysCount = (to.getTime() - from.getTime()) / 86400000;
    const r: Reservation = {
      id: crypto.randomUUID(), userId, carId,
      from: from.toISOString(), to: to.toISOString(),
      deposit: car.dailyRate * daysCount,
    };
    for (const k of days) car.bookedDays.set(k, r.id);
    this.reservations.set(r.id, r);
    return r;
  }

  closeTrip(reservationId: string, actualKm: number, returnDate: Date): Invoice {
    const r = this.reservations.get(reservationId);
    if (!r) throw new Error("no reservation");
    const car = this.cars.get(r.carId)!;
    const lateHours = Math.max(0, (returnDate.getTime() - new Date(r.to).getTime()) / 3_600_000);
    const fee = this.pricing.compute(car, r, actualKm, Math.round(lateHours));
    for (let d = new Date(r.from); d < new Date(r.to); d.setDate(d.getDate() + 1)) {
      car.bookedDays.delete(d.toISOString().slice(0, 10));
    }
    car.status = CarStatus.AVAILABLE;
    this.reservations.delete(reservationId);
    return { reservationId, amount: fee, km: actualKm, lateHours: Math.round(lateHours) };
  }
}

Extensibility

1. "Hourly bookings?"

Replace TreeMap<LocalDate, String> with an interval tree keyed on (start, end). Booking becomes a classical interval-overlap check instead of a day-membership check.

Tradeoff: More complex data structure. Switching data structure changes the time complexity of book from O(days) to O(log N + K) where K is the number of overlapping intervals.

2. "Different pricing per day — weekends cost more?"

PricingStrategy queries a RateCard per date.

java

public class RateCardPricing implements PricingStrategy {
    private final RateCard rateCard;
    public BigDecimal compute(Car car, Reservation r, int km, long lateHours) {
        BigDecimal base = BigDecimal.ZERO;
        LocalDate d = r.from();
        while (d.isBefore(r.to())) {
            base = base.add(rateCard.rateFor(car, d));
            d = d.plusDays(1);
        }
        // ...
    }
}

3. "Waitlist when a car is unavailable?"

Per-car PriorityQueue<WaitlistEntry>. On cancel or closeTrip, promote the head of the queue and fire an Observer-style notification with the newly freed dates.

Tradeoff: Notifications are async and can arrive out of order. Design with idempotency so duplicate notifications do not double-book.

What is Expected at Each Level

Level	Expectations
Junior (L4)	Single boolean `isBooked` on car — loses day-level granularity. Correct happy path for immediate book/return.
Mid (L5)	Day-map index, per-car lock, Strategy for pricing. Correct late-fee math.
Senior (L5A)	Clean state transitions, explicit cancellation policy as a strategy, pricing strategy parameterized by car type, shard-friendly per-car lock design.
Staff (L6)	Fleet-wide optimization, dynamic pricing, maintenance scheduling, inter-location rebalancing, fleet utilization analytics.

39 — LLD: Car Rental System ​

Understanding the Problem ​

Requirements ​

Clarifying Questions ​

Final Requirements ​

Core Entities and Relationships ​

Class Design ​

Car ​

Reservation (value object) ​

PricingStrategy ​

CancellationPolicy ​

RentalService ​

Implementation ​

Core Logic: book ​

Core Logic: closeTrip ​

Core Logic: cancel ​

Implementations ​

Thread Safety ​

Verification ​

Complete Code Implementation ​

Extensibility ​

1. "Hourly bookings?" ​

2. "Different pricing per day — weekends cost more?" ​

3. "Waitlist when a car is unavailable?" ​

What is Expected at Each Level ​

39 — LLD: Car Rental System

Understanding the Problem

Requirements

Clarifying Questions

Final Requirements

Core Entities and Relationships

Class Design

Car

Reservation (value object)

PricingStrategy

CancellationPolicy

RentalService

Implementation

Core Logic: book

Core Logic: closeTrip

Core Logic: cancel

Implementations

Thread Safety

Verification

Complete Code Implementation

Extensibility

1. "Hourly bookings?"

2. "Different pricing per day — weekends cost more?"

3. "Waitlist when a car is unavailable?"

What is Expected at Each Level