Design a Movie Ticket Booking System in Java

Ticket booking is the classic "two people click the same seat" problem. The domain is small (shows, seats, bookings) but the design pressure is real: a seat must never be sold twice, a held seat must come back if the customer walks away, and a payment call must not freeze everyone else. The steps follow the LLD interview framework.

Requirements

Functional

A theater runs shows. Each show has a movie, a price per seat and a grid of seats.
A user selects one or more seats. The seats are held for a limited time (for example five minutes) while the user pays.
If payment succeeds, the booking is confirmed and the seats are sold. If the hold expires, or the user cancels, the seats are released.
A seat can never belong to two active bookings. A request for several seats succeeds fully or not at all.
Payment goes through a gateway that can fail.

Non-functional and scope

Concurrent requests for the same seat must produce exactly one winner.
Time must be injectable so expiry is testable without sleeping.
In memory. Search, pricing tiers, refunds and notifications are extensions. Movie and theater catalogs are reduced to fields on the show.

Entities

classDiagram
    class BookingService {
        -Object lock
        -Clock clock
        -PaymentGateway payments
        +addShow(...) ShowId
        +hold(show, user, seats) BookingId
        +confirm(booking, user)
        +cancel(booking, user)
    }
    class Show {
        +String movie
        +Cents price
        +TreeMap~Seat, SeatState~ seats
    }
    class SeatState {
        <<sealed interface>>
        Free
        Held(BookingId)
        Booked(BookingId)
    }
    class Booking {
        +ShowId show
        +UserId user
        +List~Seat~ seats
        +Cents amount
        +BookingStatus status
    }
    class BookingStatus {
        <<sealed interface>>
        Pending
        Confirming
        Confirmed
        Cancelled
        Expired
    }
    class Clock {
        <<java.time>>
        +instant() Instant
    }
    class PaymentGateway {
        <<interface>>
        +charge(user, amount)
    }
    BookingService *-- Show
    BookingService *-- Booking
    Show *-- SeatState
    Booking --> BookingStatus
    BookingService ..> Clock
    BookingService ..> PaymentGateway
    Clock <|-- FakeClock
    PaymentGateway <|.. FakePayment

SeatState and BookingStatus are sealed interfaces with record variants because each is a closed state machine, and some variants carry data (the holding booking, the deadline). Clock and PaymentGateway are the two places where the outside world enters, and tests substitute fakes. See testability and dependency injection. Seats point to bookings by BookingId and bookings point to shows by ShowId, so the object graph has no cycles (object graphs and references).

API

Java

ShowId BookingService.addShow(String movie, int rows, int perRow, Cents price)
BookingId BookingService.hold(ShowId show, UserId user, Collection<Seat> seats)   // throws BookingException
void BookingService.confirm(BookingId booking, UserId user)                      // throws BookingException
void BookingService.cancel(BookingId booking, UserId user)                       // throws BookingException

Failures throw an unchecked BookingException that carries a sealed BookingError (unknown show, seat unavailable, hold expired, and so on). The error is data, so a caller can switch over it. Unchecked is the choice because every method has several failure reasons, and a checked exception would add the same throws clause to every caller. The service is shared across request threads, and it protects its own state with one lock. See thread-safe components.

Design decisions

An injected clock makes expiry testable

Code that calls Instant.now() directly can only be tested by sleeping. The service instead asks a java.time.Clock. Production wires Clock.systemUTC() and tests wire a fake that only moves when told to. Clock is an abstract class, so the fake extends it and implements instant(), getZone() and withZone().

The fake is read by request threads and moved by the test thread. A plain Instant field written by one thread has no guarantee of being visible to another thread: Java only guarantees visibility across a synchronization action, such as a write and a later read of the same volatile field, or of an atomic variable. The fake stores the time in an AtomicReference<Instant>, so every advance happens-before the next instant() that observes it.

Java

