Design a restaurant reservation service

• A restaurant has tables (seat capacity), opening hours and a turn time (how long a party holds a table).
• Search: for a day and party size, list 30-minute start times where a fitting table is free.
• Book a start time for a party; the system picks the table. Reject party
  size <= 0, out-of-hours slots, and parties larger than every table.
• Modify time and/or party size; on failure the original stays untouched.
• Cancel releases the table; cancelling twice is an error.
• No double-booking: active reservations on a table never overlap, even under concurrency.
• Out of scope: payments, combining tables, waitlists, notifications, multi-node storage.

• TimeSlot: immutable [start, end) interval; knows if it overlaps another.
• Table: immutable id and capacity.
• Status (enum): CONFIRMED, SEATED, COMPLETED, CANCELLED, NO_SHOW.
• Reservation: guest, party size, assigned table, slot, status.
• Restaurant: tables, hours, turn time, per-table bookings, and the lock that guards them.
• TableStrategy (ABC) / SmallestFit: choose a table from the free ones; default is the smallest that seats the party.
• ReservationService: facade for search, book, modify, cancel; raises BookingError on rejection.

{"type":"excalidraw","elements":[
 {"type":"rectangle","id":"svc","x":0,"y":0,"width":240,"height":150,"label":{"text":"ReservationService\nsearch()\nbook()\nmodify()\ncancel()"}},
 {"type":"rectangle","id":"rest","x":420,"y":15,"width":220,"height":120,"label":{"text":"Restaurant\nturn\nbookings\nis_free()"}},
 {"type":"rectangle","id":"table","x":860,"y":40,"width":180,"height":70,"label":{"text":"Table"}},
 {"type":"rectangle","id":"resv","x":420,"y":300,"width":220,"height":100,"label":{"text":"Reservation\nstatus\nactive()"}},
 {"type":"rectangle","id":"slot","x":860,"y":300,"width":200,"height":100,"label":{"text":"TimeSlot\nstart, end\noverlaps()"}},
 {"type":"rectangle","id":"strat","x":0,"y":300,"width":240,"height":100,"label":{"text":"TableStrategy\n(abstract)\nchoose()"}},
 {"type":"rectangle","id":"fit","x":30,"y":540,"width":180,"height":70,"label":{"text":"SmallestFit"}},
 {"type":"arrow","id":"svc-rest","x":240,"y":75,"width":180,"height":0,"start":{"id":"svc"},"end":{"id":"rest"},"label":{"text":"has"}},
 {"type":"arrow","id":"rest-table","x":640,"y":75,"width":220,"height":0,"start":{"id":"rest"},"end":{"id":"table"},"label":{"text":"has many"}},
 {"type":"arrow","id":"rest-resv","x":530,"y":135,"width":1,"height":165,"start":{"id":"rest"},"end":{"id":"resv"},"label":{"text":"bookings"}},
 {"type":"arrow","id":"resv-table","x":640,"y":320,"width":260,"height":-210,"start":{"id":"resv"},"end":{"id":"table"},"label":{"text":"uses"}},
 {"type":"arrow","id":"resv-slot","x":640,"y":350,"width":220,"height":0,"start":{"id":"resv"},"end":{"id":"slot"},"label":{"text":"has"}},
 {"type":"arrow","id":"svc-strat","x":120,"y":150,"width":1,"height":150,"start":{"id":"svc"},"end":{"id":"strat"},"label":{"text":"uses"}},
 {"type":"arrow","id":"fit-strat","x":120,"y":540,"width":1,"height":-140,"start":{"id":"fit"},"end":{"id":"strat"},"label":{"text":"extends"}}
]}

Search. Walk the 30-minute grid while start + turn <= close, asking Restaurant.is_free
for any table with enough seats. No lock: the result is a hint; book re-checks.

Book. Validate the slot (party size, hours). Under the restaurant's lock, collect
free tables, let TableStrategy.choose pick one (None means BookingError), and
append a CONFIRMED Reservation to that table's list. One lock around check-then-act
means two threads can't both take a free table; that race is the core of the question.

Modify. Under the lock, find a free table for the new slot, ignoring this reservation
(so 19:00 to 19:30 can keep its table). Only then does it move lists; else nothing changes.

Cancel. Under the lock, require CONFIRMED, set CANCELLED; is_free skips it.

