Restaurant Reservation: LLD Design

Problem statement (interviewer prompt)

Design the classes for an OpenTable-style restaurant reservation system: tables, reservations, time slots, walk-in conflict, overbooking, concurrent double-booking prevention. Optimise for correctness and clean boundaries.

The restaurant reservation lld problem is a favourite booking variant: a single physical resource (a table) is shared across many short time slots, with humans (walk-ins, no-shows, late cancellations) constantly perturbing the schedule. The interviewer wants to see a tight class model, a state machine for the reservation lifecycle, and a concrete answer for the double-booking race.

Requirements

Functional

• A customer can search availability for (restaurant, date, party_size, slot_window).
• A customer can book a specific table for a slot; the reservation is CONFIRMED only after the table is locked.
• A customer can cancel or modify (party size, time) up to a cutoff.
• A host can seat walk-ins; walk-ins must not collide with upcoming reservations.
• A wait list captures demand past capacity and promotes when a slot frees.
• Overbooking is configurable per restaurant.

Non-functional

• No double-booking, ever, even under concurrent requests.
• Idempotent booking API (duplicate clicks must not create two reservations).
• Availability lookup should be O(log n) per table via interval indexing.
• State transitions are auditable.

Class design

classDiagram
  direction TB

  class Restaurant {
    +id: String
    +name: String
    +tables: List~Table~
    +openHours: Hours
    +policy: OverbookingPolicy
  }
  class Table {
    +id: String
    +capacity: int
    +location: String
    +mergeableWith: Set~String~
  }
  class TimeSlot {
    +start: Instant
    +end: Instant
    +overlaps(other) bool
  }
  class Reservation {
    +id: String
    +tableId: String
    +customerId: String
    +slot: TimeSlot
    +partySize: int
    +state: ReservationState
    +idempotencyKey: String
    +version: long
  }
  class Customer {
    +id: String
    +name: String
    +phone: String
    +noShowCount: int
  }
  class AvailabilityService {
    +findCandidates(restaurantId, slot, partySize) List~Table~
    +isFree(tableId, slot) bool
  }
  class BookingService {
    +book(req: BookRequest) Reservation
    +cancel(reservationId) void
    +modify(reservationId, change) Reservation
  }
  class OverbookingPolicy {
    <<interface>>
    +admit(restaurant, slot, currentLoad) Decision
  }
  class WaitList {
    +enqueue(req) Ticket
    +promoteNext(slot) Optional~Ticket~
  }

  Restaurant "1" *-- "many" Table
  Restaurant "1" -- "1" OverbookingPolicy
  Restaurant "1" -- "1" WaitList
  Reservation "many" --> "1" Table
  Reservation "many" --> "1" Customer
  BookingService --> AvailabilityService
  BookingService --> OverbookingPolicy
  BookingService --> WaitList

  class Restaurant:::service
  class BookingService:::service
  class AvailabilityService:::service
  class OverbookingPolicy:::compute
  class WaitList:::queue
  class Table:::storage
  class Reservation:::storage
  class Customer:::storage
  class TimeSlot:::storage

  classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
  classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
  classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
  classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
  classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
  classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
  classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
  classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
  classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
  classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;

Key choices worth defending:

• TimeSlot is a value object, not a database row. It exists per-reservation and is the unit the AvailabilityService indexes on.
• OverbookingPolicy is a strategy so each restaurant can plug in NoOverbooking, FixedPercent, or WaitList without changing BookingService.
• Reservation.version enables optimistic locking; idempotencyKey dedupes retries from the client.

Reservation lifecycle

stateDiagram-v2
  [*] --> REQUESTED: customer submits
  REQUESTED --> CONFIRMED: table locked + payment hold ok
  REQUESTED --> CANCELLED: validation fails
  CONFIRMED --> SEATED: host marks arrival
  CONFIRMED --> CANCELLED: customer cancels before cutoff
  CONFIRMED --> NO_SHOW: grace period elapsed, no arrival
  SEATED --> COMPLETED: party leaves
  NO_SHOW --> [*]
  CANCELLED --> [*]
  COMPLETED --> [*]

Notes on transitions:

• REQUESTED to CONFIRMED is the only transition that needs the concurrency guard, because that is where the table is consumed.
• CONFIRMED to NO_SHOW is driven by a scheduled sweep, not a user action.
• SEATED blocks AvailabilityService until COMPLETED to handle parties that overstay; the slot extends rather than collides.

Core flow (book a table)

sequenceDiagram
  autonumber
  participant C as Customer
  participant BS as BookingService
  participant AS as AvailabilityService
  participant T as Table (row + version)
  participant R as Reservation store

  C->>BS: book(restaurant, slot, partySize, idemKey)
  BS->>R: lookup(idemKey)
  alt duplicate request
    R-->>BS: existing reservation
    BS-->>C: 200 idempotent reply
  else fresh request
    BS->>AS: findCandidates(restaurant, slot, partySize)
    AS-->>BS: [tableA v=7, tableB v=3]
    BS->>T: CAS update tableA where version=7
    alt CAS wins
      T-->>BS: ok, version=8
      BS->>R: insert Reservation(CONFIRMED)
      BS-->>C: 201 reservation
    else CAS loses
      T-->>BS: stale, retry
      BS->>AS: refresh candidates
    end
  end

