BookMyShow

The idea

What it is

“Design a movie ticket booking system like BookMyShow.” That is the whole prompt. Most candidates hear it and start listing screens, movies, cities and reviews.

The interviewer is not shopping for a catalogue. They are shopping for one seat, two people, one second. Everything else on the page — the movies, the theatres, the search — is scaffolding around a single contended resource that two strangers are allowed to reach for at exactly the same moment.

The whole lesson in one line

Two people click the same seat in the same second. Exactly one of them may get it — and the loser must find out immediately, not after paying. That splits into two ideas: the thing you book is a ShowSeat, not a Seat; and taking it is an atomic compare-and-set on that one seat, never a lock around the theatre.

Read the two orange labels on the left and the right. Seat is furniture. ShowSeat is furniture-at-a-time. Everything hard in this problem happens because beginners collapse those two into one class.

Here is what that collapse costs you. Put a boolean on the seat — Seat { id, isBooked } — and it works beautifully for exactly one show. Then the interviewer asks for the 9:00 PM listing, and “is C8 free?” becomes a question your model cannot answer, because C8 is taken at 6:00 and empty at 9:00, and there is only one C8 object in memory.

The fix is one word long: materialise. When a Show is created, it makes one ShowSeat per Seat in the Screen. Status lives there. Price lives there. The Seat never changes again.

What is actually being graded

Did you find ShowSeat? A Seat with a boolean on it is the single most common way this round is failed, and it fails silently — the design looks fine until the second show exists.
Is taking a seat atomic on the seat itself? A compare-and-set from AVAILABLE to HELD, on that one row. Not a synchronized method on BookingService, which serialises every seat click in the country through one lock.
Is there a hold with an expiry? AVAILABLE → HELD → BOOKED, plus HELD → AVAILABLE when the timer runs out. No expiry means one abandoned checkout kills that seat forever.
Is payment outside the transaction, and is confirm idempotent? Payment is slow, external, and retries. A duplicate webhook must not book the seat twice or charge the card twice.
Is selecting three seats all-or-nothing, in a canonical order? Partial success is worse than failure, and unordered acquisition is a textbook deadlock (Deadlock, race conditions, starvation).

The sentence that separates the top 10% in this round

“I will not lock the show. I will compare-and-set the individual ShowSeat row from AVAILABLE to HELD, and the loser gets false back synchronously.” Say it in minute six, while you are still drawing boxes. Everything after that is easier because the interviewer already knows you understand the problem.

Mechanics

How it works

Step 1 · Clarify — 6 minutes

The prompt is one sentence, so the first six minutes are yours to shape. Ask these, and ask them in this order — the first two decide the entire design (A repeatable 5-step framework).

Is one movie shown at several times in the same hall? — yes. Say it out loud, because this is the question that forces Show into existence and kills seat.isBooked before you ever type it.
When I pick a seat, is it mine while I pay? — yes, for a few minutes. That single answer buys you the whole HELD state, the TTL, and the release-on-failure path. If you do not ask it, you will design a system where the seat is only taken after payment succeeds, and two people will pay for it.
How long is the hold? — 5 to 10 minutes in the real product. Pick 7 and make it a constant, not a magic number.
Can one booking span several seats? — yes, and it must be all-or-nothing. Nobody wants two of the three seats they asked for.
Do different seats cost different amounts? — yes: Silver, Gold, Recliner, and evening shows cost more than matinees. That is a PricingStrategy, not a chain of ifs (Strategy).
Single process or a cluster? — assume a single process for the 90 minutes, and say “the atomic seat update becomes a conditional UPDATE on the seat row when this is ten servers”. That one sentence banks the distributed answer without spending time on it.
Search, reviews, food ordering, offers, seat-map rendering, real payments? — out of scope, in one sentence each.

Everything orange on the left is what the round is actually about. If you are at minute 45 and the orange rows are not working, cut a grey one — not an orange one.

Step 2 · Nouns → classes, and the one nobody says out loud

Read the prompt back and underline the nouns: movie, theatre, screen, seat, show, ticket, user. Six of those map to a class in the obvious way. The seventh — the one that is not in the prompt — is the one you have to invent.

The last line is the general version of the trick. “Is C8 free?” has two different answers at 6 PM and 9 PM — so Seat was hiding a second class inside it. That is the same instinct as Identifying entities, attributes & behaviors.

How to say the ShowSeat idea in fifteen seconds

“A Seat is furniture — row C, number 8, gold tier — and it is never booked. A Show is a movie in a screen at a time. When I create a Show I materialise one ShowSeat per Seat, and that object carries the status, the holder, the expiry and the price. Two shows in the same hall get two independent sets of forty ShowSeats over the same forty chairs.”

One follow-up always lands here: “a 500-seat hall × 30 shows a day × 200 screens — are you really creating all those objects?” The answer is yes, and it is fine: they are small, they are created once when the show is scheduled, and they are exactly the rows a real database would hold. If they push, the alternative is to materialise lazily — create the ShowSeat row on first touch and treat “no row” as AVAILABLE. Say that, then move on. It is a storage optimisation, not a model change.

Step 3 · The APIs — five methods, and the shape of each

Write the method signatures before the classes. If the signatures are right, the classes almost fall out. Notice that now is a parameter everywhere — the moment you call the clock inside the logic, hold expiry becomes untestable.

the API surface — write this on the whiteboard first

// ---- browsing (boring, but they will ask) -------------------------------
List<Show>      showsFor(String movieId, String city, LocalDate day);
SeatMap         seatMap(String showId, long now);        // 40 ShowSeats + status + price

// ---- the part the round is about ---------------------------------------
Booking         selectSeats(String showId, List<String> seatLabels,
                            String userId, long now);    // PENDING + holds, all-or-nothing
Booking         confirm(String bookingId, String paymentRef, long now);  // IDEMPOTENT
void            abandon(String bookingId, long now);     // user walked away / pay failed
void            cancel(String bookingId, long now);      // after booking, inside refund window

// ---- housekeeping -------------------------------------------------------
int             sweepExpiredHolds(long now);             // returns dead holds to the pool

