The real-world analogy: physical ticket booths and sand timers
Imagine walking up to the ticket window of a grand old theater in downtown:
- The Seating Map: Behind the cashier hangs a giant magnetic board showing all seats (F7, F8, etc.). This map represents permanent slots (Seats). The magnetic labels (AVAILABLE, HELD, SOLD) placed on top represent the SeatingState—which varies entirely per screening show.
- The Hourglass Hold (Two-Phase Lock): You ask for seats F7 and F8. The cashier places yellow "HELD" magnets on them and flips a 5-minute physical sand hourglass on the counter. While that sand is running, no one else standing in other lines can buy those seats. If you hand over your credit card and complete payment before the sand runs out, the cashier replaces the magnets with red "SOLD" labels. If you walk away or your card declines, the sand timer finishes, and the cashier immediately returns the magnets to "AVAILABLE" for the next guest.
In code, this is modeled as a two-phase check-and-set transaction with a lazy Time-To-Live (TTL) expiry stamp, protected by locking mechanisms to resolve concurrent booking races.
Scope it first
"Browse movies by city, pick a show, see the seat map, hold seats, pay, get a ticket. One city's catalog, ignore payments beyond success/failure callbacks, ignore pricing tiers — OK?"
And know what you're walking into: every other classic hides its concurrency question at the end — BookMyShow is the concurrency question. Two users, one seat, same second; everything else is supporting cast.
UML Class Diagram
The non-obvious modeling decision — the one graders watch for: a Seat is physical and permanent; its availability belongs to the Show. Screen 4's seat F7 exists once; whether it's free is a different fact for the 6 PM and 9 PM shows. So Show owns Map<Seat, ShowSeatState> where SeatState = AVAILABLE | LOCKED | BOOKED. Hanging state on Seat itself is the classic mistake here.
BookingStatus: PENDING → CONFIRMED | EXPIRED | CANCELLED — a small state machine again, because payment isn't instant.
The flow: lock → pay → confirm
Booking can't be atomic — payment takes a minute and might fail — so the flow is two-phase with a TTL:
- Lock. User picks seats → atomically transition each from
AVAILABLE → LOCKED(user, expiresAt = now + 7 min). Any seat unavailable → whole request fails (all-or-nothing; nobody wants half a family's seats). - Pay. A
PENDINGBooking exists; user completes payment with the gateway. - Confirm or release. Payment success →
LOCKED → BOOKED, bookingCONFIRMED. Failure or timeout → lock expires, seats return toAVAILABLE, bookingEXPIRED.
The TTL is the design's quiet hero: no user action is ever required to free a seat — abandonment self-heals. Expiry via lazy check (isLocked() = state == LOCKED && now < expiresAt) plus a sweeper; lazy checking means correctness never depends on the sweeper being on time.
The race, and the only acceptable answer
Two users hit "lock F7" in the same 10 ms. A read-then-write (if seat is available → mark locked) lets both see AVAILABLE and both proceed — double-booking, the cinema equivalent of the parking lot's last spot and a balance double-spend. The invariant must be enforced at the point of mutation.
Implementation
Below are complete implementations featuring O(1) checks, lazy TTL evaluation, and per-show lock synchronization.
Python
import time
import threading
from enum import Enum
from typing import Dict, List, Optional
class SeatState(Enum):
AVAILABLE = 1
LOCKED = 2
BOOKED = 3
class Seat:
def __init__(self, seat_id: str, row: str, number: int):
self.seat_id = seat_id
self.row = row
self.number = number
class ShowSeatState:
def __init__(self, seat: Seat):
self.seat = seat
self.state = SeatState.AVAILABLE
self.locked_by: Optional[str] = None
self.expires_at: float = 0.0
class Show:
def __init__(self, show_id: str, movie_title: str, seats: List[Seat]):
self.show_id = show_id
self.movie_title = movie_title
self.seat_map: Dict[str, ShowSeatState] = {s.seat_id: ShowSeatState(s) for s in seats}
self.lock = threading.Lock() # Per-show lock to prevent races
def is_seat_available(self, seat_id: str, now: float) -> bool:
seat_state = self.seat_map.get(seat_id)
if not seat_state:
return False
if seat_state.state == SeatState.AVAILABLE:
return True
if seat_state.state == SeatState.LOCKED and now > seat_state.expires_at:
return True # Lock expired lazily
return False
def lock_seats(self, seat_ids: List[str], user_id: str, duration_sec: int = 420) -> bool:
# Atomic lock check-and-set
with self.lock:
now = time.time()
# 1. Check all seats first
for seat_id in seat_ids:
if not self.is_seat_available(seat_id, now):
return False
# 2. Reserve all seats (All-or-Nothing)
for seat_id in seat_ids:
seat_state = self.seat_map[seat_id]
seat_state.state = SeatState.LOCKED
seat_state.locked_by = user_id
seat_state.expires_at = now + duration_sec
return True
def confirm_booking(self, seat_ids: List[str], user_id: str) -> bool:
with self.lock:
now = time.time()
for seat_id in seat_ids:
seat_state = self.seat_map.get(seat_id)
if not seat_state or seat_state.state != SeatState.LOCKED or seat_state.locked_by != user_id or now > seat_state.expires_at:
return False
for seat_id in seat_ids:
self.seat_map[seat_id].state = SeatState.BOOKED
return True
Java
import java.time.Instant;
import java.util.*;
import java.util.concurrent.locks.ReentrantLock;
enum SeatState { AVAILABLE, LOCKED, BOOKED }
class Seat {
String seatId;
String row;
int number;
Seat(String id, String r, int n) { this.seatId = id; this.row = r; this.number = n; }
}
class ShowSeatState {
Seat seat;
SeatState state = SeatState.AVAILABLE;
String lockedBy;
long expiresAt = 0;
ShowSeatState(Seat seat) { this.seat = seat; }
}
class Show {
String showId;
String movieTitle;
Map<String, ShowSeatState> seatMap = new HashMap<>();
final ReentrantLock lock = new ReentrantLock();
Show(String id, String title, List<Seat> seats) {
this.showId = id;
this.movieTitle = title;
for (Seat s : seats) {
seatMap.put(s.seatId, new ShowSeatState(s));
}
}
boolean isAvailable(String seatId, long now) {
ShowSeatState ss = seatMap.get(seatId);
if (ss == null) return false;
if (ss.state == SeatState.AVAILABLE) return true;
return ss.state == SeatState.LOCKED && now > ss.expiresAt;
}
public boolean lockSeats(List<String> seatIds, String userId, long durationSec) {
lock.lock();
try {
long now = Instant.now().getEpochSecond();
for (String seatId : seatIds) {
if (!isAvailable(seatId, now)) {
return false; // Already locked or booked
}
}
for (String seatId : seatIds) {
ShowSeatState ss = seatMap.get(seatId);
ss.state = SeatState.LOCKED;
ss.lockedBy = userId;
ss.expiresAt = now + durationSec;
}
return true;
} finally {
lock.unlock();
}
}
public boolean confirmBooking(List<String> seatIds, String userId) {
lock.lock();
try {
long now = Instant.now().getEpochSecond();
for (String seatId : seatIds) {
ShowSeatState ss = seatMap.get(seatId);
if (ss == null || ss.state != SeatState.LOCKED || !userId.equals(ss.lockedBy) || now > ss.expiresAt) {
return false;
}
}
for (String seatId : seatIds) {
seatMap.get(seatId).state = SeatState.BOOKED;
}
return true;
} finally {
lock.unlock();
}
}
}
C++
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <mutex>
#include <chrono>
#include <memory>
enum class SeatState { AVAILABLE, LOCKED, BOOKED };
class Seat {
public:
std::string seatId;
std::string row;
int number;
Seat(std::string id, std::string r, int n) : seatId(id), row(r), number(n) {}
};
struct ShowSeatState {
std::shared_ptr<Seat> seat;
SeatState state = SeatState::AVAILABLE;
std::string lockedBy = "";
long long expiresAt = 0;
ShowSeatState(std::shared_ptr<Seat> s) : seat(s) {}
};
class Show {
private:
std::string showId;
std::string movieTitle;
std::unordered_map<std::string, std::shared_ptr<ShowSeatState>> seatMap;
std::mutex mtx;
bool isAvailable(const std::string& seatId, long long now) {
auto it = seatMap.find(seatId);
if (it == seatMap.end()) return false;
if (it->second->state == SeatState::AVAILABLE) return true;
return it->second->state == SeatState::LOCKED && now > it->second->expiresAt;
}
public:
Show(std::string id, std::string title, const std::vector<std::shared_ptr<Seat>>& seats)
: showId(id), movieTitle(title) {
for (const auto& s : seats) {
seatMap[s->seatId] = std::make_shared<ShowSeatState>(s);
}
}
bool lockSeats(const std::vector<std::string>& seatIds, const std::string& userId, long long durationSec) {
std::lock_guard<std::mutex> lock(mtx);
long long now = std::chrono::duration_cast<std::chrono::seconds>(
std::chrono::system_clock::now().time_since_epoch()
).count();
for (const auto& seatId : seatIds) {
if (!isAvailable(seatId, now)) return false;
}
for (const auto& seatId : seatIds) {
auto ss = seatMap[seatId];
ss->state = SeatState::LOCKED;
ss->lockedBy = userId;
ss->expiresAt = now + durationSec;
}
return true;
}
bool confirmBooking(const std::vector<std::string>& seatIds, const std::string& userId) {
std::lock_guard<std::mutex> lock(mtx);
long long now = std::chrono::duration_cast<std::chrono::seconds>(
std::chrono::system_clock::now().time_since_epoch()
).count();
for (const auto& seatId : seatIds) {
auto it = seatMap.find(seatId);
if (it == seatMap.end() || it->second->state != SeatState::LOCKED ||
it->second->lockedBy != userId || now > it->second->expiresAt) {
return false;
}
}
for (const auto& seatId : seatIds) {
seatMap[seatId]->state = SeatState::BOOKED;
}
return true;
}
};
Interactive Quiz
1.
2.
3.
Walk a scenario
Asha and Rahul, both eyeing F7+F8 for the 9 PM show. Asha's lock request wins the mutex: both seats → LOCKED(asha), PENDING booking, 7-minute clock. Rahul's request enters the mutex 80 ms later, sees F7 LOCKED and unexpired → SeatUnavailable; UI offers the Strategy's next-best contiguous pair. Asha pays in 3 minutes → seats BOOKED, booking CONFIRMED, observers repaint the map. Had she abandoned: at minute 7 the seats lazily read as AVAILABLE again — no cleanup dependency, no stuck inventory.
Q&A
Practice — level up
BookMyShow is reserve under contention with a TTL. Drill the allocation and the expiry separately, then together:
Climb in order — every rung assumes the one above it. Solve on LeetCode, then tick it here; progress is saved on this device.
Warm-up — reserve a specific slot
- Seat Reservation ManagerMedium
Reserve the next free seat, release on cancel — the allocation core.
Core — expiry & time-versioned state
Tokens with a TTL — exactly the seat-lock that self-heals on timeout.
State versioned by time — reason about lock expiry windows.
Stretch — paired entry/exit
Check-in/check-out pairs and charge on completion.