vishal maurya

LLD Series: Hotel Booking System - LLD

Overview

Part of the Interview Prep series. Dotted-underline words are glossary terms: hover for the meaning or open the Glossary. Track your progress on the Interview Prep tracker. Series index: Start here.

1. Problem statement and how it is asked

"Design a hotel booking system: search availability for a date range, book rooms, cancel, and make sure the hotel is never overbooked even with concurrent requests. Support different pricing (weekend, seasonal)." Asked at: Amex (travel/Membership Rewards flavour), PayU, Visa, Mastercard (travel-tech/commerce teams); a cousin of BookMyShow and meeting-room-booking questions.

2. Requirements

Functional: room types with counts and base rate; availability query for [check-in, check-out); book N rooms of a type; cancel (idempotent); quote price via pluggable strategy. Non-functional: no overbooking under concurrency; different room types do not contend; price locked at booking; extensible pricing. Assumptions: inventory is by room type (fungible rooms, like real hotels), not specific room numbers; nights are half-open [in, out) so back-to-back stays are allowed; single hotel, single node, BigDecimal for money. Out of scope: payment (see BookMyShow design for hold+pay), room-number assignment, modification of bookings, multi-hotel search, taxes, overbooking-by-policy.

3. Entities and class diagram

+------------------+ 1   * +-----------+ 1   1 +-------------+
| HotelService     |------>| RoomType  |<------| Inventory   |  date -> bookedCount, ReentrantLock
|------------------|       | id,total, |       | tryReserve()|
| book/cancel/     |       | baseRate  |       | release()   |
| availability/    |       +-----------+       | available() |
| quote            |             ^ *           +-------------+
| pricing:Pricing  |             |
+--------+---------+       +-----+-----+  status: CONFIRMED|CANCELLED
         | * Booking ------| Booking   |
         v                 +-----------+
 <<interface>> PricingStrategy.nightlyRate(type, date)
    ^ BasePricing   ^ WeekendSurcharge(inner)   ^ SeasonalPricing(inner)   (decorators)

4. Design patterns and why

  • Strategy + Decorator for pricing: WeekendSurcharge(SeasonalPricing(BasePricing)) composes rules without a combinatorial class explosion. Rejected: if/else in service (violates OCP) or one subclass per combination.
  • Inventory ledger (date -> booked count): availability of a range = min over nights of (total - booked). Rejected: list of bookings scanned for overlap (O(B) per query, harder to make atomic); per-room-number calendar (needed only if guests pick rooms).
  • Pessimistic per-room-type lock: the check-then-act over many nights must be atomic. Alternatives: per-date AtomicInteger with CAS plus rollback on partial failure (more complex, ABA/partial-state issues); DB SELECT ... FOR UPDATE or conditional update in the distributed version.
  • Facade: HotelService is the single entry point.

5. Code

javac *.java && java Main (default package; demo dates are computed relative to today, so dates in the output vary).

RoomType.java

import java.math.BigDecimal;
public final class RoomType {
    private final String id, name; private final int totalRooms; private final BigDecimal baseRate;
    public RoomType(String id, String name, int totalRooms, BigDecimal baseRate){this.id=id;this.name=name;this.totalRooms=totalRooms;this.baseRate=baseRate;}
    public String id(){return id;} public String name(){return name;} public int totalRooms(){return totalRooms;} public BigDecimal baseRate(){return baseRate;}
}

BookingStatus.java

public enum BookingStatus { CONFIRMED, CANCELLED }

Booking.java

import java.math.BigDecimal; import java.time.LocalDate;
public class Booking {
    private final String id, guest; private final RoomType roomType; private final LocalDate checkIn, checkOut; private final int rooms; private final BigDecimal total;
    private volatile BookingStatus status = BookingStatus.CONFIRMED;
    public Booking(String id, String guest, RoomType rt, LocalDate in, LocalDate out, int rooms, BigDecimal total){this.id=id;this.guest=guest;this.roomType=rt;this.checkIn=in;this.checkOut=out;this.rooms=rooms;this.total=total;}
    public String id(){return id;} public RoomType roomType(){return roomType;} public LocalDate checkIn(){return checkIn;} public LocalDate checkOut(){return checkOut;}
    public int rooms(){return rooms;} public BigDecimal total(){return total;} public BookingStatus status(){return status;} void setStatus(BookingStatus s){status=s;}
    @Override public String toString(){return id+"["+guest+", "+roomType.name()+" x"+rooms+", "+checkIn+"->"+checkOut+", "+total+", "+status+"]";}
}

