BookMyShow: Seat Locking Under Concurrency

10.1Problem Statement

Design the booking subsystem for a movie-ticketing platform: a user browses shows by city and movie, selects seats, and books them with payment. It reads like a straightforward CRUD-over-a-hierarchy exercise until the second sentence of the constraints: seat locking must be atomic, and a lock expires. That single requirement is the whole interview.

Functional requirements:

• A City has Theatres; each Theatre has Screens; each Screen runs Shows of Movies at given times.
• A Show has a seat map; each seat has a status: AVAILABLE / LOCKED / BOOKED.
• A user can search shows by city + movie, select seats, and book them.
• Booking flow: lock selected seats → take payment → confirm (mark BOOKED) or release on timeout/failure.

Non-functional constraints, which are the actual point of the exercise:

• Concurrency: seat locking must be atomic; a lock has a timeout after which seats auto-release.
• Observer for notifications (booking confirmed, payment failed, seats released).
• Payment as a small State machine: PENDING → SUCCESS / FAILED, with the booking reacting accordingly.

The expected public interface, given up front so the design effort goes into the locking semantics, not the signatures:

enum class SeatStatus { AVAILABLE, LOCKED, BOOKED };

class SeatLockProvider {              // the concurrency core
public:
    bool lockSeats(const Show& show, const std::vector<Seat>& seats,
                   const std::string& userId);          // atomic; false if any taken
    void unlockSeats(const Show& show, const std::vector<Seat>& seats,
                     const std::string& userId);
    bool validateLock(const Show&, const Seat&, const std::string& userId) const;
};

class BookingService {
public:
    std::vector<Show> searchShows(const std::string& city, const std::string& movie);
    Booking createBooking(const std::string& userId, const Show& show,
                          const std::vector<Seat>& seats);   // locks seats
    Booking confirmBooking(const Booking& booking, const Payment& payment);
};

What the interviewer is really testing:

• The atomic seat-lock with timeout — this is the make-or-break detail. A solution where two threads can both succeed on the last seat is a fail, full stop.
• A clean entity hierarchy (City → Theatre → Screen → Show → Seat) kept separate from the two services that hold the actual behavior.
• Observer wired for notifications, and the payment state handled explicitly rather than folded into a boolean.

Follow-up questions to expect once the base design stands:

• Distributed locking if the service is horizontally scaled — discuss it, even if you implement in-memory.
• Dynamic / tiered pricing (recliner vs. regular, weekend surge) via a pricing strategy.
• Waitlist and auto-allocation when seats release.
• Idempotent booking under client retries.

10.2How to Approach

Finding the Nouns: Data vs. Behaviour

Mine the hard constraints before drawing a single class. "Two users must never book the same seat" names the one thing being tested — everything else is scaffolding around one atomic operation. "A lock has a timeout after which seats auto-release" tells you locking isn't a boolean flag; it's an all-or-nothing claim over multiple seats, owned by a user, that expires. That phrasing alone screams one mutex-guarded provider plus a per-lock expiry timestamp.

Circle the remaining nouns — city, theatre, screen, show, movie, seat, lock, booking, payment, user, notification — and they split cleanly in two: a containment hierarchy (City → Theatre → Screen → Show → Seat, almost pure data) and three services that hold all the behavior (SeatLockProvider, BookingService, and the BookingObserver family).

Pinning the Interface Before Internals

The statement hands us the shape; lock it before internals, because it forces the hard decision — what "atomic lock" actually returns — to the front. lockSeats is all-or-nothing: it returns bool, and on failure it must leave the world untouched, no partial locks. That single guarantee is what prevents double-booking. createBooking locks but does not confirm — locking and paying are separate phases, and a lock is a reservation with a deadline, not a sale. validateLock is the gate before confirming, because payment success means nothing if the lock already expired and someone else grabbed the seat.

Modeling the Leaves: Seat, Show, and the Timed Lock

