46 — LLD: Movie Ticket Booking (BookMyShow)

Understanding the Problem

Design a ticket-booking platform. The hierarchy is City → Cinema → Screen → Show → Seat. Users search shows, view seat layout, hold seats for N minutes while they pay, then confirm. On seat availability changes, any subscribed client (web, mobile) gets a live push.

What is a ticket-booking system?

It is concurrency plus UX. Two users tap the same seat at once — only one wins, the other needs to know immediately. The hold/confirm phase exists to let payment breathe without locking the seat forever.

---

Requirements

Clarifying Questions

You: Hold window before payment?

Interviewer: Yes, 10 minutes.

A SeatHold with expiresAt, plus a background reaper.

You: Are cancellations supported during the hold?

Interviewer: Yes, the user can release the hold or the timer can.

Two release paths: voluntary and timed.

You: Dynamic pricing?

Interviewer: Not for v1, but interface should allow it.

Pluggable PricingStrategy.

You: Concurrency — many users on the same show?

Interviewer: Yes, this is our Friday-night problem.

Per-show lock scope, not per-cinema.

You: Real-time seat updates to clients?

Interviewer: Yes, push out availability changes.

Observer pattern at the Show level.

You: Search — list cinemas in a city showing a movie, and list shows in a cinema for a movie?

Interviewer: Yes — and the search results must stay correct as new shows are added live.

Second observer at a different layer: the catalog publishes ShowAdded events; per-city and per-cinema indexes subscribe and update their inverted maps. Reads stay O(1) and never scan the catalog.

Final Requirements

1. City / Cinema / Screen / Show hierarchy.
2. Seat states: Available, Held, Booked.
3. tryHold(userId, seatIds) — atomic across the seat set.
4. confirm(holdId) after payment.
5. release(holdId) — manual or timer-driven.
6. Two Observer use-sites:
   • SeatObserver on Show — push seat-availability changes to live clients.
   • CatalogObserver on Catalog — push ShowAdded to MovieByCityIndex and MovieByCinemaIndex so search lookups (cinemasInCity(movie), showsInCinema(cinema, movie)) stay current without scanning.
7. Thread-safe at per-show granularity.

Out of scope: payment provider integration, seat recommendations, fraud detection beyond the obvious.

---

Core Entities and Relationships

Entity	Responsibility
City / Cinema / Screen	Structural hierarchy.
Show	Movie + time + screen + seat map. Owns holds.
Seat	Row, number, category, state.
SeatHold	{id, userId, seatIds, expiresAt}.
BookingService	Hold, confirm, release orchestration.
SeatObserver	Interface for push subscribers (live seat changes).
Catalog	Authoritative store of cinemas and shows. Publishes ShowAdded to subscribers.
CatalogObserver	Interface — onShowAdded(show).
MovieByCityIndex	Inverted map: cityId → movieId → Set<cinemaId>. Subscribes to Catalog.
MovieByCinemaIndex	Inverted map: cinemaId → movieId → List<showId>. Subscribes to Catalog.
PricingStrategy	Pluggable per show.
HoldReaper	Background job expiring stale holds.

Why per-show ownership of seats and holds? Because different shows never conflict — the concurrency boundary is the show, not the cinema.

Why an explicit SeatHold entity? Because confirm and release need to find the hold atomically by ID; a flat seat state is not enough.

Design is iterative — start with hold/confirm/release and a single observer, then add pricing and waitlist.

---

Class Design

Seat

State: id, row, number, state, holdId?

Show

State:

• id, movieId, startTime
• seats: Map<id, Seat>
• holds: Map<id, SeatHold>
• holdMs: number
• observers: Set<SeatObserver>
• lock: Mutex

Methods:

• tryHold(userId, seatIds) -> SeatHold
• confirm(holdId)
• release(holdId)
• subscribe(observer)

BookingService

Methods:

• hold(showId, userId, seatIds)
• confirm(showId, holdId)
• release(showId, holdId)

Design principles at play:

• Observer Pattern — seat availability pub/sub.
• State Pattern — seat state transitions.
• Strategy Pattern — pricing.
• Singleton — BookingService.

---

Implementation

Core Logic: Atomic Hold

Bad approach: loop through seats, mark each available to held as you go.

• Leaves partial state on mid-loop conflict.

Good approach: two-phase check-then-apply inside a lock. If any seat is not available, abort before any mutation.

Great approach: same, but release the lock before notifying observers so a slow observer cannot block the next booking.

Verification

Show S1 with seats {A1, A2, A3}. All available. Lock per show.

