LLD-008 · LOW LEVEL DESIGN

Movie Ticket Booking

Protect scarce seats with atomic holds, deadline checks and explicit late-payment repair.

Local Java 21 reference verified: 26 checks. Learner drafts are not executed. Author self-review; independent review pending.

Existing introductory lesson · Version 1

Understand the problem

Design seat reservation for several shows. Hold a group atomically for one owner until a deadline, confirm a trusted successful payment, and handle expiry, cancellation and duplicate callbacks without selling the same seat twice. Explain why payment success cannot overrule ownership that has already expired.

Before you start

• Atomic compound updates
• Leases and authoritative deadlines
• Idempotency fingerprints
• Money versus inventory outcomes

Scope and explicit decisions

• In-memory inventory across configured shows and named seats. Each seat costs one configured positive minor-unit price; show-seat identity matters. Search, seat-map rendering, real payment processing, authentication, durable storage and a waiting room are not implemented.
• A hold is all-or-nothing over a nonempty seat set. HELD and CONFIRMED both own their seats. A HELD record expires when expiresAt<=trusted now. CONFIRMED ownership does not expire.
• Time is a nonnegative, nondecreasing elapsed-unit value supplied by a trusted adapter. New operations and duplicate holds advance time and sweep all expired HELD records. A read through get shows the last processed state and does not itself advance time.
• TTL and total price use checked arithmetic before allocation. A valid operation that advances time may expire unrelated old holds even if its requested seats remain unavailable; rejection does not undo the passage of time.
• hold keys are scoped to the inventory and fingerprint show, seat set, owner and TTL. Same key resolves the same hold identity; a retry cannot extend its deadline or create a new hold after expiry. Set iteration order does not change identity.
• confirm accepts an authenticated completed-payment fact from a trusted adapter, not an unverified browser receipt. Owner and amount must match the stored hold. The implementation does not actually charge or refund money.
• A first valid payment confirms only a still-HELD record. Payment after EXPIRED/CANCELLED, or another distinct successful payment after CONFIRMED, records REFUND_REQUIRED without changing seat ownership. A matching duplicate payment returns its stored result; conflicting reuse fails.
• cancel releases an unconfirmed HELD record or returns its existing terminal state. Confirmed booking cancellation requires a separate refund policy/workflow and is rejected here. A refund obligation is a recorded result, not proof the external refund occurred.
• Hold, command and payment histories remain in memory for the process lifetime. Restart loses ownership and dedupe state; a durable multi-process adapter is a Staff design extension.

Worked examples

Try before revealing

Requirements and invariants

R1 — Allocate every requested show-seat or none, with at most one owner per seat. hold protects I1.

R2 — Expiry and cancellation release only seats still owned by that hold. release protects I2.

R3 — Late or duplicate successful charges cannot acquire another owner’s seats. confirm protects I3.

I1: Each HELD/CONFIRMED seat maps to exactly its hold ID; no seat has two active owners.

I2: Terminal unconfirmed holds own no seats. Conditional release cannot remove a later hold’s ownership.

I3: Each payment ID has one immutable request fingerprint and one stored confirmation/refund outcome.

Derive the design

Availability display is not an allocation decision

A seat-map reader can show which seats appear available, but read-then-write from independent callers permits both to observe the same free seat. Start with a single atomic service decision: validate the whole group and claim it under one owner. The reference adds time-limited holds and immutable IDs before payment integration so scarce ownership remains authoritative.

Alternative: Per-seat locks can permit unrelated seats to progress, but group claims need deterministic lock ordering and shared hold/payment records. A database conditional update or transaction can coordinate multiple processes; a JVM lock cannot. A waiting room reduces pressure but does not replace ownership checks.

Responsibilities and ownership

Method contracts

What, when, why and how

Each concept is attached to the requirement it protects, its implementation, an alternative and a test.

Read and run the Java reference