Build bottom-up: dependency-free types first. Movie, Seat, and Show are almost pure data — a seat map is just a vector of seats hanging off a show. The interesting leaf is SeatLock, which carries the timeout the problem demanded: "these seats, held by this user, valid until this instant."

The Key Insight: Atomic Check-Then-Set Under One Mutex

This is the heart of the problem, and it deserves real thought. A naive design marks each seat LOCKED one at a time. Two threads booking seats {A1, A2} and {A2, A3} can interleave: thread 1 locks A1, thread 2 locks A2 and A3, thread 1 tries A2 and fails — but it already locked A1, so it must roll back. Worse, without a lock around the whole check-then-set, both threads can read "A2 available" before either writes.

The fix is three rules: (1) one owner of all locks — SeatLockProvider holds the single source of truth, a map from showId to seatId → SeatLock; nobody else mutates seat-claim state. (2) guard check-then-set with a mutex — no window between checking and claiming. (3) all-or-nothing — inside the lock, first verify every requested seat is free (treating expired locks as free), then claim them all; if any check fails, claim nothing. A locked seat is free again the instant its lock expires, so the timeout is enforced lazily, right inside the availability check — no background sweeper is required for correctness, only to reclaim memory eventually.

Payment and Booking: Match Modeling Weight to the Requirement

The problem says payment is a small state machine, PENDING → SUCCESS / FAILED. That doesn't need a full polymorphic State pattern — three enum values plus the booking's reaction to them is the right altitude. A SUCCESS confirms (seats become permanently booked); a FAILED, or a lock that turned out to have expired, cancels and releases. Reserve heavyweight State classes for genuinely behaviour-rich modes, like a vending machine's multi-step session — a three-outcome payment is honestly served by an enum and a switch.

Observer for Notifications, and Orchestrating the Whole Flow

Booking events — confirmed, payment failed, seats released — need to fan out to subscribers (email, SMS, a waitlist trigger) without the service knowing who's listening. Observer earns its keep exactly here: the list of reactions grows independently of the action, so the service publishes one event and stays oblivious to who reacts.

BookingService is the conductor, and it follows a validate → mutate → transition rhythm with the dangerous part delegated entirely to the lock provider. createBooking locks the seats and records a CREATED booking, or throws if the lock fails. confirmBooking re-validates the lock is still ours for every seat — because payment success is necessary but not sufficient if the hold already expired — then branches on the payment outcome to confirm or release, publishing the matching event either way. The lock provider is the only class that needs to be thread-safe; the service stays a thin, boring coordinator, which is exactly where you want the complexity to not be.

A correct driver for this problem doesn't just show the happy path — it attempts the race. Spin up two threads booking the same seats and assert exactly one wins. That assertion, not a green checkmark on a single-threaded run, is the proof an interviewer is looking for.

Follow-Ups: Naming the Seams

A strong finish names the extension points instead of coding all of them. Distributed locking: the in-memory mutex only protects one process; swap the provider's internals for a shared atomic store — Redis SET seat:<show>:<id> <user> NX EX <ttl> gives all-or-nothing via NX and the timeout for free via EX. The interface doesn't change, only the backend behind it. Tiered pricing: extract a PricingStrategy interface and inject it — recliner vs. regular, weekend surge, each a strategy implementation, orthogonal to the lock logic. Waitlist: already an Observer payoff — a WaitlistObserver reacts to SEATS_RELEASED by offering the freed seats to the next queued user. Idempotent retries: have the client pass an idempotency key, and have the service keep a key → Booking map so a retried request returns the existing booking instead of creating a second one.

10.3Whole Solution

