05 — Movie Ticket Booking System

“Design a movie ticket booking system. Users browse shows, pick seats, and pay.”

Selling numbered seats at a cinema is, at heart, an object model problem — the object model being the set of classes you define plus the relationships between them, the thing you draw on the whiteboard. And one problem decides this interview: what happens when two people tap the same seat inside the same 200 milliseconds.

By the end you will be able to:

• name the class almost every first draft is missing, and say exactly what breaks without it;
• trace, step by step, the interleaving of two servers that sells one chair twice;
• choose between three fixes for that race and put a number on each;
• explain why the expiry deadline has to arrive through a constructor argument instead of a call to the system clock.

What goes in, and what comes out

Before any class diagram, fix the shape of the thing you are building.

The core object is a Show — one screening, of one movie, in one auditorium, at one time. Everything a caller can do goes through it.

The block below is that contract. Read each pair as one request: IN is what a caller sends, OUT is what comes back. Notice that the first call does not sell anything — it only reserves, and it can fail.

IN   hold(["C5", "C6", "C7"], "user_42")     a set of seat labels, and who wants them
OUT  SeatHold(hold_id="h1", user_id="user_42",
              seat_ids=("C5", "C6", "C7"), expires_at=120.0)
     ...or it raises HoldRejected and changes NOTHING -- no seat is half-taken

IN   confirm("h1", amount_cents=4500)         a hold id, and the money actually taken
OUT  Booking(booking_id="bh1", seat_ids=("C5","C6","C7"), amount_cents=4500)

IN   release_expired()                        nothing at all; a timer calls this
OUT  4                                        how many abandoned holds were dropped

IN   available()                              nothing at all
OUT  ["C1", "C2", "C8"]                       seat labels still on sale, right now

Those four calls are the whole external surface, or API — application programming interface, the set of calls the outside world is allowed to make.

Seat labels go in, a time-limited claim comes out, and a second call turns that claim into a receipt. A timer sweeps up claims nobody paid for, and a read-only query renders the seat map. Everything else in this chapter exists to make those calls correct when many people issue them at once.

The three ways candidates lose this round

• They model Seat.is_booked. That flag silently makes a seat bookable once ever instead of once per show, because it has nowhere to record which screening booked it.
• They say “we’d take a lock” and stop there. They cannot say what the lock protects, how long it is held, or what happens when the holder abandons the payment page.
• They ship a claim that expires on a timer and then cannot test it. The expiry reads the wall clock, so the only way to observe an expiry is to wait for it.

Where this sits relative to other chapters

Two links, offered for depth rather than required for comprehension. The interview method — how to spend the 45 minutes — is 02 — the object-oriented design (OOD) framework; the pattern vocabulary is 03 — object-oriented programming (OOP) fundamentals.

The identical race one layer down, inside the database, is derived in system design 23. That chapter owns the transaction; this one owns the object model. They are the same defect seen from two heights, and an interviewer who asks both wants to hear you say so.

1. Clarifying questions that change the design

Four questions are worth your five minutes here. The test for each is the same: does the answer add or delete a class, or does it merely fill in a field? Only the first kind is worth interview time.

Each answer below produces a different design, not a different setting — every row moves at least one class.

Four pieces of vocabulary appear in that table. In plain words:

• General admission — any ticket entitles you to any free chair. The inventory is then a number, not a list of labels.
• TTL, time to live — a deadline stamped on a claim, after which the claim is worth nothing.
• Reaper — the background job that sweeps up claims whose deadline has passed and puts their seats back on sale.
• Atomically — all-or-nothing. The operation either happens completely or leaves no trace. Never half.

The last row is the one that pays. Design the hold to take a set of seats even when the requirement says one. “Book 4 together for my family” arrives in week three, and an all-or-nothing set is not something you can retrofit onto a single-seat API — every caller, every error path and the lock scope all change with it.

Out of scope, said out loud: search and ranking of shows (a query problem), payment gateway internals (system design 27), and seat maps as a rendering concern.

2. Actors and use cases

An actor is anyone or anything that starts an interaction with the system. Listing them takes two minutes, and the value here is that the exercise surfaces one actor who is not a person.

The third row is the one candidates leave out.

Listing the reaper as an actor is not pedantry. It is the only actor that mutates state with no user behind it, which is why it is the one that needs a clock and the one that gets forgotten in tests.

3. Core objects, and the one first drafts are missing

Everything below rests on a single modelling move: separating the chair you sit in from the thing you buy.

The tempting model is Seat { row, number, is_booked }. It is wrong in a way that survives code review and fails in production: a physical seat is bookable once per show, not once. is_booked has no room to say for which show.

The fix is to split the physical thing from the sellable thing.

The table below is the five-object core of the design. The Lifetime column is the one to study: it is what tells you which object owns which, and it is where the split becomes obvious — the chair lasts years, the thing you sell lasts one screening.

ShowSeat is the object first drafts are missing, and its absence is the root of the is_booked bug. A ShowSeat is one chair at one screening, so the status it carries can only ever mean “taken for this show”.

Once ShowSeat exists, the counting writes itself — and the count matters, because it tells you how many rows the design creates. A 200-seat auditorium running 6 shows a day mints 200 x 6 = 1200 ShowSeat rows per screen per day. All of that is inventory; none of it is furniture. The 200 Seat rows are created once and never again.

