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.

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. Observer pattern for seat-change notifications.
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.
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.

---

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.