The reference solution below is a single, self-contained program with its own main(). It merges every incremental fragment from the walkthrough into one internally consistent design: the entity hierarchy, the mutex-guarded SeatLockProvider with lazy timeout expiry, the enum-driven payment/booking lifecycle, the BookingObserver fan-out, and a BookingService that orchestrates all of it. The driver proves the design with the same race an interviewer would ask for — two threads booking the same seats, exactly one winner — followed by a successful-payment path and a failed-payment path.

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <mutex>
#include <chrono>
#include <thread>
#include <atomic>
#include <stdexcept>

// ---------------------------------------------------------------------
// Seat status as seen from outside. In this single-process demo a seat's
// AVAILABLE / LOCKED state is derived lazily from SeatLockProvider's lock
// table rather than stored per seat -- a seat becomes AVAILABLE again the
// instant its lock expires, with no background sweeper required for
// correctness (see SeatLockProvider below). BOOKED is recorded on the
// Booking, not mutated back onto the Seat, to keep this demo's data model
// small; a production system would flip a stored SeatStatus too.
// ---------------------------------------------------------------------
enum class SeatStatus { AVAILABLE, LOCKED, BOOKED };

// ---------------------------------------------------------------------
// Data hierarchy: dumb structs, no behaviour. City -> Theatre -> Screen
// -> Show -> Seat is a containment tree used for browsing; a Show is also
// addressable directly by id, which is all BookingService needs.
// ---------------------------------------------------------------------
struct Movie {
    std::string id;
    std::string title;
};

enum class SeatType { REGULAR, PREMIUM, RECLINER };

struct Seat {
    std::string id;        // e.g. "A12" -- unique within a show's seat map
    int row = 0, col = 0;
    SeatType type = SeatType::REGULAR;
    int price = 0;         // base price; tiering is a follow-up (Strategy)
};

struct Show {
    std::string id;
    Movie movie;
    std::string screenId;
    std::string city;
    long long startTime = 0;   // epoch seconds
    std::vector<Seat> seatMap;
};

struct Screen {
    std::string id;
    std::string name;
    std::vector<std::string> showIds;      // shows scheduled on this screen
};

struct Theatre {
    std::string id;
    std::string name;
    std::vector<Screen> screens;
};

struct City {
    std::string name;
    std::vector<Theatre> theatres;
};

// ---------------------------------------------------------------------
// SeatLock: one timed, user-owned claim over a set of seats. The moment a
// spec says "timeout / TTL / expires", store an absolute expiry instant --
// now() > expiry is the simplest, race-free expiry check.
// ---------------------------------------------------------------------
class SeatLock {
public:
    SeatLock(std::vector<std::string> seatIds, std::string userId,
             std::chrono::seconds ttl)
        : seatIds_(std::move(seatIds)), userId_(std::move(userId)),
          expiry_(std::chrono::steady_clock::now() + ttl) {}

    bool isExpired() const { return std::chrono::steady_clock::now() > expiry_; }
    const std::string& userId() const { return userId_; }
    const std::vector<std::string>& seatIds() const { return seatIds_; }

private:
    std::vector<std::string> seatIds_;
    std::string userId_;
    std::chrono::steady_clock::time_point expiry_;
};

// ---------------------------------------------------------------------
// SeatLockProvider: the concurrency core, and the only class in this whole
// program that needs to be thread-safe. One mutex-guarded map is the
// single source of truth for every seat claim.
// ---------------------------------------------------------------------
class SeatLockProvider {
public:
    explicit SeatLockProvider(std::chrono::seconds ttl) : ttl_(ttl) {}

    // Atomic: locks ALL requested seats or NONE. Returns false if any seat
    // is already held by a non-expired lock -- and on false, nothing is
    // mutated (no partial locks, no rollback needed).
    bool lockSeats(const Show& show, const std::vector<Seat>& seats,
                   const std::string& userId) {
        std::lock_guard<std::mutex> guard(mutex_);      // ONE critical section
        auto& showLocks = locks_[show.id];

        // Phase 1: verify EVERY seat is free (or held by an expired lock).
        for (const Seat& s : seats) {
            auto it = showLocks.find(s.id);
            if (it != showLocks.end() && !it->second.isExpired())
                return false;                            // taken -> claim nothing
        }

        // Phase 2: claim them all. Still holding the mutex, so no other
        // thread could have slipped in between phase 1 and phase 2.
        for (const Seat& s : seats)
            showLocks.insert_or_assign(s.id, SeatLock({s.id}, userId, ttl_));
        return true;
    }