import java.time.Clock;
import java.time.Duration;
import java.time.Instant;
import java.time.ZoneId;
import java.time.ZoneOffset;
import java.util.concurrent.atomic.AtomicReference;

public class Main {
    static class FakeClock extends Clock {
        private final AtomicReference<Instant> now;

        FakeClock(Instant start) {
            this.now = new AtomicReference<>(start);
        }

        void advance(Duration duration) {
            now.updateAndGet(current -> current.plus(duration));
        }

        @Override
        public Instant instant() {
            return now.get();
        }

        @Override
        public ZoneId getZone() {
            return ZoneOffset.UTC;
        }

        @Override
        public Clock withZone(ZoneId zone) {
            return this; // the fake ignores zones: only instant() is used
        }
    }

    static boolean isExpired(Clock clock, Instant expiresAt) {
        return !clock.instant().isBefore(expiresAt);
    }

    public static void main(String[] args) {
        var clock = new FakeClock(Instant.ofEpochSecond(1_000));
        var expiresAt = clock.instant().plusSeconds(300);
        System.out.println("expired at t=1000? " + isExpired(clock, expiresAt));
        clock.advance(Duration.ofSeconds(299));
        System.out.println("expired at t=1299? " + isExpired(clock, expiresAt));
        clock.advance(Duration.ofSeconds(1));
        System.out.println("expired at t=1300? " + isExpired(clock, expiresAt));
    }
}

Output

expired at t=1000? false
expired at t=1299? false
expired at t=1300? true

The hold lasts for [start, expiresAt), so at exactly expiresAt it is over. Choosing the boundary once and writing a test for it avoids off-by-one arguments later.

Expiry is lazy

Nothing needs to run in the background. Every operation first sweeps holds whose expiresAt has passed, marks those bookings Expired and frees their seats. A user who returns after the deadline finds the seats gone, and a competing user finds them free. This removes a timer thread and the races between it and request handling. A background sweeper is only an optimization for freeing memory.

The booking is a state machine

Code

Pending --start payment--> Confirming --payment ok--> Confirmed
   |   ^                        |
   |   +------payment fails-----+
   +--cancel--> Cancelled       Confirmed --cancel--> Cancelled
   +--deadline passes--> Expired

Confirming exists so the payment call can run without holding the lock. While a booking is Confirming, the sweeper leaves it alone, so the seats cannot be released and resold in the middle of a charge. If the charge fails, the booking returns to Pending with its original deadline. Data that only exists in some states, such as the deadline, lives in that variant. See state machines with sealed types.

Java

import java.time.Instant;

public class Main {
    sealed interface Status {
        record Pending(Instant expiresAt) implements Status {}
        record Confirming(Instant expiresAt) implements Status {}
        record Confirmed() implements Status {}
        record Cancelled() implements Status {}
        record Expired() implements Status {}
    }

    enum Event { START_PAYMENT, PAYMENT_OK, PAYMENT_FAILED, CANCEL, DEADLINE }

    static Status apply(Status status, Event event) {
        return switch (status) {
            case Status.Pending(var at) -> switch (event) {
                case START_PAYMENT -> new Status.Confirming(at);
                case CANCEL -> new Status.Cancelled();
                case DEADLINE -> new Status.Expired();
                case PAYMENT_OK, PAYMENT_FAILED -> throw notAllowed(status, event);
            };
            case Status.Confirming(var at) -> switch (event) {
                case PAYMENT_OK -> new Status.Confirmed();
                case PAYMENT_FAILED -> new Status.Pending(at);
                case START_PAYMENT, CANCEL, DEADLINE -> throw notAllowed(status, event);
            };
            case Status.Confirmed c -> switch (event) {
                case CANCEL -> new Status.Cancelled();
                case START_PAYMENT, PAYMENT_OK, PAYMENT_FAILED, DEADLINE -> throw notAllowed(status, event);
            };
            case Status.Cancelled c -> throw notAllowed(status, event);
            case Status.Expired e -> throw notAllowed(status, event);
        };
    }

