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
| Question | Answer we assume | Consequence |
|---|---|---|
| What does the customer book, a specific car or a type? | A type at a branch ("an SUV at SFO"). The system picks the car | Booking searches the branch's fleet of that type |
| Date or time granularity? | Whole days, with handover at 10:00 | DateRange of LocalDate, half-open |
| Can a car be picked up the day it's returned? | Yes | Ranges are [start, end), so touching ranges don't overlap |
| How is the price built? | Daily rate, a weekend surcharge, and a long-rental discount | An 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 hours | A 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 released | A daily sweep |
| One-way rentals, upgrades, licence checks? | Not at first. They come as extensions | The design must absorb them |
| Payments, damage inspection, loyalty? | Out of scope |
Functional requirements
- Branches have fleets. Each vehicle has a type that sets its rates.
- Search for free vehicles of a type at a branch over a date range.
- Quote and reserve. Reserving picks a free vehicle and blocks its dates.
- Cancel before pickup, which frees the dates.
- Pick up on a date within the range, and return. Late returns are charged, and early returns free the remaining days.
- 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
| Entity | Kind | Notes |
|---|---|---|
Branch | Identifier here | A real system adds address and hours. We key fleets by branch id |
VehicleType | Value object, Type Object | name, daily rate, hourly late rate |
Vehicle | Entity | id, home branch, type, and its calendar of reservations |
DateRange | Value object | [start, end), overlaps, days |
Reservation | Entity | customer, vehicle, range, quote, status, late fee |
PricingRule | Strategy | adds one optional line to a quote |
PricingEngine | Domain service | runs the rules in order |
Quote / PriceLine | Value objects | an itemised price |
LateFeePolicy | Strategy | lateness and type give cents |
RentalService | Facade | search, 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 category | VehicleType object | |
|---|---|---|
| Adding "Electric SUV" | New class, recompile, redeploy | New row of data |
| Changing the SUV rate | Code change, or a static field that's awkward to test | Edit the type |
| Fleet manager UI to create categories | Impossible without code | Natural |
| Category-specific behaviour (a truck needs a tachograph check) | Natural | Needs 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
| Pattern | Where | Why | Rejected alternative |
|---|---|---|---|
| Type Object | VehicleType | Categories differ in data, not behaviour | A subclass per category (section 2) |
| Strategy, as an ordered list | PricingRules in PricingEngine | Promotions come and go, and each one is a class with one job | One computePrice with every rule inline |
| Strategy | LateFeePolicy | Late-fee rules differ by market and get tuned | Constants in returnVehicle |
| Value objects | DateRange, Quote, PriceLine | Immutability, and validation in one place (start before end) | Pairs of loose dates passed around |
| Injected clock | Supplier<LocalDateTime> | Late fees and no-shows are about time | LocalDateTime.now() inside the service |
| Facade | RentalService | Calendar and status change together, under one lock | Callers 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
| State | Writers | Guard |
|---|---|---|
| A vehicle's calendar | reserve, cancel, return, no-show sweep | the vehicle's monitor |
| A reservation's status and late fee | cancel, pick up, return, sweep | the same vehicle monitor |
| Fleet and reservation registries | add vehicle, reserve | concurrent 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
tryBookis atomic by construction. The test fires 20 bookings as separate timer callbacks in random order and expects one winner. Ifreserveever gains anawait(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
- An
isAvailableflag onVehicle. It can't answer questions about future dates. Availability is a function of a range. - Closed date ranges.
[Dec 4, Dec 7]and[Dec 7, Dec 8]"overlap" on Dec 7, which blocks same-day turnarounds or forces+1hacks. - Overlap written as four cases.
a.start < b.end && b.start < a.endcovers every case. A hand-rolled if-ladder usually misses containment. - A subclass per category. It hard-codes data and makes the fleet manager's job a deployment.
- Checking availability in
searchand trusting it inreserve. That's the check-then-act race. Re-check at commit under the lock. 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.- 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.
- 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.