Notes
Requirements
Start with scope. Users list the shows for a movie, open the seat map and pick one or more seats. Those seats are held while the user pays. A successful payment confirms a booking. A failed payment, or a user who walks away, must release the seats. Prices depend on the seat type and the day. Many users book at once. Say that refunds, snacks and coupons are out of scope so the interviewer can pull them back in if they care.
Ask the questions that change the code. How long do we hold seats? Ten minutes. If a user asks for four seats and one is gone, do we give them three? No, all or nothing, because families sit together. Is there a limit per booking? Ten seats. Each answer turns into a rule in one class, which is exactly what the interviewer is listening for.
- list shows for a movie
- show the seat map with states
- pick one or more seats
- hold them while the user pays
- pay, then confirm a booking
- release seats if payment fails
- release seats if time runs out
- price by seat type and day
- many users at once
- out of scope: refunds, snacks
- how long is a hold?
- ten minutes
- partial seats if one is gone?
- no: all or nothing
- max seats per booking?
- ten
- one city or many?
- many, but one show at a time
- cancel after paying?
- out of scope for now
Entities
Underline the nouns. A movie plays as a show, at a time, on a screen, and a screen is a fixed layout of seats with a type: regular, premium or recliner. All of this is static data that rarely changes, so every one of them is an immutable Java record. Theatres and cities are just groupings above the screen; keep them out until a requirement needs them.
Now the part that changes. Seat G5 can be free for the three o'clock show and sold for the seven o'clock show, so seat state cannot live on the seat. It lives in a ShowInventory, one per show, with three maps: which hold owns each held seat, the holds themselves, and which booking owns each sold seat. Free simply means a seat is in neither map.
enum SeatType { REGULAR, PREMIUM,
RECLINER }
record Seat(String id, SeatType type)
record Screen(String id, List<Seat> s)
record Movie(String id, String title,
int minutes)
record Show(String id, Movie movie,
Screen screen, Instant start) - the same seat is free at 3 pm
- and sold at 7 pm
- so state lives per show, not
- on the Seat record
- ShowInventory:
- heldBy: seatId -> holdId
- holds: holdId -> Hold
- booked: seatId -> bookingId
Seat lifecycle
Draw the seat lifecycle for one show. A free seat becomes held when a user picks it. A held seat becomes booked when payment succeeds, or free again when payment fails or the ten minutes run out. Booked stays booked. The hold itself is a small record: an id, the user, the seats and an expiry time. Making the hold a first class object is the key idea of the whole design.
- FREE
- -> HELD (user picks it)
- HELD
- -> BOOKED (payment succeeds)
- -> FREE (payment fails)
- -> FREE (ten minutes pass)
- BOOKED
- -> stays booked
- a Hold is a record with an expiry
Flow: hold seats
The hold flow. First drop any expired holds. Then check every requested seat; if any one is held or booked, throw and change nothing, so the user never ends up with half their seats. Only when all are free do we create the hold with an expiry ten minutes from now and mark each seat as held by it. Check everything, then write everything: that is how all or nothing stays simple.
synchronized Hold hold(...) {
expire(now);
for (id : seatIds)
if (booked or held) throw taken
Hold h = new Hold(id, user, seats,
now + 10 min);
for (seat : seats) heldBy.put(..)
return h;
} Concurrency
Now the real question. Asha and Ravi both tap seat G5 at the same instant. Without a lock, both check, both see it free, and both get it. One global lock fixes that but makes every show in every city wait in one line. The right grain is one lock per show: different shows never block each other, and a single show has a few hundred seats, so the time inside the lock is microseconds. Ravi gets a clear seat taken message.
Interviewers often ask why not lock each seat. You can, but watch for deadlock: user one locks A1 then waits for A2 while user two locks A2 and waits for A1. The fix is to always lock seats in sorted order. Another option is compare-and-set on each seat with a rollback if a later seat fails. Both work, but one lock per show is simpler and fast enough, so say that and move on.
- check-then-set without a lock:
- both see G5 free, both win
- one global lock: every show
- in every city waits in line
- one lock per show:
- shows never block each other
- a show has ~300 seats, so
- the critical section is tiny
- user 1 wants A1 then A2
- user 2 wants A2 then A1
- each holds one, waits forever
- fix: sort seat ids, lock in order
- or skip locks: compare-and-set
- each seat, roll back on failure
- per show is simpler and fast
- enough: say so, then move on
Strategy: pricing
Pricing is a business policy, so put it behind an interface with one method: the price of this seat for this show. Our default charges by seat type and adds twenty five percent from Friday to Sunday, so two premium seats on a Friday cost seven hundred and fifty. Demand-based surge pricing or a bank offer is another class, and the booking service never changes. Money is a whole number of paise, never a double.
interface PricingStrategy {
long priceCents(Show s, Seat seat);
}
WeekendPricing: base by seat type,
+25% Friday to Sunday
G4, G5 premium on a Friday:
2 x 300.00 x 1.25 = 750.00
surge, offers: new classes Flow: pay
The payment flow has one rule: never call the payment gateway while holding the show lock. A card payment can take seconds, and holding the lock that long would freeze the whole show. So we take the lock briefly to check the hold is alive, release it, charge the card, then take the lock again to confirm. If the card is declined we release the seats right away instead of making others wait ten minutes.
Hold h = inv.live(holdId) // lock
long amount = quote(h)
if (!payments.charge(user, amount)) {
inv.release(holdId) // lock
throw: payment declined
}
return inv.confirm(h, amount) // lock Expiry
How do held seats come back after ten minutes? You could run a timer per hold, but there is a simpler way: lazy expiry. Every time anyone touches the show, we first drop holds whose expiry has passed. A seat map request, a hold or a confirm all clean up as a side effect. For the seat map to look right with no traffic, a small background sweep every minute is enough.
private void expire(Instant now) {
holds.values().removeIf(h -> {
if (h.expires().isAfter(now))
return false;
free every seat of h;
return true;
});
}
called inside hold, live, confirm Edge cases
Here is the edge case that impresses interviewers. The user starts paying at nine minutes fifty eight seconds and the gateway answers after the hold has expired. Someone else may already hold those seats. Confirm must check the hold again and, if it is gone, fail and refund rather than double book. A common fix is to extend the hold by a minute when payment starts, so this almost never happens.
- user pays at minute 9:58
- gateway answers at 10:03
- confirm finds no hold
- never book seats that may now
- belong to someone else
- refund the payment instead
- (or extend holds on payment
- start by a minute)
- tell the user clearly
Concurrency
Walk through every shared field. Seat state for a show is guarded by that show's lock. The map from show id to inventory is a concurrent hash map, so finding a show never blocks. Payments run outside every lock. Hold ids are random, so a guessed id cannot steal someone's seats. Everything else is an immutable record. If you push live seat maps to clients, listeners go in a copy-on-write list.
- seat state: per-show lock
- inventories: ConcurrentHashMap
- keyed by show id
- payment: outside every lock
- hold ids: random UUIDs
- records: immutable, share freely
- expiry: inside the lock
- listeners for seat-map pushes:
- CopyOnWriteArrayList
Extensibility
Now the follow-up changes. Many theatres and cities? Add Theatre and City objects that group screens. Coupons? A pricing decorator. Cancellation? A new booking state and the seats go back to free. Live seat maps? Observers on each show inventory. And at real scale, inventories are sharded by show id across servers, with the database enforcing that a seat for a show is sold once.
- many theatres: a Theatre groups
- screens, a City groups theatres
- coupons: a pricing decorator
- cancel and refund: BOOKED ->
- CANCELLED, seat back to free
- waitlist: notify on release
- live seat map: observers on
- each ShowInventory
- scale out: shard inventories
- by show id across servers
Testing
The full code is below the player. The demo holds two premium seats on a Friday and checks the price, shows that a second user cannot take one of them, declines a card and checks the seat is free again, moves an injected clock forward eleven minutes to expire a hold, and finally starts twenty threads that race for the same two seats. Exactly one booking wins, every run.
asha holds G4 G5, quote 750.00 ravi: G5 is taken (nothing held) asha booked [G4, G5], paid 750.00 meera: payment declined, H1 free After 11 minutes free seats: 78 ravi pays late: hold expired Race for E5 E6: 1 winner of 20
Say it like this
Here is the short version to say out loud. Movies, shows, screens and seats are immutable records. Seat state lives in one show inventory per show, guarded by its own lock. Seats are held all or nothing for ten minutes and expire lazily. Payment runs outside the lock, and we check the hold again before confirming, so no seat is ever sold twice.
- "Shows, screens and seats are
- records. Seat state lives in
- one ShowInventory per show,
- guarded by its own lock. Seats
- are held all or nothing for
- ten minutes and expire lazily.
- Payment runs outside the lock,
- then we confirm the hold again."