{"type":"excalidraw","elements":[
 {"type":"ellipse","id":"start","x":0,"y":145,"width":120,"height":60,"label":{"text":"start"}},
 {"type":"rectangle","id":"confirmed","x":300,"y":140,"width":180,"height":70,"label":{"text":"CONFIRMED"}},
 {"type":"rectangle","id":"cancelled","x":760,"y":0,"width":180,"height":70,"label":{"text":"CANCELLED"}},
 {"type":"rectangle","id":"seated","x":760,"y":140,"width":180,"height":70,"label":{"text":"SEATED"}},
 {"type":"rectangle","id":"noshow","x":760,"y":280,"width":180,"height":70,"label":{"text":"NO_SHOW"}},
 {"type":"rectangle","id":"completed","x":1140,"y":140,"width":180,"height":70,"label":{"text":"COMPLETED"}},
 {"type":"arrow","id":"book","x":120,"y":175,"width":180,"height":0,"start":{"id":"start"},"end":{"id":"confirmed"},"label":{"text":"book"}},
 {"type":"arrow","id":"modify","x":360,"y":140,"width":60,"height":0,"points":[[0,0],[0,-60],[60,-60],[60,0]],"start":{"id":"confirmed"},"end":{"id":"confirmed"},"label":{"text":"modify"}},
 {"type":"arrow","id":"cancel","x":480,"y":155,"width":280,"height":-120,"start":{"id":"confirmed"},"end":{"id":"cancelled"},"label":{"text":"cancel"}},
 {"type":"arrow","id":"arrive","x":480,"y":175,"width":280,"height":0,"start":{"id":"confirmed"},"end":{"id":"seated"},"label":{"text":"guest arrives"}},
 {"type":"arrow","id":"noshow-t","x":480,"y":195,"width":280,"height":120,"start":{"id":"confirmed"},"end":{"id":"noshow"},"label":{"text":"grace period passes"}},
 {"type":"arrow","id":"cleared","x":940,"y":175,"width":200,"height":0,"start":{"id":"seated"},"end":{"id":"completed"},"label":{"text":"table cleared"}}
]}

from __future__ import annotations
import itertools, threading
from abc import ABC, abstractmethod
from dataclasses import dataclass
from datetime import datetime, time, timedelta
from enum import Enum

class Status(Enum):
    CONFIRMED, SEATED, COMPLETED, CANCELLED, NO_SHOW = range(5)

class BookingError(Exception): ...

@dataclass(frozen=True)
class TimeSlot:
    start: datetime
    end: datetime
    def overlaps(self, other: TimeSlot) -> bool:
        return self.start < other.end and other.start < self.end

@dataclass(frozen=True)
class Table:
    table_id: str
    capacity: int

@dataclass
class Reservation:
    reservation_id: int
    restaurant_id: str
    table: Table
    slot: TimeSlot
    party_size: int
    guest: str
    status: Status = Status.CONFIRMED
    @property
    def active(self) -> bool:  # cancelled / finished bookings free the table
        return self.status in (Status.CONFIRMED, Status.SEATED)

class Restaurant:
    def __init__(self, restaurant_id: str, tables: list[Table],
                 open_at: time, close_at: time, turn: timedelta) -> None:
        self.restaurant_id, self.tables = restaurant_id, tables
        self.open_at, self.close_at, self.turn = open_at, close_at, turn
        self.bookings: dict[str, list[Reservation]] = {t.table_id: [] for t in tables}
        self.lock = threading.Lock()

    def is_free(self, table: Table, slot: TimeSlot, ignore: int | None = None) -> bool:
        return not any(r.active and r.reservation_id != ignore and r.slot.overlaps(slot)
                       for r in self.bookings[table.table_id])

    def within_hours(self, slot: TimeSlot) -> bool:
        day = slot.start.date()
        return datetime.combine(day, self.open_at) <= slot.start and slot.end <= datetime.combine(day, self.close_at)

class TableStrategy(ABC):
    @abstractmethod
    def choose(self, candidates: list[Table], party_size: int) -> Table | None: ...

class SmallestFit(TableStrategy):
    def choose(self, candidates: list[Table], party_size: int) -> Table | None:
        fits = [t for t in candidates if t.capacity >= party_size]
        return min(fits, key=lambda t: t.capacity, default=None)

