17. Movie Ticket Booking System Advanced (Concurrency Showcase)

Jump to section:

A. Realistic Interview Prompt

"Design a movie ticket booking system like BookMyShow. Users can browse shows, select seats, hold them briefly while paying, and confirm a booking. Thousands of users may try to book seats for a popular show at the same time."

B. Difficulty

Advanced — the concurrency showcase of this document's second half. The entity model is not the hard part; the hard part is that every popular-show demo scenario is a high-contention multi-seat race, and the interview is really evaluating whether the candidate's locking design survives that contention without deadlocking, double-booking, or leaving seats stuck in limbo.

C. What This Problem Tests

Splitting the physical Seat from its per-show status (ShowSeat) — the same "shared static thing vs. per-instance changing state" split as Library's Book/BookItem and Hotel's Room/RoomInventory, now at genuinely high contention
State machine for a seat's per-show lifecycle (available → locked → booked, with expiry back to available)
TTL-based soft locking during payment, converted to a hard commit only on payment success
Multi-seat atomicity: booking several seats together must be all-or-nothing and deadlock-free
Idempotent payment confirmation under retries

D. Requirements

Functional

Browse shows for a movie by city/theater/time
View a show's seat map with real-time availability
Select one or more seats and hold them temporarily while completing payment
Confirm a booking on successful payment; release the hold on failure or timeout
Price seats by category (Silver/Gold/Premium) and show (peak/off-peak)

Non-Functional

Two users must never both successfully book the same seat for the same show
A user who abandons checkout must not permanently lock a seat — the hold must expire
Booking multiple seats together must not deadlock against another user doing the same for an overlapping seat set

E. Clarifying Questions

#	Question	Why It Matters	Design Decision Affected
1	How long should a seat hold last before it expires and releases automatically?	Sets the TTL for the soft lock and whether a background sweep or lazy expiry check is needed	Design of `SeatLock` and its expiry mechanism
2	Can a user select and hold multiple seats in one transaction?	Introduces the multi-resource deadlock question, not just single-seat contention	Locking order strategy in the booking flow
3	Is payment synchronous (blocking) or asynchronous (webhook-confirmed later)?	Determines whether the hard lock commits inline or on a later, possibly-retried callback	Whether payment confirmation needs an idempotency key
4	Should users be waitlisted for a sold-out show and notified on a cancellation?	Adds an Observer-driven notification path on top of the core booking flow	Presence and design of a waitlist Observer

F. Assumptions

Confirmed: show browsing, seat-map viewing, temporary seat hold, payment-gated confirmation, category/show-based pricing.
Assumption: holds expire after a fixed TTL (e.g. 5–10 minutes) unless stated otherwise.
Assumption: payment confirmation arrives via a callback/webhook that may be retried by the payment provider, so it must be handled idempotently.

G. Actors

Actor	Responsibility
User	Browses shows, selects seats, pays, confirms booking
Payment Gateway	External system that authorizes payment and calls back with the result
BookingService (facade)	Top-level API coordinating seat selection, holds, and confirmation

H. Core Domain Entities

Class	Responsibility	Key Attributes	Key Methods	Does NOT Handle
`Seat`	One physical seat's static attributes in a screen	seatNumber, category	—	Any per-show status — delegates to `ShowSeat`
`Show`	One scheduled screening of a movie in a screen	movie, screen, startTime	—	Individual seat status directly
`ShowSeat`	One seat's status for one specific show, and the State-machine owner	seat, show, status	`lock()`, `confirm()`, `release()`	Payment processing or pricing math
`ShowSeatState` (interface)	One lifecycle state's allowed transitions	—	`onLock()`, `onConfirm()`, `onExpire()`	—
`SeatLock`	A TTL-bound soft hold on a set of `ShowSeat`s for one user	seats, userId, expiresAt	`isExpired()`	—
`Booking`	One booking attempt spanning hold → payment → confirmation	user, show, seats, status, totalPrice	`confirm()`, `cancel()`	Seat-level status directly — delegates to each `ShowSeat`
`PricingStrategy` (interface)	One price-calculation rule	—	`calculatePrice(seat, show)`	—
`WaitlistNotifier`	Observer subject notifying waitlisted users when a seat frees up	—	`notifyWaiting(showSeat)`	—
`BookingService` (facade)	Top-level orchestration	—	`holdSeats()`, `confirmBooking()`, `cancelBooking()`	—

I. Class Relationships

Seat vs. ShowSeat is the central modeling decision, once again: a seat's physical attributes (number, category) are static across every show that ever plays in that screen, while its booking status only makes sense relative to one specific show — the same seat is available for the 3pm show and booked for the 7pm show. This is the identical split-shape already seen in Library's Book/BookItem and Hotel's Room/RoomInventory, but the contention here is dramatically higher because a single popular show creates a genuine thundering-herd on a small set of good seats.
State machine for ShowSeat: AVAILABLE → LOCKED → BOOKED, with LOCKED → AVAILABLE on hold expiry or payment failure. Encoding this as a ShowSeatState hierarchy (rather than a raw enum checked with scattered if statements) keeps every transition's legality colocated with the state itself — a BOOKED seat simply has no onLock() transition to accept.
SeatLock as a TTL-bound soft hold, Booking confirmation as the hard commit: selecting seats doesn't book them — it soft-locks them for a bounded window so the seat isn't shown as available to other users while this user pays, but the lock self-expires if they abandon checkout. Only a successful payment converts the soft lock into a permanent BOOKED status. This two-phase shape is deliberately similar to a database's optimistic-lock-then-commit pattern, made explicit at the domain level.
Strategy for pricing, Observer for the waitlist: both are the same shapes already established in Hotel (Problem 16) and Library (Problem 15) respectively — pricing varies by seat category and show timing behind PricingStrategy, and waitlist notification on a cancellation reuses the same subject/observer relationship rather than a bespoke path.

J. Class Diagram

View Mermaid source

classDiagram
  class Seat {
    seatNumber
    category
  }
  class ShowSeat {
    status
    +lock()
    +confirm()
    +release()
  }
  class ShowSeatState {
    <<interface>>
    +onLock()
    +onConfirm()
    +onExpire()
  }
  class SeatLock {
    userId
    expiresAt
    +isExpired()
  }
  class Booking {
    status
    totalPrice
    +confirm()
    +cancel()
  }
  class PricingStrategy {
    <<interface>>
    +calculatePrice(seat, show)
  }
  class BookingService {
    +holdSeats()
    +confirmBooking()
    +cancelBooking()
  }
  Seat "1" --> "*" ShowSeat
  ShowSeat --> ShowSeatState
  ShowSeat --> SeatLock
  Booking --> "*" ShowSeat
  Booking --> PricingStrategy
  BookingService --> Booking

K. Responsibility Mapping

Class	Responsibility	Does NOT Handle
ShowSeat	Per-show status and legal state transitions	Payment, pricing math
SeatLock	TTL-bound soft hold and expiry check	Deciding what happens after expiry — that's Booking/BookingService
Booking	Coordinating a multi-seat hold-to-confirm lifecycle	Individual seat state transitions themselves
PricingStrategy implementations	One price formula	Booking commitment itself
BookingService	Top-level orchestration, locking order	State-transition legality, price math

L. SOLID Analysis

Principle	How It's Applied	Naive Violation
SRP	`ShowSeat` owns status; `SeatLock` owns TTL/expiry; `PricingStrategy` owns pricing; `Booking` owns multi-seat coordination	One `Booking` class directly flipping seat booleans, running a timer, and computing price inline
OCP	A new pricing rule is a new `PricingStrategy`; a new seat lifecycle state is a new `ShowSeatState` implementation	A giant `switch` on a status enum scattered across every method that touches seat state
LSP	Every `ShowSeatState` honestly rejects transitions it doesn't support (e.g. `BOOKED.onLock()` throws/rejects) rather than silently no-op-ing	A state that silently allows an illegal transition "just to be safe," masking a bug instead of surfacing it
ISP	`PricingStrategy` stays a single-method interface	A combined "SeatPolicy" interface mixing pricing with cancellation-fee rules
DIP	`Booking` depends on the `PricingStrategy` abstraction, not a hardcoded category-rate table	`Booking.calculateTotal()` embedding a rate table directly

M. Design Patterns

Pattern	Problem It Solves	Where It Appears	When NOT to Use
State	A seat's legal transitions genuinely depend on its current status, not just external checks	`ShowSeatState` (AVAILABLE/LOCKED/BOOKED)	Skip if the round only ever needs a boolean booked flag with no hold/expiry concept
Strategy	Price varies by seat category and show timing, and changes more often than the booking flow	`PricingStrategy`	Skip if every seat in a show is one flat price
Observer	Waitlist notification on cancellation shouldn't require the cancel path to know who's waiting	`WaitlistNotifier`	Skip if waitlisting is out of scope for the round

Explicitly avoided: a single boolean "booked" flag per seat shared across all shows — see I for why per-show status is the entire point of this problem.

N. What Is Likely to Change?

Behavior	Current Design	Anticipated Change	Protecting Abstraction
Pricing rules	Category-and-show-timing-based	Dynamic demand pricing, group discounts, promo codes	`PricingStrategy` interface
Hold TTL	Fixed window	Variable TTL by seat scarcity or user tier	`SeatLock`'s expiry field, no change to the state machine itself
Seat lifecycle	AVAILABLE/LOCKED/BOOKED	Add a CANCELLED-pending-refund state distinct from AVAILABLE	New `ShowSeatState` implementation, additive

O. Design Evolution

V1: one booked boolean per seat, no hold concept, one flat price, synchronous payment.
V2: split Seat from ShowSeat the moment a screen hosts more than one show — the "same seat, different show" case that a single boolean cannot represent.
V3: introduce the ShowSeatState machine and SeatLock TTL once "hold while paying" becomes a real requirement rather than instant booking.
V4: extract PricingStrategy once category/show-based pricing is requested.
V5: wire WaitlistNotifier once sold-out waitlisting is requested.

What stays stable: BookingService's public hold/confirm/cancel API. New states and pricing rules are additive.

P. API / Interface Design

interface PricingStrategy {
  Money calculatePrice(Seat seat, Show show);
}

class BookingService {
  SeatLock holdSeats(User user, Show show, List<SeatId> seatIds);
  Booking confirmBooking(String lockId, PaymentResult result);  // idempotency-keyed
  void cancelBooking(String bookingId);
}

interface PricingStrategy {
  Money calculatePrice(Seat seat, Show show);
}

class BookingService {
  SeatLock holdSeats(User user, Show show, List<SeatId> seatIds);
  Booking confirmBooking(String lockId, PaymentResult result);  // idempotency-keyed
  void cancelBooking(String bookingId);
}