One more thing to notice in that table: Booking stores the price charged, not a pointer to a price rule. The reason arrives in full in Extension 3 cancellation with a partial refund: a refund computed from today’s pricing rule is a bug, and the only defence is a receipt that cannot change.

4. Class diagram

The diagram below is the whole design in one picture. The notation is UML — the Unified Modeling Language, the standard boxes-and-arrows notation for class models — and only four marks matter here.

• A box is a class. Inside it, + marks a member visible to callers; +str show_id is a public field of type string, and +hold(seat_ids, user) SeatHold is a public method taking those two arguments and returning a SeatHold.
• <<interface>> marks a box that is a promise, not an implementation: it lists methods that some other class must supply. Nothing there has a body.
• The arrows differ in what they claim about ownership. *-- is composition: the part cannot exist without the whole, and the whole creates and destroys it. o-- is aggregation: the whole holds a reference to something that lives its own independent life. A plain --> is a mere association — this class knows about that one and calls it.
• The quoted numbers are multiplicities, the count allowed at each end. "1" is exactly one, "0..*" is zero or more, "1..*" is one or more.

classDiagram
    class Cinema
    class Auditorium
    class Movie
    class Seat {
        +str seat_id
        +SeatClass seat_class
    }
    class Show {
        +str show_id
        +datetime starts_at
        +hold(seat_ids, user) SeatHold
        +confirm(hold_id, amount_cents) Booking
        +release_expired() int
        +available() list
    }
    class ShowSeat {
        +SeatStatus status
        +Optional~str~ held_by
        +float hold_expires_at
    }
    class SeatHold {
        +str hold_id
        +float expires_at
    }
    class Booking {
        +str booking_id
        +int amount_cents
        +BookingStatus status
    }
    class PricingStrategy {
        <<interface>>
        +price_cents(show, show_seat) int
    }
    class RefundPolicy {
        <<interface>>
        +refund_cents(paid_cents, minutes_to_show) int
    }
    class Clock {
        <<interface>>
        +now() float
    }

    Cinema "1" *-- "1..*" Auditorium : composition
    Auditorium "1" *-- "1..*" Seat : composition
    Show "0..*" --> "1" Auditorium : scheduled in
    Show "0..*" --> "1" Movie : screens
    Show "1" *-- "1..*" ShowSeat : composition
    ShowSeat "1" --> "1" Seat : physical chair
    Show "1" *-- "0..*" SeatHold : composition
    SeatHold "1" o-- "1..*" ShowSeat : claims
    Booking "1" o-- "1..*" ShowSeat : sold
    Booking "0..*" --> "1" Show : belongs to
    PricingStrategy "1" --> "1" ShowSeat : prices
    RefundPolicy "1" --> "1" Booking : refunds
    Show "1" --> "1" Clock : injected

Reading the diagram out loud

Every arrow in that diagram is a sentence. Here they are, grouped by what they are about.

The building. A cinema owns one or more auditoriums, and an auditorium owns one or more seats. Both are composition, because demolishing the building takes the chairs with it.

The schedule. Many shows are scheduled in one auditorium, and many shows screen one movie. Both are plain associations, because a movie survives the screening and an auditorium survives the show.

The inventory. A show owns its ShowSeat inventory and its SeatHold records outright — composition, both. Each ShowSeat points at the one physical chair it corresponds to.

The sale. A hold claims one or more ShowSeats, and a booking records which ones were sold. Both are aggregation, because the chairs outlive the paperwork. A booking belongs to exactly one show.

The policies. PricingStrategy prices a ShowSeat and RefundPolicy refunds a Booking. Both arrows point away from the interfaces on purpose: neither interface is a field on Show. The price is computed by the caller and handed to confirm as amount_cents (Extension 1 seat classes with different pricing); the refund is computed from the amount recorded on the receipt (Extension 3 cancellation with a partial refund). That is precisely why confirm takes the money as an argument instead of reaching for a rule.

The clock. A show has a clock injected into it — “injected” meaning handed in from outside at construction time rather than reached for from inside. Decision 2 the clock is a dependency argues that one at length.

Two arrows are worth defending out loud, because an interviewer will ask why they differ:

• Show *-- ShowSeat is composition because deleting a cancelled show must delete its seat inventory. Nothing else can own those rows.
• Booking o-- ShowSeat is aggregation because the ShowSeat outlives the booking. Cancel the booking and the chair goes back on sale.

What the runnable code in §7 actually implements

The diagram is the design you would draw on the whiteboard. The Python in Working python is deliberately smaller, and you should know which boxes it skips before you meet the code and go looking for them.

The reason for cutting is that the interesting part of this problem is 60 lines wide, and Cinema holding a list of Auditoriums is not in it. In the interview you draw all the boxes and write code for the ones under contention.

What this class structure assumes

A class diagram is a frozen bet about what will change. Every interface you draw says “I expect this to vary”. Every field you hard-code says “I expect this to hold forever”.

Stating those bets out loud is the transferable skill here. The specific cinema problem is not going to be your job; the habit of naming your own assumptions is. The general version of this argument is What a class structure assumes; what follows is this design’s version of it.

Assumed to vary — and therefore given an interface or a parameter. The third column is the one to read closely: it is what the design would have looked like had you bet the other way.

Assumed fixed — and therefore baked into the structure, not into a parameter. These are the six bets that have no interface behind them, because changing one changes the shape of the design rather than a value in it.