1. Alice: tryHold(S1, [A1, A2]) → under lock, all three seats available, mark A1/A2 held with holdH1, notify observers. Returns H1.
2. Bob: tryHold(S1, [A2, A3]) → under lock, A2 is Held → throw SEAT_UNAVAILABLE:A2. No mutation.
3. Alice pays: confirm(H1) → under lock, H1 not expired, seats booked, hold removed, observers notified.
4. Carol: tryHold(S1, [A3]) → succeeds, H2 issued.
5. Carol walks away → 10 minutes pass → HoldReaper.tick() finds H2 expired, releases A3, notifies observers.

Thread Safety

• tryHold, confirm, release must all run under the same per-show lock.
• holds is a ConcurrentHashMap for dirty-reads from the reaper, with the critical section under the lock.
• Background reaper scans holds periodically; it takes the show lock only when actually expiring.
• Multi-node deployments: per-show lock becomes a Redis SETNX with a short TTL, or a distributed lock via Redlock / etcd lease.

Complete Code Implementation

Java

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.locks.ReentrantLock;

enum SeatState { AVAILABLE, HELD, BOOKED }

class Seat {
    public final String id, row;
    public final int number;
    public volatile SeatState state = SeatState.AVAILABLE;
    public volatile String holdId;
    public Seat(String id, String row, int n) { this.id = id; this.row = row; this.number = n; }
}

interface SeatObserver { void onSeatsChanged(String showId, List<String> seatIds); }

class SeatHold {
    public final String id, userId;
    public final List<String> seatIds;
    public final long expiresAt;
    public SeatHold(String id, String userId, List<String> seatIds, long expiresAt) {
        this.id = id; this.userId = userId; this.seatIds = seatIds; this.expiresAt = expiresAt;
    }
}

class Show {
    public final String id, movieId;
    public final long startTime;
    public final Map<String, Seat> seats;
    private final ConcurrentHashMap<String, SeatHold> holds = new ConcurrentHashMap<>();
    private final Set<SeatObserver> observers = ConcurrentHashMap.newKeySet();
    private final ReentrantLock lock = new ReentrantLock();
    private final long holdMs;

    public Show(String id, String movieId, long startTime, Map<String, Seat> seats, long holdMs) {
        this.id = id; this.movieId = movieId; this.startTime = startTime;
        this.seats = seats; this.holdMs = holdMs;
    }

    public void subscribe(SeatObserver o) { observers.add(o); }

    private void notify(List<String> ids) {
        // snapshot observers so listeners can resubscribe safely
        for (SeatObserver o : new ArrayList<>(observers)) {
            try { o.onSeatsChanged(id, ids); } catch (Exception ignored) {}
        }
    }

    public SeatHold tryHold(String userId, List<String> seatIds) {
        lock.lock();
        List<String> changed;
        SeatHold hold;
        try {
            for (String sid : seatIds) {
                Seat s = seats.get(sid);
                if (s == null || s.state != SeatState.AVAILABLE)
                    throw new IllegalStateException("SEAT_UNAVAILABLE:" + sid);
            }
            String holdId = UUID.randomUUID().toString();
            for (String sid : seatIds) {
                Seat s = seats.get(sid);
                s.state = SeatState.HELD; s.holdId = holdId;
            }
            hold = new SeatHold(holdId, userId, seatIds, System.currentTimeMillis() + holdMs);
            holds.put(holdId, hold);
            changed = new ArrayList<>(seatIds);
        } finally { lock.unlock(); }
        notify(changed);  // fire observers outside the lock
        return hold;
    }

    public void confirm(String holdId) {
        List<String> changed;
        lock.lock();
        try {
            SeatHold hold = holds.get(holdId);
            if (hold == null) throw new IllegalStateException("HOLD_NOT_FOUND");
            if (hold.expiresAt < System.currentTimeMillis()) {
                release(holdId);
                throw new IllegalStateException("HOLD_EXPIRED");
            }
            for (String sid : hold.seatIds) seats.get(sid).state = SeatState.BOOKED;
            holds.remove(holdId);
            changed = hold.seatIds;
        } finally { lock.unlock(); }
        notify(changed);
    }

    public void release(String holdId) {
        List<String> changed;
        lock.lock();
        try {
            SeatHold hold = holds.remove(holdId);
            if (hold == null) return;
            for (String sid : hold.seatIds) {
                Seat s = seats.get(sid);
                if (s.state == SeatState.HELD && holdId.equals(s.holdId)) {
                    s.state = SeatState.AVAILABLE; s.holdId = null;
                }
            }
            changed = hold.seatIds;
        } finally { lock.unlock(); }
        notify(changed);
    }
}