class PricingStrategy {
public:
  virtual Money calculatePrice(std::shared_ptr<Seat> seat, std::shared_ptr<Show> show) = 0;
};

class BookingService {
public:
  std::shared_ptr<SeatLock> holdSeats(std::shared_ptr<User> user, std::shared_ptr<Show> show, const std::vector<SeatId>& seatIds);
  std::shared_ptr<Booking> confirmBooking(const std::string& lockId, PaymentResult result);  // idempotency-keyed
  void cancelBooking(const std::string& bookingId);
};

class PricingStrategy {
  calculatePrice(seat, show) { throw new Error('not implemented'); }
}

class BookingService {
  holdSeats(user, show, seatIds) {}
  confirmBooking(lockId, result) {}  // idempotency-keyed
  cancelBooking(bookingId) {}
}

interface PricingStrategy {
  calculatePrice(seat: Seat, show: Show): Money;
}

class BookingService {
  holdSeats(user: User, show: Show, seatIds: SeatId[]): SeatLock {}
  confirmBooking(lockId: string, result: PaymentResult): Booking {}  // idempotency-keyed
  cancelBooking(bookingId: string): void {}
}

Ownership/validation notes: holdSeats() acquires locks on every requested ShowSeat in one atomic step (all-or-nothing — see W for lock ordering), and confirmBooking() is keyed by an idempotency key derived from the payment provider's transaction id, so a retried webhook call cannot double-confirm or double-charge.

Q. Pseudocode — Critical Logic

BookingService.holdSeats(user, show, seatIds):
  orderedIds = sort(seatIds)          // canonical order — see W
  locks = []
  try:
    for id in orderedIds:
      lock(showSeatFor(id))
      locks.append(showSeatFor(id))
      if showSeatFor(id).status != AVAILABLE: rollback(locks); reject
    for seat in locks: seat.status = LOCKED
    seatLock = new SeatLock(user, locks, expiresAt = now + HOLD_TTL)
    return seatLock
  finally:
    for seat in locks: unlock(seat)

BookingService.confirmBooking(lockId, paymentResult, idempotencyKey):
  if alreadyProcessed(idempotencyKey): return existingBookingFor(idempotencyKey)  // idempotent retry
  seatLock = lockFor(lockId)
  if seatLock.isExpired(): reject
  if paymentResult.success:
    for seat in seatLock.seats: seat.status = BOOKED
    booking = new Booking(seatLock, CONFIRMED)
  else:
    for seat in seatLock.seats: seat.status = AVAILABLE
    waitlistNotifier.notifyWaiting(seatLock.seats)
  recordProcessed(idempotencyKey, booking)
  return booking

SeatLock holdSeats(User user, Show show, List<SeatId> seatIds) {
  List<SeatId> orderedIds = sort(seatIds);          // canonical order — see W
  List<ShowSeat> locks = new ArrayList<>();
  try {
    for (SeatId id : orderedIds) {
      lock(showSeatFor(id));
      locks.add(showSeatFor(id));
      if (showSeatFor(id).getStatus() != AVAILABLE) { rollback(locks); reject(); }
    }
    for (ShowSeat seat : locks) { seat.setStatus(LOCKED); }
    SeatLock seatLock = new SeatLock(user, locks, /* expiresAt = */ now().plus(HOLD_TTL));
    return seatLock;
  } finally {
    for (ShowSeat seat : locks) { unlock(seat); }
  }
}

Booking confirmBooking(String lockId, PaymentResult paymentResult, String idempotencyKey) {
  if (alreadyProcessed(idempotencyKey)) { return existingBookingFor(idempotencyKey); }  // idempotent retry
  SeatLock seatLock = lockFor(lockId);
  if (seatLock.isExpired()) { reject(); }
  Booking booking;
  if (paymentResult.isSuccess()) {
    for (ShowSeat seat : seatLock.getSeats()) { seat.setStatus(BOOKED); }
    booking = new Booking(seatLock, CONFIRMED);
  } else {
    for (ShowSeat seat : seatLock.getSeats()) { seat.setStatus(AVAILABLE); }
    waitlistNotifier.notifyWaiting(seatLock.getSeats());
  }
  recordProcessed(idempotencyKey, booking);
  return booking;
}

std::shared_ptr<SeatLock> BookingService::holdSeats(std::shared_ptr<User> user, std::shared_ptr<Show> show, const std::vector<SeatId>& seatIds) {
  auto orderedIds = sort(seatIds);          // canonical order — see W
  std::vector<std::shared_ptr<ShowSeat>> locks;
  try {
    for (auto& id : orderedIds) {
      lock(showSeatFor(id));
      locks.push_back(showSeatFor(id));
      if (showSeatFor(id)->status != AVAILABLE) { rollback(locks); reject(); }
    }
    for (auto& seat : locks) { seat->status = LOCKED; }
    auto seatLock = std::make_shared<SeatLock>(user, locks, /* expiresAt = */ now() + HOLD_TTL);
    for (auto& seat : locks) { unlock(seat); }
    return seatLock;
  } catch (...) {
    for (auto& seat : locks) { unlock(seat); }
    throw;
  }
}

std::shared_ptr<Booking> BookingService::confirmBooking(const std::string& lockId, PaymentResult paymentResult, const std::string& idempotencyKey) {
  if (alreadyProcessed(idempotencyKey)) { return existingBookingFor(idempotencyKey); }  // idempotent retry
  auto seatLock = lockFor(lockId);
  if (seatLock->isExpired()) { reject(); }
  std::shared_ptr<Booking> booking;
  if (paymentResult.success) {
    for (auto& seat : seatLock->seats) { seat->status = BOOKED; }
    booking = std::make_shared<Booking>(seatLock, CONFIRMED);
  } else {
    for (auto& seat : seatLock->seats) { seat->status = AVAILABLE; }
    waitlistNotifier->notifyWaiting(seatLock->seats);
  }
  recordProcessed(idempotencyKey, booking);
  return booking;
}

holdSeats(user, show, seatIds) {
  const orderedIds = sort(seatIds);          // canonical order — see W
  const locks = [];
  try {
    for (const id of orderedIds) {
      lock(showSeatFor(id));
      locks.push(showSeatFor(id));
      if (showSeatFor(id).status !== AVAILABLE) { rollback(locks); reject(); }
    }
    for (const seat of locks) { seat.status = LOCKED; }
    const seatLock = new SeatLock(user, locks, /* expiresAt = */ now() + HOLD_TTL);
    return seatLock;
  } finally {
    for (const seat of locks) { unlock(seat); }
  }
}

confirmBooking(lockId, paymentResult, idempotencyKey) {
  if (alreadyProcessed(idempotencyKey)) { return existingBookingFor(idempotencyKey); }  // idempotent retry
  const seatLock = lockFor(lockId);
  if (seatLock.isExpired()) { reject(); }
  let booking;
  if (paymentResult.success) {
    for (const seat of seatLock.seats) { seat.status = BOOKED; }
    booking = new Booking(seatLock, CONFIRMED);
  } else {
    for (const seat of seatLock.seats) { seat.status = AVAILABLE; }
    waitlistNotifier.notifyWaiting(seatLock.seats);
  }
  recordProcessed(idempotencyKey, booking);
  return booking;
}

holdSeats(user: User, show: Show, seatIds: SeatId[]): SeatLock {
  const orderedIds = sort(seatIds);          // canonical order — see W
  const locks: ShowSeat[] = [];
  try {
    for (const id of orderedIds) {
      lock(showSeatFor(id));
      locks.push(showSeatFor(id));
      if (showSeatFor(id).status !== AVAILABLE) { rollback(locks); reject(); }
    }
    for (const seat of locks) { seat.status = LOCKED; }
    const seatLock = new SeatLock(user, locks, /* expiresAt = */ now() + HOLD_TTL);
    return seatLock;
  } finally {
    for (const seat of locks) { unlock(seat); }
  }
}

confirmBooking(lockId: string, paymentResult: PaymentResult, idempotencyKey: string): Booking {
  if (alreadyProcessed(idempotencyKey)) { return existingBookingFor(idempotencyKey); }  // idempotent retry
  const seatLock = lockFor(lockId);
  if (seatLock.isExpired()) { reject(); }
  let booking: Booking;
  if (paymentResult.success) {
    for (const seat of seatLock.seats) { seat.status = BOOKED; }
    booking = new Booking(seatLock, CONFIRMED);
  } else {
    for (const seat of seatLock.seats) { seat.status = AVAILABLE; }
    waitlistNotifier.notifyWaiting(seatLock.seats);
  }
  recordProcessed(idempotencyKey, booking);
  return booking;
}

R. End-to-End Use Case

userA.holdSeats(show, [A4, A5]) → both locked atomically in sorted order → SeatLock (TTL 8 min)
  │
  ▼
userA pays within the window
  │  payment webhook fires → confirmBooking(lockId, success, idempotencyKey)
  │  A4, A5 → BOOKED; Booking CONFIRMED
  ▼
Same webhook retried by the payment provider due to a network blip
  │  idempotencyKey already processed → same Booking returned, no double-booking, no double-charge

S. Data Structures

Structure	Used For	Why	Alternative & Trade-off
Hash map of seatId → `ShowSeat` per show	O(1) seat status lookup during hold/confirm	Seat-map rendering and locking both need fast point lookups, not range queries	A 2D grid array also works if the seat map is genuinely rectangular
Sorted order of seat ids before locking	Deadlock-free multi-seat locking	Guarantees every concurrent booking attempt acquires shared seats in the same global order	Without this, two users booking overlapping seat sets in opposite orders can deadlock — see W
Idempotency-key store (processed payment confirmations)	Safe webhook retries	O(1) check for "have I already handled this exact confirmation"	A TTL-bounded cache is sufficient since providers don't retry indefinitely

T. Complexity Analysis

Operation	Time	Space
`holdSeats()` for k seats	O(k log k) for the sort + O(k) for the locks	O(k)
`confirmBooking()`	O(k) for k held seats + O(1) idempotency check	O(1)
Seat-map render for a show	O(seats in the screen)	O(seats in the screen)

U. Testing Strategy

Happy path: holding then confirming a set of seats transitions exactly those seats to BOOKED and no others.
Edge cases: a hold that expires before payment completes releases all its seats back to AVAILABLE and, if a waitlist exists, triggers notification.
Idempotency tests: calling confirmBooking() twice with the same idempotency key produces exactly one Booking and one charge, not two.
Concurrency tests: two users concurrently holding overlapping seat sets (e.g. user A wants A4-A5, user B wants A5-A6) result in exactly one success for the shared seat A5, and neither request deadlocks against the other.

V. Interviewer Follow-Ups