• A seat is a physical location, not a unit of interchangeable capacity. This single assumption is why ShowSeat exists at all, and it is what makes overbooking a bug here rather than a business strategy.
• The unit of contention is one Show. That assumes a screening’s inventory fits comfortably inside one lock, in one process.
• Inventory is materialised. Materialised means every ShowSeat row is created up front when the show is scheduled, rather than computed on demand. That assumes hundreds of seats per show, not millions.
• A Booking belongs to exactly one show. There is no cart spanning a festival weekend.
• Money is an integer count of cents in one currency. No rounding, no exchange rate.
• The authority on whether a hold is alive is a timestamp, not a heartbeat from the browser.

What a different assumption would have produced. This is the part worth rehearsing, because interviewers reach for it when they want to see whether you understood your own design or copied it.

• If seats were substitutable capacity — general admission, or an airline cabin where the seat is assigned at check-in — ShowSeat disappears entirely. The model becomes a counter with a reserved count, holds become a decrement, and overbooking stops being a defect and becomes a tunable, because a displaced passenger can be given a different seat and a displaced moviegoer cannot.
• If a booking could span several shows — a festival pass, a double bill — Booking could no longer hang off a single Show, and hold/confirm would move up into a coordinating service that locks several shows. That service would have to acquire those locks in a fixed order, for the reason given in What interviewers probe: two callers grabbing the same two locks in opposite orders deadlock.
• If inventory were enormous — a 100,000-seat stadium with dynamically opened sections — materialising every row at schedule time stops being free, and you would create rows lazily on first touch, which trades a simple invariant — a statement that must be true at every observable moment, here “the row exists” — for a cheaper write path.
• If the hold were renewable while the user is still typing card details, expires_at becomes a lease with a renew() method, and the reaper has to lose races gracefully: it must not delete a hold that was renewed a microsecond ago.
• If prices never changed, PricingStrategy is over-engineering. One price_cents method on Show, deleted interface, smaller design. An interface you cannot name a second implementation for is a guess, not a design.

5. Decision 1: the hold, and the race it exists to lose

The class diagram froze the structure; the behaviour is where the trouble lives. At the centre of it sits one concurrency bug — a bug that “add a lock” misdescribes, and whose fix deserves a price tag, not just a name.

Why a hold exists at all

A hold is a temporary, exclusive claim on a seat that expires by itself.

Without one, the seat map is a lie for the whole payment flow. The page says a seat is free, the user spends ninety seconds typing card details, and somebody else buys it out from under them.

With a naive hold — one written the obvious way, with no lock — the seat map is a lie for only about 200 milliseconds. That turns out to be plenty.

The race, traced

The block below is an interleaving: the step-by-step story of what two servers actually did, in the order they did it. The left column is user A on app server 1, the right column is user B on app server 2, and vertical position is time. Two app servers, no lock, seat C7 free at the start.

Watch for the two lines marked -- decision. Both say “allowed”, and both are correct given what that server read.

 T1  (user A, app server 1)               T2  (user B, app server 2)
 GET /shows/42/seats
   C7 -> AVAILABLE
                                          GET /shows/42/seats
                                            C7 -> AVAILABLE
 POST /holds {seats: [C7]}
   read  seats[C7].status  -> AVAILABLE
                                          POST /holds {seats: [C7]}
                                            read  seats[C7].status  -> AVAILABLE
   -- decision: allowed
                                            -- decision: allowed
   write seats[C7] = HELD by A
                                            write seats[C7] = HELD by B
 POST /confirm -> ticket A, seat C7
                                          POST /confirm -> ticket B, seat C7

 -- one chair, two tickets, and not one error line in either log

The defect is not “we forgot a lock”. The defect is that the read that made the decision and the write that acted on it were two separate steps, and the world was allowed to change in between.

Say it that way in the interview. “We forgot a lock” names one fix; “read and write were not one step” names the bug, and every fix follows from it.

The pattern has a name worth knowing: check-then-act, an instance of a race condition — two threads race, and which one wins changes the answer.

Three fixes, priced

Any fix that rejoins the read and the write into one indivisible step works. The three below all do that; they differ only in what they cost and where they work.

Unpacking those three names:

• A monitor is an object that owns a lock and takes it around every method that touches its own state, so only one thread is ever inside the object at a time. The stretch of code the lock protects is the critical section.
• Compare-and-set, usually abbreviated CAS, is a single hardware- or store-level instruction meaning “change this value from exactly this to that, and tell me whether you were the one who did it”. It is indivisible by construction, so no lock is needed.
• A conditional UPDATE is the database’s version of the same idea. The WHERE status = 'AVAILABLE' clause makes the check and the write one statement, and the row count it returns tells you whether you won.

Why one lock per show is not a bottleneck

The per-Show monitor is the right object model answer, and the arithmetic below is how you defend it when an interviewer calls the lock “too coarse”.

The arithmetic runs in three parts: first the demand on the lock (0.33 holds per second), then its capacity (200,000 per second), then capacity divided by demand — the headroom.

seats in one auditorium                        200
sell-out window for a hit opening, seconds     600
peak hold attempts on one show, per second
  200 / 600                                   =  0.33
critical section: dict lookups and a status write, microseconds
                                               5
holds one lock can serialize, per second
  1000000 / 5                                 =  200000
