Design a restaurant waitlist

01The design, in the six-step framework

1. Requirements and use cases

This is the most reported Google OOD prompt of the last two years, and every report says the same thing: the interviewer writes the problem themselves, gives almost no detail, and grades how the candidate states assumptions and lets the implementation follow from them. So the first deliverable is the list below, said aloud.

• A host adds a party (a name and a size) to the waitlist; parties are served in arrival order among those that fit.
• A party can leave the waitlist at any time, before being seated.
• When a table frees up, the host asks for the first party that fits that table's size, and that party is seated.
• Tables have fixed sizes; a party fits if its size is at most the table size.
• The host can list the current waitlist in order.

Out of scope: reservations by time, combining tables, payment. Stated assumptions: party sizes are small integers (1 to, say, 20), names are unique per visit (an id is issued), and the restaurant has tens of tables. Constraints: add and leave should be O(1); seating the first party that fits should be fast even with hundreds waiting; one person holding several entries must not break arrival order.

2. Core entities and relationships

• Party: an immutable record with a ticket id, a name, a size and an arrival sequence number.
• Table: an id, a capacity and the party currently seated, if any.
• Waitlist: arrival-ordered queue with O(1) removal and a fast "first that fits" query; this is the class the interviewer wants to see.
• Restaurant: owns tables and the waitlist, and runs the seat-on-free flow.

The restaurant composes its waitlist and tables. Parties are aggregated: the same party object moves from the waitlist to a table, so neither owns its lifetime.

3. Interfaces and key methods

from dataclasses import dataclass
from typing import Optional

@dataclass(frozen=True)
class Party:
    ticket: str
    name: str
    size: int
    arrived: int     # monotonically increasing sequence number

class Waitlist:
    def add(self, party: Party) -> None:
        """O(1). Keeps arrival order."""
    def remove(self, ticket: str) -> bool:
        """O(1). False if the ticket is not waiting (already seated or left)."""
    def first_fitting(self, capacity: int) -> Optional[Party]:
        """Earliest-arrived party with size <= capacity, removed from the list; None if nobody fits."""
    def snapshot(self) -> list:
        """Parties in arrival order, for the host display."""

class Restaurant:
    def arrive(self, name: str, size: int) -> str:
        """Issue a ticket and enqueue; the same name may hold several tickets."""
    def leave(self, ticket: str) -> None:
        """Idempotent."""
    def table_freed(self, table_id: int) -> Optional[Party]:
        """Seat the first fitting party at the table, or leave it empty."""

Invariants: every waiting party appears exactly once in order and exactly once in by_size[party.size]; both are keyed by ticket, and both are ordered by arrival. first_fitting removes from both. A ticket is the identity, never the name, which is what makes "one person, several reservations" a non-issue.

4. Design patterns and the choices behind them

Identity by ticket, not by name

The force: the reported follow-up is a person holding multiple entries. If the waitlist is keyed by name, the second entry overwrites the first or removal is ambiguous. Issuing a ticket makes identity explicit: equality of parties is equality of tickets, names are display data. This is the kind of assumption the interviewer wants to hear before the code.

One queue per size, plus a global order

The force: "first that fits" over a plain queue is a linear scan. Because sizes are small integers, keep an arrival-ordered map per size; first_fitting(c) looks at the head of each map with size at most c and takes the smallest arrival number, O(number of distinct sizes). The global order map gives O(1) removal and the host's display. The structures are both insertion-ordered dictionaries, the same hash-map-plus-ordering trick as the LRU cache. If sizes were unbounded, the alternative is a heap per size with lazy deletion; say that trade-off out loud.

Classes found from the use cases

Walking the three verbs (add, leave, seat) is the requirements-to-classes method: the nouns that hold changing state are the waitlist and the tables; the party is a record. Resisting a Host or Reservation class that has no state is part of the machine-coding rubric: fewer, well-named classes read better in 45 minutes, which is also why naming such as first_fitting and table_freed mirrors the verbs the interviewer used.

5. Core flow and code

1. Restaurant.arrive mints a ticket and a sequence number, builds a Party, and calls Waitlist.add.
2. Waitlist.add inserts the party into order and into by_size[size].
3. When a table frees, table_freed asks first_fitting(capacity); it inspects the head of each size bucket up to the capacity and picks the earliest arrival.
4. The chosen party is removed from both maps and placed on the table.
5. leave(ticket) removes from both maps; a ticket already seated or already gone is a no-op.

import itertools, threading
from collections import OrderedDict
from dataclasses import dataclass
from typing import Optional

