InterviewKata
Low-level design · Problem P13 of 15 · Bigger designs

Hotel reservation

Hotel booking looks like movie booking, but the resource is a range of nights instead of a seat. Everything hinges on one line: when do two stays overlap? Get that right (half-open ranges) and search, booking and cancellation follow.

1. The prompt

The prompt"Design a hotel reservation system. Guests search for a room type for a range of dates and book; they can cancel. A room must never be booked twice for the same night."

2. Clarify the requirements

Spend the first five minutes here. Ask, then write the answers down where the interviewer can see them.

AskAssume (unless told otherwise)
Is the check-out day a night?No: a stay is the half-open range [in, out).
Price?Nights × the room type's nightly rate.
Which room if several are free?The lowest number (any rule works; make it explicit).
Dates?Day numbers in the demo; real dates in production.

Must do

  • Search available rooms of a type for [check-in, check-out)
  • Book the first free room and price it
  • Cancel a reservation

Must be

  • No overlapping stays in one room
  • Back-to-back stays allowed (one leaves, one arrives the same day)
  • Reject invalid ranges

Out of scope

  • Payments, loyalty, overbooking strategies (follow-up)
  • Multiple hotels and search ranking

3. The classes

The class diagram: arrows show who uses or holds whom.
ClassIts one job
HotelSearch, book and cancel, under one lock
RoomNumber and type
RoomTypeSingle, double, suite with nightly rate
ReservationRoom, guest, the half-open range of nights, and the price

4. How it works

Move your stay and watch the overlap rule decide. Room 101 has Ana (10–13) then Dev (13–15), back to back; room 102 has Ben (12–14).

81318

5. Patterns and why

PatternWhereWhy it's worth it here
Half-open ranges[check-in, check-out)Back-to-back stays don't clash, and lengths are simply out − in
Search and book under one lockHotel.book()No gap for another booking between finding a room and taking it
Enum with dataRoomType carries its ratePricing lives in one place
Memory hook: "a.in < b.out and b.in < a.out"Two half-open stays overlap only if each starts before the other ends.

6. The code

The demo also shows back-to-back stays sharing a room, and a one-night stay fitting in front of another guest's arrival.

from __future__ import annotations
import itertools
import threading
from dataclasses import dataclass
from enum import Enum
from typing import Optional


class RoomType(Enum):
    SINGLE = 80     # nightly rate, dollars
    DOUBLE = 120
    SUITE = 300


@dataclass(frozen=True)
class Room:
    number: int
    type: RoomType


@dataclass(frozen=True)
class Reservation:
    id: str
    room: int
    guest: str
    check_in: int    # day numbers; a stay is the half-open range [check_in, check_out)
    check_out: int
    price: int


def overlaps(a_in: int, a_out: int, b_in: int, b_out: int) -> bool:
    """Half-open ranges: leaving on day 13 and arriving on day 13 don't clash."""
    return a_in < b_out and b_in < a_out


class Hotel:
    def __init__(self, rooms: list[Room]) -> None:
        self.rooms = sorted(rooms, key=lambda r: r.number)
        self.reservations: dict[str, Reservation] = {}
        self.ids = itertools.count(1)
        self.lock = threading.Lock()

    def available(self, rtype: RoomType, check_in: int, check_out: int) -> list[int]:
        if check_in >= check_out:
            raise ValueError("check-out must be after check-in")
        busy = {r.room for r in self.reservations.values() if overlaps(r.check_in, r.check_out, check_in, check_out)}
        return [r.number for r in self.rooms if r.type is rtype and r.number not in busy]

    def book(self, guest: str, rtype: RoomType, check_in: int, check_out: int) -> Optional[Reservation]:
        with self.lock:   # search and insert together, or two guests could get the same room
            free = self.available(rtype, check_in, check_out)
            if not free:
                return None
            res = Reservation(f"R{next(self.ids)}", free[0], guest, check_in, check_out, (check_out - check_in) * rtype.value)
            self.reservations[res.id] = res
            return res

    def cancel(self, res_id: str) -> None:
        with self.lock:
            del self.reservations[res_id]


def show(guest: str, r: Optional[Reservation]) -> str:
    return f"{guest}: room {r.room}, nights {r.check_in}-{r.check_out}, ${r.price} ({r.id})" if r else f"{guest}: no room free"