1import java.util.*;
2/** Local multi-show seat inventory. Payment arguments come from a trusted completed-payment adapter. */
3public final class Solution {
4    private Solution() {}
5    public enum State { HELD, CONFIRMED, EXPIRED, CANCELLED }
6    public enum Outcome { BOOKED, REFUND_REQUIRED }
7    public record Hold(String id,String show,Set<String> seats,String owner,long expiresAt,long amount,State state){public Hold{seats=Set.copyOf(seats);}}
8    public record Confirmation(String paymentId,String holdId,Outcome outcome){}
9    private record Seat(String show,String seat){}
10    private record Request(String show,Set<String> seats,String owner,long ttl){public Request{seats=Set.copyOf(seats);}}
11    private record Operation(Request request,String holdId){}
12    private record Payment(String holdId,String owner,long amount,Confirmation result){}
13    private static void id(String s){if(s==null||s.isBlank())throw new IllegalArgumentException("identifier");}
14    public static final class Inventory {
15        private final Map<String,Set<String>> shows=new HashMap<>();
16        private final long price;
17        private final Map<Seat,String> ownership=new HashMap<>();
18        private final Map<String,Hold> holds=new LinkedHashMap<>();
19        private final Map<String,Operation> operations=new HashMap<>();
20        private final Map<String,Payment> payments=new HashMap<>();
21        private long sequence,time;
22        public Inventory(Map<String,Set<String>> shows,long price){if(price<1)throw new IllegalArgumentException("price");this.price=price;shows.forEach((show,seats)->{id(show);seats.forEach(Solution::id);this.shows.put(show,Set.copyOf(seats));});}
23        private void at(long now){if(now<time)throw new IllegalArgumentException("time");time=now;expire();}
24        private static Hold state(Hold h,State s){return new Hold(h.id(),h.show(),h.seats(),h.owner(),h.expiresAt(),h.amount(),s);}
25        private void release(Hold h){for(String seat:h.seats())ownership.remove(new Seat(h.show(),seat),h.id());}
26        private void expire(){for(var h:new ArrayList<>(holds.values()))if(h.state()==State.HELD&&h.expiresAt()<=time){release(h);holds.put(h.id(),state(h,State.EXPIRED));}}
27        public synchronized Hold hold(String show,Set<String> seats,String owner,long ttl,String key,long now){
28            id(owner);id(key);if(seats==null||seats.isEmpty()||ttl<1)throw new IllegalArgumentException("request");
29            var request=new Request(show,seats,owner,ttl);var previous=operations.get(key);
30            if(previous!=null){if(!previous.request().equals(request))throw new IllegalArgumentException("key reused");at(now);return get(previous.holdId());}
31            var configured=shows.get(show);if(configured==null||!configured.containsAll(seats))throw new IllegalArgumentException("seats");
32            long deadline=Math.addExact(now,ttl),amount=Math.multiplyExact(price,seats.size());at(now);
33            for(String seat:seats)if(ownership.containsKey(new Seat(show,seat)))throw new IllegalStateException("unavailable");
34            var h=new Hold("H"+(++sequence),show,seats,owner,deadline,amount,State.HELD);
35            holds.put(h.id(),h);for(String seat:seats)ownership.put(new Seat(show,seat),h.id());operations.put(key,new Operation(request,h.id()));return h;
36        }
37        public synchronized Confirmation confirm(String holdId,String owner,String paymentId,long amount,long now){
38            id(paymentId);var prior=payments.get(paymentId);
39            if(prior!=null){if(!prior.holdId().equals(holdId)||!prior.owner().equals(owner)||prior.amount()!=amount)throw new IllegalArgumentException("payment reused");return prior.result();}
40            var h=get(holdId);if(!h.owner().equals(owner)||h.amount()!=amount)throw new IllegalArgumentException("owner or amount");at(now);h=get(holdId);
41            Outcome outcome;
42            if(h.state()==State.HELD){holds.put(h.id(),state(h,State.CONFIRMED));outcome=Outcome.BOOKED;}
43            else outcome=Outcome.REFUND_REQUIRED; // Includes a second distinct successful payment after confirmation.
44            var result=new Confirmation(paymentId,holdId,outcome);payments.put(paymentId,new Payment(holdId,owner,amount,result));return result;
45        }
46        public synchronized Hold cancel(String holdId,String owner,long now){var h=get(holdId);if(!h.owner().equals(owner))throw new IllegalArgumentException("owner");at(now);h=get(holdId);if(h.state()==State.CONFIRMED)throw new IllegalStateException("confirmed cancellation needs refund workflow");if(h.state()==State.HELD){release(h);h=state(h,State.CANCELLED);holds.put(h.id(),h);}return h;}
47        public synchronized Hold get(String id){var h=holds.get(id);if(h==null)throw new IllegalArgumentException("hold");return h;}
48        public synchronized String ownerOf(String show,String seat,long now){at(now);return ownership.get(new Seat(show,seat));}
49        public synchronized boolean invariantHolds(){
50            int count=0;for(var h:holds.values())if(h.state()==State.HELD||h.state()==State.CONFIRMED){for(String s:h.seats()){count++;if(!h.id().equals(ownership.get(new Seat(h.show(),s))))return false;}}
51            return count==ownership.size();
52        }
53    }
54}
55

Complexity and limits

• A fresh hold/confirm/cancel advances time and scans H retained holds for expiry: O(H+K) expected work for K group seats, plus checked fixed-width amount arithmetic.
• ownerOf also sweeps expiry; it is not a free O(1) read in this implementation. get is expected O(1) without clock advancement. invariantHolds recounts all active seat memberships.
• Space is O(configured seats + active ownership + retained hold/operation/payment histories). History is unbounded over process lifetime; no persistence or retention cleanup is implemented.
• A single monitor provides local atomicity but serializes unrelated shows. Per-show partitioning is a plausible next boundary if payment/hold identities and cross-show groups are explicitly scoped.

Walk through the actual reference

These walkthrough fixtures are emitted only after the Java harness verifies their operations and expected state. Concurrency tests additionally exercise competing callers.

Mistakes and counterexamples

Engineer → Senior → Staff

Open focused practice →

Provenance and scope of evidence

Original teaching material. The local contract is implemented by Solution.java and tested by Test.java on Java 21. Distributed persistence, real provider/device adapters and deployment are not claimed.

Reference verification is not independent editorial review, production deployment verification or a claim that distributed adapters are implemented.