    static IllegalStateException notAllowed(Status status, Event event) {
        return new IllegalStateException(event + " is not allowed in " + status);
    }

    public static void main(String[] args) {
        var path = new Event[] {
            Event.START_PAYMENT, Event.PAYMENT_FAILED, Event.START_PAYMENT, Event.PAYMENT_OK, Event.CANCEL
        };
        Status status = new Status.Pending(Instant.ofEpochSecond(300));
        for (var event : path) {
            status = apply(status, event);
            System.out.println(event + " -> " + status);
        }
        try {
            apply(new Status.Cancelled(), Event.PAYMENT_OK);
        } catch (IllegalStateException e) {
            System.out.println(e.getMessage());
        }
        try {
            apply(new Status.Confirming(Instant.ofEpochSecond(1)), Event.DEADLINE);
        } catch (IllegalStateException e) {
            System.out.println(e.getMessage());
        }
    }
}

Output

START_PAYMENT -> Confirming[expiresAt=1970-01-01T00:05:00Z]
PAYMENT_FAILED -> Pending[expiresAt=1970-01-01T00:05:00Z]
START_PAYMENT -> Confirming[expiresAt=1970-01-01T00:05:00Z]
PAYMENT_OK -> Confirmed[]
CANCEL -> Cancelled[]
PAYMENT_OK is not allowed in Cancelled[]
DEADLINE is not allowed in Confirming[expiresAt=1970-01-01T00:00:01Z]

The second-to-last line shows that terminal states accept nothing, and the last shows that a booking in the middle of a payment cannot expire. The nested switch expressions have no default branch, so adding a new event or status stops the code from compiling until every transition is decided.

Double booking is prevented by one lock and a check-then-act under it

The dangerous sequence is: thread A sees a seat free, thread B sees it free, both mark it taken. The fix is to make "check every requested seat, then mark all of them" one atomic step. All shows, seats and bookings live in one object guarded by one lock, and hold performs the check and the update inside one synchronized block. It validates every seat before changing any, so a request for [A3, A2] where A2 is taken leaves A3 free. This also keeps the state consistent when an exception is thrown: Java releases a synchronized lock on any exit, but it does not undo a half-finished update, so no update may start before its validation is complete.

Because every read and write of the state happens inside a block on the same lock, each block sees everything the previous block wrote (the lock release happens-before the next acquire), and no field needs to be volatile.

One lock serializes all bookings, which is correct and simple. Because critical sections are microseconds of in-memory work, this is fine at the scale of one cinema chain. The scaling path is one lock per show, since bookings for different shows never conflict. Correctness argument first, then optimize.

The payment call happens outside the lock

confirm runs in three steps: lock, validate and move to Confirming; unlock and call the gateway; lock again and record the result. Holding a lock across a network call would block every other customer for the duration of one slow charge. The Confirming state is what makes the middle step safe, and it also rejects a second concurrent confirm of the same booking, so a customer cannot be charged twice by a double click.

If the gateway throws, the service treats every RuntimeException as a failed charge and returns the booking to Pending. A booking stuck in Confirming would never expire and would hold its seats forever.

Payment is an interface

The gateway is the second boundary. FakePayment can be told to fail, and it records what it charged, so tests need no network.

Full implementation

Java

import java.time.Clock;
import java.time.Duration;
import java.time.Instant;
import java.time.ZoneId;
import java.time.ZoneOffset;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Optional;
import java.util.Random;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.concurrent.Callable;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicReference;

/** A clock that only moves when advance is called. Safe to share across threads. */
class FakeClock extends Clock {
    private final AtomicReference<Instant> now;

    FakeClock(Instant start) {
        this.now = new AtomicReference<>(start);
    }

    void advance(Duration duration) {
        now.updateAndGet(current -> current.plus(duration));
    }