Follow-Up	Testing	Design Change	Classes Changed	Pattern/Trade-off
"What if two users try to lock overlapping seats in opposite order — A4-then-A5 vs. A5-then-A4?"	Whether lock acquisition order was ever left to caller discretion	Enforce sorted-id lock ordering inside `holdSeats()` itself, not left to the caller	BookingService only	This is the File System (Problem 9) canonical-ordering deadlock lesson, reapplied
"Scale to a flash-sale-level popular show — thousands of concurrent hold attempts on the same 200 seats."	Whether locking was assumed to be in-process rather than distributed	Move seat locks to a distributed lock service (e.g. Redis with TTL) so multiple app servers coordinate correctly	SeatLock's underlying implementation, not its interface	LLD→HLD boundary — see Y
"Add a waitlist for sold-out shows."	Whether cancellation was already decoupled from "who cares"	`WaitlistNotifier` subscribes to seat-release events	New Observer wiring only	Reuses the Library/Pub-Sub Observer shape

W. Concurrency

Shared mutable state: each ShowSeat's status for a popular show, under genuinely high simultaneous contention — this is the highest-contention scenario in the entire document.

The check-then-act race, at multi-resource scale: holding a single seat has the same check-then-lock-then-commit shape seen throughout this document (Parking Lot, Splitwise, ATM, Library, Hotel). What's new here is that a booking often spans multiple seats, which introduces a genuine deadlock risk: if user A locks A4 then tries to lock A5 while user B has already locked A5 and is trying to lock A4, both wait on each other forever.
Canonical lock ordering resolves it: sorting the requested seat ids before acquiring any locks, and always acquiring in that sorted order, guarantees every concurrent request converges on the same global lock order — this is exactly File System's (Problem 9) inter-process lock-ordering fix for the same deadlock shape, reapplied to seats instead of files.
TTL-based soft locks prevent indefinite holds: a SeatLock that never expired would let an abandoned checkout permanently starve a seat; the TTL guarantees eventual release even if the client disappears mid-payment.
Idempotent confirmation under retries: payment webhooks can and do get retried by the provider; keying confirmBooking() on an idempotency key prevents a retry from double-booking or double-charging — the same lesson Pub-Sub (Problem 10) established for message redelivery.

X. Persistence

Bookings and confirmed seat status must survive a restart without question — a booking that vanishes after payment is a trust-destroying failure. Seat holds are a middle ground: they could technically be rebuilt from a fast in-memory/distributed cache (with the TTL as the natural expiry), but the confirmed Booking record itself is always durable, repository-backed data.

Y. Scaling Boundary

Layer	What Belongs Here
LLD	Seat/ShowSeat model, state machine, canonical lock ordering, TTL holds, idempotent confirmation
HLD	Distributed locking across app servers (Redis/Zookeeper), flash-sale traffic shaping/queueing, multi-region show-inventory replication
Explicitly out of scope	Distributed-systems infrastructure detail unless the round explicitly pivots to HLD

Z. Failure Scenarios

Payment gateway times out with an unknown result: the seat must stay LOCKED (not auto-release, not auto-confirm) until an explicit success/failure callback or a manual reconciliation job resolves it — assuming either outcome is a correctness bug in one direction or the other.
The service crashes between locking seats and returning the SeatLock to the caller: a background sweep that releases any lock past its TTL guarantees seats don't stay stuck forever even if the in-flight request never got its response.

AA. Common Bad Designs

A single booked boolean per seat, shared across all shows — the defining mistake for this problem; see I.
Locking seats one at a time in whatever order the caller happened to request them — the deadlock trap; see W.
No TTL on a seat hold — an abandoned checkout permanently locks a seat no one else can ever book.
Treating payment confirmation as safe to process more than once — without an idempotency key, a retried webhook can double-book or double-charge.

AB. Design Trade-Offs

Decision	Option A	Option B	Recommendation
Lock scope for multi-seat holds	Lock seats individually in sorted order	Lock the entire show for the duration of any hold attempt	Sorted individual locks — locking the whole show serializes unrelated bookings on unrelated seats, destroying throughput for a popular show
Ambiguous payment result handling	Auto-release the seat after a short grace timeout	Keep the seat locked indefinitely pending manual reconciliation	A bounded grace timeout with a reconciliation job as backstop — indefinite locking on an ambiguous result is a worse failure mode than occasionally releasing a seat that later turns out to have been paid for (refundable) than double-selling one that wasn't (not always reversible)

AC. Interviewer Evaluation

Strong signal: splitting Seat/ShowSeat unprompted; proposing a TTL-bound hold before being asked how checkout abandonment is handled; independently identifying the multi-seat deadlock risk and fixing it with canonical lock ordering; flagging idempotency for payment confirmation without being prompted.

Red flag: one booked flag per seat; per-seat locking with no defined acquisition order; no hold expiry; treating payment confirmation as safe to run twice.

AD. Interview Simulation

Interviewer: Design a movie ticket booking system for a popular show with thousands of concurrent users.

Candidate: I'd split the physical Seat from ShowSeat, since booking status only makes sense relative to one specific show — the same seat is free for one showtime and booked for another. Each ShowSeat runs a small state machine: available, locked, booked.

Interviewer: What happens between selecting a seat and actually paying for it?

Candidate: Selecting seats acquires a TTL-bound SeatLock — a soft hold, not a booking. If payment succeeds within the window, the hold converts to a permanent BOOKED status; if it fails or the TTL expires, the seats revert to available automatically.

Interviewer: What if a user tries to book two seats, and another user is simultaneously trying to book an overlapping pair in the opposite order?

Candidate: That's a real deadlock risk if each request locks seats in whatever order the user clicked them. I'd sort the requested seat ids and always acquire locks in that canonical sorted order — the same fix I'd use for the file-lock-ordering problem — so every concurrent request converges on the same global order and none of them can circularly wait on each other.

Interviewer: The payment provider retries its confirmation webhook due to a network blip. What happens?

Candidate: confirmBooking() is keyed by an idempotency key derived from the payment transaction id. A retried call with the same key returns the already-created booking instead of creating a second one or charging twice.

AE. Online Solution Comparison

Source	Approach	Strength	Weakness	Worth Learning
GeeksforGeeks — Design BookMyShow	Requirements-and-entity walkthrough covering movies, shows, seats, and bookings	Clear breakdown of the browsing/search side of the problem (city → theater → show)	Seat locking is generally described at a conceptual level without a concrete deadlock-free multi-seat locking strategy or explicit idempotency handling for payment retries	Good for the browsing/search entity model; this document's canonical lock ordering and idempotent confirmation are the concurrency depth worth adding on top
AlgoMaster — Design BookMyShow	Structured walkthrough including a seat-locking discussion and class diagrams	Explicitly discusses temporary seat locking during checkout, which most treatments skip	Does not typically dive into the specific multi-seat deadlock scenario or a canonical-ordering fix — usually stops at single-seat locking	Strong starting point for the TTL-hold concept; this document extends it to the multi-seat deadlock case and payment-retry idempotency

AF. Interview Cheat Sheet

Problem	Movie Ticket Booking System (BookMyShow-style)
Difficulty	Advanced (concurrency showcase)
Core requirements	Show browsing, seat-map viewing, temporary hold, payment-gated confirmation, category/show-based pricing
Key clarifications	Hold TTL length? Multi-seat holds allowed? Synchronous or webhook-based payment? Waitlisting needed?
Core entities	Seat, Show, ShowSeat, ShowSeatState, SeatLock, Booking, PricingStrategy, WaitlistNotifier, BookingService
Key relationships	Seat/ShowSeat split; State machine for seat lifecycle; TTL soft lock → hard commit on payment; Strategy for pricing; Observer for waitlist
Key patterns	State, Strategy, Observer
Most important decision	Splitting per-show seat status from the physical seat, and locking multiple seats in canonical order
Likely-changing behavior	Pricing rules, hold TTL, additional seat lifecycle states
Concurrency concern	Multi-seat deadlock (fixed by canonical lock ordering) and idempotent payment confirmation under retries
Top follow-ups	Opposite-order concurrent multi-seat locks, flash-sale-scale distributed locking, waitlist notifications
Common mistakes	One booked flag per seat across all shows; unordered multi-seat locking; no hold TTL; non-idempotent payment confirmation
What NOT to over-engineer	Don't design the distributed-lock infrastructure itself unless the round explicitly pivots to HLD

AG. Full Implementation

A complete, compilable reference implementation of every class in the diagram above (composition, inheritance, interface realization, and dependency-injected strategies all preserved per section I), with a runnable demo exercising the primary flow — in Java, C++, JavaScript, and TypeScript.

import java.time.LocalDateTime;
import java.util.*;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

/**
 * Problem 17: Movie Ticket Booking System (Concurrency Showcase)
 *
 * Key design decisions faithfully reproduced from the class diagram:
 *  - Seat (static attrs) vs ShowSeat (per-show status) split.
 *  - ShowSeatState hierarchy encodes AVAILABLE -> LOCKED -> BOOKED legality, and LOCKED/BOOKED -> AVAILABLE on expire/release.
 *  - SeatLock is a TTL-bound soft hold; only a successful payment converts it into a Booking confirmation.
 *  - PricingStrategy is injected (Strategy); WaitlistNotifier is an Observer subject.
 *  - BookingService is the facade; holdSeats() locks seats in canonical (sorted) order to avoid deadlock
 *    against another user holding an overlapping seat set.
 */
public class p17 {

    enum SeatCategory { SILVER, GOLD, PREMIUM }
    enum ShowSeatStatus { AVAILABLE, LOCKED, BOOKED }
    enum BookingStatus { HOLD, CONFIRMED, CANCELLED }

    static final class User {
        final String id, name;
        User(String id, String name) { this.id = id; this.name = name; }
    }

    static final class PaymentResult {
        final boolean success;
        PaymentResult(boolean success) { this.success = success; }
    }

    // ---------- Seat / Show ----------

    static final class Seat {
        final String seatNumber;
        final SeatCategory category;
        Seat(String seatNumber, SeatCategory category) { this.seatNumber = seatNumber; this.category = category; }
    }

    static final class Movie {
        final String id, title;
        final int durationMinutes;
        Movie(String id, String title, int durationMinutes) { this.id = id; this.title = title; this.durationMinutes = durationMinutes; }
    }