    void unlockSeats(const Show& show, const std::vector<Seat>& seats,
                      const std::string& userId) {
        std::lock_guard<std::mutex> guard(mutex_);
        auto& showLocks = locks_[show.id];
        for (const Seat& s : seats) {
            auto it = showLocks.find(s.id);
            if (it != showLocks.end() && it->second.userId() == userId)
                showLocks.erase(it);                      // only the owner may unlock
        }
    }

    bool validateLock(const Show& show, const Seat& seat,
                       const std::string& userId) const {
        std::lock_guard<std::mutex> guard(mutex_);
        auto showIt = locks_.find(show.id);
        if (showIt == locks_.end()) return false;
        auto it = showIt->second.find(seat.id);
        return it != showIt->second.end()
            && !it->second.isExpired()
            && it->second.userId() == userId;              // still mine, still valid
    }

private:
    mutable std::mutex mutex_;                              // mutable: const validateLock locks too
    std::chrono::seconds ttl_;
    std::unordered_map<std::string,
        std::unordered_map<std::string, SeatLock>> locks_;  // showId -> seatId -> lock
};

// ---------------------------------------------------------------------
// Payment: an enum plus a switch in BookingService, not a polymorphic
// State hierarchy -- a three-outcome state machine doesn't earn one.
// ---------------------------------------------------------------------
enum class PaymentStatus { PENDING, SUCCESS, FAILED };

struct Payment {
    std::string id;
    int amount = 0;
    PaymentStatus status = PaymentStatus::PENDING;
};

enum class BookingStatus { CREATED, CONFIRMED, CANCELLED };

struct Booking {
    std::string id;
    std::string userId;
    Show show;
    std::vector<Seat> seats;
    BookingStatus status = BookingStatus::CREATED;
};

// ---------------------------------------------------------------------
// Observer: booking events fan out to subscribers without BookingService
// knowing who is listening. Email today; SMS and a waitlist trigger
// tomorrow, with zero changes to the publisher.
// ---------------------------------------------------------------------
enum class BookingEvent { CONFIRMED, PAYMENT_FAILED, SEATS_RELEASED };

class BookingObserver {
public:
    virtual ~BookingObserver() = default;
    virtual void onEvent(BookingEvent event, const Booking& booking) = 0;
};

class EmailNotifier : public BookingObserver {
public:
    void onEvent(BookingEvent event, const Booking& booking) override {
        std::cout << "[email] " << booking.userId
                  << " event=" << static_cast<int>(event)
                  << " booking=" << booking.id << "\n";
    }
};

// ---------------------------------------------------------------------
// BookingService: the conductor. It orchestrates lock -> pay -> confirm
// or release, and stays deliberately boring -- the one tricky invariant
// (no double-booking) is entirely inside SeatLockProvider.
// ---------------------------------------------------------------------
class BookingService {
public:
    BookingService(SeatLockProvider& lockProvider,
                   std::vector<BookingObserver*> observers)
        : lockProvider_(lockProvider), observers_(std::move(observers)) {}

    void addShow(const Show& s) { shows_.push_back(s); }

    std::vector<Show> searchShows(const std::string& city,
                                   const std::string& movie) {
        std::vector<Show> out;
        for (const Show& s : shows_)
            if (s.city == city && s.movie.title == movie)
                out.push_back(s);
        return out;
    }