    @Override
    public Instant instant() {
        return now.get();
    }

    @Override
    public ZoneId getZone() {
        return ZoneOffset.UTC;
    }

    @Override
    public Clock withZone(ZoneId zone) {
        return this;
    }
}

record ShowId(int id) {}

record UserId(int id) {}

record BookingId(int id) {}

record Cents(long amount) {
    Cents {
        if (amount < 0) {
            throw new IllegalArgumentException("amount must not be negative: " + amount);
        }
    }
}

record Seat(int row, int number) implements Comparable<Seat> {
    static Seat of(char row, int number) {
        return new Seat(row - 'A', number);
    }

    @Override
    public int compareTo(Seat other) {
        int byRow = Integer.compare(row, other.row);
        return byRow != 0 ? byRow : Integer.compare(number, other.number);
    }

    @Override
    public String toString() {
        return "" + (char) ('A' + row) + number;
    }
}

sealed interface SeatState {
    record Free() implements SeatState {}
    record Held(BookingId booking) implements SeatState {}
    record Booked(BookingId booking) implements SeatState {}
}

sealed interface BookingStatus {
    record Pending(Instant expiresAt) implements BookingStatus {}
    record Confirming(Instant expiresAt) implements BookingStatus {}
    record Confirmed() implements BookingStatus {}
    record Cancelled() implements BookingStatus {}
    record Expired() implements BookingStatus {}
}

sealed interface BookingError {
    record UnknownShow(ShowId show) implements BookingError {}
    record UnknownBooking(BookingId booking) implements BookingError {}
    record NoSeats() implements BookingError {}
    record SeatDoesNotExist(Seat seat) implements BookingError {}
    record SeatUnavailable(Seat seat) implements BookingError {}
    record NotOwner() implements BookingError {}
    record HoldExpired() implements BookingError {}
    record InvalidState(BookingStatus status) implements BookingError {}
    record PaymentFailed(String reason) implements BookingError {}
}

class BookingException extends RuntimeException {
    private final BookingError error;

    BookingException(BookingError error) {
        super(error.toString());
        this.error = error;
    }

    BookingError error() {
        return error;
    }
}

/** Throws PaymentException when the charge is declined. */
interface PaymentGateway {
    void charge(UserId user, Cents amount);
}

class PaymentException extends RuntimeException {
    PaymentException(String reason) {
        super(reason);
    }
}

class FakePayment implements PaymentGateway {
    private final AtomicBoolean failNext = new AtomicBoolean();
    private final List<Long> charged = new ArrayList<>();

    void failNextCharge() {
        failNext.set(true);
    }

    synchronized long totalCharged() {
        return charged.stream().mapToLong(Long::longValue).sum();
    }

    @Override
    public void charge(UserId user, Cents amount) {
        if (failNext.getAndSet(false)) {
            throw new PaymentException("card declined");
        }
        synchronized (this) {
            charged.add(amount.amount());
        }
    }
}

class BookingService {
    private static final class Show {
        final String movie;
        final Cents price;
        final TreeMap<Seat, SeatState> seats = new TreeMap<>();

        Show(String movie, Cents price) {
            this.movie = movie;
            this.price = price;
        }
    }

    private static final class Booking {
        final ShowId show;
        final UserId user;
        final List<Seat> seats;
        final Cents amount;
        BookingStatus status; // read and written only while holding the service lock

        Booking(ShowId show, UserId user, List<Seat> seats, Cents amount, BookingStatus status) {
            this.show = show;
            this.user = user;
            this.seats = seats;
            this.amount = amount;
            this.status = status;
        }
    }

    private final Clock clock;
    private final PaymentGateway payments;
    private final Duration holdTime;

    // All fields below are guarded by lock.
    private final Object lock = new Object();
    private final Map<ShowId, Show> shows = new HashMap<>();
    private final Map<BookingId, Booking> bookings = new HashMap<>();
    private int nextShow;
    private int nextBooking;

