On this page

Design a Car Rental System

Car rental is a booking problem with a twist that catches many candidates out. A hotel room or a cinema seat is booked for one slot. A rental car is booked for a range of dates, and "is this car free?" is a question about intervals, not a status flag. Get that wrong and every other part of the design wobbles. You end up with an isAvailable boolean that can't answer "free next weekend?", or with a nightly job that flips flags and races with live bookings.

This page also has a classic modelling question at its centre: should Suv, Sedan and Truck be subclasses of Vehicle? Interviewers ask it on purpose, and the answer they want is a reasoned "no, mostly", explained.

The other topics are pricing rules that stack, late-return fees (which are all about time, so the clock must be injectable), and the race that every booking system has: two customers clicking "reserve" on the last SUV at the same moment. If you've read hotel management, this is its date-range cousin. The upcoming meeting room booking study solves the same interval problem with minutes instead of days.

1. Requirements

Clarifying questions

QuestionAnswer we assumeConsequence
What does the customer book, a specific car or a type?A type at a branch ("an SUV at SFO"). The system picks the carBooking searches the branch's fleet of that type
Date or time granularity?Whole days, with handover at 10:00DateRange of LocalDate, half-open
Can a car be picked up the day it's returned?YesRanges are [start, end), so touching ranges don't overlap
How is the price built?Daily rate, a weekend surcharge, and a long-rental discountAn ordered list of pricing rules
What if the car comes back late?30 minutes grace, then a fee per started hour, capped at one day's rate per 24 hoursA LateFeePolicy, measured against an injected clock
What if the customer never shows up?The reservation becomes NO_SHOW the next day and the car is releasedA daily sweep
One-way rentals, upgrades, licence checks?Not at first. They come as extensionsThe design must absorb them
Payments, damage inspection, loyalty?Out of scope

Functional requirements

  1. Branches have fleets. Each vehicle has a type that sets its rates.
  2. Search for free vehicles of a type at a branch over a date range.
  3. Quote and reserve. Reserving picks a free vehicle and blocks its dates.
  4. Cancel before pickup, which frees the dates.
  5. Pick up on a date within the range, and return. Late returns are charged, and early returns free the remaining days.
  6. Unclaimed reservations become no-shows.

Non-functional requirements

  • Never double-book a vehicle, even under concurrent requests.
  • Availability checks shouldn't scan a vehicle's whole history: O(log n) per car.
  • Pricing and late-fee rules must be swappable without editing the booking code.
  • Time is injected, so "returned 105 minutes late" can be tested at any time of day.

2. Entities, and the hierarchy question

EntityKindNotes
BranchIdentifier hereA real system adds address and hours. We key fleets by branch id
VehicleTypeValue object, Type Objectname, daily rate, hourly late rate
VehicleEntityid, home branch, type, and its calendar of reservations
DateRangeValue object[start, end), overlaps, days
ReservationEntitycustomer, vehicle, range, quote, status, late fee
PricingRuleStrategyadds one optional line to a quote
PricingEngineDomain serviceruns the rules in order
Quote / PriceLineValue objectsan itemised price
LateFeePolicyStrategylateness and type give cents
RentalServiceFacadesearch, quote, reserve, lifecycle operations

Vehicle subclasses versus a vehicle type

The tempting design is abstract class Vehicle with Economy, Suv, Luxury and Truck subclasses. Ask what the subclasses would do differently. Mostly nothing. They differ in data: the rate, seats, luggage space, required licence. Data differences belong in data. That's the Type Object pattern: one Vehicle class pointing to a VehicleType instance.

Subclass per categoryVehicleType object
Adding "Electric SUV"New class, recompile, redeployNew row of data
Changing the SUV rateCode change, or a static field that's awkward to testEdit the type
Fleet manager UI to create categoriesImpossible without codeNatural
Category-specific behaviour (a truck needs a tachograph check)NaturalNeeds a strategy or rule keyed by type

So: use a type object by default, and reach for a subclass or strategy only for genuine behaviour differences. Even the truck licence case is better served by a rule table (extension 2) than by a Truck subclass, because the rule belongs to the rental process, not the vehicle. A subclass hierarchy does earn its place when vehicle kinds have different structure the system acts on. A rental company that also rents boats (hull id, mooring, skipper requirement) is an example. Saying this aloud scores well because it shows you know both tools and when each one applies.

Where availability lives

Availability isn't a field. A car is "available" only relative to a date range. So each Vehicle owns a calendar: its active reservations, sorted by start date. Because a car's bookings never overlap, sorting by start also sorts by end. That gives a neat O(log n) check: find the last booking that starts before the requested end. If that one doesn't overlap, nothing does, because every earlier booking ends before it starts.

classDiagram
    class RentalService {
        +addType(type)
        +addVehicle(id, branchId, typeName) Vehicle
        +search(branchId, typeName, range) List~Vehicle~
        +quote(customerId, branchId, typeName, range) Quote
        +reserve(customerId, branchId, typeName, range) Reservation
        +cancel(reservationId)
        +pickUp(reservationId)
        +returnVehicle(reservationId) long
        +markNoShows() int
    }
    class Vehicle {
        +id
        +branchId
        -calendar TreeMap
        +isFree(range) boolean
        +tryBook(reservation) boolean
        +release(reservation)
    }
    class VehicleType {
        +name
        +dailyRateCents
        +hourlyLateCents
    }
    class DateRange {
        +start
        +end
        +overlaps(other) boolean
        +days() long
    }
    class Reservation {
        +id
        +customerId
        +range
        +quote
        -status ReservationStatus
        -lateFeeCents
    }
    class PricingEngine {
        -rules List~PricingRule~
        +quote(request) Quote
    }
    class PricingRule {
        <<interface>>
        +apply(request, runningTotal) PriceLine
    }
    class LateFeePolicy {
        <<interface>>
        +feeCents(late, type) long
    }
    class Quote {
        +lines List~PriceLine~
        +total() long
    }
    RentalService o-- "*" Vehicle
    RentalService o-- "*" Reservation
    RentalService --> PricingEngine
    RentalService --> LateFeePolicy
    Vehicle --> VehicleType
    Vehicle o-- "*" Reservation : calendar
    Reservation --> Vehicle
    Reservation *-- DateRange
    Reservation *-- Quote
    PricingEngine o-- "*" PricingRule
    PricingRule <|.. DailyRate
    PricingRule <|.. WeekendSurcharge
    PricingRule <|.. LongRentalDiscount
    LateFeePolicy <|.. HourlyLateFee

3. Lifecycles

Reservation

stateDiagram-v2
    [*] --> RESERVED : dates blocked on one vehicle
    RESERVED --> ACTIVE : picked up within the range
    RESERVED --> CANCELLED : customer cancels, dates freed
    RESERVED --> NO_SHOW : start date passed, dates freed
    ACTIVE --> COMPLETED : returned, late fee computed, dates freed
    COMPLETED --> [*]
    CANCELLED --> [*]
    NO_SHOW --> [*]

Every arrow out of RESERVED or ACTIVE also removes the reservation from the vehicle's calendar. That's the invariant to guard: the calendar holds exactly the reservations that are RESERVED or ACTIVE. Both changes happen under the same lock, so nobody can observe one without the other.

Vehicle

The car's own lifecycle is coarse and independent of bookings:

stateDiagram-v2
    [*] --> IN_SERVICE : added to a branch fleet
    IN_SERVICE --> MAINTENANCE : scheduled service
    MAINTENANCE --> IN_SERVICE : cleared
    IN_SERVICE --> RETIRED : sold or written off
    RETIRED --> [*]