    // Locks the seats (atomic); does NOT charge or confirm. A lock is a
    // reservation with a deadline, not a sale. Throws if someone else
    // already holds at least one of the requested seats.
    Booking createBooking(const std::string& userId, const Show& show,
                           const std::vector<Seat>& seats) {
        if (!lockProvider_.lockSeats(show, seats, userId))
            throw std::runtime_error("seats unavailable");

        Booking b;
        b.id     = nextBookingId();
        b.userId = userId;
        b.show   = show;
        b.seats  = seats;
        b.status = BookingStatus::CREATED;      // locked, awaiting payment
        return b;
    }

    // Re-validates the lock (payment success means nothing if the hold
    // already expired and someone else grabbed the seat), then branches
    // on the payment outcome.
    Booking confirmBooking(const Booking& booking, const Payment& payment) {
        Booking b = booking;

        for (const Seat& s : b.seats) {
            if (!lockProvider_.validateLock(b.show, s, b.userId)) {
                b.status = BookingStatus::CANCELLED;
                notify(BookingEvent::SEATS_RELEASED, b);    // lock expired under us
                return b;
            }
        }

        if (payment.status == PaymentStatus::SUCCESS) {
            b.status = BookingStatus::CONFIRMED;            // seats become BOOKED
            notify(BookingEvent::CONFIRMED, b);
        } else {                                             // FAILED or still PENDING
            lockProvider_.unlockSeats(b.show, b.seats, b.userId);
            b.status = BookingStatus::CANCELLED;
            notify(BookingEvent::PAYMENT_FAILED, b);
        }
        return b;
    }

private:
    void notify(BookingEvent event, const Booking& booking) {
        for (BookingObserver* obs : observers_)
            obs->onEvent(event, booking);
    }
    std::string nextBookingId() { return "BK" + std::to_string(++counter_); }

    SeatLockProvider& lockProvider_;
    std::vector<BookingObserver*> observers_;
    std::vector<Show> shows_;
    int counter_ = 0;
};

// ---------------------------------------------------------------------
// Driver: happy path, failed-payment path, and -- the point of this
// chapter -- two threads racing for the same seats, asserting exactly
// one winner. That assertion is the proof the design actually works.
// ---------------------------------------------------------------------
int main() {
    SeatLockProvider lockProvider(std::chrono::seconds(5));   // 5s hold
    EmailNotifier email;
    BookingService service(lockProvider, {&email});

    Show show;
    show.id = "S1";
    show.city = "NYC";
    show.movie = {"M1", "Inception"};
    show.seatMap = { {"A1"}, {"A2"}, {"A3"}, {"B1"} };
    service.addShow(show);

    std::vector<Seat> wanted = { {"A1"}, {"A2"} };

    // Two users race for the SAME seats. The mutex inside SeatLockProvider
    // serializes their check-then-claim, so exactly one can win.
    std::atomic<int> wins{0};
    auto attempt = [&](const std::string& user) {
        try { service.createBooking(user, show, wanted); ++wins; }
        catch (const std::exception&) { /* lost the race, expected */ }
    };
    std::thread t1(attempt, "alice");
    std::thread t2(attempt, "bob");
    t1.join(); t2.join();
    std::cout << "winners: " << wins.load() << "\n";           // exactly 1

    // Successful payment path: lock -> pay -> confirm.
    Booking b = service.createBooking("carol", show, { {"A3"} });
    Payment ok{"P1", 250, PaymentStatus::SUCCESS};
    Booking done = service.confirmBooking(b, ok);
    std::cout << "carol booking confirmed="
              << (done.status == BookingStatus::CONFIRMED) << "\n";

    // Failed payment path: lock -> pay fails -> seats released, event fired.
    Booking b2 = service.createBooking("dave", show, { {"B1"} });
    Payment bad{"P2", 250, PaymentStatus::FAILED};
    Booking done2 = service.confirmBooking(b2, bad);
    std::cout << "dave booking cancelled="
              << (done2.status == BookingStatus::CANCELLED) << "\n";

    return 0;
}