    BookingService(Clock clock, PaymentGateway payments, Duration holdTime) {
        this.clock = Objects.requireNonNull(clock);
        this.payments = Objects.requireNonNull(payments);
        this.holdTime = Objects.requireNonNull(holdTime);
    }

    ShowId addShow(String movie, int rows, int perRow, Cents price) {
        synchronized (lock) {
            var id = new ShowId(nextShow++);
            var show = new Show(movie, price);
            for (int r = 0; r < rows; r++) {
                for (int n = 1; n <= perRow; n++) {
                    show.seats.put(new Seat(r, n), new SeatState.Free());
                }
            }
            shows.put(id, show);
            return id;
        }
    }

    /** All-or-nothing: either every seat is held for this user or none is. */
    BookingId hold(ShowId showId, UserId user, Collection<Seat> seats) {
        if (seats.isEmpty()) {
            throw new BookingException(new BookingError.NoSeats());
        }
        var wanted = List.copyOf(new TreeSet<>(seats)); // sorted, duplicates removed
        synchronized (lock) {
            var now = clock.instant();
            expireHolds(now);
            var show = shows.get(showId);
            if (show == null) {
                throw new BookingException(new BookingError.UnknownShow(showId));
            }
            for (var seat : wanted) { // validate every seat before changing any
                var state = show.seats.get(seat);
                if (state == null) {
                    throw new BookingException(new BookingError.SeatDoesNotExist(seat));
                }
                if (!(state instanceof SeatState.Free)) {
                    throw new BookingException(new BookingError.SeatUnavailable(seat));
                }
            }
            var id = new BookingId(nextBooking++);
            for (var seat : wanted) {
                show.seats.put(seat, new SeatState.Held(id));
            }
            var amount = new Cents(Math.multiplyExact(show.price.amount(), (long) wanted.size()));
            bookings.put(id, new Booking(showId, user, wanted, amount, new BookingStatus.Pending(now.plus(holdTime))));
            return id;
        }
    }

    void confirm(BookingId id, UserId user) {
        // Step 1: validate and move to Confirming under the lock.
        Cents amount;
        synchronized (lock) {
            expireHolds(clock.instant());
            var booking = find(id);
            if (!booking.user.equals(user)) {
                throw new BookingException(new BookingError.NotOwner());
            }
            amount = switch (booking.status) {
                case BookingStatus.Pending(var expiresAt) -> {
                    booking.status = new BookingStatus.Confirming(expiresAt);
                    yield booking.amount;
                }
                case BookingStatus.Expired e -> throw new BookingException(new BookingError.HoldExpired());
                case BookingStatus.Confirming c -> throw new BookingException(new BookingError.InvalidState(c));
                case BookingStatus.Confirmed c -> throw new BookingException(new BookingError.InvalidState(c));
                case BookingStatus.Cancelled c -> throw new BookingException(new BookingError.InvalidState(c));
            };
        }

        // Step 2: the slow call, with no lock held. Any failure counts as a declined charge,
        // so the booking never stays in Confirming.
        Optional<String> failure = Optional.empty();
        try {
            payments.charge(user, amount);
        } catch (RuntimeException e) {
            failure = Optional.of(String.valueOf(e.getMessage()));
        }

        // Step 3: record the outcome.
        synchronized (lock) {
            var booking = bookings.get(id);
            if (!(booking.status instanceof BookingStatus.Confirming(var expiresAt))) {
                throw new IllegalStateException("only this call can leave Confirming");
            }
            if (failure.isEmpty()) {
                booking.status = new BookingStatus.Confirmed();
                var show = shows.get(booking.show);
                for (var seat : booking.seats) {
                    show.seats.put(seat, new SeatState.Booked(id));
                }
            } else {
                booking.status = new BookingStatus.Pending(expiresAt);
                throw new BookingException(new BookingError.PaymentFailed(failure.get()));
            }
        }
    }