The core code doesn't model this, to stay short. A maintenance window is just another entry in the calendar (a block with no customer), and you'd add it the same way as a reservation. Keeping "booked" out of the vehicle's state is the important part.

4. Key flows

Reserve

sequenceDiagram
    participant C as Customer
    participant S as RentalService
    participant P as PricingEngine
    participant V1 as Vehicle suv0
    participant V2 as Vehicle suv1
    C->>S: reserve SUV at SFO, Dec 4 to Dec 7
    S->>P: quote request
    P-->>S: daily 27000, weekend 4500
    S->>V1: tryBook
    V1->>V1: lock, lowerEntry Dec 7 overlaps, unlock
    V1-->>S: false
    S->>V2: tryBook
    V2->>V2: lock, free, insert, unlock
    V2-->>S: true
    S-->>C: Reservation R1 on suv1, 31500

Return late

sequenceDiagram
    participant A as Counter agent
    participant S as RentalService
    participant K as Clock
    participant F as LateFeePolicy
    participant V as Vehicle
    A->>S: returnVehicle R1
    S->>K: now
    K-->>S: Dec 7 11:45
    S->>V: lock
    S->>S: due Dec 7 10:00, late 105 min
    S->>F: feeCents 105 min, ECONOMY
    F-->>S: 2 started hours, 2000
    S->>V: COMPLETED, release from calendar, unlock
    S-->>A: late fee 2000

Two customers, one car

sequenceDiagram
    participant A as Customer A
    participant V as Vehicle suv0 lock
    participant B as Customer B
    A->>V: tryBook Dec 4 to Dec 7
    B->>V: tryBook Dec 5 to Dec 8, waits
    V-->>A: free, inserted, true
    V-->>B: lock acquired, overlaps Dec 4 to Dec 7, false
    Note over B: B tries the next SUV, or gets sold out

5. Patterns, and why

PatternWhereWhyRejected alternative
Type ObjectVehicleTypeCategories differ in data, not behaviourA subclass per category (section 2)
Strategy, as an ordered listPricingRules in PricingEnginePromotions come and go, and each one is a class with one jobOne computePrice with every rule inline
StrategyLateFeePolicyLate-fee rules differ by market and get tunedConstants in returnVehicle
Value objectsDateRange, Quote, PriceLineImmutability, and validation in one place (start before end)Pairs of loose dates passed around
Injected clockSupplier<LocalDateTime>Late fees and no-shows are about timeLocalDateTime.now() inside the service
FacadeRentalServiceCalendar and status change together, under one lockCallers editing Vehicle calendars

Why a list of rules and not a Decorator chain? Both work. A list gives an itemised quote for free, since each rule contributes a labelled line, and customers and regulators both want to see "weekend +25%". Decorators compose a number and lose the breakdown unless each layer also records a line. The cost of the list is that order is implicit in the list's construction. Make that explicit in code review, because "discount before or after surcharges?" is a business question. Here, the discount sees the surcharges, because it reads runningTotal.

Why isn't Reservation using the State pattern? Five states with simple guarded transitions, and no behaviour that varies by state beyond "is this allowed". An enum and a require helper are clearer. See State for when it's worth it.

6. The code

Complete and runnable, each ending in asserts. The Java main includes the concurrent last-car test. Save the Python as car_rental.py for the tests in section 9.

import java.time.*;
import java.time.temporal.ChronoUnit;
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicLong;
import java.util.function.Supplier;

/** Half-open [start, end): returning on the 7th and picking up on the 7th do not clash. */
record DateRange(LocalDate start, LocalDate end) {
    DateRange {
        if (!start.isBefore(end)) throw new RentalException("range must be at least one day");
    }
    boolean overlaps(DateRange o) { return start.isBefore(o.end) && o.start.isBefore(end); }
    long days() { return ChronoUnit.DAYS.between(start, end); }
}

/** Type Object: categories are data, not subclasses. */
record VehicleType(String name, long dailyRateCents, long hourlyLateCents) {}

record PriceLine(String label, long cents) {}

record Quote(List<PriceLine> lines) {
    long total() { return lines.stream().mapToLong(PriceLine::cents).sum(); }
}

record RentalRequest(String customerId, String branchId, String returnBranchId, VehicleType type, DateRange range) {}

enum ReservationStatus { RESERVED, ACTIVE, COMPLETED, CANCELLED, NO_SHOW }

class RentalException extends RuntimeException {
    RentalException(String message) { super(message); }
}

final class Reservation {
    final String id, customerId; final Vehicle vehicle; final DateRange range; final Quote quote;
    // guarded by the vehicle's monitor
    ReservationStatus status = ReservationStatus.RESERVED;
    long lateFeeCents;
    Reservation(String id, String customerId, Vehicle vehicle, DateRange range, Quote quote) {
        this.id = id; this.customerId = customerId; this.vehicle = vehicle; this.range = range; this.quote = quote;
    }
    ReservationStatus status() { synchronized (vehicle) { return status; } }
    long lateFeeCents() { synchronized (vehicle) { return lateFeeCents; } }
}

final class Vehicle {
    final String id, branchId; final VehicleType type;
    private final TreeMap<LocalDate, Reservation> calendar = new TreeMap<>();   // guarded by this
    Vehicle(String id, String branchId, VehicleType type) { this.id = id; this.branchId = branchId; this.type = type; }

    /** Bookings never overlap, so only the latest one starting before r.end can clash: O(log n). */
    synchronized boolean isFree(DateRange r) {
        Map.Entry<LocalDate, Reservation> before = calendar.lowerEntry(r.end());
        return before == null || !before.getValue().range.overlaps(r);
    }

    synchronized boolean tryBook(Reservation res) {         // check and insert under one lock
        if (!isFree(res.range)) return false;
        calendar.put(res.range.start(), res);
        return true;
    }

    synchronized void release(Reservation res) { calendar.remove(res.range.start(), res); }
}

interface PricingRule { Optional<PriceLine> apply(RentalRequest req, long runningTotal); }

final class DailyRate implements PricingRule {
    public Optional<PriceLine> apply(RentalRequest r, long running) {
        long days = r.range().days();
        return Optional.of(new PriceLine(days + " days x " + r.type().dailyRateCents(), days * r.type().dailyRateCents()));
    }
}

final class WeekendSurcharge implements PricingRule {
    private final int percent;
    WeekendSurcharge(int percent) { this.percent = percent; }
    public Optional<PriceLine> apply(RentalRequest r, long running) {
        long weekendDays = r.range().start().datesUntil(r.range().end())
            .filter(d -> d.getDayOfWeek() == DayOfWeek.SATURDAY || d.getDayOfWeek() == DayOfWeek.SUNDAY).count();
        if (weekendDays == 0) return Optional.empty();
        return Optional.of(new PriceLine("weekend +" + percent + "%", weekendDays * r.type().dailyRateCents() * percent / 100));
    }
}

final class LongRentalDiscount implements PricingRule {
    private final int minDays, percent;
    LongRentalDiscount(int minDays, int percent) { this.minDays = minDays; this.percent = percent; }
    public Optional<PriceLine> apply(RentalRequest r, long running) {
        if (r.range().days() < minDays) return Optional.empty();
        return Optional.of(new PriceLine(minDays + "+ days -" + percent + "%", -running * percent / 100));
    }
}