    static 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 = seats; }
    }

    static final class Show {
        final String id;
        final Movie movie;
        final Screen screen;
        final LocalDateTime startTime;
        private final Map<String, ShowSeat> showSeats = new LinkedHashMap<>();

        Show(String id, Movie movie, Screen screen, LocalDateTime startTime) {
            this.id = id;
            this.movie = movie;
            this.screen = screen;
            this.startTime = startTime;
            // One ShowSeat per physical seat -- the same Seat is independently bookable per Show.
            for (Seat seat : screen.seats) showSeats.put(seat.seatNumber, new ShowSeat(seat, this));
        }

        ShowSeat getShowSeat(String seatNumber) {
            ShowSeat seat = showSeats.get(seatNumber);
            if (seat == null) throw new NoSuchElementException("No such seat: " + seatNumber);
            return seat;
        }
    }

    // ---------- ShowSeatState (State pattern) ----------

    interface ShowSeatState {
        void onLock(ShowSeat seat);
        void onConfirm(ShowSeat seat);
        void onExpire(ShowSeat seat);
    }

    static final class AvailableState implements ShowSeatState {
        static final AvailableState INSTANCE = new AvailableState();
        public void onLock(ShowSeat seat) { seat.setState(ShowSeatStatus.LOCKED, LockedState.INSTANCE); }
        public void onConfirm(ShowSeat seat) { throw new IllegalStateException("Cannot confirm a seat that was never locked"); }
        public void onExpire(ShowSeat seat) { /* already available; no-op */ }
    }

    static final class LockedState implements ShowSeatState {
        static final LockedState INSTANCE = new LockedState();
        public void onLock(ShowSeat seat) { throw new IllegalStateException("Seat already locked"); }
        public void onConfirm(ShowSeat seat) { seat.setState(ShowSeatStatus.BOOKED, BookedState.INSTANCE); }
        public void onExpire(ShowSeat seat) { seat.setState(ShowSeatStatus.AVAILABLE, AvailableState.INSTANCE); }
    }

    static final class BookedState implements ShowSeatState {
        static final BookedState INSTANCE = new BookedState();
        public void onLock(ShowSeat seat) { throw new IllegalStateException("Seat already booked"); }
        public void onConfirm(ShowSeat seat) { throw new IllegalStateException("Seat already booked"); }
        // Freeing a booked seat (e.g. booking cancellation) returns it to the pool.
        public void onExpire(ShowSeat seat) { seat.setState(ShowSeatStatus.AVAILABLE, AvailableState.INSTANCE); }
    }

    // ---------- ShowSeat ----------

    static final class ShowSeat {
        final Seat seat;
        final Show show;
        private volatile ShowSeatStatus status = ShowSeatStatus.AVAILABLE;
        private ShowSeatState state = AvailableState.INSTANCE;
        private final Lock lock = new ReentrantLock();

        ShowSeat(Seat seat, Show show) { this.seat = seat; this.show = show; }

        void setState(ShowSeatStatus status, ShowSeatState state) { this.status = status; this.state = state; }
        ShowSeatStatus getStatus() { return status; }

        /** Soft-lock this seat for a pending hold. Throws if not currently AVAILABLE. */
        void lock() {
            lock.lock();
            try { state.onLock(this); } finally { lock.unlock(); }
        }

        /** Hard-commit: LOCKED -> BOOKED. */
        void confirm() {
            lock.lock();
            try { state.onConfirm(this); } finally { lock.unlock(); }
        }

        /** Free the seat back to AVAILABLE -- used for hold expiry, payment failure, or booking cancellation. */
        void release() {
            lock.lock();
            try { state.onExpire(this); } finally { lock.unlock(); }
        }
    }

    // ---------- SeatLock ----------

    static final class SeatLock {
        final String id;
        final User user;
        final List<ShowSeat> seats;
        final long expiresAt; // epoch millis

        SeatLock(String id, User user, List<ShowSeat> seats, long expiresAt) {
            this.id = id; this.user = user; this.seats = seats; this.expiresAt = expiresAt;
        }

        boolean isExpired() { return System.currentTimeMillis() > expiresAt; }
    }

    // ---------- PricingStrategy ----------

    interface PricingStrategy {
        double calculatePrice(Seat seat, Show show);
    }

    static final class CategoryTimeBasedPricingStrategy implements PricingStrategy {
        private final Map<SeatCategory, Double> baseRates = Map.of(
                SeatCategory.SILVER, 100.0, SeatCategory.GOLD, 180.0, SeatCategory.PREMIUM, 280.0);

        public double calculatePrice(Seat seat, Show show) {
            double base = baseRates.get(seat.category);
            int hour = show.startTime.getHour();
            boolean peak = hour >= 18 && hour < 22; // evening peak window
            return peak ? base * 1.3 : base;
        }
    }

    // ---------- Booking ----------

    static final class Booking {
        final String id;
        final User user;
        final Show show;
        final List<ShowSeat> seats;
        BookingStatus status;
        final double totalPrice;

        Booking(String id, User user, Show show, List<ShowSeat> seats, PricingStrategy pricingStrategy) {
            this.id = id; this.user = user; this.show = show; this.seats = seats;
            this.status = BookingStatus.HOLD;
            double total = 0;
            for (ShowSeat s : seats) total += pricingStrategy.calculatePrice(s.seat, show);
            this.totalPrice = total;
        }

        void confirm() {
            for (ShowSeat s : seats) s.confirm();
            status = BookingStatus.CONFIRMED;
        }

        void cancel() {
            for (ShowSeat s : seats) s.release();
            status = BookingStatus.CANCELLED;
        }
    }

    // ---------- WaitlistNotifier (Observer) ----------

    interface WaitlistObserver {
        void onSeatAvailable(ShowSeat seat);
    }

    static final class WaitlistNotifier {
        private final List<WaitlistObserver> observers = new ArrayList<>();
        void subscribe(WaitlistObserver observer) { observers.add(observer); }
        void notifyWaiting(List<ShowSeat> freedSeats) {
            for (ShowSeat seat : freedSeats) for (WaitlistObserver o : observers) o.onSeatAvailable(seat);
        }
    }

    static final class ConsoleWaitlistNotifier implements WaitlistObserver {
        public void onSeatAvailable(ShowSeat seat) {
            System.out.printf("[waitlist] Seat %s on show %s is available again%n", seat.seat.seatNumber, seat.show.id);
        }
    }

    // ---------- BookingService (facade) ----------

    static final class BookingService {
        private static final long HOLD_TTL_MILLIS = 2000;
        private final PricingStrategy pricingStrategy;
        private final WaitlistNotifier waitlistNotifier;
        private final Map<String, SeatLock> activeLocks = new HashMap<>();
        private final Map<String, Booking> bookings = new HashMap<>();
        private final Map<String, Booking> idempotencyRecords = new HashMap<>();
        private int lockSeq = 0, bookingSeq = 0;

        BookingService(PricingStrategy pricingStrategy, WaitlistNotifier waitlistNotifier) {
            this.pricingStrategy = pricingStrategy;
            this.waitlistNotifier = waitlistNotifier;
        }

        /** Locks seats in canonical (sorted) order so two overlapping multi-seat holds never deadlock. */
        synchronized SeatLock holdSeats(User user, Show show, List<String> seatNumbers) {
            List<String> ordered = new ArrayList<>(seatNumbers);
            Collections.sort(ordered);
            List<ShowSeat> locked = new ArrayList<>();
            try {
                for (String id : ordered) {
                    ShowSeat seat = show.getShowSeat(id);
                    seat.lock(); // throws IllegalStateException if not AVAILABLE
                    locked.add(seat);
                }
            } catch (IllegalStateException rejected) {
                for (ShowSeat seat : locked) seat.release(); // rollback partial holds
                throw new IllegalStateException("Could not hold all requested seats: " + rejected.getMessage());
            }
            String lockId = "LOCK-" + (++lockSeq);
            SeatLock seatLock = new SeatLock(lockId, user, locked, System.currentTimeMillis() + HOLD_TTL_MILLIS);
            activeLocks.put(lockId, seatLock);
            return seatLock;
        }

        synchronized Booking confirmBooking(String lockId, PaymentResult paymentResult, String idempotencyKey) {
            if (idempotencyRecords.containsKey(idempotencyKey)) return idempotencyRecords.get(idempotencyKey); // idempotent retry

            SeatLock seatLock = activeLocks.get(lockId);
            if (seatLock == null) throw new NoSuchElementException("Unknown or already-consumed lock " + lockId);
            if (seatLock.isExpired()) {
                activeLocks.remove(lockId);
                for (ShowSeat seat : seatLock.seats) seat.release();
                throw new IllegalStateException("Seat hold expired for lock " + lockId);
            }

            Booking booking = new Booking("BKG-" + (++bookingSeq), seatLock.user, seatLock.seats.get(0).show, seatLock.seats, pricingStrategy);
            if (paymentResult.success) {
                booking.confirm();
            } else {
                booking.cancel();
                waitlistNotifier.notifyWaiting(seatLock.seats);
            }
            activeLocks.remove(lockId);
            bookings.put(booking.id, booking);
            idempotencyRecords.put(idempotencyKey, booking);
            return booking;
        }

        synchronized void cancelBooking(String bookingId) {
            Booking booking = bookings.get(bookingId);
            if (booking == null) throw new NoSuchElementException("Unknown booking " + bookingId);
            booking.cancel();
            waitlistNotifier.notifyWaiting(booking.seats);
        }
    }

    // ---------- Demo ----------

    public static void main(String[] args) throws InterruptedException {
        List<Seat> seats = List.of(
                new Seat("A1", SeatCategory.PREMIUM), new Seat("A2", SeatCategory.PREMIUM),
                new Seat("B1", SeatCategory.GOLD), new Seat("B2", SeatCategory.GOLD),
                new Seat("C1", SeatCategory.SILVER), new Seat("C2", SeatCategory.SILVER));
        Screen screen = new Screen("SCR-1", "Screen 1", seats);
        Movie movie = new Movie("MOV-1", "Interstellar", 169);
        Show show = new Show("SHOW-1", movie, screen, LocalDateTime.of(2026, 10, 2, 19, 0)); // peak hour

        WaitlistNotifier waitlistNotifier = new WaitlistNotifier();
        waitlistNotifier.subscribe(new ConsoleWaitlistNotifier());
        BookingService bookingService = new BookingService(new CategoryTimeBasedPricingStrategy(), waitlistNotifier);

        User alice = new User("u1", "Alice");
        User bob = new User("u2", "Bob");

        // Concurrency demo: Alice holds {A1,A2}, Bob holds {A2,B1} -- overlapping sets, sorted-order locking prevents deadlock.
        final SeatLock[] results = new SeatLock[2];
        Thread t1 = new Thread(() -> {
            try { results[0] = bookingService.holdSeats(alice, show, List.of("A1", "A2")); } catch (Exception ignored) { }
        });
        Thread t2 = new Thread(() -> {
            try { results[1] = bookingService.holdSeats(bob, show, List.of("A2", "B1")); } catch (Exception e) {
                System.out.println("Bob's hold rejected (expected, contends on A2): " + e.getMessage());
            }
        });
        t1.start(); t2.start();
        t1.join(); t2.join();

        SeatLock aliceLock = results[0];
        System.out.println("Alice locked seats: " + aliceLock.seats.size() + " totalPrice will be computed at confirm");

        Booking booking = bookingService.confirmBooking(aliceLock.id, new PaymentResult(true), "idem-key-1");
        System.out.printf("Booking %s CONFIRMED, total=%.2f%n", booking.id, booking.totalPrice);

        // Idempotent retry with the same key returns the same booking, no double charge/booking.
        Booking retry = bookingService.confirmBooking(aliceLock.id, new PaymentResult(true), "idem-key-1");
        System.out.println("Idempotent retry returns same booking: " + (retry == booking));

        // Bob can now hold A2 since Alice's booking only used A1 -- retry with a valid, non-conflicting set.
        SeatLock bobLock = bookingService.holdSeats(bob, show, List.of("B1", "B2"));
        Booking failedPayment = bookingService.confirmBooking(bobLock.id, new PaymentResult(false), "idem-key-2");
        System.out.println("Bob's failed-payment booking status: " + failedPayment.status + " (seats released, waitlist notified)");

        // Cancel Alice's confirmed booking, freeing A1 and A2 back to the pool.
        bookingService.cancelBooking(booking.id);
        System.out.println("A1 status after cancellation: " + show.getShowSeat("A1").getStatus());
        System.out.println("A2 status after cancellation: " + show.getShowSeat("A2").getStatus());

        // TTL expiry demo: hold C1, let it expire, then confirming should be rejected.
        SeatLock shortLock = bookingService.holdSeats(alice, show, List.of("C1"));
        Thread.sleep(2100);
        try {
            bookingService.confirmBooking(shortLock.id, new PaymentResult(true), "idem-key-3");
        } catch (IllegalStateException e) {
            System.out.println("Expired hold correctly rejected: " + e.getMessage());
        }
        System.out.println("C1 status after expiry: " + show.getShowSeat("C1").getStatus());
    }
}