    void cancel(BookingId id, UserId user) {
        synchronized (lock) {
            expireHolds(clock.instant());
            var booking = find(id);
            if (!booking.user.equals(user)) {
                throw new BookingException(new BookingError.NotOwner());
            }
            switch (booking.status) {
                case BookingStatus.Pending p -> cancelNow(booking, id);
                case BookingStatus.Confirmed c -> cancelNow(booking, id);
                case BookingStatus.Expired e -> throw new BookingException(new BookingError.HoldExpired());
                case BookingStatus.Confirming c -> throw new BookingException(new BookingError.InvalidState(c));
                case BookingStatus.Cancelled c -> throw new BookingException(new BookingError.InvalidState(c));
            }
        }
    }

    Optional<BookingStatus> status(BookingId id) {
        synchronized (lock) {
            expireHolds(clock.instant());
            return Optional.ofNullable(bookings.get(id)).map(b -> b.status);
        }
    }

    /** One line per row: {@code .} free, {@code h} held, {@code B} booked. */
    String seatMap(ShowId showId) {
        synchronized (lock) {
            expireHolds(clock.instant());
            var show = shows.get(showId);
            if (show == null) {
                throw new BookingException(new BookingError.UnknownShow(showId));
            }
            var out = new StringBuilder(show.movie).append('\n');
            int currentRow = -1;
            for (var entry : show.seats.entrySet()) {
                var seat = entry.getKey();
                if (seat.row() != currentRow) {
                    if (currentRow >= 0) {
                        out.append('\n');
                    }
                    out.append((char) ('A' + seat.row())).append(':');
                    currentRow = seat.row();
                }
                out.append(' ').append(switch (entry.getValue()) {
                    case SeatState.Free f -> '.';
                    case SeatState.Held h -> 'h';
                    case SeatState.Booked b -> 'B';
                });
            }
            return out.toString();
        }
    }

    // ---- helpers: the caller must hold the lock ----

    private Booking find(BookingId id) {
        var booking = bookings.get(id);
        if (booking == null) {
            throw new BookingException(new BookingError.UnknownBooking(id));
        }
        return booking;
    }

    private void cancelNow(Booking booking, BookingId id) {
        booking.status = new BookingStatus.Cancelled();
        release(booking, id);
    }

    /** Releases every hold whose deadline has passed. Bookings in Confirming are left alone. */
    private void expireHolds(Instant now) {
        var due = new ArrayList<BookingId>();
        for (var entry : bookings.entrySet()) {
            if (entry.getValue().status instanceof BookingStatus.Pending(var expiresAt) && !expiresAt.isAfter(now)) {
                due.add(entry.getKey());
            }
        }
        for (var id : due) {
            var booking = bookings.get(id);
            booking.status = new BookingStatus.Expired();
            release(booking, id);
        }
    }

    private void release(Booking booking, BookingId id) {
        var show = shows.get(booking.show);
        for (var seat : booking.seats) {
            if (ownedBy(show.seats.get(seat), id)) {
                show.seats.put(seat, new SeatState.Free());
            }
        }
    }

    private static boolean ownedBy(SeatState state, BookingId id) {
        return switch (state) {
            case SeatState.Free f -> false;
            case SeatState.Held(var booking) -> booking.equals(id);
            case SeatState.Booked(var booking) -> booking.equals(id);
        };
    }
}

public class Main {
    static void show(String label, Runnable action) {
        try {
            action.run();
            System.out.println(label + ": ok");
        } catch (BookingException e) {
            System.out.println(label + ": " + e.getMessage());
        }
    }