if __name__ == "__main__":
    hotel = Hotel([Room(101, RoomType.SINGLE), Room(102, RoomType.SINGLE), Room(201, RoomType.DOUBLE), Room(301, RoomType.SUITE)])
    print(show("ana", hotel.book("ana", RoomType.SINGLE, 10, 13)))
    ben = hotel.book("ben", RoomType.SINGLE, 12, 14)
    print(show("ben", ben))
    print(show("cara", hotel.book("cara", RoomType.SINGLE, 11, 12)))
    print(show("dev", hotel.book("dev", RoomType.SINGLE, 13, 15)))
    print("free doubles, nights 10-20:", hotel.available(RoomType.DOUBLE, 10, 20))
    assert ben is not None
    hotel.cancel(ben.id)
    print("ben cancels", ben.id)
    print(show("cara", hotel.book("cara", RoomType.SINGLE, 12, 14)))
    try:
        hotel.book("eve", RoomType.SUITE, 15, 15)
    except ValueError as e:
        print("eve:", e)
enum RoomType { SINGLE = "SINGLE", DOUBLE = "DOUBLE", SUITE = "SUITE" }
const RATE: Record<RoomType, number> = { SINGLE: 80, DOUBLE: 120, SUITE: 300 }; // nightly rate, dollars

interface Room { number: number; type: RoomType; }

/** Day numbers; a stay is the half-open range [checkIn, checkOut). */
interface Reservation { id: string; room: number; guest: string; checkIn: number; checkOut: number; price: number; }

/** Half-open ranges: leaving on day 13 and arriving on day 13 don't clash. */
const overlaps = (aIn: number, aOut: number, bIn: number, bOut: number) => aIn < bOut && bIn < aOut;

class Hotel {
  private rooms: Room[];
  private reservations = new Map<string, Reservation>();
  private nextId = 1;

  constructor(rooms: Room[]) { this.rooms = [...rooms].sort((a, b) => a.number - b.number); }

  available(type: RoomType, checkIn: number, checkOut: number): number[] {
    if (checkIn >= checkOut) throw new Error("check-out must be after check-in");
    const busy = new Set([...this.reservations.values()].filter((r) => overlaps(r.checkIn, r.checkOut, checkIn, checkOut)).map((r) => r.room));
    return this.rooms.filter((r) => r.type === type && !busy.has(r.number)).map((r) => r.number);
  }

  // Search and insert run in one synchronous call, so no other request can slip in between.
  book(guest: string, type: RoomType, checkIn: number, checkOut: number): Reservation | null {
    const free = this.available(type, checkIn, checkOut);
    if (!free.length) return null;
    const res: Reservation = { id: `R${this.nextId++}`, room: free[0], guest, checkIn, checkOut, price: (checkOut - checkIn) * RATE[type] };
    this.reservations.set(res.id, res);
    return res;
  }

  cancel(id: string): void { this.reservations.delete(id); }
}

const show = (guest: string, r: Reservation | null) =>
  r ? `${guest}: room ${r.room}, nights ${r.checkIn}-${r.checkOut}, $${r.price} (${r.id})` : `${guest}: no room free`;

const hotel = new Hotel([{ number: 101, type: RoomType.SINGLE }, { number: 102, type: RoomType.SINGLE },
  { number: 201, type: RoomType.DOUBLE }, { number: 301, type: RoomType.SUITE }]);
console.log(show("ana", hotel.book("ana", RoomType.SINGLE, 10, 13)));
const ben = hotel.book("ben", RoomType.SINGLE, 12, 14)!;
console.log(show("ben", ben));
console.log(show("cara", hotel.book("cara", RoomType.SINGLE, 11, 12)));
console.log(show("dev", hotel.book("dev", RoomType.SINGLE, 13, 15)));
console.log("free doubles, nights 10-20:", `[${hotel.available(RoomType.DOUBLE, 10, 20).join(", ")}]`);
hotel.cancel(ben.id);
console.log("ben cancels", ben.id);
console.log(show("cara", hotel.book("cara", RoomType.SINGLE, 12, 14)));
try {
  hotel.book("eve", RoomType.SUITE, 15, 15);
} catch (e) {
  console.log("eve:", (e as Error).message);
}
import java.util.Comparator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.stream.Collectors;

enum RoomType {
    SINGLE(80), DOUBLE(120), SUITE(300);

    final int rate; // nightly rate, dollars

    RoomType(int rate) {
        this.rate = rate;
    }
}

record Room(int number, RoomType type) {}

/** Day numbers; a stay is the half-open range [checkIn, checkOut). */
record Reservation(String id, int room, String guest, int checkIn, int checkOut, int price) {}

class Hotel {
    private final List<Room> rooms;
    private final Map<String, Reservation> reservations = new LinkedHashMap<>();
    private int nextId = 1;