// Problem 17: Movie Ticket Booking System (Concurrency Showcase)
//
// Seat (static attrs) vs ShowSeat (per-show status) split.
// ShowSeatState hierarchy encodes AVAILABLE -> LOCKED -> BOOKED legality, and LOCKED/BOOKED -> AVAILABLE on expire/release.
// SeatLock is a TTL-bound soft hold; only a successful payment converts it into a Booking confirmation.
// PricingStrategy is injected (Strategy); WaitlistNotifier is an Observer subject.
// BookingService is the facade; holdSeats() locks seats in canonical (sorted) order to avoid deadlock
// against another user holding an overlapping seat set.
#include <iostream>
#include <vector>
#include <memory>
#include <string>
#include <map>
#include <mutex>
#include <thread>
#include <chrono>
#include <stdexcept>
#include <algorithm>

enum class SeatCategory { SILVER, GOLD, PREMIUM };
enum class ShowSeatStatus { AVAILABLE, LOCKED, BOOKED };
enum class BookingStatus { HOLD, CONFIRMED, CANCELLED };

struct User { std::string id, name; };
struct PaymentResult { bool success; };

struct Seat {
    std::string seatNumber;
    SeatCategory category;
};

struct Movie { std::string id, title; int durationMinutes; };

struct Screen {
    std::string id, name;
    std::vector<Seat> seats;
};

class ShowSeat;

class Show {
public:
    std::string id;
    Movie movie;
    Screen screen;
    int startHour; // simplified: just the hour-of-day, enough to decide "peak"

    Show(std::string id_, Movie movie_, Screen screen_, int startHour_)
        : id(std::move(id_)), movie(std::move(movie_)), screen(std::move(screen_)), startHour(startHour_) {
        buildShowSeats();
    }

    ShowSeat& getShowSeat(const std::string& seatNumber);

private:
    void buildShowSeats();
    std::map<std::string, std::unique_ptr<ShowSeat>> showSeats_;
};

// ---------- ShowSeatState (State pattern) ----------
class ShowSeat;

class ShowSeatState {
public:
    virtual ~ShowSeatState() = default;
    virtual void onLock(ShowSeat& seat) = 0;
    virtual void onConfirm(ShowSeat& seat) = 0;
    virtual void onExpire(ShowSeat& seat) = 0;
};

class AvailableState : public ShowSeatState {
public:
    static ShowSeatState& instance();
    void onLock(ShowSeat& seat) override;
    void onConfirm(ShowSeat&) override { throw std::logic_error("Cannot confirm a seat that was never locked"); }
    void onExpire(ShowSeat&) override { /* already available; no-op */ }
};

class LockedState : public ShowSeatState {
public:
    static ShowSeatState& instance();
    void onLock(ShowSeat&) override { throw std::logic_error("Seat already locked"); }
    void onConfirm(ShowSeat& seat) override;
    void onExpire(ShowSeat& seat) override;
};

class BookedState : public ShowSeatState {
public:
    static ShowSeatState& instance();
    void onLock(ShowSeat&) override { throw std::logic_error("Seat already booked"); }
    void onConfirm(ShowSeat&) override { throw std::logic_error("Seat already booked"); }
    void onExpire(ShowSeat& seat) override; // booking cancellation frees the seat
};

class ShowSeat {
public:
    Seat seat;
    Show* show;

    ShowSeat(Seat seat_, Show* show_) : seat(std::move(seat_)), show(show_), status_(ShowSeatStatus::AVAILABLE), state_(&AvailableState::instance()) {}

    void setState(ShowSeatStatus status, ShowSeatState& state) { status_ = status; state_ = &state; }
    ShowSeatStatus getStatus() const { return status_; }

    void lock() { std::lock_guard<std::mutex> g(mutex_); state_->onLock(*this); }
    void confirm() { std::lock_guard<std::mutex> g(mutex_); state_->onConfirm(*this); }
    void release() { std::lock_guard<std::mutex> g(mutex_); state_->onExpire(*this); }

private:
    ShowSeatStatus status_;
    ShowSeatState* state_;
    std::mutex mutex_;
};

ShowSeatState& AvailableState::instance() { static AvailableState s; return s; }
ShowSeatState& LockedState::instance() { static LockedState s; return s; }
ShowSeatState& BookedState::instance() { static BookedState s; return s; }
void AvailableState::onLock(ShowSeat& seat) { seat.setState(ShowSeatStatus::LOCKED, LockedState::instance()); }
void LockedState::onConfirm(ShowSeat& seat) { seat.setState(ShowSeatStatus::BOOKED, BookedState::instance()); }
void LockedState::onExpire(ShowSeat& seat) { seat.setState(ShowSeatStatus::AVAILABLE, AvailableState::instance()); }
void BookedState::onExpire(ShowSeat& seat) { seat.setState(ShowSeatStatus::AVAILABLE, AvailableState::instance()); }

void Show::buildShowSeats() {
    for (auto& s : screen.seats) showSeats_[s.seatNumber] = std::make_unique<ShowSeat>(s, this);
}

ShowSeat& Show::getShowSeat(const std::string& seatNumber) {
    auto it = showSeats_.find(seatNumber);
    if (it == showSeats_.end()) throw std::out_of_range("No such seat: " + seatNumber);
    return *it->second;
}

// ---------- SeatLock ----------
struct SeatLock {
    std::string id;
    User user;
    std::vector<ShowSeat*> seats;
    std::chrono::steady_clock::time_point expiresAt;

    bool isExpired() const { return std::chrono::steady_clock::now() > expiresAt; }
};

// ---------- PricingStrategy ----------
class PricingStrategy {
public:
    virtual ~PricingStrategy() = default;
    virtual double calculatePrice(const Seat& seat, const Show& show) = 0;
};

class CategoryTimeBasedPricingStrategy : public PricingStrategy {
public:
    double calculatePrice(const Seat& seat, const Show& show) override {
        double base = baseRate(seat.category);
        bool peak = show.startHour >= 18 && show.startHour < 22;
        return peak ? base * 1.3 : base;
    }
private:
    static double baseRate(SeatCategory c) {
        switch (c) {
            case SeatCategory::SILVER: return 100.0;
            case SeatCategory::GOLD: return 180.0;
            case SeatCategory::PREMIUM: return 280.0;
        }
        return 0.0;
    }
};

// ---------- Booking ----------
class Booking {
public:
    std::string id;
    User user;
    Show* show;
    std::vector<ShowSeat*> seats;
    BookingStatus status;
    double totalPrice;

    Booking(std::string id_, User user_, Show* show_, std::vector<ShowSeat*> seats_, PricingStrategy& pricingStrategy)
        : id(std::move(id_)), user(std::move(user_)), show(show_), seats(std::move(seats_)), status(BookingStatus::HOLD) {
        totalPrice = 0;
        for (auto* s : seats) totalPrice += pricingStrategy.calculatePrice(s->seat, *show);
    }

    void confirm() {
        for (auto* s : seats) s->confirm();
        status = BookingStatus::CONFIRMED;
    }

    void cancel() {
        for (auto* s : seats) s->release();
        status = BookingStatus::CANCELLED;
    }
};

// ---------- WaitlistNotifier (Observer) ----------
class WaitlistObserver {
public:
    virtual ~WaitlistObserver() = default;
    virtual void onSeatAvailable(ShowSeat& seat) = 0;
};

class WaitlistNotifier {
public:
    void subscribe(std::shared_ptr<WaitlistObserver> observer) { observers_.push_back(std::move(observer)); }
    void notifyWaiting(const std::vector<ShowSeat*>& freedSeats) {
        for (auto* seat : freedSeats) for (auto& o : observers_) o->onSeatAvailable(*seat);
    }
private:
    std::vector<std::shared_ptr<WaitlistObserver>> observers_;
};

class ConsoleWaitlistNotifier : public WaitlistObserver {
public:
    void onSeatAvailable(ShowSeat& seat) override {
        std::cout << "[waitlist] Seat " << seat.seat.seatNumber << " on show " << seat.show->id << " is available again\n";
    }
};

// ---------- BookingService (facade) ----------
class BookingService {
public:
    BookingService(std::shared_ptr<PricingStrategy> pricingStrategy, std::shared_ptr<WaitlistNotifier> waitlistNotifier)
        : pricingStrategy_(std::move(pricingStrategy)), waitlistNotifier_(std::move(waitlistNotifier)) {}