headroom on the hottest show in the building
  200000 / (200 / 600)                        =  600000

In words: a sold-out 200-seat show that empties in ten minutes generates about a third of a hold attempt per second. A critical section of five microseconds — a couple of dictionary lookups and a status write — can be entered two hundred thousand times a second.

Say the headroom number out loud. One lock around one show’s entire seat map sits five orders of magnitude away from being a bottleneck.

So the interesting question is never “is the lock too coarse”. It is “what is the lock’s scope across twelve app servers”, and that answer moves the lock out of Python and into the store.

The seat state machine

The hold adds a third state, so a seat is now a state machine: a fixed set of states it can be in, plus the only transitions allowed between them.

Read the diagram below left to right for the happy path, and read the three +---- lines underneath as the ways a seat returns to AVAILABLE.

AVAILABLE --hold()--------> HELD --confirm()--> BOOKED
    ^                        |                    |
    |                        |                    |
    +---- release() ---------+                    |
    +---- TTL expiry --------+                    |
    +---- cancel() --------------------------------+

HELD is the state that exists purely because payment takes human time. Delete the payment step and the state disappears.

6. Decision 2: the clock is a dependency

The hold from the last section carries a deadline, and somebody has to tell the time. The current time has to be passed into the design rather than read from inside it — and once it is, the deadline itself can be chosen by arithmetic instead of by taste.

The problem with reading the clock

A TTL means somebody has to notice the deadline.

The tempting implementation reads time.monotonic() inside hold() and inside the reaper. It is untestable. The only way to observe an expiry is to sleep for it, and a test suite that sleeps 120 seconds per assertion is a test suite nobody runs.

Make the clock a constructor parameter typed as a Protocol, and the expiry test becomes three lines and zero seconds.

Two terms in that sentence:

• Dependency injection means an object receives the collaborators it needs as arguments, instead of constructing or importing them itself. The dependency is injected by whoever builds the object.
• A Protocol, in Python, is a type that describes a shape rather than an ancestry. Anything with a now() method returning a float satisfies Clock — no base class to inherit, no registration step.

This is the smallest example of dependency injection earning its keep, and it is worth naming as such. The alternative is a module-level time call. That is a global, which is a singleton wearing different clothes: one shared instance that every test silently agrees on and no test can replace.

State the cost too, because it is real. Every object that can expire now carries a clock field. Constructors get longer. A caller who forgets to pass one gets production behaviour in a test.

You can default it to the real clock, and then the mistake is silent; or require it, and then every construction site gets noisier. Pick “require it” for anything with a TTL, and “default it” elsewhere.

Choosing the TTL by arithmetic

The number 120 seconds is not a round guess. The chain below derives it, starting from a sold-out show and ending at the fraction of inventory the hold makes temporarily unbuyable.

The line to watch is the last one: that is the price you pay, expressed as a share of inventory.

seats in a sold-out show                       200
sell-through rate assumed                      0.95
holds started to sell 200 seats
  200 / 0.95                                  =  210
holds abandoned at the payment page
  210 - 200                                   =  10
seat-seconds locked by abandonment at a 120 s TTL
  10 x 120                                    =  1200
seat-seconds of inventory in the 600 s window
  200 x 600                                   =  120000
inventory made temporarily unsellable
  1200 / 120000                               =  0.01

The sell-through rate of 0.95 is the share of started checkouts that end in a payment. The other 5% walk away, so selling 200 seats takes 210 attempts and leaves 10 seats pinned by nobody for 120 seconds each.

A seat-second is one seat being unavailable for one second — the unit that lets you compare “10 seats for 120 seconds” against a whole show’s inventory. Measured against the 120,000 seat-seconds available during the ten-minute rush, the abandoned holds cost 1% of inventory, briefly, and buy every user a calm checkout.

Double the TTL to 240 s and you pay 2%. The TTL is priced in unsellable inventory, and 120 s is a p95-checkout number, not a round one — p95 meaning the 95th percentile, the duration that 95 out of 100 real checkouts finish inside.

7. Working Python

Now the implementation: the broken version first, then the supporting types, the Show class, and the assertions that prove it works — in that order, because each block builds on the last.

The broken version, run on purpose

Start with the bug, so that it is something you watch happen rather than something you are asked to believe.

NaiveShow below splits the decision into two public methods — can_hold reads, take writes — which is exactly the gap the trace in Decision 1 the hold and the race it exists to lose exploited. The four calls under the class drive it deterministically: both users read before either writes. That makes the defect a passing assertion rather than a flaky one, which is the only way to put a race in a chapter and have it reproduce every time.

from __future__ import annotations

import threading
from dataclasses import dataclass, field
from enum import Enum
from typing import Iterable, Protocol


class SeatStatus(Enum):
    AVAILABLE = "available"
    HELD = "held"
    BOOKED = "booked"


class NaiveShow:
    """Read, decide, write -- as three separate steps. This oversells."""

    def __init__(self, seat_ids: Iterable[str]) -> None:
        self.status = {s: SeatStatus.AVAILABLE for s in seat_ids}

    def can_hold(self, seat_id: str) -> bool:          # step 1: read + decide
        return self.status[seat_id] is SeatStatus.AVAILABLE

    def take(self, seat_id: str) -> None:              # step 2: write
        self.status[seat_id] = SeatStatus.HELD