// Note what is NOT here: there is no bookSeat(seatId). Booking a seat is two
// calls separated by a slow, failable payment. Collapsing them into one method
// is the same mistake as putting isBooked on Seat - it works until reality shows up.

Why selectSeats returns a Booking and not a boolean

Because the hold has to be findable. If selectSeats returns true, the only record that three seats are held for this user lives inside three seat objects, and nothing ties them together. A PENDING Booking is the handle: it knows the user, the seats, the amount and when it dies. confirm and abandon both take that one id.

The class diagram

Three groups. The left column never changes after setup. The orange box is the only place contention exists. BookingService at the bottom orchestrates and owns nothing (Single Responsibility (SRP)) — notice it never touches a Seat, only ShowSeats.

Step 4 · The `ShowSeat` lifecycle — three states, five edges

Draw this before you write a line of tryHold. Three states, and every legal move between them. If a transition is not on this diagram, the code must refuse it — that is the difference between a state machine and a pile of booleans (State).

Point at the two edges that do not exist — AVAILABLE → BOOKED and HELD → HELD(other user). A state machine is defined by what it refuses (State diagrams).

Why HELD and not just a lock you hold during payment

Because payment takes forty seconds and can fail. A real lock held across a network call to a bank is a lock you will eventually leak — the process dies mid-payment and that seat is gone until someone restarts the server. HELD is soft state with an owner and a deadline: it survives a crash badly on purpose, because the deadline cleans it up.

Step 5 · Two clicks, one seat — the race this problem is built around

Here is the code every first draft contains. It reads correctly, it passes every single-user test, and it is wrong.

the bug, in four lines

// DO NOT SHIP THIS
if (showSeat.getStatus() == AVAILABLE) {      // 1. read
    showSeat.setStatus(HELD);                 // 2. write
    showSeat.setHeldBy(userId);
    return true;                              // "the seat is yours"
}
return false;

// Between line 1 and line 2 there is a gap. It is microseconds wide.
// A thousand people are clicking A5 on a Friday. Somebody is in that gap.

The gap between the read and the write is the entire problem. It is microseconds wide, which is why it never shows up in your demo and always shows up on a Friday night.

The fix is not a bigger lock. The fix is to make the check and the take one indivisible operation on that one seat — a compare-and-set. “If and only if you are AVAILABLE, become HELD by me.” One of the two callers gets true. The other gets false, immediately, and the UI can grey the seat out before the user has finished moving the mouse.

Both boxes at the bottom are correct. Only the left one is a design. This is the same trade-off as Locks, Mutex, Semaphore: the size of the critical section is the whole engineering decision.

the only method that matters

/**
 * The compare-and-set, on ONE seat. In Java, "synchronized" on the ShowSeat
 * instance is the lock - and the instance IS the contended resource, so the
 * lock is exactly as wide as the thing it protects.
 *
 * Note: expiry is checked on the way in. A hold whose deadline passed is
 * already dead, so the next caller through the door gets the seat for free.
 */
synchronized boolean tryHold(String userId, long now, long ttlMillis) {
    expireIfDue(now);                                  // lazy expiry

    if (status == SeatStatus.AVAILABLE) {              // COMPARE
        status      = SeatStatus.HELD;                 // ...and SET
        heldBy      = userId;
        holdExpires = now + ttlMillis;
        return true;
    }
    if (status == SeatStatus.HELD && userId.equals(heldBy)) {
        holdExpires = now + ttlMillis;                 // my own hold: extend, do not fail
        return true;
    }
    return false;                                      // the loser, told synchronously
}

private void expireIfDue(long now) {                   // caller already holds the monitor
    if (status == SeatStatus.HELD && now >= holdExpires) {
        status = SeatStatus.AVAILABLE;
        heldBy = null;
        holdExpires = 0L;
    }
}

The one-server answer and the ten-server answer, in one breath

“On one process this is a synchronized method on the ShowSeat — or a compareAndSet on an AtomicReference if I want it lock-free (Atomic operations & CAS). On ten processes the object is a database row and the same operation becomes UPDATE show_seat SET status='HELD', held_by=?, expires_at=? WHERE id=? AND status='AVAILABLE' — I check that it affected exactly one row. Same shape, different place.” Have that sentence ready; it gets asked every time.

Three seats or none — and why the order matters

Nobody books one seat. They book three, and getting two of them is a worse outcome than getting zero. So selectSeats takes them one at a time and rolls back everything it already took the moment one refuses.

Then there is the part that separates a careful candidate from a fast one. Two users ask for overlapping sets: U1 wants [C4, C5], U2 wants [C5, C4]. If each takes them in the order the user typed, U1 can hold C4 while U2 holds C5, and now neither can finish. Sort the seats into one canonical order before acquiring — by id — and that interleaving becomes impossible. It is the classic lock-ordering fix, and it costs one line (Deadlock, race conditions, starvation).

The rollback is the interesting half. Without it, a failed selection leaves two seats invisibly held for seven minutes — and the customer who could have taken them sees a full row.

Why the hold must expire — and who does the expiring

Ask “what happens if the user closes the tab?” and answer it before they do. Without an expiry, that seat is HELD forever. One abandoned checkout, one dead seat, for every show, for the rest of time. A cinema fills up with ghosts.

Say both mechanisms. Lazy expiry is what makes it correct; the sweeper is what makes the seat-map screen and the “12 seats left” counter honest for seats nobody is looking at.

The trap inside lazy expiry

expireIfDue(now) must run inside the same atomic step as the compare-and-set, not before it. If you check expiry, release the lock, and then try to hold, you have re-opened the exact gap you were closing — two callers can both see “expired, therefore free” and both take it. In the Java code above, expireIfDue is called from inside the synchronized method for precisely that reason.

Payment is not part of the transaction

The whole reason HELD exists is that payment is slow, external, and allowed to fail. So the flow is three separate steps with a network call in the middle: hold → pay → confirm. The seats are held across the payment, not locked across it.