Step 4 is the race: two BookingService instances may read the same candidate. Step 5's compare-and-swap (UPDATE table_slot SET version=v+1 WHERE id=? AND version=v) lets only one commit. The loser retries against a fresh candidate list. If no candidate remains, BookingService consults the OverbookingPolicy and either rejects, overbooks, or enqueues onto the WaitList.

Code (Java)

public enum ReservationState { REQUESTED, CONFIRMED, SEATED, COMPLETED, CANCELLED, NO_SHOW }

public record TimeSlot(Instant start, Instant end) {
    public boolean overlaps(TimeSlot o) {
        return start.isBefore(o.end) && o.start.isBefore(end);
    }
}

public record BookRequest(String restaurantId, TimeSlot slot,
                          int partySize, String customerId, String idempotencyKey) {}

public interface OverbookingPolicy {
    enum Decision { ADMIT, REJECT, WAITLIST }
    Decision admit(String restaurantId, TimeSlot slot, int currentLoad, int capacity);
}

public class NoOverbooking implements OverbookingPolicy {
    public Decision admit(String r, TimeSlot s, int load, int cap) {
        return load < cap ? Decision.ADMIT : Decision.REJECT;
    }
}

public class FixedPercent implements OverbookingPolicy {
    private final double pct;
    public FixedPercent(double pct) { this.pct = pct; }
    public Decision admit(String r, TimeSlot s, int load, int cap) {
        int allowed = (int) Math.floor(cap * (1.0 + pct));
        return load < allowed ? Decision.ADMIT : Decision.REJECT;
    }
}

public class WaitListPolicy implements OverbookingPolicy {
    public Decision admit(String r, TimeSlot s, int load, int cap) {
        return load < cap ? Decision.ADMIT : Decision.WAITLIST;
    }
}

public class AvailabilityService {
    private final Map<String, NavigableMap<Instant, Reservation>> byTable = new ConcurrentHashMap<>();

    public List<Table> findCandidates(String restaurantId, TimeSlot slot, int partySize) {
        return tableRepo.byRestaurant(restaurantId).stream()
            .filter(t -> t.capacity() >= partySize)
            .filter(t -> isFree(t.id(), slot))
            .sorted(Comparator.comparingInt(Table::capacity))
            .toList();
    }

    public boolean isFree(String tableId, TimeSlot slot) {
        var idx = byTable.getOrDefault(tableId, new TreeMap<>());
        var prior = idx.floorEntry(slot.end());
        if (prior == null) return true;
        return !prior.getValue().slot().overlaps(slot);
    }
}

public class BookingService {
    private final AvailabilityService availability;
    private final OverbookingPolicy policy;
    private final WaitList waitList;
    private final ReservationRepo reservations;
    private final TableRepo tables;

    public Reservation book(BookRequest req) {
        var existing = reservations.findByIdempotencyKey(req.idempotencyKey());
        if (existing.isPresent()) return existing.get();

        for (int attempt = 0; attempt < 3; attempt++) {
            var candidates = availability.findCandidates(req.restaurantId(), req.slot(), req.partySize());
            if (candidates.isEmpty()) return applyPolicy(req);

            Table t = candidates.get(0);
            boolean won = tables.compareAndSwap(t.id(), t.version(), req.slot());
            if (!won) continue;

            return reservations.insert(new Reservation(
                UUID.randomUUID().toString(), t.id(), req.customerId(),
                req.slot(), req.partySize(), ReservationState.CONFIRMED,
                req.idempotencyKey(), 1L));
        }
        throw new BookingConflict("could not acquire table after retries");
    }

    private Reservation applyPolicy(BookRequest req) {
        int load = reservations.countActive(req.restaurantId(), req.slot());
        int capacity = tables.capacityOf(req.restaurantId());
        return switch (policy.admit(req.restaurantId(), req.slot(), load, capacity)) {
            case ADMIT -> bookOverflowTable(req);
            case WAITLIST -> waitList.enqueue(req).asReservation();
            case REJECT -> throw new NoCapacity("slot full");
        };
    }
}

The tables.compareAndSwap boils down to a single SQL statement: UPDATE table_slot SET version = version + 1, reserved_until = ? WHERE table_id = ? AND version = ? AND reserved_until < ?. If zero rows were updated, another writer won.

Concurrency

The double-booking race surfaces whenever two BookingService nodes read the same (table, slot) snapshot before either writes. Three viable fixes, ranked by what most interviews prefer:

Strategy	Where the guarantee lives	Cost
DB UNIQUE constraint on (table_id, slot_start)	Database, primary key style	Cheapest, hardest to bypass, but slot granularity is fixed at row level
CAS via version column	Application + DB	Flexible, retries are easy, needs a retry budget
Distributed lock (Redis SETNX, Zookeeper)	External coordinator	Works across services but adds a single point of failure and a fencing problem