show = NaiveShow(["C7"])
a_allowed = show.can_hold("C7")     # user A reads
b_allowed = show.can_hold("C7")     # user B reads, before A writes
show.take("C7")                     # A writes
show.take("C7")                     # B writes, over the top
assert a_allowed and b_allowed, "both users were told the seat was free"

That assertion passes, and that is the whole point: both users were told the seat was free, and both were told the truth at the moment they asked.

Three Python constructs appear in that block and recur through the rest of the chapter, so they are worth a sentence each.

• from __future__ import annotations makes Python treat every type annotation as plain text instead of evaluating it. That is what lets str | None — syntax introduced in Python 3.10 — appear in a file running on 3.9.
• An Enum is a closed set of named constants. SeatStatus.HELD is a distinct object, not the string "held", so a typo becomes an AttributeError instead of a comparison that silently never matches.
• Protocol, imported here for use below, is the shape-based type described in Decision 2 the clock is a dependency.

The clock and the data classes

Next, the supporting types: the clock, a fake clock for tests, and the three records the design passes around.

The thing to notice is that FakeClock never mentions Clock anywhere and is still accepted wherever a Clock is wanted. That is what Protocol buys — a test clock with no base class and no mocking library.

from __future__ import annotations   # so `str | None` works on Python 3.9

class Clock(Protocol):
    def now(self) -> float: ...


class FakeClock:
    def __init__(self, t: float = 0.0) -> None:
        self.t = t

    def now(self) -> float:
        return self.t

    def advance(self, seconds: float) -> None:
        self.t += seconds


@dataclass
class ShowSeat:
    seat_id: str
    seat_class: str = "standard"
    status: SeatStatus = SeatStatus.AVAILABLE
    held_by: str | None = None
    hold_expires_at: float = 0.0


@dataclass(frozen=True)
class SeatHold:
    hold_id: str
    user_id: str
    seat_ids: tuple[str, ...]
    expires_at: float


@dataclass(frozen=True)
class Booking:
    booking_id: str
    user_id: str
    seat_ids: tuple[str, ...]
    amount_cents: int          # the price CHARGED, not a pointer to a rule


class HoldRejected(Exception):
    """Raised with the seats that were not available. Never partially applied."""

The decorators there carry design meaning, not just typing convenience.

@dataclass writes the constructor, the __repr__ and the equality test from the field list, so a class that is just data costs four lines instead of twenty.

@dataclass(frozen=True) additionally makes instances immutable: assigning to a field raises. That is a deliberate choice here, not a stylistic one. A SeatHold and a Booking are facts that happened, and a fact you can edit after the fact is how a receipt comes to silently disagree with the money that moved.

Say the limit of that out loud, though. frozen=True stops b.amount_cents = 1. It does not stop object.__setattr__ or dataclasses.replace. Immutability here is a statement of intent to the next reader, not a guarantee against a determined caller — the real guarantee has to be a validated constructor plus a persisted receipt.

ShowSeat is the one class left mutable, because its whole job is to change status.

The Show class

The whole design lives in Show.hold. Everything else in the class is bookkeeping.

Four things to look for as you read: the threading.Lock created in the constructor; the with self._lock: block inside hold that wraps read, decide and write together; the two guard clauses in hold that run before that lock is taken; and _reap, which is called on every read path rather than only by the timer.

class Show:
    def __init__(self, show_id: str, seats: Iterable[ShowSeat], clock: Clock,
                 ttl_seconds: float = 120.0) -> None:
        self.show_id = show_id
        self.seats = {s.seat_id: s for s in seats}
        self.clock = clock
        self.ttl_seconds = ttl_seconds
        self.holds: dict[str, SeatHold] = {}
        self._lock = threading.Lock()      # the monitor: one per show
        self._next = 0

    # -- caller must hold self._lock ------------------------------------
    def _reap(self, seat: ShowSeat) -> None:
        if seat.status is SeatStatus.HELD and self.clock.now() >= seat.hold_expires_at:
            seat.status, seat.held_by, seat.hold_expires_at = SeatStatus.AVAILABLE, None, 0.0

    def hold(self, seat_ids: Iterable[str], user_id: str) -> SeatHold:
        wanted = tuple(sorted(set(seat_ids)))
        unknown = [s for s in wanted if s not in self.seats]
        if unknown:                                   # or `hold` raises KeyError,
            raise HoldRejected(f"no such seat: {unknown}")   # not HoldRejected
        if not wanted:                                # and an empty set would mint
            raise HoldRejected("a hold must name at least one seat")   # a free Booking
        with self._lock:                              # read-decide-write, one step
            for sid in wanted:
                self._reap(self.seats[sid])
            taken = [s for s in wanted if self.seats[s].status is not SeatStatus.AVAILABLE]
            if taken:
                raise HoldRejected(f"unavailable: {taken}")
            self._next += 1
            h = SeatHold(f"h{self._next}", user_id, wanted,
                         self.clock.now() + self.ttl_seconds)
            for sid in wanted:
                seat = self.seats[sid]
                seat.status, seat.held_by, seat.hold_expires_at = (
                    SeatStatus.HELD, user_id, h.expires_at)
            self.holds[h.hold_id] = h
            return h

    def confirm(self, hold_id: str, amount_cents: int) -> Booking:
        with self._lock:
            if type(amount_cents) is not int or amount_cents < 0:
                raise HoldRejected(
                    f"amount_cents must be a non-negative int, got {amount_cents!r}")
            h = self.holds.get(hold_id)
            if h is None or self.clock.now() >= h.expires_at:
                raise HoldRejected("hold expired; seats returned to the pool")
            for sid in h.seat_ids:
                self.seats[sid].status = SeatStatus.BOOKED
            del self.holds[hold_id]
            return Booking(f"b{h.hold_id}", h.user_id, h.seat_ids, amount_cents)

    def release_expired(self) -> int:
        """The reaper. Idempotent, so it is safe to run on a timer."""
        with self._lock:
            now = self.clock.now()
            gone = [hid for hid, h in self.holds.items() if now >= h.expires_at]
            for hid in gone:
                for sid in self.holds[hid].seat_ids:
                    self._reap(self.seats[sid])
                del self.holds[hid]
            return len(gone)

    def available(self) -> list[str]:
        with self._lock:
            for s in self.seats.values():
                self._reap(s)
            return sorted(s.seat_id for s in self.seats.values()
                          if s.status is SeatStatus.AVAILABLE)