And because payments retry, confirm will be called twice. A gateway webhook fires, times out, and fires again with the same paymentRef. If confirm is not idempotent, the second call either double-books the seat or double-charges the card — and in this problem it can do both.

Step 1 is the whole idempotency answer, and it is four lines of code: key the operation on something the caller supplies — paymentRef — and return the existing result if you have seen it. Never key it on “time” or “the seat state”.

Two smaller things the good candidates say here

1. confirm re-checks that each seat is still HELD by me. The payment took forty seconds; the hold may have expired in the middle. If it did, you refund rather than book — and you say that out loud, because it is the failure everyone forgets. 2. The seat-level confirm is itself replay-safe: confirming a seat that is already BOOKED with the same bookingId returns true, so a partial retry finishes cleanly instead of throwing.

Pricing lives on the `ShowSeat`, and comes from a strategy

A recliner at 9 PM does not cost what a silver seat at 11 AM costs. Two inputs — seat tier and show time — and interviewers love to add a third mid-round (weekend surge, a discount code, dynamic pricing on demand). That is your cue to put the rule behind an interface instead of a growing if ladder (Strategy, Open/Closed (OCP)).

pricing — one interface, integer paise, no doubles

interface PricingStrategy {
    /** Never returns a double. Money is a long of paise, always. */
    long priceInPaise(Show show, Seat seat);
}

final class FlatPricing implements PricingStrategy {
    private final long paise;
    FlatPricing(long paise) { this.paise = paise; }
    public long priceInPaise(Show show, Seat seat) { return paise; }
}

final class TierAndTimePricing implements PricingStrategy {
    public long priceInPaise(Show show, Seat seat) {
        long base = switch (seat.tier()) {          // the chair
            case SILVER   -> 15000L;                // Rs.150.00
            case GOLD     -> 25000L;                // Rs.250.00
            case RECLINER -> 45000L;                // Rs.450.00
        };
        int pct = show.startHour() >= 21 ? 150      // late night
                : show.startHour() >= 18 ? 130      // prime evening
                : show.startHour() >= 12 ? 110      // afternoon
                : 90;                               // morning show, cheaper
        return base * pct / 100;                    // integer maths, rounds DOWN, never drifts
    }
}

// The price is computed ONCE, when the Show materialises its ShowSeats, and
// stamped onto each one. A price change tomorrow must not silently re-price a
// seat somebody is already holding - that is why it is a field, not a lookup.

Say this while you type it

“Money is a long of paise. ₹325.00 is 32500. A double cannot represent 0.1 exactly, and a ticket price that drifts by a paisa is a reconciliation ticket six months later. I format to rupees only at the very edge, when I print.” Same rule as Splitwise — and it costs one sentence.

The follow-ups they always ask

“A 500-seat hall — are you sending 500 objects to the browser?” Yes, and it is about 20 KB of JSON, which is fine. The real answer is that the seat map is read-heavy and stale-tolerant: cache it, and let the tryHold call be the source of truth. A user seeing a seat that was taken 200 ms ago is not a bug — they just lose the CAS and are told instantly.
“Can I hold six seats?” Cap it, and say why: an uncapped hold is a free denial-of-service. maxSeatsPerBooking = 10 is a business rule, not a technical one, so it lives in one constant that a product manager can change.
“I want four seats together.” That is a selection problem, not a booking problem. Scan each row for a run of maxSeats consecutive AVAILABLE seats and offer the best run; then hold them through the exact same holdAll. Nothing in the concurrency design changes — which is the point worth making.
“What about cancellation and refunds?” BOOKED → AVAILABLE plus a RefundPolicy that takes (booking, now, show.startsAt) and returns an amount in paise: full refund up to 2 hours before, half up to 20 minutes, nothing after. Another strategy, another swappable rule.
“Why not just retry when the hold fails?” Because the seat is gone, not busy. Retrying a lost CAS on a specific seat is pure hope — the honest UX is to say “A5 was just taken” and let the user pick again. Retry is right when the resource is fungible (any seat, any spot); it is wrong when the user chose that one.
“Ten servers instead of one?” The ShowSeat becomes a row and tryHold becomes UPDATE … WHERE id = ? AND status = 'AVAILABLE' with a check on rows-affected, or a Redis SET seat:id holder NX PX 420000. The lifecycle, the TTL, the rollback and the idempotency key all survive unchanged — which is exactly why they were designed as data rather than as in-process locks.
“How would you test it?” Two tests carry the round. First: 100 threads call tryHold on one seat; assert exactly one returns true. Second: a property test that fires random select, confirm, abandon and sweep calls with a fake clock, asserting after every step that no ShowSeat is BOOKED by two bookings and that available + held + booked == totalSeats.
“Overbooking, like airlines?” Say no for cinemas and explain why: a plane seat is fungible and a bumped passenger can be compensated; a cinema seat is chosen by the customer and there is nowhere to move them to. Knowing when the trick does not apply reads better than knowing the trick.

Look at the last row. Going distributed touches one method, because the hold was modelled as data with a deadline rather than as a language-level lock. That is the payoff for the design you made in minute six.

The 90 minutes

The two orange blocks are the round. If you reach minute 60 without tryHold working under two callers, drop pricing, drop cancellation, and get the race test running — it is the single most convincing thing you can show.

How this round is lost

boolean isBooked on Seat. The model is dead the moment a second show exists, and you usually find out in minute 50 when the interviewer asks for the 9 PM listing.
No hold state at all — the seat is taken only after payment succeeds. Two people pay, one gets a refund and a bad review, and the design has no place to put a fix.
A hold with no expiry. One abandoned tab and that chair is unsellable forever. This is the follow-up that catches people who did remember the hold.
synchronized on BookingService. Correct and useless: every seat click in the country queues behind one lock. The interviewer will not say anything; they will just write it down.
Acquiring several seats in the user's order. Two overlapping requests, two half-held sets, nobody finishes. One sort line prevents it.
Partial selection with no rollback. Two seats silently held for seven minutes after a failed request — invisible to everyone, including you.
confirm that is not idempotent. The retried webhook charges twice. Money bugs are the ones that get escalated.
Calling the clock inside the logic. System.currentTimeMillis() inside tryHold means you cannot test expiry without sleeping seven real minutes, so you will not test it, so it will be broken.
double for the ticket price. Free marks thrown away in a problem that already has enough hard parts.