    public static void main(String[] args) throws Exception {
        var clock = new FakeClock(Instant.EPOCH);
        var payments = new FakePayment();
        var service = new BookingService(clock, payments, Duration.ofSeconds(300));
        var show = service.addShow("Metropolis", 3, 4, new Cents(1_250));
        var alice = new UserId(1);
        var bob = new UserId(2);
        var carol = new UserId(3);

        // Hold and confirm.
        var a = service.hold(show, alice, List.of(Seat.of('A', 1), Seat.of('A', 2)));
        service.confirm(a, alice);
        System.out.println("alice: " + service.status(a).orElseThrow() + ", charged " + payments.totalCharged());

        // Atomic: A3 stays free because A2 is taken.
        show("bob", () -> service.hold(show, bob, List.of(Seat.of('A', 3), Seat.of('A', 2))));
        System.out.println(service.seatMap(show));

        // Expiry on the fake clock.
        var b = service.hold(show, bob, List.of(Seat.of('B', 1)));
        clock.advance(Duration.ofSeconds(299));
        System.out.println("t=299 bob: " + service.status(b).orElseThrow());
        clock.advance(Duration.ofSeconds(1));
        System.out.println("t=300 bob: " + service.status(b).orElseThrow());
        var c = service.hold(show, carol, List.of(Seat.of('B', 1)));
        show("bob confirm", () -> service.confirm(b, bob));

        // A failed payment keeps the hold; a retry succeeds.
        payments.failNextCharge();
        show("carol confirm", () -> service.confirm(c, carol));
        System.out.println("carol status: " + service.status(c).orElseThrow());
        service.confirm(c, carol);
        System.out.println("carol status: " + service.status(c).orElseThrow() + ", charged " + payments.totalCharged());

        // Ownership and cancellation.
        show("bob cancels carol's", () -> service.cancel(c, bob));
        service.cancel(c, carol);
        System.out.println(service.seatMap(show));

        // Eight threads race for the same seat: exactly one wins.
        var contested = List.of(Seat.of('C', 1));
        var start = new CountDownLatch(1);
        var results = new ArrayList<Future<Boolean>>();
        try (var pool = Executors.newVirtualThreadPerTaskExecutor()) {
            for (int user = 10; user < 18; user++) {
                var id = new UserId(user);
                Callable<Boolean> task = () -> {
                    start.await();
                    try {
                        service.hold(show, id, contested);
                        return true;
                    } catch (BookingException e) {
                        assert e.error() instanceof BookingError.SeatUnavailable;
                        return false;
                    }
                };
                results.add(pool.submit(task));
            }
            start.countDown();
        }
        int won = 0;
        for (var result : results) {
            if (result.get()) {
                won++;
            }
        }
        System.out.println("winners " + won + ", rejected " + (results.size() - won));

        // Stress: 16 threads, 400 requests for 2 or 3 random seats in a 10 x 10 hall.
        var hall = service.addShow("Stress", 10, 10, new Cents(500));
        var granted = new ConcurrentLinkedQueue<List<Seat>>();
        try (var pool = Executors.newFixedThreadPool(16)) {
            for (int t = 0; t < 400; t++) {
                int seed = t;
                pool.submit(() -> {
                    var random = new Random(seed);
                    var request = new ArrayList<Seat>();
                    for (int k = 2 + random.nextInt(2); k > 0; k--) {
                        request.add(Seat.of((char) ('A' + random.nextInt(10)), 1 + random.nextInt(10)));
                    }
                    try {
                        service.hold(hall, new UserId(100 + seed), request);
                        granted.add(List.copyOf(new TreeSet<>(request)));
                    } catch (BookingException e) {
                        // seat taken by an earlier request: the request changed nothing
                    }
                });
            }
        }
        var seen = new TreeSet<Seat>();
        int duplicates = 0;
        int grantedSeats = 0;
        for (var seats : granted) {
            for (var seat : seats) {
                grantedSeats++;
                if (!seen.add(seat)) {
                    duplicates++;
                }
            }
        }
        long heldCells = service.seatMap(hall).lines().skip(1).flatMapToInt(String::chars).filter(ch -> ch == 'h').count();
        System.out.println("stress: some holds granted " + !granted.isEmpty()
            + ", double-booked seats " + duplicates
            + ", held cells match granted seats " + (heldCells == grantedSeats));
    }
}