The four load-bearing lines

• self._lock = threading.Lock() and every with self._lock: block. Together these are the monitor. Every method that reads a seat’s status and then writes it does both inside one lock, so the gap the trace in Decision 1 the hold and the race it exists to lose exploited does not exist.
• wanted = tuple(sorted(set(seat_ids))). This deduplicates and sorts. The sort looks cosmetic and is not; What interviewers probe explains what it prevents.
• _reap on every read path. An expired hold is cleaned up by whoever notices it first, rather than only when the timer next runs. A seat map rendered one second after an expiry shows the seat free.
• release_expired is idempotent. Idempotent means running it twice has the same effect as running it once. That is exactly the property a job on a timer needs, because timers fire twice and overlap.

The three guards, and what each one prevents

These exist because the contract at the top of this chapter — HoldRejected or nothing changed — is otherwise a lie.

• Unknown seat ids, checked before the lock. This is a statement about the request, not about the state, so it belongs outside. Without it, hold(["Z9"], "u") raises KeyError, which is not HoldRejected; worse, hold(["C1", "Z9"], "b") reaps an expired hold on C1 on its way to raising, so a call that failed still changed something. That is precisely what “changes NOTHING” forbids.
• The empty set. Same defect, different disguise. Without the check, hold([], "ghost") succeeds, and confirm then mints a paid Booking for zero seats.
• The money, checked at the top of confirm. amount_cents: int is a comment until something enforces it. confirm(h, amount_cents=45.5) would store a float on a receipt, and -100000 would store a refund shaped like a sale.

The caveat to volunteer before the interviewer finds it

self.seats and self.holds are public. So this one line defeats every lock in the class:

show.seats['C7'].status = SeatStatus.AVAILABLE

Two holders, two confirms, one chair, two tickets — and the lock was taken correctly every single time. The algorithm is not the weak point; the unguarded field is.

In production these are _seats and _holds behind read-only accessors, and the real enforcement is the database’s WHERE status = 'AVAILABLE', not Python. The lock protects the method, not the field.

The assertions

Four numbered tests follow, and each one is a requirement from the contract rather than a coverage exercise. Test 1 proves the lock works under real threads, test 2 proves all-or-nothing, test 2b proves bad requests fail cleanly, test 3 proves the TTL in zero wall-clock time, and test 4 proves the money guard.

clock = FakeClock()
show = Show("s42", [ShowSeat(f"C{i}") for i in range(1, 9)], clock, ttl_seconds=120.0)

# 1. Under real threads, exactly one holder wins the contested seat.
start, wins, errs = threading.Barrier(16), [], []
def grab(uid: str) -> None:
    start.wait()
    try:
        wins.append(show.hold(["C7"], uid))
    except HoldRejected:
        errs.append(uid)

threads = [threading.Thread(target=grab, args=(f"u{i}",)) for i in range(16)]
for t in threads:
    t.start()
for t in threads:
    t.join()
assert len(wins) == 1 and len(errs) == 15, (len(wins), len(errs))

# 2. All-or-nothing: a group hold that touches the taken seat takes nothing.
try:
    show.hold(["C5", "C6", "C7"], "family")
    raise AssertionError("should have been rejected")
except HoldRejected:
    pass
assert show.seats["C5"].status is SeatStatus.AVAILABLE   # no partial application

# 2b. A bad request is HoldRejected too -- never KeyError, never a silent success.
for bad in (["Z9"], ["C1", "Z9"], []):
    try:
        show.hold(bad, "typo")
        raise AssertionError(f"should have been rejected: {bad}")
    except HoldRejected:
        pass
assert show.seats["C1"].status is SeatStatus.AVAILABLE   # and nothing was touched

# 3. The TTL, tested in zero wall-clock seconds.
clock.advance(121.0)
assert "C7" in show.available()            # reaped lazily, on read
assert show.release_expired() == 1         # the reaper drops the stale hold record
assert show.release_expired() == 0         # and is idempotent
h = show.hold(["C5", "C6", "C7"], "family")

# 4. Money is a non-negative whole number of cents, checked at the boundary.
for bad_amount in (45.5, -100000):
    try:
        show.confirm(h.hold_id, amount_cents=bad_amount)
        raise AssertionError(f"accepted {bad_amount!r} as cents")
    except HoldRejected:
        pass