Interactive prototype

See it. Build it. Break it.

A sandboxed, hands-on simulation — no setup, no install. Play with it as you read.

simulation › BookMyShow

About this simulation

A live seat map for one 6:00 PM show, driven by two users. Press ⚔️ Both click A5 while the toggle reads 🔒 Guarded — one compare-and-set wins, the loser's card shakes red and is told in the same millisecond. Now flip to 🔓 Unguarded and press it again: both users are told “confirmed”, and the red ⚠ double-booked: 1 counter appears. Then hold a few seats as 👤 U1, press ⏳ Let the hold expire to watch them snap back to available, and switch 🎟 Flat / 🪜 Tier × time to re-price the same selection with zero caller changes.

Hands-on

Try these yourself

Open the prototype above, predict what happens, then verify.

try 01

Hold a seat, and watch the countdown start

The chip 👤 U1 is lit, so you are Aditi. Click C4, C5 and C6. Each one turns amber with a U1 badge and a live countdown, and the call line prints the real call: seatLock.tryHold(SH-6PM:C4, U1, ttl=7s) → true. Nothing is booked yet — read the counters strip: held 3, booked 0. That amber state is the whole HELD idea, and the number ticking down is expiresAt.

try 02

The money button — ⚔️ Both click A5

Leave the toggle on 🔒 Guarded and press ⚔️ Both click A5. Two tryHold calls hit the same seat in the same tick. One returns true, the seat goes amber for the winner, and the loser's card shakes red — the explain line says they were told in the same call, before typing a card number. Now press 🔓 Unguarded and press ⚔️ Both click A5 again: both users are told “confirmed”, the seat shows U1✚U2, and the red ⚠ double-booked: 1 counter appears. That counter is the whole lesson.

try 03

Let a hold die

Hold two or three seats as 👤 U1, then press ⏳ Let the hold expire. The simulated clock jumps past the 7-second TTL, the amber seats snap back to outlined available, and the held counter drops to 0. Nothing else happened — no user, no button. That is what stops one abandoned tab from killing a chair for the rest of the evening.

try 04

Pay, then break the payment

Hold D1 and D2, then press 💳 Pay: they go solid and a booking id like BK-1041 is printed with the total. Reset, hold the same two seats, and press 💥 Payment fails instead — they return to available in front of you. Watch which seats stay untouched both times: the payment hop never froze the rest of the hall, because the seats were held, not locked.

try 05

Re-price the same selection with nobody's code changed

With a few seats held, switch between 🎟 Flat and 🪜 Tier × time. The running total changes and the per-seat prices change — silver, gold and recliner diverge under 🪜 Tier × time and collapse to one number under 🎟 Flat. The explain line says it plainly: 0 lines of caller code changed. Then press ⚡ Fill the show and click any seat to see the sold-out path, and ↺ Reset to start over.

try 06

Then build it blank-file, in this order

Close the page and write it from memory: Seat (row, number, tier, no status) → Show → ShowSeat materialised one-per-seat → tryHold as a single atomic compare-and-set with lazy expiry inside it → holdAll sorting by id and rolling back on the first refusal → confirm with an idempotency check on paymentRef before anything else. Then write the test that matters: 100 threads on one seat, assert exactly one true.

In practice

When to use it — and what trips people up

The shape you just learned

Take the cinema away and what is left is a scarce, non-fungible resource that two strangers may reach for at the same instant, where the taking is fast but the paying is slow. That shape has a fixed recipe, and you now know all four steps: split the thing from the thing-at-a-time, take it with one atomic compare-and-set, hold it with an owner and a deadline, and make the confirmation idempotent because the slow step retries.

Concert, train and flight seats — the same problem with a different vocabulary. A train seat is Seat × Journey-leg, which is the same materialisation trick with an extra dimension.
Restaurant tables and doctors' appointments — a slot is Resource × TimeWindow. Once you see that, the “is table 6 free?” question stops being ambiguous, the same way “is C8 free?” did.
Flash sales and limited-stock checkout — hold the stock unit while the customer pays, release it on abandonment. The only difference is that stock is fungible, so a lost CAS can retry against a different unit instead of failing.
Domain names, usernames, phone-number ports — the pure case: one atomic claim, no expiry, and whoever loses is told instantly.
Parking spots, meeting rooms, library copies — you have already met these as Parking Lot, Meeting room scheduler and Library Management. Read them again with ShowSeat in mind and the resemblance is uncomfortable.

The 25-second version to say out loud

“The bookable unit is a ShowSeat — one per Seat per Show — because a chair is free at 6 and taken at 9, so status cannot live on the chair. Taking one is an atomic compare-and-set from AVAILABLE to HELD on that single seat, so the loser is told in the same call and the other 39 seats keep selling. The hold carries a holder and an expiry, so an abandoned checkout heals itself. Payment sits between hold and confirm, outside any lock, and confirm is idempotent on the payment reference so a retried webhook cannot double-book or double-charge. Multi-seat selection sorts by seat id and rolls back on the first refusal.”

Where this design stops working

When it is more than one process. In-memory synchronized protects one JVM. Ten booking servers need the atomicity to live where the state lives — a conditional UPDATE … WHERE status = 'AVAILABLE' with a rows-affected check, or a Redis SET NX PX. The lifecycle survives; the mechanism moves.
When the hold must survive a restart. An in-memory expiresAt dies with the process, and every held seat comes back either stuck or free depending on which way you initialise. Persist the hold, and the sweeper becomes a job rather than a thread.
When 200,000 people hit one show at 10:00 AM. A single hot row is a single hot row, wherever it lives. That is when you add a queue in front of the show — a virtual waiting room — and admit users in batches. The seat logic does not change; the admission does.
When seats stop being independent. Reserved wheelchair bays, sofa seats sold in pairs, or “no single seat left behind” policies make the units interact, and a per-seat CAS can no longer express the rule. At that point the atomic unit becomes the group, not the seat.
When money must be exactly reconciled. Here charge is one call that throws or does not. Real payments settle asynchronously and can be reversed hours later, which turns the booking into a small saga with compensating actions — and the idempotency key becomes the most important field in the system, not just a nice touch.

