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 an object model problem — the set of classes you define plus the relationships between them. The central difficulty is concurrency: what happens when two people select the same seat within a few hundred milliseconds of each other.

This chapter covers:

• the class most first drafts omit, and what breaks without it;
• a step-by-step interleaving of two servers that sells one seat twice;
• three fixes for that race, each with a cost estimate;
• why the expiry deadline must be passed in through a constructor argument instead of read from 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 the contract. Read each pair as one request: IN is what a caller sends, OUT is what comes back. 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

• Modelling Seat.is_booked. That flag makes a seat bookable once ever instead of once per show, because it has nowhere to record which screening booked it.
• Saying “we’d take a lock” and stopping there. Without describing what the lock protects, how long it is held, or what happens when the holder abandons the payment page.
• Shipping a claim that expires on a timer and cannot be tested. 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 for depth. 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 same 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.

1. Clarifying questions that change the design

Four questions are worth asking 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 — 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 matters most. Design the hold to take a set of seats even when the requirement says one. A group booking (“book 4 together”) cannot be retrofitted onto a single-seat API without changing every caller, every error path, and the lock scope.

Out of scope: 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. The exercise is worth doing because it surfaces one actor who is not a person.

The third row is the one candidates leave out.

The reaper 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 one 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 record 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 shows which object owns which, and where the split matters — 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 mean “taken for this show”.

The count of ShowSeat rows follows directly. A 200-seat auditorium running 6 shows a day creates 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.

Note also that Booking stores the price charged, not a pointer to a price rule. The reason is given 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. The notation is UML — the Unified Modeling Language, the standard boxes-and-arrows notation for class models — and 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

Each arrow is a sentence, grouped below by topic.

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 differ in a way an interviewer will ask about:

• 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 full whiteboard design. The Python in Working python is deliberately smaller. Here is which boxes it skips.

The cut is justified because the interesting part of this problem is about 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 bet about what will change. Every interface says “I expect this to vary”. Every hard-coded field says “I expect this to hold forever”.

Naming those bets is the transferable skill. The general version of this argument is What a class structure assumes; what follows is this design’s version.

Assumed to vary — and therefore given an interface or a parameter. The third column shows what the design would have looked like with the opposite bet.

Assumed fixed — and therefore baked into the structure, not into a parameter. These six bets 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. Interviewers reach for this to test whether you understand your own design.

• 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, no 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 fixed the structure; the behaviour is where the trouble lives. At its centre is one concurrency bug that “add a lock” misdescribes, and whose fix needs a cost estimate, 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 stale for the whole payment flow. The page shows a seat as free, the user spends ninety seconds typing card details, and somebody else buys it in the meantime.

With a naive hold — written the obvious way, with no lock — the seat map is stale for only about 200 milliseconds. That is still enough to double-sell.

The race, traced

The block below is an interleaving: the step-by-step order in which two servers execute. 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.

Note 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”. It is that the read that made the decision and the write that acted on it were two separate steps, and the state could change in between.

“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 is called 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 differ 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. The arithmetic below defends it when an interviewer calls the lock “too coarse”. It runs in three parts: the demand on the lock (0.33 holds per second), 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.

One lock around one show’s entire seat map is five orders of magnitude away from being a bottleneck.

The real question is not “is the lock too coarse” but “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 plus the only transitions allowed between them. The happy path runs AVAILABLE -> HELD -> BOOKED; the return edges are the ways a seat goes back on sale.

stateDiagram-v2
    [*] --> AVAILABLE
    AVAILABLE --> HELD: hold()
    HELD --> BOOKED: confirm()
    HELD --> AVAILABLE: release() / TTL expiry
    BOOKED --> AVAILABLE: cancel()

HELD 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 something has to report the time. The current time must be passed into the design rather than read from inside it. Once it is, the deadline itself can be chosen by arithmetic.

The problem with reading the clock

A TTL means something 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 one 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. The alternative is a module-level time call, which is a global: one shared instance that every test silently agrees on and no test can replace.

The cost is real. Every object that can expire now carries a clock field, constructors get longer, and a caller who forgets to pass one gets production behaviour in a test.

You can default it to the real clock, in which case the mistake is silent; or require it, in which case every construction site is noisier. Require it for anything with a TTL, and default it elsewhere.

Choosing the TTL by arithmetic

The 120-second value 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 last line is the price paid, 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, in exchange for a payment window.

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

7. Working Python

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

The broken version, run on purpose

Start with the bug, so it can be observed rather than taken on faith.

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, so the race reproduces 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"

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

Three Python constructs appear here and recur through the chapter.

• 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.

Note that FakeClock never mentions Clock 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 deliberate. A SeatHold and a Booking are facts that happened, and an editable fact is how a receipt comes to disagree with the money that moved.

Note the limit. 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 is 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 core of the design is Show.hold. Everything else in the class is bookkeeping.

Four things to look for: 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 to uphold the contract at the top of this chapter: HoldRejected or nothing changed.

• 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 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, each one 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 deserve a closer look.

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

clock.advance(121.0) moves time past the 120-second TTL in no measurable wall-clock time. That single line is the 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 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 edited weekly breaks.

The right shape is the Strategy pattern: pull the varying rule 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 — there is no such field in Show.__init__ in Working python. 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.

The block below defines the interface, one implementation, and one wrapper, then prices two seats. The two assertions 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 stops “recliner on a Tuesday in a loyalty scheme” from becoming its own subclass, and “recliner on a Tuesday in a loyalty scheme with a student card” from 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; answering “why was this 900” means tracing a decorator chain. 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 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. 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 treat the search as 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 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. Two problems, both worth raising before the interviewer does.

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, 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

The follow-up questions this design invites, each with the answer that satisfies it.

Three of those rows use 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.