Cruxly › Low-level design › LLD Exercises

Movie Ticket Booking

two users cannot hold the same seat, and a hold must expire on its own

Prompt: design the seat-booking core of a movie ticket system. A user picks a showtime and one or more seats, holds them while completing payment, and either confirms the booking or the hold expires and the seats return to available — automatically, with no user action required.

45 minutes. The interesting part is not the seat map. It's that "hold" is a state with a deadline, and two users racing for the same seat must never both win.

Applying the five moves: nouns are Showtime, Seat, Hold (with an expiry timestamp), Booking — Hold as its own noun rather than a boolean flag on Seat is the modelling decision the whole exercise turns on, because a flag has no natural place to carry a deadline. The invariant is "a seat is available, held, or booked — never two of those at once, and a hold that outlives its deadline is treated as if it never existed" — say this before the seat-map class. There's no interface seam worth forcing here (payment processing is out of scope) — the real design pressure is the invariant and the concurrency, not extension. The concurrency sentence is the actual exercise: claiming a hold is check-then-act across concurrently racing users, and the hold's automatic expiry means the system also has to notice time passing without anyone polling for it — both need naming explicitly, not just the seat model.

Scope, and why a seat is three states, not two

In scope: seat map per showtime, holding seats for payment, confirming or expiring a hold, preventing double-booking. Out of scope (say it): payment processing itself (a downstream integration, name it and move on), pricing/discounts, seat-map layout rendering.

A seat is not simply available-or-booked — it has a third state, HELD, with a deadline:

AVAILABLE  -- anyone can hold it
HELD       -- one user has it for a bounded window (e.g. 5 minutes), everyone else is blocked
BOOKED     -- payment confirmed, permanent until a cancellation flow (out of scope) touches it

The two-state version — available/booked — is the version that breaks in production, because there is no window between "user clicked seats" and "payment confirmed" during which the seat is provably reserved but not yet paid for. Without HELD, either two users can both proceed to payment for the same seat (a race that surfaces as a support ticket, not a test failure), or the system has to hold a database transaction open for the entire payment flow, which no real payment integration allows.

The hold must expire without anyone polling for it. A cron job that scans for expired holds every 30 seconds means a seat can sit falsely HELD for up to 30 seconds after the real deadline — during a flash sale for a popular showtime, that is exactly the window where the design's honesty matters most. The hold's expiry needs to be enforced by the read path itself, not just by a background sweep, which is the actual point of this exercise.

The classes, and the atomic hold

public enum SeatStatus { AVAILABLE, HELD, BOOKED }

public class Seat {
    final String seatId;
    private volatile SeatStatus status = SeatStatus.AVAILABLE;
    private volatile String holderId;
    private volatile Instant holdExpiresAt;

    // package-private: only SeatMap mutates a Seat, and only under its lock
    void markHeld(String holder, Instant expiresAt) {
        status = SeatStatus.HELD; holderId = holder; holdExpiresAt = expiresAt;
    }
    void markBooked() { status = SeatStatus.BOOKED; holdExpiresAt = null; }
    void release()    { status = SeatStatus.AVAILABLE; holderId = null; holdExpiresAt = null; }

    /** The read path enforces expiry — a HELD seat past its deadline is
     *  treated as AVAILABLE right here, not by waiting for a sweep to notice. */
    SeatStatus effectiveStatus(Instant now) {
        if (status == SeatStatus.HELD && now.isAfter(holdExpiresAt)) return SeatStatus.AVAILABLE;
        return status;
    }
}

effectiveStatus computed lazily at read time is the same discipline as the rate limiter's lazy token refill elsewhere in this track — no background thread has to run on a schedule for the system to behave correctly; an expired hold behaves as available the instant anyone asks, not up to 30 seconds later.

public HoldResult hold(List<String> seatIds, String userId, Duration window, Clock clock) {
    List<String> held = new ArrayList<>();
    for (String id : seatIds) {
        Seat s = seats.get(id);
        synchronized (s) {                                  // lock ONE seat at a time
            if (s.effectiveStatus(clock.instant()) != SeatStatus.AVAILABLE) {
                held.forEach(h -> seats.get(h).release());   // try to undo what we already held
                return HoldResult.failed(id);
            }
            s.markHeld(userId, clock.instant().plus(window));
            held.add(id);
        }
    }
    return HoldResult.success(seatIds, clock.instant().plus(window));
}

public class SeatMap {
    private final Map<String, Seat> seats;
    private final Object lock = new Object();               // one lock per showtime's seat map

    /** Atomically holds every requested seat, or none of them. */
    public HoldResult hold(List<String> seatIds, String userId, Duration window, Clock clock) {
        synchronized (lock) {
            Instant now = clock.instant();
            for (String id : seatIds) {
                Seat s = seats.get(id);
                if (s == null || s.effectiveStatus(now) != SeatStatus.AVAILABLE) {
                    return HoldResult.failed(id);            // fail fast, hold nothing
                }
            }
            Instant expiresAt = now.plus(window);
            for (String id : seatIds) seats.get(id).markHeld(userId, expiresAt);
            return HoldResult.success(seatIds, expiresAt);
        }
    }