class Waitlist:
    def __init__(self, max_size: int = 20):
        self.order: "OrderedDict[str, Party]" = OrderedDict()
        self.by_size: dict = {s: OrderedDict() for s in range(1, max_size + 1)}
        self._lock = threading.RLock()

    def add(self, party: Party) -> None:
        if party.size not in self.by_size:
            raise ValueError(f"party size {party.size} not supported")
        with self._lock:
            self.order[party.ticket] = party
            self.by_size[party.size][party.ticket] = party

    def remove(self, ticket: str) -> bool:
        with self._lock:
            party = self.order.pop(ticket, None)
            if party is None:
                return False
            del self.by_size[party.size][ticket]
            return True

    def first_fitting(self, capacity: int) -> Optional[Party]:
        with self._lock:                                  # two tablets must not seat one party twice
            best: Optional[Party] = None
            for size in range(1, min(capacity, len(self.by_size)) + 1):
                bucket = self.by_size[size]
                if bucket:
                    head = next(iter(bucket.values()))    # earliest arrival of this size
                    if best is None or head.arrived < best.arrived:
                        best = head
            if best is not None:
                self.remove(best.ticket)
            return best

    def snapshot(self) -> list:
        with self._lock:
            return list(self.order.values())

    def __len__(self) -> int:
        return len(self.order)

@dataclass
class Table:
    id: int
    capacity: int
    seated: Optional[Party] = None

class Restaurant:
    def __init__(self, table_sizes: dict):
        self.tables = {tid: Table(tid, cap) for tid, cap in table_sizes.items()}
        self.waitlist = Waitlist()
        self._tickets = itertools.count(1)
        self._arrivals = itertools.count(1)

    def arrive(self, name: str, size: int) -> str:
        ticket = f"T{next(self._tickets)}"
        self.waitlist.add(Party(ticket, name, size, next(self._arrivals)))
        return ticket

    def leave(self, ticket: str) -> None:
        self.waitlist.remove(ticket)

    def table_freed(self, table_id: int) -> Optional[Party]:
        table = self.tables[table_id]
        table.seated = None
        party = self.waitlist.first_fitting(table.capacity)
        if party is not None:
            table.seated = party
        return party

    def party_left_table(self, table_id: int) -> Optional[Party]:
        """Convenience for the host: the table is cleared and immediately refilled."""
        return self.table_freed(table_id)

if __name__ == "__main__":
    r = Restaurant({1: 2, 2: 4, 3: 6})
    a = r.arrive("Ana", 5); b = r.arrive("Bo", 2); c = r.arrive("Cy", 4)
    assert r.table_freed(2).name == "Bo"       # table for 4: Ana (5) does not fit, Bo arrived before Cy
    r.leave(a)
    assert r.table_freed(3).name == "Cy"       # table for 6: Ana left, Cy is next
    assert r.table_freed(1) is None            # nobody waiting

The three asserts are the ones to write on the whiteboard before the code: they encode the arrival-order rule, the fit rule and the leave rule, and they are what the interviewer checks the implementation against.

6. Extensions, concurrency and what interviewers probe

• "What is the complexity?" add and remove O(1); first_fitting O(S) for S distinct sizes (20), independent of how many are waiting. With unbounded sizes, a sorted structure over sizes or a heap per size with lazy deletion makes it O(log S).
• "One person, several reservations." Already handled: tickets are the identity; add a by_name index only if the host must list a person's tickets.
• "Prefer the smallest table that fits" when several tables free at once. Sort free tables by capacity ascending and call table_freed in that order; the waitlist does not change.
• "Parties that waited too long jump the queue." Replace the arrival number with a priority computed from arrival and size in first_fitting; the comparison is in one place.
• Concurrency: hosts on two tablets. The two maps must change together and the pick and the removal must be one step, so Waitlist methods take one re-entrant lock; see locks and mutexes. Unit tests (designed in by injecting the sequence counter) come before any threading talk.
• Common mistake: a single list scanned per seating, or seating the largest fitting party instead of the earliest, which violates the arrival-order requirement the candidate agreed to in minute one.

02Where this question was reported

• LeetCode Discuss · Add/remove parties; seat the first party that fits when a table frees; candidate chose data structures and wrote the class
• LeetCode Discuss · Restaurant class that seats people, maintains waitlist, seats next party when a table is vacated; interviewer confirmed approach
• LeetCode Discuss · Variant: a party can leave at any time; tables matched by size
• FastPrep · Interviewer wanted every assumption stated aloud and the implementation to follow from it; not LC 1845, interviewer-written
• FastPrep · join/add, delete, find_first_match(table_size); two separate reports; assumptions changed the design
• FastPrep · One of two OOD rounds; HashMap + queue; follow-ups then complexity analysis
• FastPrep · Explicit OOD round; follow-up: one person holding multiple reservations and how the model changes; complexity
• 1point3acres · 'OOD/coding: design a restaurant waiting system, write the main classes and methods'
• 1point3acres · Short entry: restaurant waitlist coding problem
• LeetCode Discuss · Community solution thread for the Google variant
• Land the Lab · Ordered-container API; likely cousin of the restaurant waitlist