If you only remember one thing

The question “is this seat free?” must have exactly one answer. The moment it has two — one for the 6 PM show and one for the 9 PM show — you are missing a class. Find it, put the status on it, and take it with a single atomic step.

What it gives you

Modelling ShowSeat separately from Seat makes “is C8 free?” answerable, lets two shows over the same hall be priced differently, and keeps the physical layout immutable for the life of the process.
A compare-and-set on one seat keeps the contended region to a few instructions, so 39 other seats in the same hall are still being sold in parallel while A5 is being fought over.
A hold with an owner and a deadline lets payment be slow and failable without ever holding a lock across a network call, and it heals abandoned checkouts with no human involved.
Sorting seats into a canonical order before acquiring makes deadlock between overlapping multi-seat requests structurally impossible rather than merely unlikely.
Idempotency keyed on a caller-supplied paymentRef makes retries free, which is what lets the gateway be at-least-once — the only delivery guarantee real payment providers offer.
Pricing behind a strategy plus integer paise means a new rule is a new class and no amount can ever drift by a fraction.

Common mistakes

Materialising every ShowSeat up front is a lot of rows — 500 seats × 30 shows × 200 screens is three million objects a day — which is fine for a database and wasteful in memory, so at scale you either shard by show or materialise lazily.
A hold TTL is a guess. Too short and a slow payer loses the seat they already paid for; too long and a popular show looks sold out while half its holds are dead. There is no correct value, only a tuned one.
Lazy expiry means the seat map can lie until somebody reads it, so counters like “12 seats left” need the sweeper to stay honest — two mechanisms for one rule.
Per-seat locking gives up any ability to reason about the show as a whole: “how many seats are free?” is now a scan, and it is never a consistent snapshot while people are clicking.
The all-or-nothing rollback is best-effort — between releasing seat one and seat two, another user can take seat one, which is correct but makes “undo my selection” non-atomic as a whole.
Everything here assumes a single process. The design survives the move to a cluster, but the actual atomicity has to be re-implemented in the datastore, and any team that skips that step ships the double-booking bug at exactly the moment it scales.

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

BookMyShow.java

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicInteger;

/* =============================================================== money ==== */
final class Money {
    private Money() {}
    /** Every amount in this file is an integer number of PAISE. Never a double. */
    static String fmt(long paise) {
        long abs = Math.abs(paise);
        return (paise < 0 ? "-" : "") + "Rs." + (abs / 100) + "." + String.format("%02d", abs % 100);
    }
}

enum SeatTier    { SILVER, GOLD, RECLINER }
enum SeatStatus  { AVAILABLE, HELD, BOOKED }
enum BookingStatus { PENDING, CONFIRMED, FAILED, CANCELLED }

/* ================================================== the physical world ==== */
record User(String id, String name) {
    @Override public String toString() { return name; }
}

/** Furniture bolted to the floor of a Screen. It NEVER carries a status. */
record Seat(String id, String row, int number, SeatTier tier) {
    String label() { return row + number; }
}

record Movie(String id, String title, int runtimeMins) {}

final class Screen {
    final String id, name;
    final List<Seat> seats;
    Screen(String id, String name, List<Seat> seats) {
        this.id = id; this.name = name; this.seats = List.copyOf(seats);
    }
    static Screen grid(String id, String name, String[] rows, int perRow, Map<String, SeatTier> tiers) {
        List<Seat> out = new ArrayList<>();
        for (String r : rows)
            for (int n = 1; n <= perRow; n++)
                out.add(new Seat(id + "-" + r + n, r, n, tiers.get(r)));
        return new Screen(id, name, out);
    }
}

final class Theatre {
    final String id, name, city;
    final List<Screen> screens;
    Theatre(String id, String name, String city, List<Screen> screens) {
        this.id = id; this.name = name; this.city = city; this.screens = List.copyOf(screens);
    }
}

/** Movie x Screen x start time. THIS is what a customer books against. */
record Show(String id, Movie movie, Screen screen, int startHour) {
    String when() { return String.format("%02d:00", startHour); }
}

/* ============================================================= pricing ==== */
interface PricingStrategy {
    /** Never returns a double. Money is a long of paise, always. */
    long priceInPaise(Show show, Seat seat);
}

final class FlatPricing implements PricingStrategy {
    private final long paise;
    FlatPricing(long paise) { this.paise = paise; }
    public long priceInPaise(Show show, Seat seat) { return paise; }
}

final class TierAndTimePricing implements PricingStrategy {
    public long priceInPaise(Show show, Seat seat) {
        long base = switch (seat.tier()) {
            case SILVER   -> 15000L;                 // Rs.150.00
            case GOLD     -> 25000L;                 // Rs.250.00
            case RECLINER -> 45000L;                 // Rs.450.00
        };
        int pct = show.startHour() >= 21 ? 150       // late night
                : show.startHour() >= 18 ? 130       // prime evening
                : show.startHour() >= 12 ? 110       // afternoon
                : 90;                                // morning
        return base * pct / 100;                     // integer maths - never drifts
    }
}

/* ==================================================== THE BOOKABLE UNIT === */
/**
 * One Seat, at ONE Show. Two shows over the same 40 chairs produce two
 * independent sets of 40 ShowSeats. Status, holder, expiry and price all
 * live here - and every mutation is atomic on THIS object, nothing wider.
 */
final class ShowSeat {
    final String id;                 // "SH-6PM:C8" - also the canonical sort key
    final String showId;
    final Seat seat;
    final long pricePaise;

    private SeatStatus status = SeatStatus.AVAILABLE;
    private String heldBy;
    private long holdExpires;
    private String bookingId;

