The idea
What it is
“Design a hotel booking system like Booking.com.” One sentence, forty-five minutes, a blank file. Most candidates start typing entities inside ninety seconds, and most of them have already made the mistake that decides the round.
The mistake is small and it looks completely reasonable. It is a field called isBooked on a class called Room.
The whole lesson in one line
“Is this room free?” is not a yes/no question — it is a question about a range of dates. A boolean can only answer “free right now”. Availability is a function of (roomType, checkIn, checkOut). Once you say that sentence out loud, the nightly counter, the overlap test, the per-night price and the last-room race all follow from it. Say it in minute three, not minute thirty.
Room has no isBooked — a room number is something you hand over at check-in, not something you sell. And the green box is where free is decided: one counter per room type per night.Here is why the boolean is fatal rather than merely inelegant. Ask it three different questions and it gives the same answer to all three, and that answer is wrong at least twice.
isBooked can recover the information it never stored — which is why this is the one design decision you must get right before you write anything else.What is actually being graded
- Is availability a range question?
isAvailable(roomType, checkIn, checkOut)— and do you know that two stays clash only when their ranges overlap, with the testaStart < bEnd && bStart < aEnd? - Are the intervals half-open?
[checkIn, checkOut). If your code counts the checkout day as a night, thirty rooms become unsellable on every changeover day and your test suite will never notice. - Do you sell a room type, not a room? Guests book “a Deluxe”, not room 402. So inventory is a count per night, and assigning the actual room number is a check-in-time decision. Saying that out loud is the strongest single signal in this round.
- Is the multi-night take all-or-nothing? Check ALL nights, then take ALL nights. A partial decrement leaves your hotel in a state no guest asked for — the exact two-pass shape from Coffee Machine.
- Is price per night, or per stay? A three-night stay is
sum(rate(night)), nevernightlyRate × 3. And the booking stores the frozen breakdown so tomorrow's price change cannot rewrite yesterday's bill. - Does the last room go to exactly one guest? Guard the nightly counters, not the whole hotel, and take the night locks in sorted date order.
This is not the meeting-room problem
Meeting room scheduler also lives on the overlap test, and you should absolutely reuse it here. But there the resource is one named room and the answer is a conflict check against a list of intervals. Here you sell an interchangeable pool of thirty identical Deluxe rooms, so the answer is a count per night. Same arithmetic, completely different data structure — and the interviewer is watching to see whether you notice.
Mechanics
How it works
Step 1 · Clarify — 5 minutes
Six questions. They take ninety seconds and they decide what the next forty minutes look like. This is A repeatable 5-step framework applied to a problem where the first question is the whole game.
- Does a guest book a specific room, or a room type? — the question that unlocks everything. The answer is a type. Ask it first and the interviewer knows you have thought about this before.
- One hotel or many? — start with one hotel, keep
hotelIdon the inventory key so multi-property is a widening, not a rewrite. - Can a booking span multiple rooms? — yes, “2 Deluxe rooms for 3 nights”. It costs you one
roomsfield and it changes the counter arithmetic from ±1 to ±n. - Is the price the same every night? — no. Weekends, seasons and festivals differ, so the total is a sum over nights. Ask it; it is the second-biggest scoring question in the round.
- What happens on cancellation? — there is a policy: free until some hours before check-in, then a penalty. Model it as an object, not an
if. - Do we overbook? — hotels deliberately do. It is one number,
overbookBuffer, and it must live in exactly one place. - Payments, reviews, loyalty points, the mobile app, search ranking? — out of scope, in one sentence, and move on.
Step 2 · Nouns → classes
Read the prompt back and underline the nouns. Almost every one becomes a class, and the two that do not are the interesting ones.
RoomType and Room being separate is the sentence that carries this table. One is a product listing; the other is a key on a hook.Step 3 · The overlap test, and the <= that costs you thirty rooms
Two stays clash when their date ranges overlap. People reach for four separate cases — a starts inside b, b starts inside a, a contains b, b contains a — write eight comparisons, and get one of them wrong. There is one line that covers all four.
/**
* Two half-open ranges [aStart, aEnd) and [bStart, bEnd) overlap
* if and only if each one starts before the other one ends.
*
* STRICT "<" on BOTH sides. That is not a style choice — it is what makes
* "checkout Tuesday, check-in Tuesday" legal, which it must be.
*/
static boolean overlaps(LocalDate aStart, LocalDate aEnd,
LocalDate bStart, LocalDate bEnd) {
return aStart.isBefore(bEnd) && bStart.isBefore(aEnd);
}The off-by-one that makes thirty rooms unsellable
Write aStart <= bEnd && bStart <= aEnd and stays that merely touch now count as a clash. Guest A checks out on Tuesday morning; guest B wants to check in on Tuesday afternoon; your system says the room is taken. On a busy changeover day that is every room in the hotel, refused. The bug never throws, never logs, and passes every test that only ever books non-adjacent dates — which is every test anyone writes by hand.
Step 4 · Sell a room type — one counter per night
Nobody has ever asked a hotel for room 402. They ask for “a Deluxe”. The hotel has three Deluxe rooms and they are interchangeable, so the only question that matters is how many are still free on each night of your stay.
So the inventory is one number per cell of a grid: room type down the side, night across the top. Map<(RoomTypeId, LocalDate), int> — either the free count directly, or the booked count with free = totalRooms − booked. The second is better, because totalRooms can then change without rewriting history.
The sentence that scores highest in this round
“I assign the actual room number at check-in, not at booking time. At booking I only decrement a nightly counter for the room type. That way a maintenance closure, an upgrade, or a guest extending by a night never has to move anyone between rooms.” Say it unprompted while you are drawing the Inventory box. It signals that you have seen how hotels really work, and it pre-answers three follow-ups.
There is an honest alternative: give each individual room a sorted list of booked intervals and use the overlap test against it. It is worth naming, because it is not wrong — it is just right for a different shape of business.
Step 5 · Two passes — check ALL nights, then take ALL nights
Booking three nights means decrementing three counters. The temptation is to loop once: check a night, take it, move to the next. That works right up until night two is full — and now night one is decremented, no booking exists, and a room is held for a guest who does not exist. That is a leak, and nothing in your code will ever notice it.
One pass is the bug; two passes is the fix
Pass 1 — check every night. Pass 2 — only then, take every night. If any night fails in pass 1, you return without having touched a single counter. This is the identical shape to the ingredient tanks in Coffee Machine: verify the whole order, then consume the whole order. The prototype's 🩹 One-pass (buggy) toggle replays exactly this and leaves a red ⚠ leaked: 1 night on the grid.
/**
* Two passes over the SAME night list, under the SAME lock.
* pass 1 can every night afford it? (no writes at all)
* pass 2 take every night (no checks at all)
*
* Returning false in pass 1 means the inventory is byte-for-byte unchanged.
*/
boolean tryTake(RoomTypeId type, Stay stay, int rooms) {
List<LocalDate> nights = stay.nightList();
lockNightsInSortedOrder(type, nights); // sorted -> no deadlock
try {
for (LocalDate n : nights) // ---- pass 1: CHECK ALL
if (freeOn(type, n) < rooms) return false;
for (LocalDate n : nights) // ---- pass 2: TAKE ALL
booked.get(type).merge(n, rooms, Integer::sum);
return true;
} finally {
unlockNights(type, nights);
}
}The class diagram
book() (Open/Closed (OCP)). Notation: Class diagrams.Step 6 · Price is per night, not per stay
“It's ₹6,500 a night for three nights, so ₹19,500.” That sentence is wrong in every hotel on earth. Friday costs more than Tuesday. Diwali costs more than Friday. A corporate rate plan costs less than both. The total for a stay is a sum over its nights, and the interface that makes that possible is one method: rateFor(roomType, night) → paise.
Freeze the bill, and count in paise
The booking stores its own List<NightCharge> — one row per night, each an integer number of paise. It is never recomputed from the live RatePlan. If you recompute at display time, a Tuesday price change silently rewrites a bill somebody already agreed to, and a refund calculation done three days later disagrees with the confirmation email. Same integer-money discipline as Splitwise: long paise, never double.
The last room, and two guests
One Deluxe room left on 12–15 Aug. Two guests press Book in the same millisecond. Both threads read free = 1, both decide yes, both decrement — and the counter is now −1. Two people have a confirmation email and one of them is going to arrive at a hotel that has nowhere to put them.
The fix is not to lock the hotel. It is to make check-and-take atomic on the contended resource, which here is the set of nightly counters the stay touches — and nothing else. Two guests booking different nights, or different room types, never contend at all. More on the failure shape in Deadlock, race conditions, starvation and on the mechanics in Locks, Mutex, Semaphore.
Why the nights must be locked in sorted order
Guest A books 12→15, guest B books 14→17. They share night 14. If A grabs 12 then 13 then 14, and B grabs 16 then 15 then 14 — two threads each holding what the other needs. Taking the night locks in ascending date order gives every thread the same global ordering, which is the textbook cure for Deadlock, race conditions, starvation. It costs one sort() and it is worth saying out loud even if you never write it.
What the production answer sounds like
“In a single process I take a lock per (roomType, night). Across ten servers that does not exist, so the counter moves into the database and the check-and-take becomes one statement — UPDATE inventory SET booked = booked + 1 WHERE type = ? AND night = ? AND booked + 1 <= capacity, executed once per night inside one transaction, and if any row updates zero rows I roll back.” One sentence, and you have answered the distributed follow-up before it is asked. Related: Atomic operations & CAS.
Cancellation, overbooking, and search
Cancellation is two separate things and juniors merge them. One is how much money comes back, which depends on how long before check-in the guest cancelled. The other is what happens to the counters, which is always the same: release exactly the nights that were taken, exactly the number of rooms that were taken.
cancel().- Overbooking is a business rule, not a bug. Hotels sell more rooms than they have because a predictable slice of guests never arrive. Model it as
capacity() = totalRooms + overbookBufferonRoomType— one place, so nobody can compute capacity a second way and disagree. ThenfreeOn(night) = capacity() − booked(night), and every other line of code is unchanged. Naming it as a deliberate rule is one of the easiest strong signals in this round. - Search is the same query with a different threshold. “Hotels in Goa, 12–15 Aug, 2 guests” filters room types where
sleeps >= guestsandminFree(type, stay) >= roomsWanted. The minimum across the nights is the clean framing because it collapses a range question into a single number, and it is the same number the booking check uses — so search and book can never disagree about what is available. - Filter on the cheap thing first.
sleeps >= guestsis one comparison;minFreewalks every night. Ordering the filter that way is free and it is the kind of detail that reads as care rather than cleverness. - Search results are advisory, always. Between the search and the booking, someone else may have taken the room. That is not a bug to fix; it is why
book()re-checks under the lock and can still say no. Say this out loud — candidates who try to make search authoritative end up inventing a hold/lock system nobody asked for.
The follow-ups they always ask
- “Two rooms, not one.” — a
roomsfield on the booking and± roomsinstead of± 1on each counter. The two-pass check becomesfreeOn(night) >= rooms. Roughly four characters of change, which is the point of counting rather than flagging. - “A group block — 20 rooms for a wedding.” — same call with
rooms = 20, and now the all-or-nothing property is doing visible work: twenty rooms on four nights either all land or none do. In production a block is usually held rather than sold, which is a hold with an expiry — an inventory entry with a TTL, released by a sweeper. - “The guest wants to move the dates.” — this is cancel + rebook against the counters, and it can fail. Release the old nights, try to take the new ones; if the take fails, put the old nights back and tell the guest their original booking is intact. Do NOT release-then-hope. Say the rollback out loud — it is the same all-or-nothing thinking one level up.
- “What about no-shows?” — a status transition, not a new flow. At check-in cut-off,
CONFIRMED → NO_SHOW, runrelease()so the nights become sellable for whatever is left of the stay, and charge whatever the policy says. ModellingBookingStatusas a real state machine (State) keeps cancelled and no-show from becoming two booleans that can both be true. - “Taxes and fees?” — they are per-night too (GST slabs change with the nightly rate in India), so they belong beside
NightCharge, not as a multiplier on the total. Keep them as separate integer paise lines so a refund can return the base and keep the fee if that is the rule. - “What changes at ten servers?” — the counters leave memory. The check-and-take becomes a conditional
UPDATEper night inside one database transaction, and you add an idempotency key onbook()so a retried request cannot double-decrement. Nothing about the model changes; only where the number lives. - “How do you test it?” — a property test: generate random bookings, cancellations and date modifications, and assert after every single operation that for every type and night,
0 <= booked(night) <= capacity()and thatbooked(night)equals the number of confirmed bookings covering that night. That one assertion catches leaks, oversells and off-by-ones together.
How this round is lost
boolean isBookedonRoom. The fastest possible loss. Everything built on top of it inherits a data model that cannot express the question being asked.<=in the overlap test, or!d.isAfter(checkOut)in the night loop. The changeover-day bug. Nothing throws, and thirty rooms silently stop selling on the busiest day of the week.- One pass instead of two. Night 1 is decremented, night 2 fails, no booking exists, and a room is held forever for nobody. Reset is the only cure, and production has no reset.
nightlyRate × nights. A festival night sold at the Tuesday price, or worse, a Tuesday sold at the festival price — and a bill that changes every time it is displayed because it was never frozen.synchronizedon the whole hotel. It is correct and it is a red flag: it says you did not identify what is actually contended. Guard the nights the stay touches, and only those.- Recomputing the total from the live rate plan at refund time. The refund disagrees with the confirmation email, and now it is a support ticket instead of a bug.
- Capacity computed in two places.
totalRoomsin one method andtotalRooms + bufferin another. Overbooking then works everywhere except the one path that forgot, and the mismatch surfaces as an oversell. - No
main(). In this tier a system that has never been run is a design document. Print the grid before and after a refused booking — that single piece of output proves the all-or-nothing property better than any explanation.
Interactive prototype
See it. Build it. Break it.
A sandboxed, hands-on simulation — no setup, no install. Play with it as you read.
About this simulation
A live nightly-availability calendar you book against. Click 12 then 15 on the date strip and read the call line: 3 nights checked, not 4. Press 🛏 Book and watch the two passes — blue checking every night, then orange taking every night. Then press 🔴 Sell out night 2 and book again: it is refused in pass 1 and nothing moves. Flip 🩹 One-pass (buggy) and repeat — night 1 is decremented, night 2 fails, and a red ⚠ leaked: 1 appears. Finish with ↔️ Checkout day (two stays share 14 Aug and both succeed), the ⚠️ Use <= instead of < toggle, and ⚔️ Two guests, last room under 🔓 Unguarded to watch a count go to −1.
Hands-on
Try these yourself
Open the prototype above, predict what happens, then verify.
Count the nights, not the dates
On the date strip click 12, then click 15. Three cells light up — 12, 13, 14 — and the call line reads inventory.isAvailable(DELUXE, 12 Aug → 15 Aug) → 3 nights checked. Now press the ⚠️ Use <= instead of < toggle and look again: the same two clicks now highlight 4 nights and the call line says 4 nights checked. That single extra cell is the off-by-one that makes every changeover day unsellable. Toggle it back off before you continue.
Watch the two passes, then break one of them
With ✨ Deluxe selected and 12→15 chosen, press 🛏 Book. Pass 1 flashes each night blue (checking, no writes), pass 2 flashes each night orange (taking), and only then does the booking bar appear and the counts drop. Now press 🔴 Sell out night 2 and press 🛏 Book again — it is refused during pass 1, and the explain panel says nothing was decremented. Compare the counts before and after: identical.
The centrepiece — run the same booking one-pass
Press ↺ Reset, then 🔴 Sell out night 2, then turn on 🩹 One-pass (buggy) and press 🛏 Book. This time night 1 is taken as it goes, night 2 fails, and the booking never exists. The grid is left holding a room for nobody and a red ⚠ leaked: 1 appears in the counter strip. Nothing in the system will ever notice — only ↺ Reset clears it. That contrast is the whole reason book() has two loops.
Prove the changeover day, then the last-room race
Press ↔️ Checkout day: with only ONE room left, the system books 12→14 and then 14→16 and both succeed — they share 14 Aug and never clash. Turn on ⚠️ Use <= instead of < and press it again: the second booking is refused and 14 Aug shades red. Then press ⚔️ Two guests, last room under 🔒 Guarded — one confirmation, one honest sold out. Switch to 🔓 Unguarded and press it again: both are confirmed, the count reads −1, and a red ⚠ oversold: 1 appears.
Price it twice, then cancel it
With a 12→15 Deluxe selection, press 📏 Flat × nights and read the total, then press 📅 Per-night rates and read it again — the breakdown shows two weekday nights and one festival night, the totals differ by thousands of rupees, and the caption says booking code changed: 0 lines. Finally press 🚫 Cancel on the booking: the exact three cells tick back up and the refund is shown with the policy band that produced it. Then close this and rebuild it blank-file in the order the lesson used: Stay with overlaps() → Inventory.freeOn/minFree → tryTake with the two passes → RatePlan summed per night → CancellationPolicy → the sorted night locks → a main() that prints the grid before and after a refused booking.
In practice
When to use it — and what trips people up
The shape you just learned
Take the hotel away and what is left is a pool of interchangeable units, reserved over a contiguous range of time slots. Once you can see that shape, the same four moves apply everywhere: half-open ranges, one counter per slot, availability as the minimum across the range, and a check-all-then-take-all that is atomic as a unit.
- Airline and train seat inventory — seats in a fare class across a set of flight legs. Booking a connecting itinerary is the same all-or-nothing take across several legs, and airlines overbook for exactly the reason hotels do.
- Cloud capacity and reserved instances — N identical machines held for a window. The counter is per instance type per hour, and the minimum across the window is the same query.
- Equipment, vehicle and tool rental — twelve identical drills, booked from Tuesday to Friday. The half-open interval matters just as much: the day it comes back is the day it goes out again.
- Course, class and clinic scheduling — thirty identical seats per session, and a multi-session enrolment that must land completely or not at all.
- Warehouse slotting and dock scheduling — a fixed number of interchangeable bays, reserved over an arrival window.
- Any quota over time — API tokens per minute, licences per day, delivery slots per hour. Distinct from Rate Limiter, which counts a rolling window rather than reserving future ones.
The 30-second version to say out loud
“Availability is a function of room type and a date range, not a flag on a room. I keep one counter per (room type, night) and compute availability across a stay as the minimum across its nights. Ranges are half-open, so 12→15 is three nights and a checkout day is immediately re-sellable. Booking checks every night before taking any night, under locks taken in sorted date order on just the nights involved. Price is summed per night from a RatePlan and frozen onto the booking in integer paise. Cancellation is a policy object that returns a refund; releasing the nights is the same code path every time. The actual room number is assigned at check-in.”
Where this design stops working
- When the units stop being interchangeable. The instant a guest can request room 402 specifically — a sea view, an accessible bathroom, adjoining rooms for a family — a count is not enough. Either promote the distinction to its own room type, or switch to per-room interval lists and accept the cost.
- When bookings must survive a crash. An in-memory map plus a process-local lock becomes a database row plus a transaction. The check-and-take turns into a conditional
UPDATEper night, andbook()needs an idempotency key so a retried request cannot double-decrement. - When there are ten servers. Process-local
ReentrantLocks guard nothing across machines. The counters have to live where the atomicity lives — a database with a uniqueness or check constraint, or a single-writer partition per (hotel, night). - When the calendar horizon is large. A cell per type per night is cheap for one hotel and a year; it is not cheap for a million properties and a two-year horizon. Real systems store bookings and materialise nightly counters only for the hot window, rebuilding the rest on demand.
- When pricing becomes dynamic.
rateFor(type, night)assumes the rate for a night is knowable independently. Yield management prices the whole itinerary — length of stay, lead time, current occupancy — so the interface has to widen to take the stay, and the moment it does, the frozen breakdown becomes even more important, not less. - When holds and payment enter. A real checkout holds inventory for ten minutes while a card is charged. That is an inventory entry with a TTL and a sweeper, plus a state machine on the booking — and now the hold is the contended resource, not the booking.
If you only remember one thing
Availability is a question about a range, and the answer is a count per night. Write Stay with a half-open [checkIn, checkOut) and an overlaps() that uses strict < on both sides; write Inventory with one counter per (type, night) and a tryTake that checks every night before it touches any night. Those two classes are eighty percent of the grade, and everything else in this lesson hangs off them.
What it gives you
- A counter per (room type, night) answers availability in O(nights) regardless of how many physical rooms exist — a hundred identical Deluxe rooms cost exactly the same as three.
- Half-open [checkIn, checkOut) intervals make the changeover day correct by construction, so a room becomes re-sellable the morning it is vacated without a single special case.
- The two-pass take makes a partial multi-night booking unrepresentable: either every night is decremented or none is, so the inventory can never hold a room for a booking that does not exist.
- Locking only the nights a stay touches, in sorted date order, keeps the critical section to a handful of integer operations while remaining deadlock-free for overlapping stays.
- Deferring the room number to check-in means maintenance closures, upgrades and stay extensions never require moving a guest between rooms, and it lets overbooking be a single number on RoomType.
- Per-night charges frozen on the booking mean a later price change cannot rewrite an agreed bill, and the refund calculation always matches the confirmation the guest received.
Common mistakes
- Counts cannot express a request for a specific room, so anything a guest can actually ask for — sea view, accessible, adjoining — has to become its own room type or force a different model entirely.
- The nightly grid grows with room types multiplied by the booking horizon, which is fine for one hotel and wasteful for a marketplace with millions of properties and a two-year window.
- Process-local night locks are worthless across servers; the correctness argument has to be rebuilt around database constraints the moment there is a second process.
- Overbooking makes the counters deliberately able to exceed physical rooms, so “sold out” and “actually full” are different questions and someone has to own the walk-in policy when the gamble loses.
- Freezing the per-night breakdown duplicates pricing data on every booking, so a genuine pricing error has to be corrected by an explicit adjustment rather than by fixing the rate plan.
- Availability from search is advisory and can go stale between the search and the booking, which is correct but produces a user experience that needs explaining rather than fixing.
Reference
Code & further reading
A minimal reference implementation and pointers worth bookmarking.
import java.time.*;
import java.time.temporal.ChronoUnit;
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.locks.ReentrantLock;
/* =============================================================== money */
/** Every amount in this file is an integer number of PAISE. Never a double. */
final class Money {
static String fmt(long paise) {
long a = Math.abs(paise);
return (paise < 0 ? "-" : "") + "Rs." + (a / 100) + "." + String.format("%02d", a % 100);
}
}
enum RoomTypeId { STANDARD, DELUXE, SUITE }
enum BookingStatus { CONFIRMED, CHECKED_IN, CANCELLED, NO_SHOW }
/* ================================================================ stay */
/**
* A date range, HALF-OPEN: [checkIn, checkOut).
* The checkout day is NOT a night. 12 Aug -> 15 Aug is THREE nights: 12, 13, 14.
*/
record Stay(LocalDate checkIn, LocalDate checkOut) {
Stay {
if (!checkIn.isBefore(checkOut))
throw new IllegalArgumentException("check-out must be after check-in");
}
int nights() { return (int) ChronoUnit.DAYS.between(checkIn, checkOut); }
/** The one line the whole problem turns on. STRICT "<" on BOTH sides. */
boolean overlaps(Stay o) {
return checkIn.isBefore(o.checkOut) && o.checkIn.isBefore(checkOut);
}
/** The buggy version, kept here only so main() can print the difference. */
boolean overlapsBuggy(Stay o) {
return !checkIn.isAfter(o.checkOut) && !o.checkIn.isAfter(checkOut);
}
/** Every night this stay occupies. Note "isBefore", NOT "!isAfter". */
List<LocalDate> nightList() {
List<LocalDate> out = new ArrayList<>(nights());
for (LocalDate d = checkIn; d.isBefore(checkOut); d = d.plusDays(1)) out.add(d);
return out;
}
@Override public String toString() {
return checkIn.getDayOfMonth() + "->" + checkOut.getDayOfMonth() + " Aug (" + nights() + "n)";
}
}
/** What you SELL. capacity() is the ONE place overbooking is decided. */
record RoomType(RoomTypeId id, String name, int sleeps, int totalRooms, int overbookBuffer) {
int capacity() { return totalRooms + overbookBuffer; }
}
/** What you HAND OVER at check-in. Notice what is missing: no isBooked flag. */
record Room(String number, RoomTypeId type) {}
/* =========================================================== inventory */
/**
* One counter per (room type, night). This is the whole availability model.
* Locks are per night too, so two stays that share no night never contend.
*/
class Inventory {
private final Map<RoomTypeId, RoomType> types = new EnumMap<>(RoomTypeId.class);
private final Map<RoomTypeId, Map<LocalDate, Integer>> booked = new EnumMap<>(RoomTypeId.class);
private final ConcurrentMap<String, ReentrantLock> nightLocks = new ConcurrentHashMap<>();
Inventory(List<RoomType> roomTypes) {
for (RoomType t : roomTypes) {
types.put(t.id(), t);
booked.put(t.id(), new ConcurrentHashMap<>());
}
}
RoomType type(RoomTypeId id) { return types.get(id); }
Collection<RoomType> allTypes() { return types.values(); }
int freeOn(RoomTypeId id, LocalDate night) {
return type(id).capacity() - booked.get(id).getOrDefault(night, 0);
}
/** Availability across a RANGE is the MINIMUM across its nights. */
int minFree(RoomTypeId id, Stay stay) {
int min = Integer.MAX_VALUE;
for (LocalDate n : stay.nightList()) min = Math.min(min, freeOn(id, n));
return min;
}
private List<ReentrantLock> locksFor(RoomTypeId id, List<LocalDate> nights) {
List<String> keys = new ArrayList<>(nights.size());
for (LocalDate n : nights) keys.add(id.name() + "@" + n);
Collections.sort(keys); // SORTED -> a global order -> no deadlock
List<ReentrantLock> out = new ArrayList<>(keys.size());
for (String k : keys) out.add(nightLocks.computeIfAbsent(k, x -> new ReentrantLock()));
return out;
}
/**
* TWO PASSES under the night locks:
* pass 1 can EVERY night afford it? (zero writes)
* pass 2 take EVERY night (zero checks)
* Returning false means the inventory is byte-for-byte unchanged.
*/
boolean tryTake(RoomTypeId id, Stay stay, int rooms) {
if (rooms <= 0) throw new IllegalArgumentException("rooms must be positive");
List<LocalDate> nights = stay.nightList();
List<ReentrantLock> locks = locksFor(id, nights);
for (ReentrantLock l : locks) l.lock();
try {
for (LocalDate n : nights) // pass 1: CHECK ALL
if (freeOn(id, n) < rooms) return false;
for (LocalDate n : nights) // pass 2: TAKE ALL
booked.get(id).merge(n, rooms, Integer::sum);
return true;
} finally {
for (int i = locks.size() - 1; i >= 0; i--) locks.get(i).unlock();
}
}
/** THE BUG, kept for the demo: takes as it goes and leaks on failure. */
boolean tryTakeOnePassBuggy(RoomTypeId id, Stay stay, int rooms) {
for (LocalDate n : stay.nightList()) {
if (freeOn(id, n) < rooms) return false; // earlier nights stay taken
booked.get(id).merge(n, rooms, Integer::sum);
}
return true;
}
void release(RoomTypeId id, Stay stay, int rooms) {
List<LocalDate> nights = stay.nightList();
List<ReentrantLock> locks = locksFor(id, nights);
for (ReentrantLock l : locks) l.lock();
try {
for (LocalDate n : nights) booked.get(id).merge(n, -rooms, Integer::sum);
} finally {
for (int i = locks.size() - 1; i >= 0; i--) locks.get(i).unlock();
}
}
/** The property every test asserts: 0 <= booked <= capacity, on every night. */
void assertInvariant() {
for (RoomType t : types.values())
for (Map.Entry<LocalDate, Integer> e : booked.get(t.id()).entrySet())
if (e.getValue() < 0 || e.getValue() > t.capacity())
throw new IllegalStateException("oversold " + t.name() + " on " + e.getKey()
+ ": booked=" + e.getValue() + " capacity=" + t.capacity());
}
String gridLine(RoomTypeId id, LocalDate from, int days) {
StringBuilder sb = new StringBuilder(String.format("%-9s", type(id).name()));
for (int i = 0; i < days; i++) sb.append(String.format("%3d", freeOn(id, from.plusDays(i))));
return sb.toString();
}
}
/* ============================================================= pricing */
interface RatePlan {
/** Paise, for ONE night. Never for a stay. */
long rateFor(RoomTypeId type, LocalDate night);
String name();
}
/** The wrong-but-common one, kept so the demo can show the gap. */
class FlatRatePlan implements RatePlan {
private final Map<RoomTypeId, Long> base;
FlatRatePlan(Map<RoomTypeId, Long> base) { this.base = base; }
public long rateFor(RoomTypeId type, LocalDate night) { return base.get(type); }
public String name() { return "FlatRatePlan"; }
}
class SeasonalRatePlan implements RatePlan {
private final Map<RoomTypeId, Long> weekday;
private final Set<LocalDate> festivalNights;
SeasonalRatePlan(Map<RoomTypeId, Long> weekday, Set<LocalDate> festivalNights) {
this.weekday = weekday;
this.festivalNights = festivalNights;
}
public long rateFor(RoomTypeId type, LocalDate night) {
long r = weekday.get(type);
DayOfWeek d = night.getDayOfWeek();
if (d == DayOfWeek.SATURDAY || d == DayOfWeek.SUNDAY) r = r * 3 / 2; // weekend
if (festivalNights.contains(night)) r = r * 5 / 2; // festival wins
return r;
}
public String name() { return "SeasonalRatePlan"; }
}
/** One frozen line of the bill. Integer paise, tied to a specific night. */
record NightCharge(LocalDate night, long paise) {}
/* ======================================================== cancellation */
interface CancellationPolicy {
/** How much comes back, in paise, if the guest cancels at "at". */
long refundFor(Booking b, Instant at, ZoneId zone);
String describe();
}
class FlexiblePolicy implements CancellationPolicy {
public long refundFor(Booking b, Instant at, ZoneId zone) {
long hours = Duration.between(at, b.stay().checkIn().atStartOfDay(zone).toInstant()).toHours();
long total = b.total();
if (hours >= 48) return total; // free
if (hours >= 24) return Math.max(0, total - b.firstNightCost()); // keep one night
return 0; // no refund
}
public String describe() { return "free >=48h, one night 48-24h, nothing inside 24h"; }
}
class NonRefundablePolicy implements CancellationPolicy {
public long refundFor(Booking b, Instant at, ZoneId zone) { return 0; }
public String describe() { return "non-refundable"; }
}
/* ============================================================= booking */
class Booking {
private final String id, guestId;
private final RoomTypeId type;
private final Stay stay;
private final int rooms;
private final List<NightCharge> charges; // FROZEN at booking time
private final Instant bookedAt;
private BookingStatus status = BookingStatus.CONFIRMED;
private final List<String> assignedRooms = new ArrayList<>(); // filled at CHECK-IN
Booking(String id, String guestId, RoomTypeId type, Stay stay, int rooms,
List<NightCharge> charges, Instant bookedAt) {
this.id = id; this.guestId = guestId; this.type = type; this.stay = stay;
this.rooms = rooms; this.charges = List.copyOf(charges); this.bookedAt = bookedAt;
}
String id() { return id; }
String guestId() { return guestId; }
RoomTypeId type() { return type; }
Stay stay() { return stay; }
int rooms() { return rooms; }
List<NightCharge> charges() { return charges; }
Instant bookedAt() { return bookedAt; }
BookingStatus status() { return status; }
void setStatus(BookingStatus s) { status = s; }
List<String> assignedRooms() { return assignedRooms; }
long firstNightCost() { return charges.get(0).paise() * rooms; }
long total() {
long s = 0;
for (NightCharge c : charges) s += c.paise();
return s * rooms;
}
String breakdown() {
StringBuilder sb = new StringBuilder();
for (NightCharge c : charges)
sb.append(" ").append(c.night()).append(" ").append(Money.fmt(c.paise())).append("\n");
sb.append(" total x").append(rooms).append(" room(s) = ").append(Money.fmt(total()));
return sb.toString();
}
}
/* ===================================================== booking service */
class BookingService {
private final Inventory inventory;
private final RatePlan ratePlan;
private final CancellationPolicy policy;
private final ZoneId zone;
private final Map<RoomTypeId, Deque<Room>> freeRooms = new EnumMap<>(RoomTypeId.class);
private final Map<String, Booking> bookings = new ConcurrentHashMap<>();
private int seq = 0;
BookingService(Inventory inv, RatePlan rp, CancellationPolicy cp, ZoneId zone, List<Room> rooms) {
this.inventory = inv; this.ratePlan = rp; this.policy = cp; this.zone = zone;
for (Room r : rooms) freeRooms.computeIfAbsent(r.type(), k -> new ArrayDeque<>()).add(r);
}
private synchronized String nextId() { return "BK-" + (++seq); }
/** Advisory: someone may take the room between this call and book(). */
List<RoomTypeId> search(Stay stay, int guests, int roomsWanted) {
List<RoomTypeId> out = new ArrayList<>();
for (RoomType t : inventory.allTypes())
if (t.sleeps() >= guests && inventory.minFree(t.id(), stay) >= roomsWanted) // cheap filter first
out.add(t.id());
return out;
}
List<NightCharge> quote(RoomTypeId type, Stay stay) {
List<NightCharge> out = new ArrayList<>(stay.nights());
for (LocalDate n : stay.nightList()) out.add(new NightCharge(n, ratePlan.rateFor(type, n)));
return out;
}
/** "at" is a PARAMETER so every test is deterministic. */
Optional<Booking> book(String guestId, RoomTypeId type, Stay stay, int rooms, Instant at) {
List<NightCharge> charges = quote(type, stay); // price first: touches no state
if (!inventory.tryTake(type, stay, rooms)) return Optional.empty();
Booking b = new Booking(nextId(), guestId, type, stay, rooms, charges, at);
bookings.put(b.id(), b);
return Optional.of(b);
}
long cancel(String bookingId, Instant at) {
Booking b = bookings.get(bookingId);
if (b == null || b.status() != BookingStatus.CONFIRMED) return 0;
long refund = policy.refundFor(b, at, zone); // the money question
inventory.release(b.type(), b.stay(), b.rooms()); // the counter question - always the same
b.setStatus(BookingStatus.CANCELLED);
return refund;
}
/** Moving the dates is cancel + rebook against the counters, and it CAN fail. */
boolean modifyDates(String bookingId, Stay newStay, Instant at) {
Booking b = bookings.get(bookingId);
if (b == null || b.status() != BookingStatus.CONFIRMED) return false;
inventory.release(b.type(), b.stay(), b.rooms());
if (!inventory.tryTake(b.type(), newStay, b.rooms())) {
inventory.tryTake(b.type(), b.stay(), b.rooms()); // put it back - rollback
return false;
}
Booking moved = new Booking(b.id(), b.guestId(), b.type(), newStay, b.rooms(),
quote(b.type(), newStay), at);
bookings.put(moved.id(), moved);
return true;
}
/** The room NUMBER is decided here, not at booking time. */
List<String> checkIn(String bookingId) {
Booking b = bookings.get(bookingId);
if (b == null || b.status() != BookingStatus.CONFIRMED) return List.of();
Deque<Room> pool = freeRooms.get(b.type());
for (int i = 0; i < b.rooms() && !pool.isEmpty(); i++) b.assignedRooms().add(pool.poll().number());
b.setStatus(BookingStatus.CHECKED_IN);
return b.assignedRooms();
}
Booking get(String id) { return bookings.get(id); }
}
/* ================================================================ demo */
public class HotelBooking {
static final ZoneId IST = ZoneId.of("Asia/Kolkata");
static LocalDate aug(int d) { return LocalDate.of(2026, 8, d); }
public static void main(String[] args) throws Exception {
List<RoomType> types = List.of(
new RoomType(RoomTypeId.STANDARD, "Standard", 2, 6, 0),
new RoomType(RoomTypeId.DELUXE, "Deluxe", 3, 3, 0),
new RoomType(RoomTypeId.SUITE, "Suite", 4, 2, 0));
List<Room> rooms = new ArrayList<>();
for (int i = 1; i <= 6; i++) rooms.add(new Room("30" + i, RoomTypeId.STANDARD));
for (int i = 1; i <= 3; i++) rooms.add(new Room("40" + i, RoomTypeId.DELUXE));
for (int i = 1; i <= 2; i++) rooms.add(new Room("50" + i, RoomTypeId.SUITE));
Map<RoomTypeId, Long> weekday = Map.of(
RoomTypeId.STANDARD, 400000L, RoomTypeId.DELUXE, 650000L, RoomTypeId.SUITE, 1200000L);
Inventory inv = new Inventory(types);
RatePlan seasonal = new SeasonalRatePlan(weekday, Set.of(aug(14), aug(15)));
RatePlan flat = new FlatRatePlan(weekday);
BookingService svc = new BookingService(inv, seasonal, new FlexiblePolicy(), IST, rooms);
Instant now = LocalDateTime.of(2026, 8, 10, 12, 0).atZone(IST).toInstant();
Stay s1215 = new Stay(aug(12), aug(15));
System.out.println("=== 0. half-open intervals =====================================");
System.out.println("Stay(12,15).nights() = " + s1215.nights() + " <- three, not four");
System.out.println("nightList() = " + s1215.nightList());
Stay a = new Stay(aug(12), aug(14)), b = new Stay(aug(14), aug(16));
System.out.println("overlaps(12->14, 14->16) = " + a.overlaps(b) + " <- checkout day is free");
System.out.println("overlapsBuggy(same, with <=) = " + a.overlapsBuggy(b) + " <- the off-by-one");
System.out.println("\n=== 1. search ==================================================");
System.out.println("search(12->15, guests=2, rooms=1) = " + svc.search(s1215, 2, 1));
System.out.println("\n=== 2. per-night pricing =======================================");
long flatTotal = 0;
for (LocalDate n : s1215.nightList()) flatTotal += flat.rateFor(RoomTypeId.DELUXE, n);
Optional<Booking> aarti = svc.book("aarti", RoomTypeId.DELUXE, s1215, 1, now);
System.out.println("Aarti books a Deluxe " + s1215 + " -> " + aarti.get().id());
System.out.println(aarti.get().breakdown());
System.out.println(" flat x nights would be = " + Money.fmt(flatTotal)
+ " (short by " + Money.fmt(aarti.get().total() - flatTotal) + ")");
System.out.println("\n=== 3. all-or-nothing ==========================================");
svc.book("house", RoomTypeId.DELUXE, new Stay(aug(13), aug(14)), 2, now); // night 13 -> 0 free
System.out.println("before: " + inv.gridLine(RoomTypeId.DELUXE, aug(11), 6));
Optional<Booking> ravi = svc.book("ravi", RoomTypeId.DELUXE, new Stay(aug(11), aug(16)), 1, now);
System.out.println("Ravi books Deluxe 11->16 -> " + (ravi.isPresent() ? ravi.get().id() : "SOLD OUT"));
System.out.println("after : " + inv.gridLine(RoomTypeId.DELUXE, aug(11), 6) + " <- identical");
System.out.println("\n=== 4. one-pass leak (the bug) =================================");
System.out.println("before: " + inv.gridLine(RoomTypeId.DELUXE, aug(11), 6));
boolean buggy = inv.tryTakeOnePassBuggy(RoomTypeId.DELUXE, new Stay(aug(11), aug(16)), 1);
System.out.println("one-pass take 11->16 -> " + (buggy ? "ok" : "FAILED"));
System.out.println("after : " + inv.gridLine(RoomTypeId.DELUXE, aug(11), 6) + " <- night 11 LEAKED");
inv.release(RoomTypeId.DELUXE, new Stay(aug(11), aug(12)), 1); // clean up the leak
System.out.println("\n=== 5. the changeover day ======================================");
svc.book("house", RoomTypeId.SUITE, new Stay(aug(12), aug(18)), 1, now); // 1 suite left
Optional<Booking> x = svc.book("meera", RoomTypeId.SUITE, new Stay(aug(12), aug(14)), 1, now);
Optional<Booking> y = svc.book("kabir", RoomTypeId.SUITE, new Stay(aug(14), aug(16)), 1, now);
System.out.println("only 1 Suite left. 12->14 = " + (x.isPresent() ? "CONFIRMED" : "sold out")
+ " , 14->16 = " + (y.isPresent() ? "CONFIRMED" : "sold out") + " <- both, sharing 14 Aug");
System.out.println("\n=== 6. two guests, one last room ===============================");
svc.book("house", RoomTypeId.STANDARD, new Stay(aug(17), aug(18)), 5, now); // 1 Standard left
Stay night17 = new Stay(aug(17), aug(18));
List<String> results = Collections.synchronizedList(new ArrayList<>());
CountDownLatch go = new CountDownLatch(1);
Runnable racer = () -> {
try { go.await(); } catch (InterruptedException ignored) { }
Optional<Booking> r = svc.book("racer", RoomTypeId.STANDARD, night17, 1, now);
results.add(r.isPresent() ? "CONFIRMED " + r.get().id() : "sold out");
};
Thread t1 = new Thread(racer), t2 = new Thread(racer);
t1.start(); t2.start(); go.countDown(); t1.join(); t2.join();
System.out.println("two threads, one room -> " + results);
System.out.println("free on 17 Aug = " + inv.freeOn(RoomTypeId.STANDARD, aug(17)));
inv.assertInvariant();
System.out.println("invariant 0 <= booked <= capacity: HOLDS");
System.out.println("\n=== 7. cancellation ============================================");
System.out.println("before: " + inv.gridLine(RoomTypeId.DELUXE, aug(11), 6));
long refund = svc.cancel(aarti.get().id(), now);
System.out.println("Aarti cancels 36h before check-in, total " + Money.fmt(aarti.get().total()));
System.out.println("refund = " + Money.fmt(refund) + " (one night kept)");
System.out.println("after : " + inv.gridLine(RoomTypeId.DELUXE, aug(11), 6) + " <- 3 cells back up");
System.out.println("\n=== 8. moving the dates can fail ===============================");
boolean moved = svc.modifyDates(x.get().id(), new Stay(aug(13), aug(15)), now);
System.out.println("move Meera's suite to 13->15 -> " + (moved ? "moved" : "REFUSED, original intact"));
System.out.println("Meera still holds = " + svc.get(x.get().id()).stay());
System.out.println("\n=== 9. the room number is a CHECK-IN decision ==================");
System.out.println("Kabir checks in -> room " + svc.checkIn(y.get().id()));
inv.assertInvariant();
}
}References & further reading
8 sources- Articlegithub.com
awesome-low-level-design — Hotel Management System
The canonical write-up of this exact interview problem, with the entity list most interviewers already have in their head before you start.
- Articleen.wikipedia.org
Allen's interval algebra
The formal enumeration of the thirteen ways two intervals can relate. Worth reading once, so you can say with confidence that the four overlapping cases collapse into a single expression.
- Articlemartinfowler.com
Martin Fowler — Range and Temporal Patterns
Fowler on modelling time properly: ranges as value objects, half-open by convention, and why “effective dating” shows up in every serious domain model.
- Docspostgresql.org
PostgreSQL — range types and exclusion constraints
The production answer to the last-room race. A daterange column plus an EXCLUDE constraint makes an overlapping booking impossible at the database level — and the docs spell out the half-open default.
- Articlemartinfowler.com
Martin Fowler — Money
Why a rate is a value object holding an integer of the smallest unit plus a currency. Read it before you type double anywhere near a nightly rate.
- Book
Designing Data-Intensive Applications — Martin Kleppmann
Chapter 7 on transactions and write skew is exactly the last-room race, one abstraction level up: two readers, one decision each, and a constraint that neither transaction can see the other breaking.
- Docsdocs.oracle.com
Java — java.time.LocalDate and Temporal API
Use isBefore and isAfter rather than compareTo, and note that ChronoUnit.DAYS.between is exactly the half-open night count you want.
- Articleen.wikipedia.org
Revenue management and overbooking — an overview
Why hotels and airlines deliberately sell more rooms than they have. Useful for one confident sentence when the interviewer asks whether overbooking is a bug.
Knowledge check
Did it land?
Quick questions, answers revealed on submit. Sign in to save your best score.
question 01 / 08
A candidate opens with class Room { boolean isBooked; }. What is the fundamental problem?
question 02 / 08
Which single expression correctly detects that two stays clash, given half-open ranges?
question 03 / 08
Stay(12 Aug, 15 Aug). How many nights, and which ones?
question 04 / 08
Why decrement a per-night count for a room type instead of marking a specific room as taken for those dates?
question 05 / 08
A three-night booking is being made. Night 2 turns out to be full. What must be true of your implementation?
question 06 / 08
Two guests take the last Deluxe room for the same nights at the same instant. What is the right guard?
question 07 / 08
A guest stays three nights: two weekdays and one festival night. How is the total computed and stored?
question 08 / 08
The interviewer asks you to let a guest move an existing booking to different dates. What is the correct answer?
0/8 answered