booking = show.confirm(h.hold_id, amount_cents=4500)
assert booking.seat_ids == ("C5", "C6", "C7")
assert show.seats["C7"].status is SeatStatus.BOOKED

Two details in that block deserve a closer look.

threading.Barrier(16) makes all sixteen threads wait until the sixteenth arrives, then releases them together. That is what turns “sixteen threads exist” into “sixteen threads collide”. Without it the threads start staggered, queue up politely, and the test passes for the wrong reason.

clock.advance(121.0) moves time past the 120-second TTL and takes no measurable wall-clock time at all. That single line is the entire payoff of Decision 2 the clock is a dependency: an expiry test that runs in microseconds.

Assertion 2 is the one candidates skip and interviewers ask about. A partially applied group hold is worse than a rejected one, because the user sees a failure and the inventory sees a success — the seats are gone and nobody is coming back to pay for them.

8. Extension 1: seat classes with different pricing

Adding pricing rules to a finished design should cost one new class and no edit at all to the concurrency code. Whether it does is the test of whether Core objects and the one first drafts are missing through Working python were built correctly.

The new requirement: recliner rows cost more, the last row costs less, and Tuesdays are half price.

The wrong shape is if seat.seat_class == "recliner": ... inside confirm, because then every new price rule edits a method that also does concurrency — and concurrency code you edit weekly is concurrency code that breaks.

The right shape is the Strategy pattern: pull the varying rule out into an interface with one method, hold a reference to whichever implementation you want, and swap implementations without the holder noticing. Here the interface is price_cents(show, seat).

Note where the reference lives. Show does not hold a PricingStrategy — look back at Show.__init__ in Working python and there is no such field. The caller holds the strategy, computes the price, and hands the result to confirm as amount_cents. That is why pricing can change without touching the locked methods at all.

The block below defines the interface, one implementation, one wrapper, and then prices two seats. The two assertions at the bottom are the worked example: follow the multipliers outwards from the base price.

class PricingStrategy(Protocol):
    def price_cents(self, show: "Show", seat: ShowSeat) -> int: ...


class TieredPricing:
    def __init__(self, base_cents: int, multipliers: dict[str, float]) -> None:
        self.base_cents, self.multipliers = base_cents, multipliers

    def price_cents(self, show: "Show", seat: ShowSeat) -> int:
        return round(self.base_cents * self.multipliers.get(seat.seat_class, 1.0))


class WeekdayDiscount:
    """Wraps another strategy. Object composition (holding one), not the UML
    composition of section 4, and not a subclass explosion."""

    def __init__(self, inner: PricingStrategy, factor: float) -> None:
        self.inner, self.factor = inner, factor

    def price_cents(self, show: "Show", seat: ShowSeat) -> int:
        return round(self.inner.price_cents(show, seat) * self.factor)


pricing = WeekdayDiscount(TieredPricing(1200, {"recliner": 1.5, "back_row": 0.75}), 0.5)
recliner = ShowSeat("A1", seat_class="recliner")
assert pricing.price_cents(show, recliner) == 900       # 1200 * 1.5 * 0.5
assert pricing.price_cents(show, ShowSeat("Z9", seat_class="back_row")) == 450

WeekdayDiscount is a decorator: an object that implements the same interface as the thing it wraps, and adds behaviour by calling through to it.

Because it is a PricingStrategy and holds a PricingStrategy, discounts stack by nesting instead of by inheritance. That is what stops “recliner on a Tuesday in a loyalty scheme” from becoming its own subclass, and then “recliner on a Tuesday in a loyalty scheme with a student card” becoming another.

The assertions are that chain running outwards:

• Recliner: 1200 base, times 1.5 for the recliner tier, times 0.5 for the weekday wrapper, is 900.
• Back row: 1200 base, times 0.75, times 0.5, is 450.

What changes: one new class per rule. What does not: hold, confirm, release_expired, ShowSeat. Why: the price is computed outside Show and arrives as a plain integer, so pricing never entered the concurrency path.

What it costs: the price of a seat is no longer readable from one place. You now trace a decorator chain to answer “why was this 900”. And Booking.amount_cents becomes load-bearing — it must be the snapshot, because the strategy chain in six months will not reproduce today’s number.

9. Extension 2: group bookings that must be adjacent

This extension collects the payoff from the decision made back in Clarifying questions that change the design — a hold that takes a set — and exposes the subtler race that survives it.

The new requirement: “four together, in the same row, no gaps.”

Almost nothing changes, and that is the point. hold already takes a set and already applies all-or-nothing. All that is missing is a query that produces a good set to pass it.

The function below finds every run of n consecutive free seats in a row. The two assertions run it against a row with a gap — row C is missing seat 4 — which is what makes the “no gaps” requirement bite.

def adjacent_runs(seat_ids: list[str], n: int) -> list[tuple[str, ...]]:
    """seat ids are ROW + NUMBER, e.g. C7. Runs are contiguous numbers in a row."""
    by_row: dict[str, list[int]] = {}
    for sid in seat_ids:
        by_row.setdefault(sid[0], []).append(int(sid[1:]))
    out: list[tuple[str, ...]] = []
    for row, nums in by_row.items():
        nums.sort()
        for i in range(len(nums) - n + 1):
            window = nums[i:i + n]
            if window[-1] - window[0] == n - 1:
                out.append(tuple(f"{row}{k}" for k in window))
    return out