    ShowSeat(String showId, Seat seat, long pricePaise) {
        this.id = showId + ":" + seat.label();
        this.showId = showId; this.seat = seat; this.pricePaise = pricePaise;
    }

    /** Lazy expiry. MUST be called from inside the monitor, never before it. */
    private void expireIfDue(long now) {
        if (status == SeatStatus.HELD && now >= holdExpires) {
            status = SeatStatus.AVAILABLE; heldBy = null; holdExpires = 0L;
        }
    }

    synchronized SeatStatus statusAt(long now) { expireIfDue(now); return status; }
    synchronized String     holderAt(long now) { expireIfDue(now); return heldBy; }
    synchronized String     bookingRef()       { return bookingId; }

    /** THE compare-and-set. One caller wins; every other caller gets false, now. */
    synchronized boolean tryHold(String userId, long now, long ttlMillis) {
        expireIfDue(now);
        if (status == SeatStatus.AVAILABLE) {                 // COMPARE
            status = SeatStatus.HELD;                         // ...and SET
            heldBy = userId;
            holdExpires = now + ttlMillis;
            return true;
        }
        if (status == SeatStatus.HELD && userId.equals(heldBy)) {
            holdExpires = now + ttlMillis;                    // my own hold: extend
            return true;
        }
        return false;
    }

    synchronized boolean release(String userId, long now) {
        expireIfDue(now);
        if (status == SeatStatus.HELD && userId.equals(heldBy)) {
            status = SeatStatus.AVAILABLE; heldBy = null; holdExpires = 0L;
            return true;
        }
        return false;
    }

    /** HELD(by me) -> BOOKED. Replaying the same bookingId is a no-op that succeeds. */
    synchronized boolean confirm(String userId, String newBookingId, long now) {
        if (status == SeatStatus.BOOKED && newBookingId.equals(bookingId)) return true;
        expireIfDue(now);
        if (status != SeatStatus.HELD || !userId.equals(heldBy)) return false;
        status = SeatStatus.BOOKED; bookingId = newBookingId;
        heldBy = null; holdExpires = 0L;
        return true;
    }

    synchronized boolean cancel(String ref) {
        if (status == SeatStatus.BOOKED && ref.equals(bookingId)) {
            status = SeatStatus.AVAILABLE; bookingId = null; return true;
        }
        return false;
    }

    /** Used by the sweeper. Returns true only if THIS call freed the seat. */
    synchronized boolean sweep(long now) {
        boolean wasHeld = status == SeatStatus.HELD;
        expireIfDue(now);
        return wasHeld && status == SeatStatus.AVAILABLE;
    }
}

/* =========================================== one Show's worth of seats ==== */
final class ShowInventory {
    final Show show;
    private final Map<String, ShowSeat> byLabel = new LinkedHashMap<>();

    private ShowInventory(Show show) { this.show = show; }

    /** THE modelling step: one ShowSeat per Seat, priced once, at creation. */
    static ShowInventory materialise(Show show, PricingStrategy pricing) {
        ShowInventory inv = new ShowInventory(show);
        for (Seat s : show.screen().seats)
            inv.byLabel.put(s.label(), new ShowSeat(show.id(), s, pricing.priceInPaise(show, s)));
        return inv;
    }

    ShowSeat seat(String label) {
        ShowSeat s = byLabel.get(label);
        if (s == null) throw new NoSuchElementException("no seat " + label + " in " + show.id());
        return s;
    }
    Collection<ShowSeat> all() { return byLabel.values(); }

    Map<SeatStatus, Integer> census(long now) {
        Map<SeatStatus, Integer> m = new EnumMap<>(SeatStatus.class);
        for (SeatStatus st : SeatStatus.values()) m.put(st, 0);
        for (ShowSeat s : byLabel.values()) m.merge(s.statusAt(now), 1, Integer::sum);
        return m;
    }
}

/* ================================================ all-or-nothing holds ==== */
final class SeatLockManager {
    private final long ttlMillis;
    SeatLockManager(long ttlMillis) { this.ttlMillis = ttlMillis; }

    record HoldResult(boolean ok, List<ShowSeat> held, String blockedBy) {}

    HoldResult holdAll(List<ShowSeat> requested, String userId, long now) {
        List<ShowSeat> ordered = new ArrayList<>(requested);
        ordered.sort(Comparator.comparing((ShowSeat s) -> s.id));   // canonical order -> no deadlock
        List<ShowSeat> taken = new ArrayList<>();
        for (ShowSeat s : ordered) {
            if (s.tryHold(userId, now, ttlMillis)) { taken.add(s); continue; }
            for (int i = taken.size() - 1; i >= 0; i--)             // ROLLBACK, in reverse
                taken.get(i).release(userId, now);
            return new HoldResult(false, List.of(), s.seat.label());
        }
        return new HoldResult(true, List.copyOf(taken), null);
    }

    void releaseAll(List<ShowSeat> seats, String userId, long now) {
        for (ShowSeat s : seats) s.release(userId, now);
    }

    int sweepExpired(Collection<ShowSeat> seats, long now) {
        int freed = 0;
        for (ShowSeat s : seats) if (s.sweep(now)) freed++;
        return freed;
    }
}

/* ============================================================ payments ==== */
interface PaymentGateway {
    /** Slow, external, and allowed to throw. Called with NO seat lock held. */
    void charge(String bookingId, long amountPaise);
}

final class FakeGateway implements PaymentGateway {
    boolean declineNext = false;
    final AtomicInteger charges = new AtomicInteger();
    public void charge(String bookingId, long amountPaise) {
        if (declineNext) { declineNext = false; throw new IllegalStateException("card declined"); }
        charges.incrementAndGet();
    }
}

/* ============================================================= booking ==== */
final class Booking {
    final String id, userId, showId;
    final List<String> seatLabels;
    final long amountPaise;
    BookingStatus status = BookingStatus.PENDING;
    String paymentRef;

    Booking(String id, String userId, String showId, List<String> seatLabels, long amountPaise) {
        this.id = id; this.userId = userId; this.showId = showId;
        this.seatLabels = List.copyOf(seatLabels); this.amountPaise = amountPaise;
    }
    @Override public String toString() {
        return id + " " + status + " " + seatLabels + " " + Money.fmt(amountPaise);
    }
}