final class PricingEngine {
    private final List<PricingRule> rules;                   // order matters: discounts see the surcharges
    PricingEngine(List<PricingRule> rules) { this.rules = List.copyOf(rules); }
    Quote quote(RentalRequest req) {
        List<PriceLine> lines = new ArrayList<>(); long running = 0;
        for (PricingRule rule : rules) {
            Optional<PriceLine> line = rule.apply(req, running);
            if (line.isPresent()) { lines.add(line.get()); running += line.get().cents(); }
        }
        return new Quote(lines);
    }
}

interface LateFeePolicy { long feeCents(Duration late, VehicleType type); }

/** Free within the grace period. Then per started hour, at most one day's rate per 24 hours. */
final class HourlyLateFee implements LateFeePolicy {
    private final Duration grace;
    HourlyLateFee(Duration grace) { this.grace = grace; }
    public long feeCents(Duration late, VehicleType t) {
        if (late.compareTo(grace) <= 0) return 0;
        long minutes = late.toMinutes(), fullDays = minutes / 1440;
        long startedHours = (minutes % 1440 + 59) / 60;
        return fullDays * t.dailyRateCents() + Math.min(t.dailyRateCents(), startedHours * t.hourlyLateCents());
    }
}

final class RentalService {
    static final LocalTime HANDOVER_TIME = LocalTime.of(10, 0);

    private final Map<String, List<Vehicle>> fleetByBranch = new ConcurrentHashMap<>();
    private final Map<String, VehicleType> types = new ConcurrentHashMap<>();
    private final Map<String, Reservation> reservations = new ConcurrentHashMap<>();
    private final AtomicLong ids = new AtomicLong();
    private final PricingEngine pricing; private final LateFeePolicy lateFees; private final Supplier<LocalDateTime> clock;

    RentalService(PricingEngine pricing, LateFeePolicy lateFees, Supplier<LocalDateTime> clock) {
        this.pricing = pricing; this.lateFees = lateFees; this.clock = clock;
    }

    void addType(VehicleType t) { types.put(t.name(), t); }

    Vehicle addVehicle(String id, String branchId, String typeName) {
        Vehicle v = new Vehicle(id, branchId, get(types, typeName));
        fleetByBranch.computeIfAbsent(branchId, b -> new CopyOnWriteArrayList<>()).add(v);
        return v;
    }

    List<Vehicle> search(String branchId, String typeName, DateRange range) {
        return candidates(branchId, typeName).stream().filter(v -> v.isFree(range)).toList();   // a hint, not a promise
    }

    Quote quote(String customerId, String branchId, String typeName, DateRange range) {
        return pricing.quote(new RentalRequest(customerId, branchId, branchId, get(types, typeName), range));
    }

    Reservation reserve(String customerId, String branchId, String typeName, DateRange range) {
        if (range.start().isBefore(clock.get().toLocalDate())) throw new RentalException("range is in the past");
        Quote q = quote(customerId, branchId, typeName, range);
        String id = "R" + ids.incrementAndGet();
        for (Vehicle v : candidates(branchId, typeName)) {
            Reservation res = new Reservation(id, customerId, v, range, q);
            if (v.tryBook(res)) { reservations.put(id, res); return res; }
        }
        throw new RentalException("no " + typeName + " free at " + branchId + " for " + range);
    }

    void cancel(String reservationId) {
        Reservation r = get(reservations, reservationId);
        synchronized (r.vehicle) {
            require(r, ReservationStatus.RESERVED);
            r.status = ReservationStatus.CANCELLED;
            r.vehicle.release(r);
        }
    }

    void pickUp(String reservationId) {
        Reservation r = get(reservations, reservationId);
        LocalDate today = clock.get().toLocalDate();
        synchronized (r.vehicle) {
            require(r, ReservationStatus.RESERVED);
            if (today.isBefore(r.range.start()) || !today.isBefore(r.range.end())) throw new RentalException("not within the rental dates");
            r.status = ReservationStatus.ACTIVE;
        }
    }

    /** Returns the late fee charged. */
    long returnVehicle(String reservationId) {
        Reservation r = get(reservations, reservationId);
        LocalDateTime now = clock.get();
        synchronized (r.vehicle) {
            require(r, ReservationStatus.ACTIVE);
            Duration late = Duration.between(r.range.end().atTime(HANDOVER_TIME), now);
            r.lateFeeCents = late.isNegative() ? 0 : lateFees.feeCents(late, r.vehicle.type);
            r.status = ReservationStatus.COMPLETED;
            r.vehicle.release(r);                             // an early return frees the remaining days
            return r.lateFeeCents;
        }
    }

    /** Releases cars for customers who never came. Run it daily. */
    int markNoShows() {
        LocalDate today = clock.get().toLocalDate(); int n = 0;
        for (Reservation r : reservations.values()) {
            synchronized (r.vehicle) {
                if (r.status == ReservationStatus.RESERVED && r.range.start().isBefore(today)) {
                    r.status = ReservationStatus.NO_SHOW; r.vehicle.release(r); n++;
                }
            }
        }
        return n;
    }

    private List<Vehicle> candidates(String branchId, String typeName) {
        VehicleType t = get(types, typeName);
        return fleetByBranch.getOrDefault(branchId, List.of()).stream().filter(v -> v.type.equals(t)).toList();
    }

    private static void require(Reservation r, ReservationStatus s) {
        if (r.status != s) throw new RentalException("reservation " + r.id + " is " + r.status);
    }

    private static <T> T get(Map<String, T> m, String id) {
        T v = m.get(id);
        if (v == null) throw new RentalException("unknown " + id);
        return v;
    }
}

public class Main {
    static LocalDateTime now = LocalDateTime.of(2026, 11, 10, 9, 0);
    static final LocalDate FRI = LocalDate.of(2026, 12, 4), MON = FRI.plusDays(3);

    static RentalService service() {
        PricingEngine pricing = new PricingEngine(List.of(new DailyRate(), new WeekendSurcharge(25), new LongRentalDiscount(7, 10)));
        RentalService s = new RentalService(pricing, new HourlyLateFee(Duration.ofMinutes(30)), () -> now);
        s.addType(new VehicleType("ECONOMY", 4000, 1000));
        s.addType(new VehicleType("SUV", 9000, 2000));
        return s;
    }

    static void check(boolean ok, String what) { if (!ok) throw new AssertionError(what); }

    static boolean fails(Runnable r) {
        try { r.run(); return false; } catch (RentalException e) { return true; }
    }

    public static void main(String[] args) throws Exception {
        RentalService s = service();
        s.addVehicle("e1", "SFO", "ECONOMY");

        // Fri to Mon: 3 days at 40.00, Sat and Sun +25% = 120.00 + 20.00
        Reservation r = s.reserve("ann", "SFO", "ECONOMY", new DateRange(FRI, MON));
        check(r.quote.total() == 14000, "weekend quote " + r.quote);
        // Mon to Mon: 280.00 + 20.00 weekend, then 10% off the 300.00
        check(s.quote("x", "SFO", "ECONOMY", new DateRange(MON, MON.plusDays(7))).total() == 27000, "long rental");

        check(fails(() -> s.reserve("bob", "SFO", "ECONOMY", new DateRange(FRI.plusDays(1), FRI.plusDays(2)))), "overlap refused");
        Reservation back2back = s.reserve("bob", "SFO", "ECONOMY", new DateRange(MON, MON.plusDays(1)));
        check(back2back.vehicle.id.equals("e1"), "half-open ranges: Monday handover is fine");

        // pick up Friday, return Monday 11:45: 105 minutes late, 2 started hours at 10.00
        now = FRI.atTime(9, 30);
        s.pickUp(r.id);
        now = MON.atTime(11, 45);
        check(s.returnVehicle(r.id) == 2000, "late fee");
        check(r.status() == ReservationStatus.COMPLETED, "completed");
        check(new HourlyLateFee(Duration.ofMinutes(30)).feeCents(Duration.ofMinutes(25), new VehicleType("E", 4000, 1000)) == 0, "grace");
        check(new HourlyLateFee(Duration.ofMinutes(30)).feeCents(Duration.ofHours(51), new VehicleType("E", 4000, 1000)) == 11000, "2 days + 3 h");

        // the customer never comes for the Monday booking
        now = MON.plusDays(1).atTime(8, 0);
        check(s.markNoShows() == 1 && back2back.status() == ReservationStatus.NO_SHOW, "no-show released");
        check(s.search("SFO", "ECONOMY", new DateRange(MON, MON.plusDays(1))).size() == 1, "car is free again");

        now = LocalDateTime.of(2026, 11, 10, 9, 0);
        lastCarRace();
        System.out.println("car-rental: all checks passed");
    }