C++

#include <chrono>
#include <memory>
#include <mutex>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

enum class SeatState { Available, Held, Booked };

struct Seat {
    std::string id, row;
    int number;
    SeatState state = SeatState::Available;
    std::string holdId;
};

struct SeatObserver { virtual void onSeatsChanged(const std::string& showId, const std::vector<std::string>& ids) = 0; };

struct SeatHold {
    std::string id, userId;
    std::vector<std::string> seatIds;
    long long expiresAt;
};

class Show {
public:
    std::string id, movieId;
    long long startTime, holdMs;
    std::unordered_map<std::string, std::shared_ptr<Seat>> seats;

    Show(std::string id, std::string m, long long t, std::unordered_map<std::string, std::shared_ptr<Seat>> s, long long h)
        : id(std::move(id)), movieId(std::move(m)), startTime(t), seats(std::move(s)), holdMs(h) {}

    void subscribe(SeatObserver* o) { std::lock_guard<std::mutex> g(obsMu); observers.insert(o); }

    SeatHold tryHold(const std::string& userId, const std::vector<std::string>& seatIds) {
        SeatHold hold;
        {
            std::lock_guard<std::mutex> g(mu);
            for (auto& sid : seatIds) {
                auto it = seats.find(sid);
                if (it == seats.end() || it->second->state != SeatState::Available)
                    throw std::runtime_error("SEAT_UNAVAILABLE:" + sid);
            }
            hold.id = std::to_string(std::chrono::steady_clock::now().time_since_epoch().count());
            hold.userId = userId; hold.seatIds = seatIds;
            hold.expiresAt = std::chrono::system_clock::now().time_since_epoch().count() / 1'000'000 + holdMs;
            for (auto& sid : seatIds) { seats[sid]->state = SeatState::Held; seats[sid]->holdId = hold.id; }
            holds[hold.id] = hold;
        }
        notify(seatIds);
        return hold;
    }

    void confirm(const std::string& holdId) {
        std::vector<std::string> changed;
        {
            std::lock_guard<std::mutex> g(mu);
            auto it = holds.find(holdId);
            if (it == holds.end()) throw std::runtime_error("HOLD_NOT_FOUND");
            long long now = std::chrono::system_clock::now().time_since_epoch().count() / 1'000'000;
            if (it->second.expiresAt < now) { throw std::runtime_error("HOLD_EXPIRED"); }
            for (auto& sid : it->second.seatIds) seats[sid]->state = SeatState::Booked;
            changed = it->second.seatIds;
            holds.erase(it);
        }
        notify(changed);
    }

    void release(const std::string& holdId) {
        std::vector<std::string> changed;
        {
            std::lock_guard<std::mutex> g(mu);
            auto it = holds.find(holdId);
            if (it == holds.end()) return;
            for (auto& sid : it->second.seatIds) {
                auto& s = seats[sid];
                if (s->state == SeatState::Held && s->holdId == holdId) {
                    s->state = SeatState::Available; s->holdId.clear();
                }
            }
            changed = it->second.seatIds;
            holds.erase(it);
        }
        notify(changed);
    }

private:
    std::unordered_map<std::string, SeatHold> holds;
    std::unordered_set<SeatObserver*> observers;
    std::mutex mu, obsMu;

    void notify(const std::vector<std::string>& ids) {
        std::unordered_set<SeatObserver*> snap;
        { std::lock_guard<std::mutex> g(obsMu); snap = observers; }
        for (auto* o : snap) try { o->onSeatsChanged(id, ids); } catch (...) {}
    }
};

TypeScript

enum SeatState { Available, Held, Booked }

class Seat {
  state: SeatState = SeatState.Available;
  holdId: string | null = null;
  constructor(public readonly id: string, public readonly row: string, public readonly number: number) {}
}

interface SeatObserver { onSeatsChanged(showId: string, seatIds: string[]): void; }

interface SeatHold { id: string; userId: string; seatIds: string[]; expiresAt: number; }

class Show {
  private observers = new Set<SeatObserver>();
  private holds = new Map<string, SeatHold>();
  constructor(
    public readonly id: string,
    public readonly movieId: string,
    public readonly startTime: number,
    public readonly seats: Map<string, Seat>,
    public readonly holdMs = 10 * 60 * 1000,
  ) {}
  subscribe(o: SeatObserver) { this.observers.add(o); }
  private notify(seatIds: string[]) {
    for (const o of this.observers) { try { o.onSeatsChanged(this.id, seatIds); } catch {} }
  }