    Hotel(List<Room> rooms) {
        this.rooms = rooms.stream().sorted(Comparator.comparingInt(Room::number)).toList();
    }

    /** Half-open ranges: leaving on day 13 and arriving on day 13 don't clash. */
    static boolean overlaps(int aIn, int aOut, int bIn, int bOut) {
        return aIn < bOut && bIn < aOut;
    }

    synchronized List<Integer> available(RoomType type, int checkIn, int checkOut) {
        if (checkIn >= checkOut) throw new IllegalArgumentException("check-out must be after check-in");
        Set<Integer> busy = reservations.values().stream().filter(r -> overlaps(r.checkIn(), r.checkOut(), checkIn, checkOut))
                .map(Reservation::room).collect(Collectors.toSet());
        return rooms.stream().filter(r -> r.type() == type && !busy.contains(r.number())).map(Room::number).toList();
    }

    /** synchronized: search and insert together, or two guests could get the same room. */
    synchronized Reservation book(String guest, RoomType type, int checkIn, int checkOut) {
        List<Integer> free = available(type, checkIn, checkOut);
        if (free.isEmpty()) return null;
        Reservation r = new Reservation("R" + nextId++, free.get(0), guest, checkIn, checkOut, (checkOut - checkIn) * type.rate);
        reservations.put(r.id(), r);
        return r;
    }

    synchronized void cancel(String id) {
        reservations.remove(id);
    }
}

public class Main {
    static String show(String guest, Reservation r) {
        return r == null ? guest + ": no room free"
                : guest + ": room " + r.room() + ", nights " + r.checkIn() + "-" + r.checkOut() + ", $" + r.price() + " (" + r.id() + ")";
    }

    public static void main(String[] args) {
        Hotel hotel = new Hotel(List.of(new Room(101, RoomType.SINGLE), new Room(102, RoomType.SINGLE),
                new Room(201, RoomType.DOUBLE), new Room(301, RoomType.SUITE)));
        System.out.println(show("ana", hotel.book("ana", RoomType.SINGLE, 10, 13)));
        Reservation ben = hotel.book("ben", RoomType.SINGLE, 12, 14);
        System.out.println(show("ben", ben));
        System.out.println(show("cara", hotel.book("cara", RoomType.SINGLE, 11, 12)));
        System.out.println(show("dev", hotel.book("dev", RoomType.SINGLE, 13, 15)));
        System.out.println("free doubles, nights 10-20: " + hotel.available(RoomType.DOUBLE, 10, 20));
        hotel.cancel(ben.id());
        System.out.println("ben cancels " + ben.id());
        System.out.println(show("cara", hotel.book("cara", RoomType.SINGLE, 12, 14)));
        try {
            hotel.book("eve", RoomType.SUITE, 15, 15);
        } catch (IllegalArgumentException e) {
            System.out.println("eve: " + e.getMessage());
        }
    }
}

Output (the same in all three languages)

ana: room 101, nights 10-13, $240 (R1)
ben: room 102, nights 12-14, $160 (R2)
cara: room 102, nights 11-12, $80 (R3)
dev: room 101, nights 13-15, $160 (R4)
free doubles, nights 10-20: [201]
ben cancels R2
cara: room 102, nights 12-14, $160 (R5)
eve: check-out must be after check-in

7. Concurrency and edge cases

8. Follow-up questions

What interviewers ask once the core works, and a short answer for each.

How do real systems model availability?
Often as inventory per room type per night (how many left), decremented atomically, with specific rooms assigned at check-in.
Overbooking?
Allow inventory to go slightly negative by a policy, expecting some no-shows; a strategy decides how much.
Modify a reservation's dates?
Check the new range excluding the reservation itself, then update in one step.
Hold while paying?
The same idea as seat holds (P12): a provisional reservation with an expiry.

9. Common mistakes

Closed ranges [in, out]Then back-to-back stays clash, and night counts are off by one.
Checking overlap with only one conditiona.in < b.out alone misses stays that are entirely before.
Search and book in separate steps without a lockTwo guests get the same room.

10. Check yourself

Stay A is nights [10, 13), stay B is [13, 15). Do they overlap?

13 < 13 is false: back to back is fine.

Which condition detects an overlap of half-open ranges?

Each must start before the other ends.

How can a database prevent double booking?

Let the database enforce the invariant.

Your turn

  1. Change dates (10 min). Move a reservation if the new range is free, excluding itself.
  2. Per-night inventory (15 min). Rewrite availability as counts per room type per night.