    static void lastCarRace() throws Exception {
        for (int cars : new int[] {1, 3}) {
            RentalService s = service();
            for (int i = 0; i < cars; i++) s.addVehicle("suv" + i, "SFO", "SUV");
            ExecutorService pool = Executors.newFixedThreadPool(20);
            CountDownLatch go = new CountDownLatch(1);
            List<Future<String>> fs = new ArrayList<>();
            for (int i = 0; i < 20; i++) {
                int offset = i % 3;                           // overlapping, not identical, ranges
                fs.add(pool.submit(() -> {
                    go.await();
                    try { return s.reserve("c", "SFO", "SUV", new DateRange(FRI.plusDays(offset), MON.plusDays(offset))).vehicle.id; }
                    catch (RentalException e) { return null; }
                }));
            }
            go.countDown();
            List<String> won = new ArrayList<>();
            for (Future<String> f : fs) if (f.get() != null) won.add(f.get());
            pool.shutdown();
            check(won.size() == cars && new HashSet<>(won).size() == cars, cars + " cars, got " + won);
        }
    }
}
from __future__ import annotations

import bisect
import threading
from dataclasses import dataclass, field
from datetime import date, datetime, time, timedelta
from enum import Enum
from itertools import count
from typing import Callable, Protocol


class RentalError(Exception):
    pass


@dataclass(frozen=True)
class DateRange:
    """Half-open [start, end): returning on the 7th and picking up on the 7th do not clash."""
    start: date
    end: date

    def __post_init__(self) -> None:
        if self.start >= self.end:
            raise RentalError("range must be at least one day")

    def overlaps(self, o: DateRange) -> bool:
        return self.start < o.end and o.start < self.end

    @property
    def days(self) -> int:
        return (self.end - self.start).days


@dataclass(frozen=True)
class VehicleType:
    """Type Object: categories are data, not subclasses."""
    name: str
    daily_rate_cents: int
    hourly_late_cents: int


@dataclass(frozen=True)
class PriceLine:
    label: str
    cents: int


@dataclass(frozen=True)
class Quote:
    lines: tuple[PriceLine, ...]

    @property
    def total(self) -> int:
        return sum(l.cents for l in self.lines)


@dataclass(frozen=True)
class RentalRequest:
    customer_id: str
    branch_id: str
    return_branch_id: str
    type: VehicleType
    range: DateRange


class ReservationStatus(Enum):
    RESERVED = 1; ACTIVE = 2; COMPLETED = 3; CANCELLED = 4; NO_SHOW = 5


@dataclass(eq=False)
class Reservation:
    id: str
    customer_id: str
    vehicle: Vehicle
    range: DateRange
    quote: Quote
    status: ReservationStatus = ReservationStatus.RESERVED   # guarded by vehicle.lock
    late_fee_cents: int = 0


class Vehicle:
    def __init__(self, id: str, branch_id: str, type: VehicleType) -> None:
        self.id, self.branch_id, self.type = id, branch_id, type
        self.lock = threading.RLock()                 # guards the calendar and this car's reservations
        self._starts: list[date] = []                 # sorted, parallel to _bookings
        self._bookings: list[Reservation] = []

    def is_free(self, r: DateRange) -> bool:
        """Bookings never overlap, so only the latest one starting before r.end can clash."""
        with self.lock:
            i = bisect.bisect_left(self._starts, r.end) - 1
            return i < 0 or not self._bookings[i].range.overlaps(r)

    def try_book(self, res: Reservation) -> bool:
        with self.lock:                               # check and insert under one lock
            if not self.is_free(res.range):
                return False
            i = bisect.bisect_left(self._starts, res.range.start)
            self._starts.insert(i, res.range.start)
            self._bookings.insert(i, res)
            return True

    def release(self, res: Reservation) -> None:
        with self.lock:
            i = self._bookings.index(res)
            del self._starts[i], self._bookings[i]


class PricingRule(Protocol):
    def apply(self, req: RentalRequest, running_total: int) -> PriceLine | None: ...


class DailyRate:
    def apply(self, r: RentalRequest, running: int) -> PriceLine | None:
        return PriceLine(f"{r.range.days} days x {r.type.daily_rate_cents}", r.range.days * r.type.daily_rate_cents)