  tryHold(userId: string, seatIds: string[]): SeatHold {
    for (const id of seatIds) {
      const s = this.seats.get(id);
      if (!s || s.state !== SeatState.Available) throw new Error(`SEAT_UNAVAILABLE:${id}`);
    }
    const holdId = crypto.randomUUID();
    for (const id of seatIds) {
      const s = this.seats.get(id)!;
      s.state = SeatState.Held;
      s.holdId = holdId;
    }
    const hold = { id: holdId, userId, seatIds, expiresAt: Date.now() + this.holdMs };
    this.holds.set(holdId, hold);
    this.notify(seatIds);
    return hold;
  }

  confirm(holdId: string): void {
    const hold = this.holds.get(holdId);
    if (!hold) throw new Error("HOLD_NOT_FOUND");
    if (hold.expiresAt < Date.now()) { this.release(holdId); throw new Error("HOLD_EXPIRED"); }
    for (const id of hold.seatIds) this.seats.get(id)!.state = SeatState.Booked;
    this.holds.delete(holdId);
    this.notify(hold.seatIds);
  }

  release(holdId: string): void {
    const hold = this.holds.get(holdId);
    if (!hold) return;
    for (const id of hold.seatIds) {
      const s = this.seats.get(id)!;
      if (s.state === SeatState.Held && s.holdId === holdId) {
        s.state = SeatState.Available; s.holdId = null;
      }
    }
    this.holds.delete(holdId);
    this.notify(hold.seatIds);
  }
}

---

Extensibility

1. "Dynamic pricing"

Inject a PricingStrategy per show. Weekday flat, weekend surge, demand-based based on current hold ratio. Kept outside Show so pricing changes do not touch seat logic.

2. "Waitlist for full shows"

Observer pattern. When a seat transitions from Booked to Available, the show's waitlist head is notified. They get a short hold window.

3. "Real-time seat map"

WebSocket subscribers register as SeatObserver. The push is the existing onSeatsChanged callback over the socket. Clients render only the changed seats.

4. "Search indexes that stay correct as new shows are added live"

Two read-side queries dominate user traffic: cinemasInCity(cityId, movieId) and showsInCinema(cinemaId, movieId). Scanning the catalog on every call is wasteful, and a stale snapshot is unacceptable. Use a second Observer at the Catalog layer: when a new show is added, the catalog publishes ShowAdded(show) and two indexes — MovieByCityIndex and MovieByCinemaIndex — update their inverted maps in place.

interface CatalogObserver { onShowAdded(show: Show): void; }

class Catalog {
  private observers = new Set<CatalogObserver>();
  subscribe(o: CatalogObserver) { this.observers.add(o); }
  addShow(show: Show, cityId: string) {
    // ... persist
    for (const o of this.observers) o.onShowAdded(show);
  }
}

class MovieByCityIndex implements CatalogObserver {
  // cityId -> movieId -> Set<cinemaId>
  private idx = new Map<string, Map<string, Set<string>>>();
  onShowAdded(show: Show) {
    const byMovie = this.idx.get(show.cityId) ?? new Map();
    const cinemas = byMovie.get(show.movieId) ?? new Set();
    cinemas.add(show.cinemaId);
    byMovie.set(show.movieId, cinemas);
    this.idx.set(show.cityId, byMovie);
  }
  cinemasInCity(cityId: string, movieId: string): string[] {
    return [...(this.idx.get(cityId)?.get(movieId) ?? [])];
  }
}

class MovieByCinemaIndex implements CatalogObserver {
  private idx = new Map<string, Map<string, string[]>>();
  onShowAdded(show: Show) {
    const byMovie = this.idx.get(show.cinemaId) ?? new Map();
    const shows = byMovie.get(show.movieId) ?? [];
    shows.push(show.id);
    byMovie.set(show.movieId, shows);
    this.idx.set(show.cinemaId, byMovie);
  }
  showsInCinema(cinemaId: string, movieId: string): string[] {
    return [...(this.idx.get(cinemaId)?.get(movieId) ?? [])];
  }
}

The win: lookups are O(1), the catalog stays the single source of truth, and adding a third index (e.g., ShowsByGenre) is a new subscriber — no edits to the catalog or other indexes. Open/Closed in action.

---

What is Expected at Each Level

Level	Expectations
Mid	Book directly, no hold phase.
Senior / SMTS	Hold + confirm + reaper, Observer, per-show lock, atomic multi-seat hold.
Staff	Sharding by show, eventual consistency across replicas, fraud checks, payment choreography.