PricingStrategy.java

import java.math.BigDecimal; import java.time.LocalDate;
/** Price of ONE room for ONE night. Composable via decorators. */
public interface PricingStrategy { BigDecimal nightlyRate(RoomType type, LocalDate night); }

BasePricing.java

import java.math.BigDecimal; import java.time.LocalDate;
public class BasePricing implements PricingStrategy { public BigDecimal nightlyRate(RoomType t, LocalDate d){ return t.baseRate(); } }

WeekendSurcharge.java

import java.math.BigDecimal; import java.time.*;
public class WeekendSurcharge implements PricingStrategy {
    private final PricingStrategy inner; private final BigDecimal factor;
    public WeekendSurcharge(PricingStrategy inner, BigDecimal factor){this.inner=inner;this.factor=factor;}
    public BigDecimal nightlyRate(RoomType t, LocalDate d){
        BigDecimal r = inner.nightlyRate(t,d); DayOfWeek w = d.getDayOfWeek();
        return (w==DayOfWeek.FRIDAY||w==DayOfWeek.SATURDAY) ? r.multiply(factor) : r;
    }
}

SeasonalPricing.java

import java.math.BigDecimal; import java.time.LocalDate;
public class SeasonalPricing implements PricingStrategy {
    private final PricingStrategy inner; private final LocalDate from, toExclusive; private final BigDecimal factor;
    public SeasonalPricing(PricingStrategy inner, LocalDate from, LocalDate toExclusive, BigDecimal factor){this.inner=inner;this.from=from;this.toExclusive=toExclusive;this.factor=factor;}
    public BigDecimal nightlyRate(RoomType t, LocalDate d){
        BigDecimal r = inner.nightlyRate(t,d);
        return (!d.isBefore(from) && d.isBefore(toExclusive)) ? r.multiply(factor) : r;
    }
}

Inventory.java

import java.time.LocalDate; import java.util.*; import java.util.concurrent.locks.ReentrantLock;
/** Per-room-type night ledger: date -> rooms booked. Lock is per room type so different types never contend. */
public class Inventory {
    private final RoomType type; private final Map<LocalDate,Integer> booked = new HashMap<>(); private final ReentrantLock lock = new ReentrantLock();
    public Inventory(RoomType t){type=t;}
    public int available(LocalDate in, LocalDate out){
        lock.lock(); try { return minFree(in,out); } finally { lock.unlock(); }
    }
    private int minFree(LocalDate in, LocalDate out){ // nights in [in, out)
        int min = type.totalRooms();
        for (LocalDate d=in; d.isBefore(out); d=d.plusDays(1)) min = Math.min(min, type.totalRooms()-booked.getOrDefault(d,0));
        return min;
    }
    /** check-then-act over the whole range is atomic under the lock => no overbooking. */
    public boolean tryReserve(LocalDate in, LocalDate out, int rooms){
        lock.lock();
        try {
            if (minFree(in,out) < rooms) return false;
            for (LocalDate d=in; d.isBefore(out); d=d.plusDays(1)) booked.merge(d, rooms, Integer::sum);
            return true;
        } finally { lock.unlock(); }
    }
    public void release(LocalDate in, LocalDate out, int rooms){
        lock.lock();
        try { for (LocalDate d=in; d.isBefore(out); d=d.plusDays(1)) booked.merge(d, -rooms, Integer::sum); }
        finally { lock.unlock(); }
    }
}

HotelService.java