class WeekendSurcharge:
    def __init__(self, percent: int) -> None:
        self._percent = percent

    def apply(self, r: RentalRequest, running: int) -> PriceLine | None:
        weekend = sum(1 for i in range(r.range.days) if (r.range.start + timedelta(i)).weekday() >= 5)
        if weekend == 0:
            return None
        return PriceLine(f"weekend +{self._percent}%", weekend * r.type.daily_rate_cents * self._percent // 100)


class LongRentalDiscount:
    def __init__(self, min_days: int, percent: int) -> None:
        self._min_days, self._percent = min_days, percent

    def apply(self, r: RentalRequest, running: int) -> PriceLine | None:
        if r.range.days < self._min_days:
            return None
        return PriceLine(f"{self._min_days}+ days -{self._percent}%", -(running * self._percent // 100))


class PricingEngine:
    def __init__(self, rules: list[PricingRule]) -> None:
        self._rules = tuple(rules)                    # order matters: discounts see the surcharges

    def quote(self, req: RentalRequest) -> Quote:
        lines, running = [], 0
        for rule in self._rules:
            line = rule.apply(req, running)
            if line is not None:
                lines.append(line)
                running += line.cents
        return Quote(tuple(lines))


class HourlyLateFee:
    """Free within the grace period. Then per started hour, at most one day's rate per 24 hours."""

    def __init__(self, grace: timedelta) -> None:
        self._grace = grace

    def fee_cents(self, late: timedelta, t: VehicleType) -> int:
        if late <= self._grace:
            return 0
        minutes = int(late.total_seconds() // 60)
        full_days, started_hours = minutes // 1440, (minutes % 1440 + 59) // 60
        return full_days * t.daily_rate_cents + min(t.daily_rate_cents, started_hours * t.hourly_late_cents)


class RentalService:
    HANDOVER_TIME = time(10, 0)

    def __init__(self, pricing: PricingEngine, late_fees: HourlyLateFee, clock: Callable[[], datetime]) -> None:
        self._pricing, self._late_fees, self._clock = pricing, late_fees, clock
        self._fleet: dict[str, list[Vehicle]] = {}
        self._types: dict[str, VehicleType] = {}
        self._reservations: dict[str, Reservation] = {}
        self._ids = count(1)

    def add_type(self, t: VehicleType) -> None:
        self._types[t.name] = t

    def add_vehicle(self, id: str, branch_id: str, type_name: str) -> Vehicle:
        v = Vehicle(id, branch_id, self._get(self._types, type_name))
        self._fleet.setdefault(branch_id, []).append(v)
        return v

    def search(self, branch_id: str, type_name: str, r: DateRange) -> list[Vehicle]:
        return [v for v in self._candidates(branch_id, type_name) if v.is_free(r)]   # a hint, not a promise

    def quote(self, customer_id: str, branch_id: str, type_name: str, r: DateRange) -> Quote:
        return self._pricing.quote(RentalRequest(customer_id, branch_id, branch_id, self._get(self._types, type_name), r))

    def reserve(self, customer_id: str, branch_id: str, type_name: str, r: DateRange) -> Reservation:
        if r.start < self._clock().date():
            raise RentalError("range is in the past")
        q = self.quote(customer_id, branch_id, type_name, r)
        rid = f"R{next(self._ids)}"
        for v in self._candidates(branch_id, type_name):
            res = Reservation(rid, customer_id, v, r, q)
            if v.try_book(res):
                self._reservations[rid] = res
                return res
        raise RentalError(f"no {type_name} free at {branch_id} for {r}")

    def cancel(self, reservation_id: str) -> None:
        r = self._get(self._reservations, reservation_id)
        with r.vehicle.lock:
            self._require(r, ReservationStatus.RESERVED)
            r.status = ReservationStatus.CANCELLED
            r.vehicle.release(r)

    def pick_up(self, reservation_id: str) -> None:
        r = self._get(self._reservations, reservation_id)
        today = self._clock().date()
        with r.vehicle.lock:
            self._require(r, ReservationStatus.RESERVED)
            if not r.range.start <= today < r.range.end:
                raise RentalError("not within the rental dates")
            r.status = ReservationStatus.ACTIVE

    def return_vehicle(self, reservation_id: str) -> int:
        r = self._get(self._reservations, reservation_id)
        now = self._clock()
        with r.vehicle.lock:
            self._require(r, ReservationStatus.ACTIVE)
            late = now - datetime.combine(r.range.end, self.HANDOVER_TIME)
            r.late_fee_cents = 0 if late < timedelta(0) else self._late_fees.fee_cents(late, r.vehicle.type)
            r.status = ReservationStatus.COMPLETED
            r.vehicle.release(r)                      # an early return frees the remaining days
            return r.late_fee_cents

    def mark_no_shows(self) -> int:
        today, n = self._clock().date(), 0
        for r in list(self._reservations.values()):
            with r.vehicle.lock:
                if r.status is ReservationStatus.RESERVED and r.range.start < today:
                    r.status = ReservationStatus.NO_SHOW
                    r.vehicle.release(r)
                    n += 1
        return n

    def _candidates(self, branch_id: str, type_name: str) -> list[Vehicle]:
        t = self._get(self._types, type_name)
        return [v for v in self._fleet.get(branch_id, []) if v.type == t]

    @staticmethod
    def _require(r: Reservation, s: ReservationStatus) -> None:
        if r.status is not s:
            raise RentalError(f"reservation {r.id} is {r.status.name}")

    @staticmethod
    def _get(m: dict, key: str):
        if key not in m:
            raise RentalError(f"unknown {key}")
        return m[key]


class FakeClock:
    def __init__(self, now: datetime) -> None:
        self.now = now

    def __call__(self) -> datetime:
        return self.now


FRI = date(2026, 12, 4)
MON = FRI + timedelta(3)


def make_service(clock: FakeClock) -> RentalService:
    s = RentalService(PricingEngine([DailyRate(), WeekendSurcharge(25), LongRentalDiscount(7, 10)]),
                      HourlyLateFee(timedelta(minutes=30)), clock)
    s.add_type(VehicleType("ECONOMY", 4000, 1000))
    s.add_type(VehicleType("SUV", 9000, 2000))
    return s


def demo() -> None:
    clock = FakeClock(datetime(2026, 11, 10, 9, 0))
    s = make_service(clock)
    s.add_vehicle("e1", "SFO", "ECONOMY")
    r = s.reserve("ann", "SFO", "ECONOMY", DateRange(FRI, MON))
    assert r.quote.total == 14000                     # 3 x 40.00 + weekend 20.00
    assert s.quote("x", "SFO", "ECONOMY", DateRange(MON, MON + timedelta(7))).total == 27000
    back2back = s.reserve("bob", "SFO", "ECONOMY", DateRange(MON, MON + timedelta(1)))
    assert back2back.vehicle.id == "e1"

    clock.now = datetime.combine(FRI, time(9, 30))
    s.pick_up(r.id)
    clock.now = datetime.combine(MON, time(11, 45))
    assert s.return_vehicle(r.id) == 2000             # 105 min late: 2 started hours
    print("car-rental: demo checks passed")


if __name__ == "__main__":
    demo()
// car-rental.ts — run with: npx tsx car-rental.ts
type Day = number;      // whole days since 1970-01-01 UTC
type Minute = number;   // minutes since 1970-01-01 UTC
const day = (iso: string): Day => Date.parse(`${iso}T00:00:00Z`) / 86_400_000;
const at = (d: Day, hour: number, minute = 0): Minute => d * 1440 + hour * 60 + minute;
const isWeekend = (d: Day): boolean => [0, 6].includes(new Date(d * 86_400_000).getUTCDay());

class RentalError extends Error {}

/** Half-open [start, end): returning on the 7th and picking up on the 7th do not clash. */
class DateRange {
  constructor(readonly start: Day, readonly end: Day) {
    if (start >= end) throw new RentalError("range must be at least one day");
  }
  overlaps(o: DateRange): boolean { return this.start < o.end && o.start < this.end; }
  get days(): number { return this.end - this.start; }
}

/** Type Object: categories are data, not subclasses. */
interface VehicleType { readonly name: string; readonly dailyRateCents: number; readonly hourlyLateCents: number }
interface PriceLine { readonly label: string; readonly cents: number }
class Quote {
  constructor(readonly lines: readonly PriceLine[]) {}
  get total(): number { return this.lines.reduce((s, l) => s + l.cents, 0); }
}
interface RentalRequest {
  customerId: string; branchId: string; returnBranchId: string; type: VehicleType; range: DateRange;
}

enum ReservationStatus { RESERVED = "RESERVED", ACTIVE = "ACTIVE", COMPLETED = "COMPLETED", CANCELLED = "CANCELLED", NO_SHOW = "NO_SHOW" }

class Reservation {
  status = ReservationStatus.RESERVED;
  lateFeeCents = 0;
  constructor(readonly id: string, readonly customerId: string, readonly vehicle: Vehicle,
              readonly range: DateRange, readonly quote: Quote) {}
}

class Vehicle {
  private readonly calendar: Reservation[] = []; // sorted by start, never overlapping
  constructor(readonly id: string, readonly branchId: string, readonly type: VehicleType) {}

  private firstStartingAtOrAfter(d: Day): number {
    let lo = 0, hi = this.calendar.length;
    while (lo < hi) { const mid = (lo + hi) >> 1; if (this.calendar[mid].range.start < d) lo = mid + 1; else hi = mid; }
    return lo;
  }
  /** Only the latest booking starting before r.end can clash: O(log n). */
  isFree(r: DateRange): boolean {
    const i = this.firstStartingAtOrAfter(r.end) - 1;
    return i < 0 || !this.calendar[i].range.overlaps(r);
  }
  /** Synchronous check-and-insert, so no other task can interleave on Node's event loop. */
  tryBook(res: Reservation): boolean {
    if (!this.isFree(res.range)) return false;
    this.calendar.splice(this.firstStartingAtOrAfter(res.range.start), 0, res);
    return true;
  }
  release(res: Reservation): void {
    const i = this.calendar.indexOf(res);
    if (i >= 0) this.calendar.splice(i, 1);
  }
}

interface PricingRule { apply(req: RentalRequest, runningTotal: number): PriceLine | null }

class DailyRate implements PricingRule {
  apply(r: RentalRequest): PriceLine {
    return { label: `${r.range.days} days x ${r.type.dailyRateCents}`, cents: r.range.days * r.type.dailyRateCents };
  }
}
class WeekendSurcharge implements PricingRule {
  constructor(private percent: number) {}
  apply(r: RentalRequest): PriceLine | null {
    let weekend = 0;
    for (let d = r.range.start; d < r.range.end; d++) if (isWeekend(d)) weekend++;
    if (weekend === 0) return null;
    return { label: `weekend +${this.percent}%`, cents: Math.floor((weekend * r.type.dailyRateCents * this.percent) / 100) };
  }
}
class LongRentalDiscount implements PricingRule {
  constructor(private minDays: number, private percent: number) {}
  apply(r: RentalRequest, running: number): PriceLine | null {
    if (r.range.days < this.minDays) return null;
    return { label: `${this.minDays}+ days -${this.percent}%`, cents: -Math.floor((running * this.percent) / 100) };
  }
}

class PricingEngine {
  constructor(private readonly rules: readonly PricingRule[]) {} // order matters
  quote(req: RentalRequest): Quote {
    const lines: PriceLine[] = [];
    let running = 0;
    for (const rule of this.rules) {
      const line = rule.apply(req, running);
      if (line) { lines.push(line); running += line.cents; }
    }
    return new Quote(lines);
  }
}

interface LateFeePolicy { feeCents(lateMinutes: number, t: VehicleType): number }

/** Free within the grace period. Then per started hour, at most one day's rate per 24 hours. */
class HourlyLateFee implements LateFeePolicy {
  constructor(private graceMinutes: number) {}
  feeCents(late: number, t: VehicleType): number {
    if (late <= this.graceMinutes) return 0;
    const fullDays = Math.floor(late / 1440), startedHours = Math.ceil((late % 1440) / 60);
    return fullDays * t.dailyRateCents + Math.min(t.dailyRateCents, startedHours * t.hourlyLateCents);
  }
}

class RentalService {
  static readonly HANDOVER_HOUR = 10;
  private readonly fleet = new Map<string, Vehicle[]>();
  private readonly types = new Map<string, VehicleType>();
  private readonly reservations = new Map<string, Reservation>();
  private nextId = 1;

  constructor(private pricing: PricingEngine, private lateFees: LateFeePolicy, private clock: () => Minute) {}

  addType(t: VehicleType): void { this.types.set(t.name, t); }
  addVehicle(id: string, branchId: string, typeName: string): Vehicle {
    const v = new Vehicle(id, branchId, get(this.types, typeName));
    this.fleet.set(branchId, [...(this.fleet.get(branchId) ?? []), v]);
    return v;
  }

  search(branchId: string, typeName: string, r: DateRange): Vehicle[] {
    return this.candidates(branchId, typeName).filter((v) => v.isFree(r)); // a hint, not a promise
  }

  quote(customerId: string, branchId: string, typeName: string, range: DateRange): Quote {
    return this.pricing.quote({ customerId, branchId, returnBranchId: branchId, type: get(this.types, typeName), range });
  }

  reserve(customerId: string, branchId: string, typeName: string, range: DateRange): Reservation {
    if (range.start < Math.floor(this.clock() / 1440)) throw new RentalError("range is in the past");
    const q = this.quote(customerId, branchId, typeName, range);
    const id = `R${this.nextId++}`;
    for (const v of this.candidates(branchId, typeName)) {
      const res = new Reservation(id, customerId, v, range, q);
      if (v.tryBook(res)) { this.reservations.set(id, res); return res; }
    }
    throw new RentalError(`no ${typeName} free at ${branchId}`);
  }

  cancel(reservationId: string): void {
    const r = get(this.reservations, reservationId);
    require(r, ReservationStatus.RESERVED);
    r.status = ReservationStatus.CANCELLED;
    r.vehicle.release(r);
  }

  pickUp(reservationId: string): void {
    const r = get(this.reservations, reservationId);
    const today = Math.floor(this.clock() / 1440);
    require(r, ReservationStatus.RESERVED);
    if (today < r.range.start || today >= r.range.end) throw new RentalError("not within the rental dates");
    r.status = ReservationStatus.ACTIVE;
  }

  returnVehicle(reservationId: string): number {
    const r = get(this.reservations, reservationId);
    require(r, ReservationStatus.ACTIVE);
    const late = this.clock() - at(r.range.end, RentalService.HANDOVER_HOUR);
    r.lateFeeCents = late < 0 ? 0 : this.lateFees.feeCents(late, r.vehicle.type);
    r.status = ReservationStatus.COMPLETED;
    r.vehicle.release(r); // an early return frees the remaining days
    return r.lateFeeCents;
  }

  markNoShows(): number {
    const today = Math.floor(this.clock() / 1440);
    let n = 0;
    for (const r of this.reservations.values()) {
      if (r.status === ReservationStatus.RESERVED && r.range.start < today) {
        r.status = ReservationStatus.NO_SHOW; r.vehicle.release(r); n++;
      }
    }
    return n;
  }

  private candidates(branchId: string, typeName: string): Vehicle[] {
    const t = get(this.types, typeName);
    return (this.fleet.get(branchId) ?? []).filter((v) => v.type === t);
  }
}

function require(r: Reservation, s: ReservationStatus): void {
  if (r.status !== s) throw new RentalError(`reservation ${r.id} is ${r.status}`);
}
function get<T>(m: Map<string, T>, key: string): T {
  const v = m.get(key);
  if (v === undefined) throw new RentalError(`unknown ${key}`);
  return v;
}
function assert(cond: unknown, msg: string): asserts cond { if (!cond) throw new Error("FAILED: " + msg); }
function fails(fn: () => unknown): boolean { try { fn(); return false; } catch (e) { return e instanceof RentalError; } }

const FRI = day("2026-12-04"), MON = FRI + 3;
let now: Minute = at(day("2026-11-10"), 9);
function makeService(): RentalService {
  const s = new RentalService(
    new PricingEngine([new DailyRate(), new WeekendSurcharge(25), new LongRentalDiscount(7, 10)]),
    new HourlyLateFee(30), () => now);
  s.addType({ name: "ECONOMY", dailyRateCents: 4000, hourlyLateCents: 1000 });
  s.addType({ name: "SUV", dailyRateCents: 9000, hourlyLateCents: 2000 });
  return s;
}

async function main(): Promise<void> {
  const s = makeService();
  s.addVehicle("e1", "SFO", "ECONOMY");
  const r = s.reserve("ann", "SFO", "ECONOMY", new DateRange(FRI, MON));
  assert(r.quote.total === 14000, "weekend quote");
  assert(s.quote("x", "SFO", "ECONOMY", new DateRange(MON, MON + 7)).total === 27000, "long rental");
  assert(fails(() => s.reserve("bob", "SFO", "ECONOMY", new DateRange(FRI + 1, FRI + 2))), "overlap refused");
  const next = s.reserve("bob", "SFO", "ECONOMY", new DateRange(MON, MON + 1));
  assert(next.vehicle.id === "e1", "back-to-back on a half-open range");

  now = at(FRI, 9, 30);
  s.pickUp(r.id);
  now = at(MON, 11, 45);
  assert(s.returnVehicle(r.id) === 2000, "105 minutes late, 2 started hours");
  now = at(MON + 1, 8);
  assert(s.markNoShows() === 1 && next.status === ReservationStatus.NO_SHOW, "no-show");

  // 20 bookings for the last SUV, each arriving as a separate event
  now = at(day("2026-11-10"), 9);
  const c = makeService();
  c.addVehicle("suv0", "SFO", "SUV");
  const tries = Array.from({ length: 20 }, (_, i) => new Promise<boolean>((done) => setTimeout(() => {
    done(!fails(() => c.reserve(`c${i}`, "SFO", "SUV", new DateRange(FRI + (i % 3), MON + (i % 3)))));
  }, Math.random() * 5)));
  assert((await Promise.all(tries)).filter(Boolean).length === 1, "exactly one booking for the last car");
  console.log("car-rental: all checks passed");
}

main();
export {}; // makes this file a module, so names do not clash with DOM globals

Run: javac -d out Main.java && java -ea -cp out Main, python car_rental.py, npx tsx car-rental.ts (also clean under tsc --strict).

Reading the calendar code

Java uses TreeMap.lowerEntry(end), which returns the greatest start strictly less than end. Python keeps two parallel sorted lists and uses bisect_left. TypeScript uses a hand-written binary search over a sorted array. All three answer one question: which booking starts last before my range ends? If its end is after my start, there's an overlap. Otherwise there isn't one.

The half-open convention is what makes back-to-back rentals work. [Dec 4, Dec 7) and [Dec 7, Dec 8) share no day, so the Monday handover succeeds. With closed ranges you'd need end + 1 arithmetic everywhere, and somebody would eventually forget it.

Reading the late fee

The fee is measured from the due instant (end date at 10:00), not the due date. A 105-minute delay is 2 started hours, which is 2000 cents. Within 30 minutes it's free. Each 24-hour block costs at most one day's rate, so a car three days late isn't charged 72 hourly fees. The policy is a pure function of (lateness, type), so its edge cases are tested without a service or a clock at all.

7. Concurrency

What's shared

StateWritersGuard
A vehicle's calendarreserve, cancel, return, no-show sweepthe vehicle's monitor
A reservation's status and late feecancel, pick up, return, sweepthe same vehicle monitor
Fleet and reservation registriesadd vehicle, reserveconcurrent maps and copy-on-write lists

Guarding the reservation's status with its vehicle's lock, instead of a lock of its own, is deliberate. Every status change also edits the calendar, so one lock covers both. There's no lock ordering to get wrong.

The last car

The race is a classic check-then-act. Customer A checks "suv0 free Dec 4 to 7", customer B checks "suv0 free Dec 5 to 8", both see free, and both insert. tryBook closes it by doing the check and the insert in one synchronized method. Search (search) is deliberately not trusted. It runs the same check without holding the lock across the user's think time, so its answer is a hint, and reserve re-checks at commit.

Locking per vehicle (rather than per branch or globally) means customers booking different cars never contend. A customer looping over a branch's SUVs takes one car lock at a time and never holds two, so there's no deadlock.

The tests run this race for real:

  • Java: 20 threads behind a latch book three mutually overlapping ranges. With 1 SUV, exactly one wins. With 3 SUVs, exactly three win, on three distinct cars.
  • Python: 16 threads, 50 rounds, one SUV, exactly one winner. A second test books 10 consecutive, non-overlapping days on one car concurrently and expects all 10 to succeed. That catches an over-eager lock or a broken overlap check.
  • TypeScript: single-threaded, so tryBook is atomic by construction. The test fires 20 bookings as separate timer callbacks in random order and expects one winner. If reserve ever gains an await (say, a credit check), keep it before the loop, or re-check after it.

In a database

The same design maps onto SQL in two common ways. One is an exclusion constraint (PostgreSQL EXCLUDE USING gist (vehicle_id WITH =, daterange(start, end) WITH &&)), which makes overlap physically impossible. The other is SELECT ... FOR UPDATE on the vehicle row before checking and inserting, which is the per-vehicle lock again. Booking and inventory concurrency compares these with optimistic versioning.

8. The interviewer adds...

"One-way rentals cost a drop fee"

A new rule appended to the engine. The only other change is that reserve accepts a return branch:

/** A new rule, no edits to the engine: one-way rentals pay to bring the car home. */
final class OneWayDropFee implements PricingRule {
    private final Map<String, Long> feeByRoute;               // "SFO>LAX" -> cents
    private final long defaultFeeCents;
    OneWayDropFee(Map<String, Long> feeByRoute, long defaultFeeCents) {
        this.feeByRoute = Map.copyOf(feeByRoute); this.defaultFeeCents = defaultFeeCents;
    }
    public Optional<PriceLine> apply(RentalRequest r, long running) {
        if (r.branchId().equals(r.returnBranchId())) return Optional.empty();
        String route = r.branchId() + ">" + r.returnBranchId();
        return Optional.of(new PriceLine("one-way " + route, feeByRoute.getOrDefault(route, defaultFeeCents)));
    }
}
// Wiring: new PricingEngine(List.of(new DailyRate(), new WeekendSurcharge(25),
//         new LongRentalDiscount(7, 10), new OneWayDropFee(Map.of("SFO>LAX", 7500L), 15000)))
// RentalService.reserve gains a returnBranchId parameter and passes it into RentalRequest.

Tested: SFO to LAX adds 7500 (21500 total), an unlisted route adds the 15000 default, and a round trip is unchanged at 14000. Because the rule sits after LongRentalDiscount, the drop fee isn't discounted. Moving it earlier would discount it, and that's a one-line decision.

The harder part of one-way rentals is the fleet, not the price. The car ends up at LAX, so its future bookings at SFO become impossible. The fix is to have each calendar entry record its end branch, and to make search consider a car at branch B for a range only if its previous booking ends at B. Mention it, but don't code it unless asked.

"Trucks need a commercial licence"

This is the moment the hierarchy question comes back. A Truck subclass overriding canBeRentedBy(customer) puts a rental policy inside the vehicle. A rule table keeps it in the rental process, where it belongs:

class LicenceRequirement:
    """Who may rent which type. Data in a table, not a Truck subclass with an overridden method."""

    def __init__(self, required: dict[str, str]) -> None:
        self._required = required                      # type name -> licence class

    def check(self, licences: set[str], t: VehicleType) -> None:
        needed = self._required.get(t.name)
        if needed is not None and needed not in licences:
            raise RentalError(f"{t.name} requires a {needed} licence")


# RentalService takes the policy in its constructor and calls it first thing in reserve():
#     self._eligibility.check(self._customers[customer_id].licences, self._types[type_name])

Tested: a standard licence can rent economy cars but not trucks, and adding COMMERCIAL allows the truck. New restrictions ("luxury needs age 25+") become more entries or another small policy, and neither touches Vehicle.

"When the requested type is sold out, upgrade for free"

Composition over the existing API. reserve already reports "sold out", so an upgrade is a loop over a ladder of types that charges the price of the type asked for:

/** Sold out? Try the next type up, but charge what the customer asked for. */
function reserveWithUpgrade(s: RentalService, customerId: string, branchId: string,
                            ladder: string[], range: DateRange): { reservation: Reservation; chargeCents: number } {
  const asked = s.quote(customerId, branchId, ladder[0], range).total; // price of the requested type
  for (const typeName of ladder) {
    try {
      return { reservation: s.reserve(customerId, branchId, typeName, range), chargeCents: asked };
    } catch (e) {
      if (!(e instanceof RentalError)) throw e;                        // only "sold out" moves us up
    }
  }
  throw new RentalError(`nothing free on the ladder ${ladder.join(" > ")}`);
}

Tested: with one economy car and one SUV, the first customer gets the economy car. The second gets the SUV (quoted at 31500) but is charged 14000, and a third fails with "nothing free on the ladder". Note that only RentalError moves up the ladder. A bug elsewhere still surfaces.

9. Tests

import sys
import threading
from concurrent.futures import ThreadPoolExecutor
from datetime import datetime, time, timedelta

from car_rental import (FRI, MON, DateRange, FakeClock, HourlyLateFee, RentalError,
                        ReservationStatus, VehicleType, make_service)

sys.setswitchinterval(1e-6)
ECON = VehicleType("E", 4000, 1000)


def start_clock() -> FakeClock:
    return FakeClock(datetime(2026, 11, 10, 9, 0))


def test_interval_overlap_edges():
    a = DateRange(FRI, MON)
    assert a.overlaps(DateRange(FRI + timedelta(1), FRI + timedelta(2)))   # inside
    assert a.overlaps(DateRange(FRI - timedelta(1), FRI + timedelta(1)))   # straddles start
    assert not a.overlaps(DateRange(MON, MON + timedelta(1)))              # touches end
    assert not a.overlaps(DateRange(FRI - timedelta(2), FRI))              # touches start


def test_late_fee_policy():
    fee = HourlyLateFee(timedelta(minutes=30))
    assert fee.fee_cents(timedelta(minutes=30), ECON) == 0                  # grace is inclusive
    assert fee.fee_cents(timedelta(minutes=31), ECON) == 1000
    assert fee.fee_cents(timedelta(hours=7), ECON) == 4000                  # capped at a day
    assert fee.fee_cents(timedelta(hours=51), ECON) == 11000                # 2 days + 3 hours


def test_cancel_frees_the_dates_and_lifecycle_is_enforced():
    clock = start_clock()
    s = make_service(clock)
    s.add_vehicle("e1", "SFO", "ECONOMY")
    r = s.reserve("ann", "SFO", "ECONOMY", DateRange(FRI, MON))
    for bad in (lambda: s.return_vehicle(r.id), lambda: s.pick_up(r.id)):   # not active, too early
        try:
            bad()
            raise AssertionError("allowed")
        except RentalError:
            pass
    s.cancel(r.id)
    assert r.status is ReservationStatus.CANCELLED
    assert s.reserve("bob", "SFO", "ECONOMY", DateRange(FRI, MON)).vehicle.id == "e1"


def test_early_return_frees_remaining_days():
    clock = start_clock()
    s = make_service(clock)
    s.add_vehicle("e1", "SFO", "ECONOMY")
    r = s.reserve("ann", "SFO", "ECONOMY", DateRange(FRI, MON + timedelta(4)))
    clock.now = datetime.combine(FRI, time(10))
    s.pick_up(r.id)
    clock.now = datetime.combine(MON, time(9))
    assert s.return_vehicle(r.id) == 0
    assert len(s.search("SFO", "ECONOMY", DateRange(MON + timedelta(1), MON + timedelta(3)))) == 1


def test_last_car_goes_to_exactly_one_customer():
    for _ in range(50):
        s = make_service(start_clock())
        s.add_vehicle("suv0", "SFO", "SUV")
        barrier = threading.Barrier(16)

        def book(i: int):
            barrier.wait()
            try:
                return s.reserve(f"c{i}", "SFO", "SUV", DateRange(FRI + timedelta(i % 3), MON + timedelta(i % 3))).id
            except RentalError:
                return None

        with ThreadPoolExecutor(16) as pool:
            won = [r for r in pool.map(book, range(16)) if r]
        assert len(won) == 1, won


def test_non_overlapping_bookings_on_one_car_all_succeed_concurrently():
    s = make_service(start_clock())
    s.add_vehicle("suv0", "SFO", "SUV")
    barrier = threading.Barrier(10)

    def book(i: int):
        barrier.wait()
        return s.reserve(f"c{i}", "SFO", "SUV", DateRange(FRI + timedelta(i), FRI + timedelta(i + 1)))

    with ThreadPoolExecutor(10) as pool:
        assert len(list(pool.map(book, range(10)))) == 10                    # ten consecutive days


if __name__ == "__main__":
    for name, fn in list(globals().items()):
        if name.startswith("test_"):
            fn()
            print("ok", name)

The tests separate pure logic (interval edges, the late-fee table) from stateful behaviour (lifecycle, early return) and from concurrency. Pure-function tests are the cheapest and catch the most bugs here, because overlap and fee arithmetic are where off-by-one errors live. The clock is a FakeClock, so "Monday 11:45" is an assignment, not a sleep.

10. Common mistakes

  1. An isAvailable flag on Vehicle. It can't answer questions about future dates. Availability is a function of a range.
  2. Closed date ranges. [Dec 4, Dec 7] and [Dec 7, Dec 8] "overlap" on Dec 7, which blocks same-day turnarounds or forces +1 hacks.
  3. Overlap written as four cases. a.start < b.end && b.start < a.end covers every case. A hand-rolled if-ladder usually misses containment.
  4. A subclass per category. It hard-codes data and makes the fleet manager's job a deployment.
  5. Checking availability in search and trusting it in reserve. That's the check-then-act race. Re-check at commit under the lock.
  6. now() inside the late-fee code. It's untestable, and the first daylight-saving change will find the bug. Inject the clock and compute in a fixed zone.
  7. Forgetting to free the calendar on cancel, return or no-show. Ghost bookings block real customers, and nobody notices until a branch looks sold out when its lot is full of cars.
  8. Charging late fees from the due date instead of the due time. A car returned at 09:00 on the due day isn't late.

11. Interview follow-ups

A car comes back two days late and the next customer's booking starts today. What happens? The late car's reservation is still ACTIVE, so the calendar still blocks those days, but the next reservation was booked against dates that are now physically unavailable. Detect it at return time, or proactively via a sweep of ACTIVE reservations past due. Then move the affected reservation to another car of the same type (calling tryBook on the alternatives, then releasing the old entry, under both vehicle locks in id order), or upgrade it.

How would you find all free SUVs across 200 branches quickly? Per-car calendars give O(cars · log bookings). For heavy search traffic, keep a per-branch, per-type, per-day count of free cars (a "day bitmap" or counter array). Search becomes "minimum free count over the range > 0". Bookings update the counters under the same lock as the calendar. That's a read-optimised projection, and the calendar stays the source of truth.

Why not lock the whole branch? It's simpler, and fine for a small branch. But two customers renting different cars at a busy airport branch would serialise. Per-vehicle locks cost nothing extra in complexity here, because every operation touches exactly one vehicle.

How do you handle time zones? Each branch has a zone. The handover instant is end date at 10:00 in the branch's zone, converted to an Instant, and the clock returns Instants. The demo uses a single zone to stay short. The point is that the conversion lives in one place.

How would you add a hold, a reservation that expires if not confirmed? Add a HELD state with an expiry time. tryBook treats an expired hold as free and removes it during the check. That's the seat-hold timeout from movie booking, applied to a range.

Could you price per hour instead of per day? Make DateRange a range of instants, and change DailyRate to a rate table by duration band. The calendar, the overlap test and the locking don't change, which is a good sign the abstraction is right.