free = Show("s43", [ShowSeat(f"C{i}") for i in [1, 2, 3, 5, 6, 7, 8]],
            FakeClock()).available()
assert adjacent_runs(free, 4) == [("C5", "C6", "C7", "C8")]
assert len(adjacent_runs(free, 3)) == 3      # C1-C3, C5-C7, C6-C8

The function groups the free seats by row letter, sorts the numbers, and slides a window of length n along them.

The test for a genuine run is the one line worth memorising: window[-1] - window[0] == n - 1. A window of n sorted numbers spans exactly n - 1 only when nothing is missing in between. Row C runs 1, 2, 3, 5, 6, 7, 8, so the window [2, 3, 5] spans 3 rather than 2 and is correctly rejected.

That is why the only run of four is C5–C8, while the runs of three are C1–C3, C5–C7 and C6–C8.

What changes: one pure function and one API endpoint. What does not: the hold protocol. Why: the all-or-nothing set was chosen in Clarifying questions that change the design, before there was a visible reason for it.

What it costs, and this is the trap. adjacent_runs runs on a snapshot taken by available(), so the seats can be taken between the search and the hold. That is check-then-act again, one level up.

The fix is not to lock for longer. It is to accept that the search is advisory, let hold reject, and re-search. A suggestion API is allowed to be stale; the commit is not.

Running the search inside the show lock would make it atomic — and would also make a slow search block every other user of that show. At 0.33 holds per second that is the wrong trade.

10. Extension 3: cancellation with a partial refund

The last extension also supplies the reason Core objects and the one first drafts are missing insisted that Booking store a number rather than a rule.

The new requirement: “cancel up to 2 hours before the show for a 100% refund, up to 30 minutes for 50%, nothing after.”

The block below turns that sentence into a policy object. A tier here is a pair — a cutoff in minutes before the show, and the fraction refunded if you cancel at or before that cutoff. The three assertions walk one booking through all three tiers.

class RefundPolicy(Protocol):
    def refund_cents(self, paid_cents: int, minutes_to_show: float) -> int: ...


class TieredRefund:
    def __init__(self, tiers: list[tuple[float, float]]) -> None:
        self.tiers = sorted(tiers, reverse=True)      # (minutes_before, fraction)

    def refund_cents(self, paid_cents: int, minutes_to_show: float) -> int:
        for minutes, fraction in self.tiers:
            if minutes_to_show >= minutes:
                return round(paid_cents * fraction)
        return 0


policy = TieredRefund([(120.0, 1.0), (30.0, 0.5)])
assert policy.refund_cents(4500, 180.0) == 4500
assert policy.refund_cents(4500, 45.0) == 2250
assert policy.refund_cents(4500, 10.0) == 0

sorted(tiers, reverse=True) puts the most generous cutoff first, and the first tier the caller clears wins. Walking the three assertions:

• 180 minutes out clears the 120-minute tier, so the whole 4500 cents comes back.
• 45 minutes out misses 120 but clears 30, so half comes back: 2250.
• 10 minutes out clears nothing, so the loop falls through to return 0.

What changes: a CANCELLED terminal state on Booking (the BookingStatus field the Class diagram diagram shows and the Working python code omits), a cancel() on Show that flips the seats back to AVAILABLE under the same lock, and one policy class.

What does not: the seat state machine gains one edge, not one dimension. BOOKED -> AVAILABLE is the same edge release_expired already implies.

What it breaks, and admit this before the interviewer finds it. Two problems.

First, the refund is computed from Booking.amount_cents, and that is only correct because Extension 1 seat classes with different pricing stored the charged amount rather than the rule. Had Booking held a pricing_strategy reference instead, a Tuesday discount removed in March would make every February refund wrong — and wrong quietly, in the customer’s favour or yours, months after anybody was watching.

Second, cancel-and-refund spans two systems, so it needs an idempotency key — a caller-supplied identifier that lets the payment side recognise a retry of a request it already performed. Without one, a retried cancel refunds twice. That mechanism belongs to system design 27, not here.

11. What interviewers probe

These are the follow-up questions this design invites, with the answer that satisfies each — phrased as the words you would actually say, not as notes.

Three of those rows lean on terms worth spelling out.

• SET NX PX is Redis for “set this key only if it does not already exist, and expire it after this many milliseconds”. It is a distributed hold in one command, with the TTL built in.
• A deadlock is the standoff where thread A holds seat 1 and waits for seat 2 while thread B holds seat 2 and waits for seat 1, and neither ever proceeds. The standard cure is a global acquisition order — everybody takes locks in the same agreed sequence — which is exactly what the sorted() in hold buys, for free.
• A Singleton is the pattern of forcing a class to have exactly one instance, reachable globally. Its cost is that tests can no longer get a fresh one.

Cheat sheet

One line per decision, in the order you would defend them at the whiteboard. If you can reconstruct the right-hand column from the left, you can redraw this design from memory.

Related:

• 02 — The OOD Framework is the method for the 45 minutes, and its section on the five assumptions generalises Class diagram here.
• 03 — OOP Fundamentals treats “what a class structure assumes” as a topic in its own right.
• 06 — Unix File Search is the composition problem this chapter’s pricing decorators gesture at.
• 07 — Vending Machine is the explicit state machine that this chapter’s three seat states stop just short of needing.
• system design 23 — Hotel Reservation is the same race at the transaction layer.