final class BookingService {
    static final int MAX_SEATS_PER_BOOKING = 10;

    private final Map<String, ShowInventory> shows   = new LinkedHashMap<>();
    private final Map<String, Booking> bookings      = new ConcurrentHashMap<>();
    private final Map<String, String> byPaymentRef   = new ConcurrentHashMap<>();  // idempotency index
    private final SeatLockManager locks;
    private final PaymentGateway gateway;
    private final AtomicInteger seq = new AtomicInteger(1040);

    BookingService(SeatLockManager locks, PaymentGateway gateway) {
        this.locks = locks; this.gateway = gateway;
    }

    // NOTE: there is deliberately no lock on this class. The only contended
    // thing in the system is a ShowSeat, and a ShowSeat guards itself.

    void addShow(ShowInventory inv) { shows.put(inv.show.id(), inv); }
    ShowInventory show(String id) { return shows.get(id); }

    /** Hold every requested seat or none of them. Returns a PENDING Booking. */
    Booking selectSeats(String showId, List<String> labels, User user, long now) {
        if (labels.isEmpty() || labels.size() > MAX_SEATS_PER_BOOKING)
            throw new IllegalArgumentException("1.." + MAX_SEATS_PER_BOOKING + " seats per booking");
        ShowInventory inv = shows.get(showId);
        List<ShowSeat> want = new ArrayList<>();
        for (String l : labels) want.add(inv.seat(l));

        SeatLockManager.HoldResult r = locks.holdAll(want, user.id(), now);
        if (!r.ok())
            throw new IllegalStateException(
                "seat " + r.blockedBy() + " was just taken - nothing was held");

        long total = 0;
        for (ShowSeat s : r.held()) total += s.pricePaise;
        Booking b = new Booking("BK-" + seq.incrementAndGet(), user.id(), showId, labels, total);
        bookings.put(b.id, b);
        return b;
    }

    /**
     * Idempotent on paymentRef: a retried gateway webhook must not charge or
     * book twice. Order matters - the replay check comes before everything.
     */
    Booking confirm(String bookingId, String paymentRef, long now) {
        String seen = byPaymentRef.get(paymentRef);                 // 1. replay?
        if (seen != null) return bookings.get(seen);

        Booking b = bookings.get(bookingId);
        if (b == null) throw new NoSuchElementException(bookingId);
        if (b.status == BookingStatus.CONFIRMED) return b;

        ShowInventory inv = shows.get(b.showId);
        List<ShowSeat> seats = new ArrayList<>();
        for (String l : b.seatLabels) seats.add(inv.seat(l));

        for (ShowSeat s : seats)                                    // 2. still mine?
            if (s.statusAt(now) != SeatStatus.HELD || !b.userId.equals(s.holderAt(now))) {
                locks.releaseAll(seats, b.userId, now);
                b.status = BookingStatus.FAILED;
                throw new IllegalStateException(
                    "hold expired on " + s.seat.label() + " - nothing was charged");
            }

        try {
            gateway.charge(b.id, b.amountPaise);                    // 3. slow hop, no lock held
        } catch (RuntimeException e) {
            locks.releaseAll(seats, b.userId, now);                 // failure branch
            b.status = BookingStatus.FAILED;
            throw e;
        }

        for (ShowSeat s : seats) s.confirm(b.userId, b.id, now);    // 4. HELD -> BOOKED
        b.status = BookingStatus.CONFIRMED;
        b.paymentRef = paymentRef;
        byPaymentRef.putIfAbsent(paymentRef, b.id);                 // 5. remember the key
        return b;
    }

    void abandon(String bookingId, long now) {
        Booking b = bookings.get(bookingId);
        if (b == null || b.status != BookingStatus.PENDING) return;
        ShowInventory inv = shows.get(b.showId);
        for (String l : b.seatLabels) inv.seat(l).release(b.userId, now);
        b.status = BookingStatus.FAILED;
    }

    /** Cancellation inside the refund window. Returns the refund, in paise. */
    long cancel(String bookingId, long minutesBeforeShow) {
        Booking b = bookings.get(bookingId);
        if (b == null || b.status != BookingStatus.CONFIRMED) return 0L;
        ShowInventory inv = shows.get(b.showId);
        for (String l : b.seatLabels) inv.seat(l).cancel(b.id);
        b.status = BookingStatus.CANCELLED;
        if (minutesBeforeShow >= 120) return b.amountPaise;         // full
        if (minutesBeforeShow >= 20)  return b.amountPaise / 2;     // half
        return 0L;                                                  // too late
    }

    int sweep(String showId, long now) { return locks.sweepExpired(shows.get(showId).all(), now); }
}

/* ================================================================ demo ==== */
public class BookMyShow {
    static final long MIN = 60_000L;
    static void say(String s) { System.out.println(s); }