class ReservationService:
    STEP = timedelta(minutes=30)
    def __init__(self, restaurants: list[Restaurant], strategy: TableStrategy | None = None) -> None:
        self.restaurants = {r.restaurant_id: r for r in restaurants}
        self.reservations: dict[int, Reservation] = {}
        self.strategy = strategy or SmallestFit()
        self._ids = itertools.count(1)

    def search(self, restaurant_id: str, day: datetime, party_size: int) -> list[datetime]:
        r, found = self.restaurants[restaurant_id], []
        start, close = (datetime.combine(day.date(), t) for t in (r.open_at, r.close_at))
        while start + r.turn <= close:
            slot = TimeSlot(start, start + r.turn)
            if any(t.capacity >= party_size and r.is_free(t, slot) for t in r.tables):
                found.append(start)
            start += self.STEP
        return found

    def _slot(self, r: Restaurant, start: datetime, party_size: int) -> TimeSlot:
        slot = TimeSlot(start, start + r.turn)
        if party_size <= 0 or not r.within_hours(slot):
            raise BookingError("invalid party size or outside opening hours")
        return slot

    def _pick(self, r: Restaurant, slot: TimeSlot, size: int, ignore: int | None = None) -> Table:
        table = self.strategy.choose([t for t in r.tables if r.is_free(t, slot, ignore)], size)
        if table is None:
            raise BookingError("no table available for that time and party size")
        return table

    def book(self, restaurant_id: str, start: datetime, party_size: int, guest: str) -> Reservation:
        r = self.restaurants[restaurant_id]
        slot = self._slot(r, start, party_size)
        with r.lock:  # check-then-act is atomic: no double-booking
            table = self._pick(r, slot, party_size)
            res = Reservation(next(self._ids), restaurant_id, table, slot, party_size, guest)
            r.bookings[table.table_id].append(res)
            self.reservations[res.reservation_id] = res
            return res

    def modify(self, reservation_id: int, new_start: datetime, new_party_size: int) -> Reservation:
        res = self.reservations[reservation_id]
        r = self.restaurants[res.restaurant_id]
        slot = self._slot(r, new_start, new_party_size)
        with r.lock:
            if res.status is not Status.CONFIRMED:
                raise BookingError(f"cannot modify a {res.status.name} reservation")
            table = self._pick(r, slot, new_party_size, ignore=reservation_id)
            r.bookings[res.table.table_id].remove(res)  # only after a table is found
            res.table, res.slot, res.party_size = table, slot, new_party_size
            r.bookings[table.table_id].append(res)
            return res

    def cancel(self, reservation_id: int) -> None:
        res = self.reservations[reservation_id]
        with self.restaurants[res.restaurant_id].lock:
            if res.status is not Status.CONFIRMED:
                raise BookingError(f"cannot cancel a {res.status.name} reservation")
            res.status = Status.CANCELLED

if __name__ == "__main__":
    svc = ReservationService([Restaurant("bistro", [Table("T1", 2), Table("T2", 4)],
                                         time(17), time(22), timedelta(minutes=90))])
    seven = datetime(2026, 10, 20, 19, 0)
    a = svc.book("bistro", seven, 2, "Ana")   # T1: smallest fit
    b = svc.book("bistro", seven, 2, "Ben")   # T2: T1 is taken
    try:
        svc.book("bistro", seven + timedelta(minutes=30), 2, "Cy")
    except BookingError as e:
        print("rejected:", e)                 # both tables overlap 19:30
    svc.modify(a.reservation_id, datetime(2026, 10, 20, 20, 30), 2)
    svc.cancel(b.reservation_id)
    print([t.strftime("%H:%M") for t in svc.search("bistro", seven, 4)])

• Strategy: TableStrategy keeps table choice out of booking logic.
  SmallestFit saves big tables for big parties; "keep the same table on
  modify" or "prefer window seats" is a new class, not an edit to the service.
• Facade: ReservationService is the one entry point; callers never touch lists or locks.
• Value objects: frozen TimeSlot/Table are thread-safe to share; overlap logic lives in one place.
• State (light): Status with guarded transitions (only CONFIRMED changes); fee rules would grow it into full State.

• Real database, many servers. The lock becomes the store's job: unique
  (table_id, slot_start) with fixed slots, a time-range exclusion constraint, or
  SELECT ... FOR UPDATE; optimistic versioning with retry fits rare conflicts.
• Checkout holds. HELD + expires_at; active counts unexpired holds during a deposit flow.
• Combinable tables. Strategy returns list[Table] (T3+T4 seats 8); every table must be free.
• Faster search. Sorted bookings + bisect (O(log n) per check) or per-table
  15-minute bitmaps; cache briefly, since book re-checks anyway.
• Waitlist. cancel emits TableReleased; a waitlist observer offers the slot onward.

Mid-level (L4)

• Clean core classes and a correct overlap check (a.start < b.end and b.start < a.end).
• Book, cancel and search work; cancelled reservations stop blocking a table.
• Spots the double-booking race when prompted and fixes it with a lock.

Senior (L5)

• Makes check-then-insert atomic unprompted, with a per-restaurant (not global) lock.
• Modify is atomic and failure-safe: it can keep its own table and survives a failed attempt.
• Table choice as a strategy with a reason; covers hours, oversized parties, double cancel.

Staff (L6+)

• Moves the invariant into storage (constraints, row locks, optimistic versions) under peak contention.
• Separates a stale-but-fast search path from the consistent write path.
• Idempotency keys on book, holds with TTLs, no-show policy, combinable tables.