    // Locks seats in canonical (sorted) order so two overlapping multi-seat holds never deadlock.
    std::shared_ptr<SeatLock> holdSeats(const User& user, Show& show, std::vector<std::string> seatNumbers) {
        std::lock_guard<std::mutex> g(serviceMutex_); // coarse-grained: whole hold operation is atomic
        std::sort(seatNumbers.begin(), seatNumbers.end());
        std::vector<ShowSeat*> locked;
        try {
            for (auto& id : seatNumbers) {
                ShowSeat& seat = show.getShowSeat(id);
                seat.lock(); // throws if not AVAILABLE
                locked.push_back(&seat);
            }
        } catch (const std::exception& rejected) {
            for (auto* seat : locked) seat->release(); // rollback partial holds
            throw std::runtime_error(std::string("Could not hold all requested seats: ") + rejected.what());
        }
        auto lock = std::make_shared<SeatLock>();
        lock->id = "LOCK-" + std::to_string(++lockSeq_);
        lock->user = user;
        lock->seats = locked;
        lock->expiresAt = std::chrono::steady_clock::now() + std::chrono::milliseconds(2000);
        activeLocks_[lock->id] = lock;
        return lock;
    }

    std::shared_ptr<Booking> confirmBooking(const std::string& lockId, PaymentResult paymentResult, const std::string& idempotencyKey) {
        std::lock_guard<std::mutex> g(serviceMutex_);
        auto idemIt = idempotencyRecords_.find(idempotencyKey);
        if (idemIt != idempotencyRecords_.end()) return idemIt->second; // idempotent retry

        auto lockIt = activeLocks_.find(lockId);
        if (lockIt == activeLocks_.end()) throw std::runtime_error("Unknown or already-consumed lock " + lockId);
        auto seatLock = lockIt->second;
        if (seatLock->isExpired()) {
            activeLocks_.erase(lockId);
            for (auto* seat : seatLock->seats) seat->release();
            throw std::runtime_error("Seat hold expired for lock " + lockId);
        }

        auto booking = std::make_shared<Booking>("BKG-" + std::to_string(++bookingSeq_), seatLock->user,
                                                   seatLock->seats[0]->show, seatLock->seats, *pricingStrategy_);
        if (paymentResult.success) {
            booking->confirm();
        } else {
            booking->cancel();
            waitlistNotifier_->notifyWaiting(seatLock->seats);
        }
        activeLocks_.erase(lockId);
        bookings_[booking->id] = booking;
        idempotencyRecords_[idempotencyKey] = booking;
        return booking;
    }

    void cancelBooking(const std::string& bookingId) {
        std::lock_guard<std::mutex> g(serviceMutex_);
        auto it = bookings_.find(bookingId);
        if (it == bookings_.end()) throw std::runtime_error("Unknown booking " + bookingId);
        it->second->cancel();
        waitlistNotifier_->notifyWaiting(it->second->seats);
    }

private:
    std::shared_ptr<PricingStrategy> pricingStrategy_;
    std::shared_ptr<WaitlistNotifier> waitlistNotifier_;
    std::map<std::string, std::shared_ptr<SeatLock>> activeLocks_;
    std::map<std::string, std::shared_ptr<Booking>> bookings_;
    std::map<std::string, std::shared_ptr<Booking>> idempotencyRecords_;
    std::mutex serviceMutex_;
    int lockSeq_ = 0, bookingSeq_ = 0;
};

static const char* statusName(ShowSeatStatus s) {
    switch (s) {
        case ShowSeatStatus::AVAILABLE: return "AVAILABLE";
        case ShowSeatStatus::LOCKED: return "LOCKED";
        case ShowSeatStatus::BOOKED: return "BOOKED";
    }
    return "?";
}
static const char* statusName(BookingStatus s) {
    switch (s) {
        case BookingStatus::HOLD: return "HOLD";
        case BookingStatus::CONFIRMED: return "CONFIRMED";
        case BookingStatus::CANCELLED: return "CANCELLED";
    }
    return "?";
}

int main() {
    std::vector<Seat> seats = {
        {"A1", SeatCategory::PREMIUM}, {"A2", SeatCategory::PREMIUM},
        {"B1", SeatCategory::GOLD}, {"B2", SeatCategory::GOLD},
        {"C1", SeatCategory::SILVER}, {"C2", SeatCategory::SILVER},
    };
    Screen screen{"SCR-1", "Screen 1", seats};
    Movie movie{"MOV-1", "Interstellar", 169};
    Show show("SHOW-1", movie, screen, 19); // peak hour

    auto waitlistNotifier = std::make_shared<WaitlistNotifier>();
    waitlistNotifier->subscribe(std::make_shared<ConsoleWaitlistNotifier>());
    auto pricing = std::make_shared<CategoryTimeBasedPricingStrategy>();
    BookingService bookingService(pricing, waitlistNotifier);

    User alice{"u1", "Alice"};
    User bob{"u2", "Bob"};

    // Concurrency demo: Alice holds {A1,A2}, Bob holds {A2,B1} -- overlapping sets, sorted-order locking prevents deadlock.
    std::shared_ptr<SeatLock> aliceLock, bobLockAttempt;
    std::thread t1([&]() {
        try { aliceLock = bookingService.holdSeats(alice, show, {"A1", "A2"}); } catch (...) { }
    });
    std::thread t2([&]() {
        try { bobLockAttempt = bookingService.holdSeats(bob, show, {"A2", "B1"}); }
        catch (const std::exception& e) { std::cout << "Bob's hold rejected (expected, contends on A2): " << e.what() << "\n"; }
    });
    t1.join(); t2.join();

    std::cout << "Alice locked seats: " << aliceLock->seats.size() << "\n";

    auto booking = bookingService.confirmBooking(aliceLock->id, {true}, "idem-key-1");
    std::cout << "Booking " << booking->id << " CONFIRMED, total=" << booking->totalPrice << "\n";

    auto retry = bookingService.confirmBooking(aliceLock->id, {true}, "idem-key-1");
    std::cout << "Idempotent retry returns same booking: " << (retry == booking ? "true" : "false") << "\n";

    auto bobLock = bookingService.holdSeats(bob, show, {"B1", "B2"});
    auto failedPayment = bookingService.confirmBooking(bobLock->id, {false}, "idem-key-2");
    std::cout << "Bob's failed-payment booking status: " << statusName(failedPayment->status) << " (seats released, waitlist notified)\n";

    bookingService.cancelBooking(booking->id);
    std::cout << "A1 status after cancellation: " << statusName(show.getShowSeat("A1").getStatus()) << "\n";
    std::cout << "A2 status after cancellation: " << statusName(show.getShowSeat("A2").getStatus()) << "\n";

    auto shortLock = bookingService.holdSeats(alice, show, {"C1"});
    std::this_thread::sleep_for(std::chrono::milliseconds(2100));
    try {
        bookingService.confirmBooking(shortLock->id, {true}, "idem-key-3");
    } catch (const std::exception& e) {
        std::cout << "Expired hold correctly rejected: " << e.what() << "\n";
    }
    std::cout << "C1 status after expiry: " << statusName(show.getShowSeat("C1").getStatus()) << "\n";

    return 0;
}

'use strict';
// Problem 17: Movie Ticket Booking System (Concurrency Showcase)
//
// Seat (static attrs) vs ShowSeat (per-show status) split.
// ShowSeatState hierarchy encodes AVAILABLE -> LOCKED -> BOOKED legality, and LOCKED/BOOKED -> AVAILABLE on expire/release.
// SeatLock is a TTL-bound soft hold; only a successful payment converts it into a Booking confirmation.
// PricingStrategy is injected (Strategy); WaitlistNotifier is an Observer subject.
// BookingService is the facade; holdSeats() locks seats in canonical (sorted) order so two overlapping
// multi-seat holds never deadlock -- modeled here with an AsyncMutex since Node has no real threads.

const SeatCategory = Object.freeze({ SILVER: 'SILVER', GOLD: 'GOLD', PREMIUM: 'PREMIUM' });
const ShowSeatStatus = Object.freeze({ AVAILABLE: 'AVAILABLE', LOCKED: 'LOCKED', BOOKED: 'BOOKED' });
const BookingStatus = Object.freeze({ HOLD: 'HOLD', CONFIRMED: 'CONFIRMED', CANCELLED: 'CANCELLED' });

/** A minimal FIFO mutual-exclusion primitive: a queue of waiters, one holder at a time. */
class AsyncMutex {
  constructor() { this._locked = false; this._waiters = []; }
  _acquire() {
    return new Promise((resolve) => {
      if (!this._locked) { this._locked = true; resolve(); }
      else this._waiters.push(resolve);
    });
  }
  _release() {
    if (this._waiters.length > 0) this._waiters.shift()();
    else this._locked = false;
  }
  async runExclusive(fn) {
    await this._acquire();
    try { return await fn(); } finally { this._release(); }
  }
}

class User {
  constructor(id, name) { this.id = id; this.name = name; }
}

class Seat {
  constructor(seatNumber, category) { this.seatNumber = seatNumber; this.category = category; }
}

class Movie {
  constructor(id, title, durationMinutes) { this.id = id; this.title = title; this.durationMinutes = durationMinutes; }
}

class Screen {
  constructor(id, name, seats) { this.id = id; this.name = name; this.seats = seats; }
}

// ---------- ShowSeatState (State pattern) ----------

class AvailableState {
  onLock(seat) { seat._setState(ShowSeatStatus.LOCKED, LOCKED_STATE); }
  onConfirm() { throw new Error('Cannot confirm a seat that was never locked'); }
  onExpire() { /* already available; no-op */ }
}
class LockedState {
  onLock() { throw new Error('Seat already locked'); }
  onConfirm(seat) { seat._setState(ShowSeatStatus.BOOKED, BOOKED_STATE); }
  onExpire(seat) { seat._setState(ShowSeatStatus.AVAILABLE, AVAILABLE_STATE); }
}
class BookedState {
  onLock() { throw new Error('Seat already booked'); }
  onConfirm() { throw new Error('Seat already booked'); }
  onExpire(seat) { seat._setState(ShowSeatStatus.AVAILABLE, AVAILABLE_STATE); } // booking cancellation frees the seat
}
const AVAILABLE_STATE = new AvailableState();
const LOCKED_STATE = new LockedState();
const BOOKED_STATE = new BookedState();

class ShowSeat {
  constructor(seat, show) {
    this.seat = seat;
    this.show = show;
    this.status = ShowSeatStatus.AVAILABLE;
    this._state = AVAILABLE_STATE;
    this._mutex = new AsyncMutex();
  }
  _setState(status, state) { this.status = status; this._state = state; }
  async lock() { return this._mutex.runExclusive(() => this._state.onLock(this)); }
  async confirm() { return this._mutex.runExclusive(() => this._state.onConfirm(this)); }
  async release() { return this._mutex.runExclusive(() => this._state.onExpire(this)); }
}