    public static void main(String[] args) throws Exception {
        Map<String, SeatTier> tiers = new HashMap<>();
        tiers.put("A", SeatTier.SILVER);   tiers.put("B", SeatTier.SILVER);
        tiers.put("C", SeatTier.GOLD);     tiers.put("D", SeatTier.GOLD);
        tiers.put("E", SeatTier.RECLINER);

        Screen screen2 = Screen.grid("SCR-2", "Screen 2",
                new String[]{"A", "B", "C", "D", "E"}, 8, tiers);
        Theatre pvr = new Theatre("TH-1", "Forum Multiplex", "Bengaluru", List.of(screen2));
        Movie dune  = new Movie("MV-1", "Dune", 155);

        // TWO shows over the SAME screen and the SAME 40 chairs
        PricingStrategy pricing = new TierAndTimePricing();
        Show at6 = new Show("SH-6PM", dune, screen2, 18);
        Show at9 = new Show("SH-9PM", dune, screen2, 21);
        ShowInventory inv6 = ShowInventory.materialise(at6, pricing);
        ShowInventory inv9 = ShowInventory.materialise(at9, pricing);

        FakeGateway gateway = new FakeGateway();
        BookingService svc = new BookingService(new SeatLockManager(7 * MIN), gateway);
        svc.addShow(inv6);
        svc.addShow(inv9);

        User aditi = new User("U1", "Aditi");
        User rohan = new User("U2", "Rohan");
        long t = 0L;                                   // the clock is a PARAMETER

        say("=== 1. the same chair, two shows ==============================");
        Booking b1 = svc.selectSeats("SH-6PM", List.of("C6", "C7", "C8"), aditi, t);
        say("selectSeats(6PM, [C6,C7,C8], Aditi) -> " + b1);
        say("confirm -> " + svc.confirm(b1.id, "PAY-77", t));
        say("  C8 @ 6PM : " + inv6.seat("C8").statusAt(t) + "  " + Money.fmt(inv6.seat("C8").pricePaise));
        say("  C8 @ 9PM : " + inv9.seat("C8").statusAt(t) + "  " + Money.fmt(inv9.seat("C8").pricePaise));
        say("  ^ a boolean on Seat cannot print those two lines");

        say("");
        say("=== 2. one hundred people, one seat ===========================");
        ShowSeat e1 = inv6.seat("E1");
        int racers = 100;
        CountDownLatch start = new CountDownLatch(1), done = new CountDownLatch(racers);
        AtomicInteger winners = new AtomicInteger();
        for (int i = 0; i < racers; i++) {
            final String uid = "racer-" + i;
            new Thread(() -> {
                try { start.await(); } catch (InterruptedException ignored) { }
                if (e1.tryHold(uid, 0L, 7 * MIN)) winners.incrementAndGet();
                done.countDown();
            }).start();
        }
        start.countDown();
        done.await();
        say("  tryHold(E1) x100 -> winners = " + winners.get() + "   (must be exactly 1)");
        say("  E1 is " + e1.statusAt(t) + " by " + e1.holderAt(t));

        say("");
        say("=== 3. three seats or none ====================================");
        inv6.seat("D3").tryHold(rohan.id(), t, 7 * MIN);        // Rohan got there first
        try {
            svc.selectSeats("SH-6PM", List.of("D1", "D2", "D3"), aditi, t);
        } catch (IllegalStateException e) {
            say("  " + e.getMessage());
        }
        say("  D1 = " + inv6.seat("D1").statusAt(t) + " · D2 = " + inv6.seat("D2").statusAt(t)
            + "   <- rolled back, not left half-held");

        say("");
        say("=== 4. the hold expires =======================================");
        svc.selectSeats("SH-6PM", List.of("B1", "B2"), rohan, t);
        say("  t+0m  B1 = " + inv6.seat("B1").statusAt(t));
        long later = t + 8 * MIN;
        say("  t+8m  B1 = " + inv6.seat("B1").statusAt(later) + "   <- lazy expiry, on read");
        say("  sweeper freed " + svc.sweep("SH-6PM", later) + " more seat(s)");

        say("");
        say("=== 5. the payment fails ======================================");
        Booking b2 = svc.selectSeats("SH-6PM", List.of("A1", "A2"), aditi, later);
        gateway.declineNext = true;
        try { svc.confirm(b2.id, "PAY-88", later); }
        catch (RuntimeException e) { say("  charge failed: " + e.getMessage()); }
        say("  A1 = " + inv6.seat("A1").statusAt(later) + " · A2 = " + inv6.seat("A2").statusAt(later)
            + "   <- back in the pool immediately");

        say("");
        say("=== 6. the webhook fires twice ================================");
        Booking b3 = svc.selectSeats("SH-6PM", List.of("E5"), aditi, later);
        Booking first  = svc.confirm(b3.id, "PAY-99", later);
        Booking second = svc.confirm(b3.id, "PAY-99", later);    // duplicate delivery
        say("  first  -> " + first);
        say("  second -> " + second);
        say("  same booking object? " + (first == second)
            + "   successful charges = " + gateway.charges.get());

        say("");
        say("=== 7. swap the pricing rule ==================================");
        ShowInventory flat6 = ShowInventory.materialise(at6, new FlatPricing(20000L));
        say("  tier x time : C8@6PM " + Money.fmt(inv6.seat("C8").pricePaise)
            + " · C8@9PM " + Money.fmt(inv9.seat("C8").pricePaise)
            + " · E1@6PM " + Money.fmt(inv6.seat("E1").pricePaise));
        say("  flat        : C8@6PM " + Money.fmt(flat6.seat("C8").pricePaise)
            + " · E1@6PM " + Money.fmt(flat6.seat("E1").pricePaise));
        say("  0 lines of BookingService changed.");

        say("");
        say("=== 8. census =================================================");
        Map<SeatStatus, Integer> c = inv6.census(later);
        int sum = c.get(SeatStatus.AVAILABLE) + c.get(SeatStatus.HELD) + c.get(SeatStatus.BOOKED);
        say("  6PM " + c + "  total = " + sum + " (screen has " + screen2.seats.size() + " chairs)");
        say("  9PM " + inv9.census(later) + "  <- untouched by anything above");
    }
}

References & further reading

8 sources

Knowledge check

Did it land?

Quick questions, answers revealed on submit. Sign in to save your best score.

question 01 / 08

Why is `boolean isBooked` on `Seat` the wrong model?

question 02 / 08

Two users click seat A5 in the same millisecond. What is the correct guard?

question 03 / 08

Why must a seat hold have an expiry?

question 04 / 08

Your `tryHold` checks whether an existing hold has expired, and then takes the seat. Where must that expiry check happen?

question 05 / 08

A user asks for [C6, C4, C5] and another asks for [C5, C4] at the same moment. Why sort the seats before acquiring them?

question 06 / 08

The payment gateway's webhook is delivered twice with the same `paymentRef`. What makes `confirm` safe?

question 07 / 08

In `confirm`, the payment succeeds but one of the three seats is no longer held by this user. What is the right behaviour?

question 08 / 08

The interviewer says: “now run this on ten servers.” What actually changes?

0/8 answered