Idempotency. Every booking request carries a client-generated idempotencyKey. BookingService stores it on the Reservation row with a UNIQUE index. A retried POST short-circuits to return the original reservation rather than create a second one.

Stale reads. AvailabilityService's index lives in process memory. Refreshing on CAS failure is mandatory, otherwise the retry will pick the same losing candidate.

Edge cases

• Late cancellations. Cancellation within a cutoff (say 2 hours before the slot) triggers a fee on the Customer's saved card and still releases the table for WaitList promotion.
• Party-size change. If the new size exceeds Table.capacity, BookingService treats it as cancel + rebook against a larger table; if no larger table is free, propose merging.
• Walk-in mid-reservation. Host marks a free table SEATED with a synthetic Reservation whose customerId is walk-in. The reservation expires after the average turn time so the next CONFIRMED booking can claim it.
• Table merge. Two 2-tops with mergeableWith pointing at each other can satisfy a party of 4. BookingService creates one Reservation per physical table, both linked to a compositeReservationId, and locks both via CAS in a single transaction.
• No-show grace period. A scheduled job sweeps CONFIRMED reservations whose slot.start + 15 minutes has passed without a SEATED transition, flips them to NO_SHOW, increments Customer.noShowCount, and calls waitList.promoteNext.

Extensions

• Wait list with auto-promotion. On any CANCELLED or NO_SHOW transition, pop the next compatible WaitList ticket, attempt CAS, and notify the customer.
• Multi-table parties. Generalise the merge case: solve a small bin-packing problem over mergeableWith graphs when partySize exceeds any single table.
• Recurring reservations. A standing-reservation entity expands into N concrete Reservation rows on a rolling 4-week window.
• POS integration. When the POS closes the bill, emit a tableCleared event that lets AvailabilityService release the table early if the party leaves before slot.end.
• Dynamic pricing / deposits. Premium slots (Saturday 8pm) attach a deposit collected at booking; refunded on COMPLETED, forfeited on NO_SHOW.

Quick reference

• Class spine: Restaurant owns Table; Reservation joins Table, Customer, and TimeSlot.
• State machine: REQUESTED, CONFIRMED, SEATED, COMPLETED, CANCELLED, NO_SHOW.
• Concurrency primitive: DB UNIQUE on (table_id, slot_start) or CAS on Table.version.
• Idempotency: client-supplied key + UNIQUE index on Reservation.
• Overbooking: pluggable strategy (None, FixedPercent, WaitList).
• Grace period: 15 minutes from slot.start to NO_SHOW.

Refs

• OpenTable engineering blog, posts on reservation availability indexing.
• Resy postmortems on no-show flagging and deposit policies.
• Designing Data-Intensive Applications, chapter on transactions and isolation levels (the foundation for the CAS vs UNIQUE choice).

FAQ

How do you design a restaurant reservation system in an LLD interview?

Model a Restaurant that owns Tables, slice the day into TimeSlots, and let a BookingService coordinate AvailabilityService lookups and Reservation writes. Wrap the write in a CAS or a database UNIQUE constraint on (table_id, slot_start) so only one Reservation can occupy a slot. Add a state machine (REQUESTED, CONFIRMED, SEATED, COMPLETED, CANCELLED, NO_SHOW) and a pluggable OverbookingPolicy.

How do you prevent double-booking the same table?

Use an atomic compare-and-swap on the table's availability for the given time slot, or a database UNIQUE constraint on (table_id, slot_start). Optimistic locking with a version column also works. The winning write commits, the loser retries with a fresh availability query.

What is the difference between restaurant reservation LLD and hotel booking LLD?

Hotels reserve a room for one or more whole nights, so the unit is a date range with night-level granularity. Restaurants reserve a table for a 90 to 120 minute seating, so the unit is a time slot inside a single day. Restaurants also deal with walk-ins, table merges, and turnover; hotels deal with check-in cutoffs and per-night pricing.

How do you handle walk-ins competing with reservations?

Reserve a percentage of tables (or a percentage of slots per table) for walk-ins via an OverbookingPolicy or WalkInPolicy. When a walk-in arrives, the host marks a free table SEATED with a synthetic Reservation that holds for the average turn time so the next reservation cannot collide.

How is overbooking modelled?

OverbookingPolicy is a strategy interface. NoOverbooking refuses any booking past capacity. FixedPercent allows up to a configured percentage above capacity per slot to absorb no-shows. WaitList accepts the booking into a queue and auto-promotes when a cancellation or no-show frees the table.

How do you handle no-shows?

Each Reservation has a grace period (typically 15 minutes). A background job transitions CONFIRMED to NO_SHOW after the grace window, releases the table back to AvailabilityService, and triggers WaitList promotion. Repeat offenders can be flagged on the Customer record for future deposit requirements.

Related Topics

• Hotel Management LLD: the long-stay cousin, useful for contrasting date-range vs slot-based booking.
• Movie Booking LLD: another seat-hold-then-pay flow with stronger inventory granularity.
• Parking Lot LLD: unreserved resource allocation, walk-in only.
• Pessimistic vs Optimistic Locking: foundation for the CAS choice.
• State Machines in LLD: pattern for the reservation lifecycle.