class Show {
  constructor(id, movie, screen, startHour) {
    this.id = id;
    this.movie = movie;
    this.screen = screen;
    this.startHour = startHour; // simplified: just the hour-of-day, enough to decide "peak"
    this._showSeats = new Map();
    for (const seat of screen.seats) this._showSeats.set(seat.seatNumber, new ShowSeat(seat, this));
  }
  getShowSeat(seatNumber) {
    const seat = this._showSeats.get(seatNumber);
    if (!seat) throw new Error(`No such seat: ${seatNumber}`);
    return seat;
  }
}

/** @interface PricingStrategy: calculatePrice(seat, show) -> number */
class CategoryTimeBasedPricingStrategy {
  calculatePrice(seat, show) {
    const baseRates = { [SeatCategory.SILVER]: 100, [SeatCategory.GOLD]: 180, [SeatCategory.PREMIUM]: 280 };
    const peak = show.startHour >= 18 && show.startHour < 22;
    return peak ? baseRates[seat.category] * 1.3 : baseRates[seat.category];
  }
}

class SeatLock {
  constructor(id, user, seats, ttlMillis) {
    this.id = id;
    this.user = user;
    this.seats = seats;
    this.expiresAt = Date.now() + ttlMillis;
  }
  isExpired() { return Date.now() > this.expiresAt; }
}

class Booking {
  constructor(id, user, show, seats, pricingStrategy) {
    this.id = id;
    this.user = user;
    this.show = show;
    this.seats = seats;
    this.status = BookingStatus.HOLD;
    this.totalPrice = seats.reduce((sum, s) => sum + pricingStrategy.calculatePrice(s.seat, show), 0);
  }
  async confirm() {
    for (const s of this.seats) await s.confirm();
    this.status = BookingStatus.CONFIRMED;
  }
  async cancel() {
    for (const s of this.seats) await s.release();
    this.status = BookingStatus.CANCELLED;
  }
}

/** @interface WaitlistObserver: onSeatAvailable(showSeat) */
class WaitlistNotifier {
  constructor() { this._observers = []; }
  subscribe(observer) { this._observers.push(observer); }
  notifyWaiting(freedSeats) {
    for (const seat of freedSeats) for (const o of this._observers) o.onSeatAvailable(seat);
  }
}
class ConsoleWaitlistNotifier {
  onSeatAvailable(seat) {
    console.log(`[waitlist] Seat ${seat.seat.seatNumber} on show ${seat.show.id} is available again`);
  }
}

/** Facade: top-level orchestration. holdSeats() locks in canonical (sorted) order. */
class BookingService {
  static HOLD_TTL_MILLIS = 2000;

  constructor(pricingStrategy, waitlistNotifier) {
    this._pricingStrategy = pricingStrategy;
    this._waitlistNotifier = waitlistNotifier;
    this._activeLocks = new Map();
    this._bookings = new Map();
    this._idempotencyRecords = new Map();
    this._serviceMutex = new AsyncMutex(); // coarse-grained: whole hold/confirm operation is atomic
    this._lockSeq = 0;
    this._bookingSeq = 0;
  }

  async holdSeats(user, show, seatNumbers) {
    return this._serviceMutex.runExclusive(async () => {
      const ordered = [...seatNumbers].sort();
      const locked = [];
      try {
        for (const id of ordered) {
          const seat = show.getShowSeat(id);
          await seat.lock(); // throws if not AVAILABLE
          locked.push(seat);
        }
      } catch (rejected) {
        for (const seat of locked) await seat.release(); // rollback partial holds
        throw new Error(`Could not hold all requested seats: ${rejected.message}`);
      }
      const lockId = `LOCK-${++this._lockSeq}`;
      const seatLock = new SeatLock(lockId, user, locked, BookingService.HOLD_TTL_MILLIS);
      this._activeLocks.set(lockId, seatLock);
      return seatLock;
    });
  }

  async confirmBooking(lockId, paymentResult, idempotencyKey) {
    return this._serviceMutex.runExclusive(async () => {
      if (this._idempotencyRecords.has(idempotencyKey)) return this._idempotencyRecords.get(idempotencyKey);

      const seatLock = this._activeLocks.get(lockId);
      if (!seatLock) throw new Error(`Unknown or already-consumed lock ${lockId}`);
      if (seatLock.isExpired()) {
        this._activeLocks.delete(lockId);
        for (const seat of seatLock.seats) await seat.release();
        throw new Error(`Seat hold expired for lock ${lockId}`);
      }

      const booking = new Booking(`BKG-${++this._bookingSeq}`, seatLock.user, seatLock.seats[0].show, seatLock.seats, this._pricingStrategy);
      if (paymentResult.success) {
        await booking.confirm();
      } else {
        await booking.cancel();
        this._waitlistNotifier.notifyWaiting(seatLock.seats);
      }
      this._activeLocks.delete(lockId);
      this._bookings.set(booking.id, booking);
      this._idempotencyRecords.set(idempotencyKey, booking);
      return booking;
    });
  }

  async cancelBooking(bookingId) {
    return this._serviceMutex.runExclusive(async () => {
      const booking = this._bookings.get(bookingId);
      if (!booking) throw new Error(`Unknown booking ${bookingId}`);
      await booking.cancel();
      this._waitlistNotifier.notifyWaiting(booking.seats);
    });
  }
}

async function main() {
  const seats = [
    new Seat('A1', SeatCategory.PREMIUM), new Seat('A2', SeatCategory.PREMIUM),
    new Seat('B1', SeatCategory.GOLD), new Seat('B2', SeatCategory.GOLD),
    new Seat('C1', SeatCategory.SILVER), new Seat('C2', SeatCategory.SILVER),
  ];
  const screen = new Screen('SCR-1', 'Screen 1', seats);
  const movie = new Movie('MOV-1', 'Interstellar', 169);
  const show = new Show('SHOW-1', movie, screen, 19); // peak hour

  const waitlistNotifier = new WaitlistNotifier();
  waitlistNotifier.subscribe(new ConsoleWaitlistNotifier());
  const bookingService = new BookingService(new CategoryTimeBasedPricingStrategy(), waitlistNotifier);

  const alice = new User('u1', 'Alice');
  const bob = new User('u2', 'Bob');

  // "Concurrency" demo: Alice holds {A1,A2}, Bob holds {A2,B1} -- overlapping sets racing via Promise.allSettled.
  const [aliceResult, bobResult] = await Promise.allSettled([
    bookingService.holdSeats(alice, show, ['A1', 'A2']),
    bookingService.holdSeats(bob, show, ['A2', 'B1']),
  ]);
  if (bobResult.status === 'rejected') console.log('Bob\'s hold rejected (expected, contends on A2):', bobResult.reason.message);
  const aliceLock = aliceResult.value;
  console.log('Alice locked seats:', aliceLock.seats.length);

  const booking = await bookingService.confirmBooking(aliceLock.id, { success: true }, 'idem-key-1');
  console.log(`Booking ${booking.id} CONFIRMED, total=${booking.totalPrice.toFixed(2)}`);

  const retry = await bookingService.confirmBooking(aliceLock.id, { success: true }, 'idem-key-1');
  console.log('Idempotent retry returns same booking:', retry === booking);

  const bobLock = await bookingService.holdSeats(bob, show, ['B1', 'B2']);
  const failedPayment = await bookingService.confirmBooking(bobLock.id, { success: false }, 'idem-key-2');
  console.log('Bob\'s failed-payment booking status:', failedPayment.status, '(seats released, waitlist notified)');

  await bookingService.cancelBooking(booking.id);
  console.log('A1 status after cancellation:', show.getShowSeat('A1').status);
  console.log('A2 status after cancellation:', show.getShowSeat('A2').status);

  const shortLock = await bookingService.holdSeats(alice, show, ['C1']);
  await new Promise((resolve) => setTimeout(resolve, 2100));
  try {
    await bookingService.confirmBooking(shortLock.id, { success: true }, 'idem-key-3');
  } catch (e) {
    console.log('Expired hold correctly rejected:', e.message);
  }
  console.log('C1 status after expiry:', show.getShowSeat('C1').status);
}

if (require.main === module) {
  main().catch((e) => { console.error(e); process.exit(1); });
}

module.exports = {
  SeatCategory, ShowSeatStatus, BookingStatus, User, Seat, Movie, Screen, Show,
  CategoryTimeBasedPricingStrategy, SeatLock, Booking, WaitlistNotifier, ConsoleWaitlistNotifier, BookingService,
};

// Problem 17: Movie Ticket Booking System (Concurrency Showcase)
//
// Seat (static attrs) vs ShowSeat (per-show status) split.
// ShowSeatState hierarchy encodes AVAILABLE -> LOCKED -> BOOKED legality, and LOCKED/BOOKED -> AVAILABLE on expire/release.
// SeatLock is a TTL-bound soft hold; only a successful payment converts it into a Booking confirmation.
// PricingStrategy is injected (Strategy); WaitlistNotifier is an Observer subject.
// BookingService is the facade; holdSeats() locks seats in canonical (sorted) order so two overlapping
// multi-seat holds never deadlock -- modeled here with an AsyncMutex since Node has no real threads.

enum SeatCategory { SILVER = 'SILVER', GOLD = 'GOLD', PREMIUM = 'PREMIUM' }
enum ShowSeatStatus { AVAILABLE = 'AVAILABLE', LOCKED = 'LOCKED', BOOKED = 'BOOKED' }
enum BookingStatus { HOLD = 'HOLD', CONFIRMED = 'CONFIRMED', CANCELLED = 'CANCELLED' }

/** A minimal FIFO mutual-exclusion primitive: a queue of waiters, one holder at a time. */
class AsyncMutex {
  private locked = false;
  private waiters: Array<() => void> = [];

  private acquire(): Promise<void> {
    return new Promise<void>((resolve) => {
      if (!this.locked) { this.locked = true; resolve(); }
      else this.waiters.push(resolve);
    });
  }
  private release(): void {
    const next = this.waiters.shift();
    if (next) next();
    else this.locked = false;
  }
  async runExclusive<T>(fn: () => T | Promise<T>): Promise<T> {
    await this.acquire();
    try { return await fn(); } finally { this.release(); }
  }
}

class User {
  constructor(public readonly id: string, public readonly name: string) {}
}

interface PaymentResult { success: boolean }

class Seat {
  constructor(public readonly seatNumber: string, public readonly category: SeatCategory) {}
}

class Movie {
  constructor(public readonly id: string, public readonly title: string, public readonly durationMinutes: number) {}
}

class Screen {
  constructor(public readonly id: string, public readonly name: string, public readonly seats: Seat[]) {}
}

// ---------- ShowSeatState (State pattern) ----------
interface ShowSeatState {
  onLock(seat: ShowSeat): void;
  onConfirm(seat: ShowSeat): void;
  onExpire(seat: ShowSeat): void;
}