    public boolean confirm(List<String> seatIds, String userId, Clock clock) {
        synchronized (lock) {
            Instant now = clock.instant();
            boolean allValid = seatIds.stream().allMatch(id -> {
                Seat s = seats.get(id);
                return s != null && s.effectiveStatus(now) == SeatStatus.HELD
                       && userId.equals(s.holderId());
            });
            if (!allValid) return false;                     // one seat's hold lapsed mid-payment
            seatIds.forEach(id -> seats.get(id).markBooked());
            return true;
        }
    }
}

The whole seat map for one showtime shares one lock, and hold takes it for the entire multi-seat check-then-mark sequence. This is the multi-seat version of the rate limiter's check-then-act race: checking seat A available, then seat B, then marking both held, is unsafe if another thread's hold call interleaves between the check and the mark for any one seat — so the check for every requested seat and the mark for every requested seat both happen inside one critical section, all-or-nothing. A partial hold (three of four requested seats held, one already taken) is worse than no hold at all, because the user now has to notice and unwind it themselves.

Why one lock per showtime, not one lock for the whole cinema

Lock granularity is the follow-up this exercise is building toward. One global lock across every showtime in the system would serialize every seat hold in the building through a single choke point — a sold-out blockbuster in screen 1 would stall seat holds for an empty arthouse film in screen 6, for no reason connected to any actual data conflict.

One lock per showtime is the right grain, because two users booking seats for different showtimes never touch the same Seat objects and have no reason to wait on each other — this is the same "lock the smallest thing that's actually contended" principle as the rate limiter's per-bucket lock, applied at the granularity of an independent seat map instead of an independent user.

Locking per seat instead of per showtime would be finer-grained but wrong here, because the multi-seat hold needs all-or-nothing atomicity across several seats at once — acquiring four separate per-seat locks in a naive order is also a well-known deadlock shape (two users each holding one of the other's wanted seats, both waiting). A per-showtime lock sidesteps the deadlock question entirely by making the multi-seat hold a single critical section instead of a multi-lock acquisition — simpler and safer, at the cost of one showtime's holds all serializing through one lock, which is an acceptable trade because a single showtime's seat count is small and holds are brief.

Expiry needs a bounded, real-world-honest window, said as a number. Five minutes is long enough to enter payment details, short enough that a distracted user doesn't hold seats a genuinely interested buyer could have used. Naming the actual number, and that it is a product decision as much as a technical one, is stronger than leaving "some reasonable timeout" unstated.

Follow-ups they will ask

"What if the user's payment succeeds one second after their hold expired?" This is the same edge the rate limiter's clock-injection and the OTP exercise's expiry both surface: a boundary condition that will happen at scale and needs an explicit, stated policy rather than an implicit assumption that it's rare enough to ignore. The honest answer: confirm() re-checks effectiveStatus at the moment of confirmation (shown above), so a lapsed hold fails confirmation even if payment technically succeeded — and the system needs a defined recovery path (refund and offer to re-hold if still available, or fail the payment before it's charged) rather than silently booking a seat whose hold already expired.

"Scale this to a flash sale — a hundred thousand users hitting refresh for the same twenty seats." The seat map read path (checking effectiveStatus for display) must not take the same lock as the write path (hold/confirm), or every page render for that showtime serializes behind booking attempts. Split reads onto a lock-free or read-optimized view (a cached snapshot refreshed on every successful hold/confirm/release) from the authoritative, lock-protected write path — the same read/write separation this track's caching material argues for generally, applied here because the read:write ratio during a flash sale is extreme.

"Add a waitlist for sold-out showtimes." This is a new state graph, not an extension of the seat state machine — a waitlist entry doesn't hold a specific seat, it holds a position, and only converts to an actual HELD seat when one frees up (a cancellation, an expired hold that nobody re-grabbed). Keeping it as a separate queue that produces hold attempts, rather than another Seat status, avoids tangling two different lifecycles into one enum.

How to say it in the interview

"The seat map is a grid, that part is easy. The actual exercise is that a seat has three states, not two — available, held, booked — and the transition into held has to be atomic across concurrent requests, plus the hold has to expire on its own without anyone polling for it."

Checklist

Modelled the seat as AVAILABLE/HELD/BOOKED, not a two-state available/booked flag
Enforced hold expiry in the read path itself, not only via a periodic background sweep
Made a multi-seat hold check and mark every seat inside one critical section, all-or-nothing
Locked per showtime rather than globally or per individual seat
Re-validated the hold's expiry and ownership inside confirm(), not just at hold time
Stated an actual hold duration as a number, not 'some reasonable timeout'
Split the high-volume read path (seat-map display) from the lock-protected write path for scale
Modelled a waitlist as a separate queue producing hold attempts, not a third seat status

Practice this interactively