Notes
Requirements
The requirements. The company has branches, each with a fleet of hatchbacks, sedans and SUVs. A customer searches by branch, type and a time range, and books any free vehicle of that type. Bookings can be picked up, returned or cancelled. Price is per day by type, long rentals get a discount, and returns can add late and damage fees. Many customers book at the same time. Payments and identity checks are out of scope.
Clarify the time rules, because they decide the data structures. Customers book a type, not a specific car, and the system picks one. If one rental ends at ten and the next starts at ten, that is allowed, which tells us ranges are half-open. A day is every started twenty four hours. Late returns are charged per started hour. Returning to a different branch is a later extension with a one-way fee.
- branches, each with a fleet
- types: hatchback, sedan, SUV
- search: type + branch + dates
- book any free vehicle of a type
- pick up, return, cancel
- price per day by type
- long rentals get a discount
- late return and damage fees
- many customers book at once
- out of scope: payments, KYC
- book a type or a specific car?
- a type; we pick the car
- return at 10:00, next pickup
- at 10:00: allowed? yes
- how is a day counted?
- every started 24 hours
- late fee?
- per started hour, by type
- return to another branch?
- extension, one-way fee
Entities
The entities. The service has branches, and each branch has vehicles. A booking ties a customer to one vehicle for one time range, with a price quoted at booking time and a status. The time range deserves its own type, because the overlap rule is subtle and should live in exactly one place. Invoices appear at return time.
Class diagram
In code, kinds and states are enums: vehicle type and booking status. Values that never change are records: the time range, customer, branch, a charge and the invoice. Two classes hold changing state. A vehicle owns its calendar of bookings, and a booking has a status that moves through its lifecycle. Money is a long count of paise, never a double.
enum VehicleType { HATCHBACK, SEDAN, SUV }
enum BookingStatus { BOOKED, PICKED_UP,
RETURNED, CANCELLED }
record TimeRange(Instant start, Instant end)
record Customer(String id, String name)
record Branch(String id, String city)
record Charge(String label, long cents)
record Invoice(id, rentCents, extras)
class Vehicle { id, type, calendar }
class Booking { ..., status } Time ranges
The overlap rule is one line, but it is where bugs hide. Treat a range as half-open: it includes the start but not the end. Two ranges overlap when each starts before the other ends. So a rental ending Wednesday at ten and the next starting Wednesday at ten do not clash, while Tuesday to Thursday does. The record's constructor also rejects a range whose end is not after its start.
// [start, end): end is not included
boolean overlaps(TimeRange o) {
return start.isBefore(o.end)
&& o.start.isBefore(end);
}
Mon 10:00 to Wed 10:00
Wed 10:00 to Thu 10:00: no clash
Tue 09:00 to Thu 09:00: clash
constructor rejects end <= start Calendar per vehicle
Each vehicle keeps its bookings in a tree map sorted by start time. Because a vehicle's bookings never overlap each other, only two can possibly clash with a new range: the one that starts at or just before it, and the next one after. Floor entry and higher entry find both in logarithmic time. That beats scanning a list of every booking the car ever had, and it is a detail interviewers notice.
TreeMap<Instant, Booking> calendar before = calendar.floorEntry(r.start) if before overlaps r: busy after = calendar.higherEntry(r.start) if after overlaps r: busy otherwise free O(log n) per vehicle, not a scan bookings never overlap each other
Flow: search
Search is a filter. Take the fleet at the branch, keep vehicles of the requested type, and ask each vehicle's calendar whether the range is free. With two sedans at the airport and one already booked from Monday to Wednesday, a search for Tuesday to Thursday returns exactly one. For a big fleet you would index vehicles by branch and type so the filter only touches candidates.
for (Vehicle v : fleetByBranch(b))
if (v.type == type
&& v.isFree(range)) out.add(v)
return out
two sedans at the airport,
one booked Mon to Wed
search Tue to Thu: 1 free Flow: book
Booking quotes the price, then walks the search results. For each candidate it tries to reserve the booking on that vehicle. Search ran without a lock, so the car may have been taken a moment ago; if the reservation fails, move on to the next candidate. The first success is stored and returned. If every candidate fails, the customer gets a clear no-availability error.
quote = pricing.quote(type, r)
for (Vehicle v : search(branch, type, r))
b = new Booking(id, c, v, r, quote)
if (v.tryReserve(b)) {
bookings.put(b.id, b)
return b
}
// lost a race: try the next one
throw: no free vehicle of this type Strategy + Decorator
Pricing is a strategy: daily pricing multiplies started days by a rate per type. Discounts are a decorator: a long rental discount wraps any pricing strategy, asks it for the base price, and takes ten percent off for seven days or more. Weekend surcharges, coupons or a loyalty discount are more decorators stacked the same way, and the service never changes. A seven day hatchback comes to eleven thousand three hundred and forty.
interface PricingStrategy {
long quote(VehicleType t, TimeRange r);
}
DailyPricing: startedDays x rate[type]
LongRentalDiscount(inner, 7 days, 10%)
base = inner.quote(t, r)
days >= 7 ? base x 90 / 100 : base
hatchback, 7 days at 1800.00
12600.00 less 10% = 11340.00 State machine
A booking is a small state machine. Booked can move to picked up or cancelled, and picked up can move to returned. Every change goes through one transition method that checks the current state under the vehicle's lock. So returning a car that was never picked up is rejected with a clear message, and cancelling removes the booking from the calendar so the car is free again.
BOOKED -> PICKED_UP -> RETURNED
BOOKED -> CANCELLED (frees the car)
transition(id, from, to):
synchronized (vehicle) {
if (status != from) throw
status = to
}
return before pick-up: rejected Flow: return
On return, move the booking to returned, then run a list of fee rules. Each rule is a small class that returns a labelled charge: the late fee charges every started hour past the end at a rate per type, the damage fee adds a flat amount. The invoice keeps the quoted rent plus whichever charges applied. Two hours fifty late on a sedan is three started hours, seven hundred and fifty extra.
b = transition(id, PICKED_UP, RETURNED) for (ReturnFee f : fees) c = f.fee(b, at, damaged) if (c.cents > 0) extras.add(c) return new Invoice(id, quote, extras) LateFee: started hours x rate[type] DamageFee: flat amount if damaged fuel, cleaning, tolls: new classes
Concurrency
Now the race. Twelve customers search at once and all see the one SUV as free. If booking were check, then insert, several would win. So checking the calendar and inserting the booking happen inside one synchronized method on that vehicle. Exactly one customer gets the SUV and the rest are told it is gone. The lock is per vehicle, so bookings for other cars never wait.
Give every shared field a safe home. The calendar is a plain tree map that is only touched under its vehicle's lock, and status changes use the same lock. The fleet and the bookings sit in concurrent maps and lists, ids come from an atomic counter, and records are immutable. In a real database the same guarantee comes from an exclusion constraint that forbids two overlapping ranges for one car.
synchronized boolean tryReserve(b) {
if (!isFree(b.range)) return false;
calendar.put(b.range.start, b);
return true;
}
check and insert under one lock
lock per vehicle: other cars and
other branches never wait
12 racers, 1 SUV: 1 booked, 11 not - calendar: TreeMap, only touched
- under the vehicle lock
- status: changed under the
- same vehicle lock
- fleet: ConcurrentHashMap of
- CopyOnWriteArrayList
- bookings: ConcurrentHashMap
- ids: AtomicLong
- records: immutable, shareable
- in a database: an exclusion
- constraint on (car, range)
Extensibility
Extensions slot in cleanly. A one-way rental records the return branch, moves the car to that fleet and adds a fee. A cleaning buffer pads each range by an hour inside the free check. Weekend surcharges and coupons are more pricing decorators, and fuel or toll charges are more return fees. Picking a specific car or features like automatic transmission is an extra search filter.
- one-way rental: a return branch,
- the car moves fleets, a fee
- cleaning buffer: pad each range
- by an hour in isFree()
- weekend surcharge, coupons:
- more pricing decorators
- fuel and tolls: more ReturnFees
- specific car or features:
- filter in search()
- loyalty tiers: a Customer field
Testing
The full code is below the player. The demo books two sedans and is refused a third on overlapping dates, proves a back-to-back booking at ten on Wednesday is allowed, applies the long rental discount, charges a late return by started hours, rejects a return before pick-up, frees a car on cancel, adds a damage fee, and finally races twelve customers for one SUV. Exactly one wins, every time.
B1: SED-1 for 2 days, quote 5000.00 Sedans free on the overlap: 1 Third request: no SEDAN free at AIRPORT Back-to-back from 10:00 Wed: SED-1 free B3: 7 days hatchback, 10% off, quote 11340.00 Return 2h50m late: rent 5000.00 + late 750.00 = 5750.00 Rejected: B2 is BOOKED, not PICKED_UP SUV race: 1 booked, 11 turned away
Follow-ups
Expect follow-ups. Why half-open ranges? Back-to-back rentals do not clash. Why a tree map? Only two neighbours can overlap, found in log time. What if a customer is late and the next booking is about to start? Reassign the next booking to another car of the same type. Holding a car during payment is a pending booking with a short expiry. And in SQL, use an exclusion constraint or lock the car's row while inserting.
- why half-open ranges?
- why a TreeMap per vehicle?
- customer is late and the next
- booking starts: swap the car
- hold a car while paying?
- BOOKED with a 10 min expiry
- search across many branches?
- index by city, then branch
- store it in SQL? exclusion
- constraint or row lock per car
Say it like this
The short version. Each vehicle owns a calendar of half-open ranges in a tree map, so only two neighbours can ever clash with a new booking. Reserving checks and inserts under that vehicle's lock, so no car is booked twice. Pricing is a strategy wrapped by discount decorators, return fees are a list of rules, and bookings move through a checked state machine.
- "Each vehicle owns a TreeMap
- calendar of half-open ranges;
- only two neighbours can clash.
- Reserving checks and inserts
- under the vehicle lock. Pricing
- is a strategy with discount
- decorators, fees at return are
- a list of rules, and bookings
- are a checked state machine."