import java.math.BigDecimal; import java.time.LocalDate; import java.time.temporal.ChronoUnit; import java.util.*; import java.util.concurrent.*; import java.util.concurrent.atomic.AtomicLong;
public class HotelService {
    private final Map<String,RoomType> types = new ConcurrentHashMap<>();
    private final Map<String,Inventory> inventories = new ConcurrentHashMap<>();
    private final Map<String,Booking> bookings = new ConcurrentHashMap<>();
    private final PricingStrategy pricing; private final AtomicLong seq = new AtomicLong(1000);
    public HotelService(PricingStrategy p){pricing=p;}
    public void addRoomType(RoomType t){ types.put(t.id(),t); inventories.put(t.id(), new Inventory(t)); }
    private void validate(LocalDate in, LocalDate out, int rooms){
        if (in==null||out==null||!out.isAfter(in)) throw new IllegalArgumentException("check-out must be after check-in");
        if (in.isBefore(LocalDate.now())) throw new IllegalArgumentException("check-in in the past");
        if (rooms<=0) throw new IllegalArgumentException("rooms must be > 0");
    }
    public int availability(String typeId, LocalDate in, LocalDate out){ return inv(typeId).available(in,out); }
    public BigDecimal quote(String typeId, LocalDate in, LocalDate out, int rooms){
        RoomType t = type(typeId); BigDecimal sum = BigDecimal.ZERO;
        for (LocalDate d=in; d.isBefore(out); d=d.plusDays(1)) sum = sum.add(pricing.nightlyRate(t,d));
        return sum.multiply(BigDecimal.valueOf(rooms));
    }
    public Booking book(String guest, String typeId, LocalDate in, LocalDate out, int rooms){
        validate(in,out,rooms);
        BigDecimal total = quote(typeId,in,out,rooms);       // price locked at booking time
        if (!inv(typeId).tryReserve(in,out,rooms)) throw new IllegalStateException("No availability for "+typeId+" "+in+" -> "+out);
        Booking b = new Booking("BK"+seq.incrementAndGet(), guest, type(typeId), in, out, rooms, total);
        bookings.put(b.id(), b); return b;
    }
    public void cancel(String bookingId){
        Booking b = bookings.get(bookingId); if (b==null) throw new IllegalArgumentException("Unknown booking");
        synchronized (b) {                                   // idempotent: release exactly once
            if (b.status()==BookingStatus.CANCELLED) return;
            b.setStatus(BookingStatus.CANCELLED);
            inv(b.roomType().id()).release(b.checkIn(), b.checkOut(), b.rooms());
        }
    }
    private RoomType type(String id){ RoomType t=types.get(id); if(t==null) throw new IllegalArgumentException("Unknown room type "+id); return t; }
    private Inventory inv(String id){ type(id); return inventories.get(id); }
}

Main.java

import java.math.BigDecimal; import java.time.LocalDate; import java.util.*; import java.util.concurrent.*; import java.util.concurrent.atomic.AtomicInteger;
public class Main {
    public static void main(String[] a) throws Exception {
        LocalDate mon = LocalDate.now().plusDays(30); while (mon.getDayOfWeek()!=java.time.DayOfWeek.MONDAY) mon = mon.plusDays(1);
        PricingStrategy p = new WeekendSurcharge(new BasePricing(), new BigDecimal("1.5"));
        HotelService h = new HotelService(p);
        h.addRoomType(new RoomType("DLX","Deluxe",3,new BigDecimal("100")));
        h.addRoomType(new RoomType("STD","Standard",10,new BigDecimal("60")));
        System.out.println("Stay Mon..Mon(+7 nights) quote x1 = " + h.quote("DLX", mon, mon.plusDays(7), 1) + "  (5 weekday + 2 weekend nights... Fri,Sat at 1.5x)");
        Booking b1 = h.book("alice","DLX",mon,mon.plusDays(3),2);
        System.out.println(b1 + "  avail=" + h.availability("DLX",mon,mon.plusDays(3)));
        // overlapping stay: needs 2 rooms but only 1 free on overlapping nights
        try { h.book("bob","DLX",mon.plusDays(2),mon.plusDays(5),2); } catch (IllegalStateException e){ System.out.println("bob rejected: " + e.getMessage()); }
        // back-to-back stay (check-in == other's check-out) is allowed
        Booking b3 = h.book("carol","DLX",mon.plusDays(3),mon.plusDays(5),3);
        System.out.println(b3);
        h.cancel(b1.id()); h.cancel(b1.id());   // idempotent
        System.out.println("after cancel alice, avail=" + h.availability("DLX",mon,mon.plusDays(3)));
        try { h.book("x","DLX",mon.plusDays(3),mon,1); } catch (IllegalArgumentException e){ System.out.println("invalid: " + e.getMessage()); }
        // concurrency: 20 threads fight for 10 STD rooms (1 each)
        ExecutorService ex = Executors.newFixedThreadPool(20); AtomicInteger ok=new AtomicInteger(), no=new AtomicInteger(); CountDownLatch go=new CountDownLatch(1), done=new CountDownLatch(20);
        final LocalDate m=mon;
        for(int i=0;i<20;i++){ final int n=i; ex.execute(() -> { try{ go.await(); h.book("g"+n,"STD",m,m.plusDays(2),1); ok.incrementAndGet(); }catch(IllegalStateException e){ no.incrementAndGet(); }catch(InterruptedException e){} finally{done.countDown();} }); }
        go.countDown(); done.await(); ex.shutdown();
        System.out.println("20 concurrent requests for 10 rooms: confirmed=" + ok + ", rejected=" + no + ", remaining=" + h.availability("STD",mon,mon.plusDays(2)));
    }
}