Output

alice: Confirmed[], charged 2500
bob: SeatUnavailable[seat=A2]
Metropolis
A: B B . .
B: . . . .
C: . . . .
t=299 bob: Pending[expiresAt=1970-01-01T00:05:00Z]
t=300 bob: Expired[]
bob confirm: HoldExpired[]
carol confirm: PaymentFailed[reason=card declined]
carol status: Pending[expiresAt=1970-01-01T00:10:00Z]
carol status: Confirmed[], charged 3750
bob cancels carol's: NotOwner[]
Metropolis
A: B B . .
B: . . . .
C: . . . .
winners 1, rejected 7
stress: some holds granted true, double-booked seats 0, held cells match granted seats true

The output lines correspond to the requirements one by one: a confirmed booking is charged once; a partly conflicting request changes nothing; a hold survives at t=299 and is gone at t=300; a failed charge leaves the booking retryable; and the race has one winner. The race and the stress test print only counts and invariants, since which thread wins is not deterministic. Waiting for every task before printing keeps the output stable: closing an ExecutorService in try-with-resources waits for submitted tasks to finish, and Future.get waits for one result. In the stress run the number of granted requests varies between runs, but the number of double-booked seats is always zero, and the seats counted from the seat map always match the seats granted.

Extensions

Follow-up	Approach
Scale beyond one lock	Give each `Show` its own lock, with its bookings inside it, and keep a `ConcurrentHashMap<ShowId, Show>` for the index. Bookings for different shows stop contending. In a multi-server system the same idea becomes a conditional write in a database: `UPDATE seat SET state='held' WHERE state='free'`, checking the affected row count.
Cheaper expiry	Every operation scans all bookings. Keep a `PriorityQueue` of `(deadline, bookingId)` and pop only the entries that are due.
Background expiry	A `ScheduledExecutorService` calls the sweep every second. Lazy expiry stays as the correctness guarantee, so a late timer never causes a wrong answer.
Refunds on cancel	Add `refund(user, amount)` to `PaymentGateway`, and make `Confirmed -> Cancelled` a two-step transition with a `Refunding` state, for the same reason `Confirming` exists.
Seat pricing tiers	Replace the flat `price` with a `PricingPolicy` interface taking a seat and returning `Cents`. Only `hold` changes.
Idempotent confirm	Accept a client-supplied request ID and store the result, so a retried confirm after a timeout does not charge twice.
Notifications	Publish `BookingConfirmed` events to a subscriber list; see event bus and observers and design a notification service.
Max seats per user, blocked seats	A new validation step in `hold`. Blocked seats are a fourth `SeatState` variant.

Interview points

A seat can be sold once: check every requested seat and mark all of them in one critical section, validating everything before mutating anything.
Hold expiry is lazy. Every operation sweeps expired holds first, so no timer thread is needed for correctness.
The clock and the payment gateway are injected. A controllable clock makes expiry tests instant.
The booking lifecycle is a sealed type. Confirming lets the payment call run outside the lock without losing the seats.
A stress test with many threads checks the invariant (no seat in two bookings) instead of a particular interleaving.

Summary

Model both seat and booking lifecycles as sealed interfaces so every state and transition is explicit and matched exhaustively.
Inject the clock and the payment gateway. A fake clock backed by an atomic reference makes expiry tests instant and deterministic.
Expire holds lazily at the start of every operation. No background thread is needed for correctness.
Prevent double booking by checking all requested seats and marking them within one critical section, validating everything before mutating anything.
Never hold the lock across the payment call. A Confirming state protects the seats while the lock is released.
Reference seats, bookings and shows by ID, and keep all state behind one lock until measurement says to split it.
Test concurrency by checking invariants after many racing threads finish, and print counts rather than interleavings.