class AvailableState implements ShowSeatState {
  onLock(seat: ShowSeat): void { seat._setState(ShowSeatStatus.LOCKED, LOCKED_STATE); }
  onConfirm(): void { throw new Error('Cannot confirm a seat that was never locked'); }
  onExpire(): void { /* already available; no-op */ }
}
class LockedState implements ShowSeatState {
  onLock(): void { throw new Error('Seat already locked'); }
  onConfirm(seat: ShowSeat): void { seat._setState(ShowSeatStatus.BOOKED, BOOKED_STATE); }
  onExpire(seat: ShowSeat): void { seat._setState(ShowSeatStatus.AVAILABLE, AVAILABLE_STATE); }
}
class BookedState implements ShowSeatState {
  onLock(): void { throw new Error('Seat already booked'); }
  onConfirm(): void { throw new Error('Seat already booked'); }
  onExpire(seat: ShowSeat): void { seat._setState(ShowSeatStatus.AVAILABLE, AVAILABLE_STATE); } // booking cancellation frees the seat
}
const AVAILABLE_STATE: ShowSeatState = new AvailableState();
const LOCKED_STATE: ShowSeatState = new LockedState();
const BOOKED_STATE: ShowSeatState = new BookedState();

class ShowSeat {
  status: ShowSeatStatus = ShowSeatStatus.AVAILABLE;
  private state: ShowSeatState = AVAILABLE_STATE;
  private mutex = new AsyncMutex();

  constructor(public readonly seat: Seat, public readonly show: Show) {}

  _setState(status: ShowSeatStatus, state: ShowSeatState): void { this.status = status; this.state = state; }
  async lock(): Promise<void> { return this.mutex.runExclusive(() => this.state.onLock(this)); }
  async confirm(): Promise<void> { return this.mutex.runExclusive(() => this.state.onConfirm(this)); }
  async release(): Promise<void> { return this.mutex.runExclusive(() => this.state.onExpire(this)); }
}

class Show {
  private showSeats = new Map<string, ShowSeat>();

  constructor(
    public readonly id: string,
    public readonly movie: Movie,
    public readonly screen: Screen,
    public readonly startHour: number // simplified: just the hour-of-day, enough to decide "peak"
  ) {
    for (const seat of screen.seats) this.showSeats.set(seat.seatNumber, new ShowSeat(seat, this));
  }

  getShowSeat(seatNumber: string): ShowSeat {
    const seat = this.showSeats.get(seatNumber);
    if (!seat) throw new Error(`No such seat: ${seatNumber}`);
    return seat;
  }
}

interface PricingStrategy {
  calculatePrice(seat: Seat, show: Show): number;
}

class CategoryTimeBasedPricingStrategy implements PricingStrategy {
  private baseRates: Record<SeatCategory, number> = {
    [SeatCategory.SILVER]: 100, [SeatCategory.GOLD]: 180, [SeatCategory.PREMIUM]: 280,
  };
  calculatePrice(seat: Seat, show: Show): number {
    const peak = show.startHour >= 18 && show.startHour < 22;
    return peak ? this.baseRates[seat.category] * 1.3 : this.baseRates[seat.category];
  }
}

class SeatLock {
  readonly expiresAt: number;
  constructor(public readonly id: string, public readonly user: User, public readonly seats: ShowSeat[], ttlMillis: number) {
    this.expiresAt = Date.now() + ttlMillis;
  }
  isExpired(): boolean { return Date.now() > this.expiresAt; }
}

class Booking {
  status: BookingStatus = BookingStatus.HOLD;
  readonly totalPrice: number;

  constructor(
    public readonly id: string,
    public readonly user: User,
    public readonly show: Show,
    public readonly seats: ShowSeat[],
    pricingStrategy: PricingStrategy
  ) {
    this.totalPrice = seats.reduce((sum, s) => sum + pricingStrategy.calculatePrice(s.seat, show), 0);
  }

  async confirm(): Promise<void> {
    for (const s of this.seats) await s.confirm();
    this.status = BookingStatus.CONFIRMED;
  }

  async cancel(): Promise<void> {
    for (const s of this.seats) await s.release();
    this.status = BookingStatus.CANCELLED;
  }
}

interface WaitlistObserver {
  onSeatAvailable(seat: ShowSeat): void;
}

class WaitlistNotifier {
  private observers: WaitlistObserver[] = [];
  subscribe(observer: WaitlistObserver): void { this.observers.push(observer); }
  notifyWaiting(freedSeats: ShowSeat[]): void {
    for (const seat of freedSeats) for (const o of this.observers) o.onSeatAvailable(seat);
  }
}
class ConsoleWaitlistNotifier implements WaitlistObserver {
  onSeatAvailable(seat: ShowSeat): void {
    console.log(`[waitlist] Seat ${seat.seat.seatNumber} on show ${seat.show.id} is available again`);
  }
}

/** Facade: top-level orchestration. holdSeats() locks in canonical (sorted) order. */
class BookingService {
  private static readonly HOLD_TTL_MILLIS = 2000;
  private activeLocks = new Map<string, SeatLock>();
  private bookings = new Map<string, Booking>();
  private idempotencyRecords = new Map<string, Booking>();
  private serviceMutex = new AsyncMutex(); // coarse-grained: whole hold/confirm operation is atomic
  private lockSeq = 0;
  private bookingSeq = 0;

  constructor(private pricingStrategy: PricingStrategy, private waitlistNotifier: WaitlistNotifier) {}

  async holdSeats(user: User, show: Show, seatNumbers: string[]): Promise<SeatLock> {
    return this.serviceMutex.runExclusive(async () => {
      const ordered = [...seatNumbers].sort();
      const locked: ShowSeat[] = [];
      try {
        for (const id of ordered) {
          const seat = show.getShowSeat(id);
          await seat.lock(); // throws if not AVAILABLE
          locked.push(seat);
        }
      } catch (rejected: any) {
        for (const seat of locked) await seat.release(); // rollback partial holds
        throw new Error(`Could not hold all requested seats: ${rejected.message}`);
      }
      const lockId = `LOCK-${++this.lockSeq}`;
      const seatLock = new SeatLock(lockId, user, locked, BookingService.HOLD_TTL_MILLIS);
      this.activeLocks.set(lockId, seatLock);
      return seatLock;
    });
  }

  async confirmBooking(lockId: string, paymentResult: PaymentResult, idempotencyKey: string): Promise<Booking> {
    return this.serviceMutex.runExclusive(async () => {
      const existing = this.idempotencyRecords.get(idempotencyKey);
      if (existing) return existing;

      const seatLock = this.activeLocks.get(lockId);
      if (!seatLock) throw new Error(`Unknown or already-consumed lock ${lockId}`);
      if (seatLock.isExpired()) {
        this.activeLocks.delete(lockId);
        for (const seat of seatLock.seats) await seat.release();
        throw new Error(`Seat hold expired for lock ${lockId}`);
      }

      const booking = new Booking(`BKG-${++this.bookingSeq}`, seatLock.user, seatLock.seats[0].show, seatLock.seats, this.pricingStrategy);
      if (paymentResult.success) {
        await booking.confirm();
      } else {
        await booking.cancel();
        this.waitlistNotifier.notifyWaiting(seatLock.seats);
      }
      this.activeLocks.delete(lockId);
      this.bookings.set(booking.id, booking);
      this.idempotencyRecords.set(idempotencyKey, booking);
      return booking;
    });
  }

  async cancelBooking(bookingId: string): Promise<void> {
    return this.serviceMutex.runExclusive(async () => {
      const booking = this.bookings.get(bookingId);
      if (!booking) throw new Error(`Unknown booking ${bookingId}`);
      await booking.cancel();
      this.waitlistNotifier.notifyWaiting(booking.seats);
    });
  }
}

async function main(): Promise<void> {
  const seats: Seat[] = [
    new Seat('A1', SeatCategory.PREMIUM), new Seat('A2', SeatCategory.PREMIUM),
    new Seat('B1', SeatCategory.GOLD), new Seat('B2', SeatCategory.GOLD),
    new Seat('C1', SeatCategory.SILVER), new Seat('C2', SeatCategory.SILVER),
  ];
  const screen = new Screen('SCR-1', 'Screen 1', seats);
  const movie = new Movie('MOV-1', 'Interstellar', 169);
  const show = new Show('SHOW-1', movie, screen, 19); // peak hour

  const waitlistNotifier = new WaitlistNotifier();
  waitlistNotifier.subscribe(new ConsoleWaitlistNotifier());
  const bookingService = new BookingService(new CategoryTimeBasedPricingStrategy(), waitlistNotifier);

  const alice = new User('u1', 'Alice');
  const bob = new User('u2', 'Bob');

  // "Concurrency" demo: Alice holds {A1,A2}, Bob holds {A2,B1} -- overlapping sets racing via Promise.allSettled.
  const [aliceResult, bobResult] = await Promise.allSettled([
    bookingService.holdSeats(alice, show, ['A1', 'A2']),
    bookingService.holdSeats(bob, show, ['A2', 'B1']),
  ]);
  if (bobResult.status === 'rejected') console.log("Bob's hold rejected (expected, contends on A2):", (bobResult.reason as Error).message);
  const aliceLock = (aliceResult as PromiseFulfilledResult<SeatLock>).value;
  console.log('Alice locked seats:', aliceLock.seats.length);

  const booking = await bookingService.confirmBooking(aliceLock.id, { success: true }, 'idem-key-1');
  console.log(`Booking ${booking.id} CONFIRMED, total=${booking.totalPrice.toFixed(2)}`);

  const retry = await bookingService.confirmBooking(aliceLock.id, { success: true }, 'idem-key-1');
  console.log('Idempotent retry returns same booking:', retry === booking);

  const bobLock = await bookingService.holdSeats(bob, show, ['B1', 'B2']);
  const failedPayment = await bookingService.confirmBooking(bobLock.id, { success: false }, 'idem-key-2');
  console.log("Bob's failed-payment booking status:", failedPayment.status, '(seats released, waitlist notified)');

  await bookingService.cancelBooking(booking.id);
  console.log('A1 status after cancellation:', show.getShowSeat('A1').status);
  console.log('A2 status after cancellation:', show.getShowSeat('A2').status);

  const shortLock = await bookingService.holdSeats(alice, show, ['C1']);
  await new Promise<void>((resolve) => setTimeout(resolve, 2100));
  try {
    await bookingService.confirmBooking(shortLock.id, { success: true }, 'idem-key-3');
  } catch (e) {
    console.log('Expired hold correctly rejected:', (e as Error).message);
  }
  console.log('C1 status after expiry:', show.getShowSeat('C1').status);
}

main().catch((e) => { console.error(e); process.exit(1); });

← 16. Hotel Reservation System 18. Restaurant / Food Delivery System →