Lock granularity: one ReentrantLock per room type's Inventory. A booking touches only one type, so Deluxe and Standard never block each other; within a type the lock is held for O(nights). A global lock would serialize the whole hotel for no reason; per-date locks would need ordered multi-lock acquisition to avoid deadlock. Cancel uses synchronized(booking) so double-cancel releases once.

Real output (compiled with javac, run with java)

Stay Mon..Mon(+7 nights) quote x1 = 800.0  (5 weekday + 2 weekend nights... Fri,Sat at 1.5x)
BK1001[alice, Deluxe x2, 2026-11-23->2026-11-26, 600, CONFIRMED]  avail=1
bob rejected: No availability for DLX 2026-11-25 -> 2026-11-28
BK1002[carol, Deluxe x3, 2026-11-26->2026-11-28, 750.0, CONFIRMED]
after cancel alice, avail=3
invalid: check-out must be after check-in
20 concurrent requests for 10 rooms: confirmed=10, rejected=10, remaining=0

(The label text in the first line is printed by the demo; the number is 5x100 + 2x150 = 800: Friday and Saturday nights carry the 1.5x surcharge.)

6. Key flows

Client        HotelService          PricingStrategy        Inventory(type)
  | book(...)     |                        |                     |
  |-------------->| validate dates/rooms   |                     |
  |               |-- nightlyRate x nights>|                     |
  |               |<-- total (locked) -----|                     |
  |               |-- tryReserve(in,out,n) ------------------->  | lock
  |               |                                              | min free over nights >= n ?
  |               |                                              | yes: booked[d]+=n ; unlock
  |<-- Booking ---|<-- true -------------------------------------|   no: return false -> IllegalStateException
cancel(id): status=CANCELLED (once) -> release(in,out,n) under same inventory lock

7. Extensibility

  • New pricing (demand-based, loyalty discount, length-of-stay): new PricingStrategy decorator, wrapped at construction; no service change.
  • Room-number assignment: add Room entity and an AllocationStrategy post-reserve.
  • Cancellation policy / refunds: CancellationPolicy strategy invoked in cancel.
  • Payment: add PENDING status with hold expiry (as in BookMyShow) before CONFIRMED.
  • Search across hotels: HotelCatalog holding many HotelServices.
  • Planned overbooking: OverbookingPolicy supplying effective capacity = total x 1.05.

8. Concurrency and edge cases

  • Check-then-act race (two guests, last room): prevented by per-type lock around the whole range check + increment.
  • Partial range failure: the check happens for all nights before any mutation, so no rollback is needed.
  • Back-to-back stays: half-open interval makes check-out day available for next check-in.
  • Idempotent cancel; cancel of unknown booking; check-out <= check-in; past dates; rooms <= 0; unknown room type.
  • Price consistency: quote computed before reserve and stored in the booking; later rate changes do not alter it.
  • Memory: booked map grows with dates; purge past dates periodically.
  • Query availability is a snapshot; it can be stale by the time of book - the book call is the source of truth.

9. Follow-ups and model answers

  • Distributed / persistent? Table inventory(room_type, date, total, booked); booking is one transaction: UPDATE inventory SET booked=booked+:n WHERE room_type=:t AND date BETWEEN ... AND booked+:n<=total and verify affected rows == nights, else rollback. Optimistic version column or SELECT FOR UPDATE ordered by date to avoid deadlocks. Idempotency key on the booking request. For scale, shard by hotel; cache availability reads (Redis) with DB as the truth.
  • Hold during payment? Reserve with state PENDING and expiry; scheduler/lazy expiry releases it.
  • Why not a list of bookings? Overlap scan is O(B) and still needs a lock; the ledger gives O(nights).
  • Dynamic pricing? Strategy reading occupancy ratio from inventory.
  • Complexity: availability O(n) nights, book O(n), cancel O(n), memory O(types x dates).
  • Deadlocks? Single lock per operation; multi-type bookings must lock in sorted id order.

10. Common mistakes and rubric

Mistakes: if (available) { book } without lock/transaction; synchronized on the whole service; treating end date as inclusive (blocks same-day turnover); storing double for money; pricing as if/else chain; decrementing a single availableRooms counter ignoring dates; non-idempotent cancel double-releasing inventory; mutating partway then failing. Rubric (10): date-range model and half-open interval (2); atomic reserve / no overbooking (3); pricing strategy/decorator (2); cancel + edge cases (1); distributed/DB answer (2).