Cross-Problem Synthesis Problems 1–21

This section spans all twenty-one problems in this document. The same handful of lessons recur throughout — the value of working through this many problems isn't twenty-one independent tricks, it's watching a small set of ideas (check-then-act races, idempotent retries, template-vs-snapshot splits, and a short list of patterns) show up again and again in different clothing.

Pattern → Problem Map

Pattern	Appears In	Consistent Role It Plays
Strategy	Parking Lot (allocation, pricing), Rate Limiter (algorithm), Splitwise (split computation), Ride-Sharing (matching, fare), Notification System (channel, rate-limit reuse), Coffee Machine (payment), Pub-Sub (overflow policy), Elevator (dispatch), Tic-Tac-Toe (winning check, AI move), ATM (transaction type), Library (fine calculation), Hotel (pricing), Movie Ticket Booking (seat pricing), Food Delivery (delivery-partner assignment), E-commerce (pricing pipeline), Stock Brokerage (order execution)	Isolates an algorithm that the interviewer is expected to change mid-round — the single most reliable "extend this" test across every problem in this document, appearing in some form in 15 of the 21
Factory / Factory Method	Rate Limiter (algorithm selection), Splitwise (strategy resolution), Notification System (channel resolution), Library (catalog item subtype)	Resolves an enum/config value to the right Strategy instance or subtype, keeping the caller free of a growing if/else chain
Facade	Every multi-class problem's top-level service (ParkingLot, RateLimiter, SplitwiseService, RideService, LoggerFactory, NotificationService, CoffeeMachine, FileSystem, PubSubBroker, Dispatcher, GameEngine, ChessGame, ATM, Library, Hotel, BookingService, OrderService, CheckoutService, ChatService, Broker)	The single orchestration entry point callers use, hiding internal collaborators — the one pattern present in essentially all twenty-one problems
Decorator	Ride-Sharing (surge over fare), E-commerce (stackable cart add-ons)	The right choice specifically when a behavior is a composable modifier — stackable, order-independent-ish, layered over a base — not a mutually exclusive alternative to it; E-commerce (Problem 19) makes the Decorator-vs-Strategy boundary fully explicit for the first time in this document
State (or state-like guarded transitions)	Ride-Sharing (ride lifecycle), Coffee Machine (Idle/Selecting/Dispensing/OutOfStock), Elevator (Idle/Moving/DoorsOpen/OutOfService), ATM (Idle/CardInserted/Authenticated/Dispensing), Movie Ticket Booking (ShowSeat: Available/Locked/Booked), Food Delivery (OrderState), E-commerce (OrderState)	Used when illegal transitions are a real correctness risk, not just cosmetic status tracking — the density of State usage climbs sharply in the second half of this document as the problems lean more device/order-lifecycle-shaped
Observer	Ride-Sharing (ride-status notifications), Notification System (event triggers), Coffee Machine (optional low-inventory alerts), Pub-Sub (the entire product), Library (hold-queue availability), Hotel (booking confirmation), Movie Ticket Booking (waitlist), Food Delivery (status push), Chat Application (the conversation itself, as both Mediator and Observer subject), Stock Brokerage (price-feed subscription driving pending limit orders)	Decouples "something happened" from "who needs to know" — starts as an optional hook in Problems 5/7/8, becomes the foundational structure Problem 10 generalizes to, gets reused as a small instance five more times in Problems 15–18, converges as the structural core of Problem 20, and reappears once more in Problem 21 as the mechanism that avoids polling a price feed
Singleton — justified once, rejected everywhere else it's tempting	Justified: Logging Framework's LoggerFactory/registry. Explicitly rejected: Parking Lot (ParkingLot), Ride-Sharing (RideService), Elevator (Dispatcher), Stock Brokerage (Broker)	The contrast is the lesson — Singleton is correct exactly when there is genuinely one process-wide coordination point with no meaningful alternative construction (a logger registry); it's a naive shortcut everywhere it's used to avoid passing a dependency, and it shows up as a tempting-but-wrong choice for coordinator/dispatcher classes specifically, four separate times in this document
Chain of Responsibility	Logging Framework (log-level threshold checks), ATM (denomination-handler cash dispensing)	Fits naturally when a request should be handled — or passed along — by a sequence of independent handlers, each with veto or partial-handling power
Composite	File System (File/Directory hierarchy)	Unifies leaf and container nodes under one interface so client code never needs to branch on which it has
Visitor	File System (DiskUsageVisitor, SearchVisitor)	Keeps an ever-growing set of read-only aggregate operations out of the base node interface — a direct ISP payoff, added as new classes rather than new methods
Iterator	File System (directory traversal)	Separates "how to walk the structure" from "what to do at each node," letting the same traversal support multiple aggregate operations without duplicating walk logic
Template Method — rejected once, used once, then made explicitly conditional a third time	Rejected: Coffee Machine's per-beverage brewing. Present: Notification System's shared send-pipeline. Explicitly conditional/deferred: Tic-Tac-Toe's TurnBasedGame — build only once a second game genuinely needs the shared skeleton	The distinguishing question is always the same: do subclasses genuinely need to override specific steps of a fixed algorithm (Notification System, yes), or is the "variation" actually just data (Coffee Machine's Recipe, no) — and is a second concrete case even in scope yet (Tic-Tac-Toe, not unless asked)
Builder	Hotel Reservation System (ReservationRequestBuilder for a request with several optional parts)	Fits when construction has multiple optional, independently-meaningful parts that don't all apply every time — the alternative is a telescoping constructor or validating partial state ad hoc throughout the object's life
Command	Chess Game (Move with execute()/undo(), backed by a MoveHistory stack)	Fits when an action needs to be represented as a first-class object specifically because it must be queued, logged, or reversed later — undo/redo is the canonical justification, and Chess is the one problem in this document that genuinely needs it
Mediator	Chat Application (GroupConversation decoupling participants from direct references to each other)	Fits specifically when a growing number of peer objects would otherwise need direct references to each other (an O(n²) mesh) — Chat's Conversation plays this role simultaneously with its Observer role, which is the clearest illustration in this document that these two patterns solve different problems and can coexist on the same class
Explicitly-considered-and-rejected patterns as a design-maturity signal	Splitwise (Payment as sibling, not subclass, of Expense), Ride-Sharing (Decorator, not a second Strategy, for surge), Notification System (Bridge for category×channel), Coffee Machine (Template Method for brewing), Pub-Sub (Bridge for delivery-model × persistence), Elevator (Singleton for Dispatcher), Chess (Strategy for piece movement — type and movement rule always change together), E-commerce (Strategy for add-ons / Decorator for pricing pipeline — the roles, not just the patterns, would be swapped), Stock Brokerage (Singleton for Broker)	Naming a plausible-looking pattern and explaining precisely why it doesn't fit is a stronger signal than reaching for any pattern reflexively — this shows up explicitly in nine of the twenty-one problems in this document, spanning every major pattern family

Cross-Problem Comparison

Problem	Primary Concept	Main Design Challenge	Important Pattern	Concurrency	Difficulty
Parking Lot	Resource allocation	Atomic check-and-occupy on a shared spot	Strategy (allocation + pricing)	Check-then-act race on spot state	Beginner → Intermediate
LRU Cache	O(1) cache eviction	Recognizing "get is a write" for LRU ordering	Whole-class Strategy (not field-level) for eviction policy	Lock contention on every read; sharding as the scale answer	Intermediate
Rate Limiter	Traffic control algorithms	Timestamp-as-parameter for testability; distributed atomicity	Strategy + Factory over algorithms	Per-client fine-grained locks; Redis Lua-script atomicity distributed	Intermediate → Advanced
Splitwise	Ledger correctness	Sum-to-zero invariant under concurrent writes; debt simplification	Strategy (splits); Payment as sibling, not subclass, of Expense	Multi-pair consistent lock ordering; idempotent settle-up	Intermediate → Advanced
Ride-Sharing	Real-time matching + lifecycle	Atomic driver reservation; two independent strategies (match, fare); LLD/HLD boundary	Strategy + Decorator + State + Observer, all in one problem	Double-booking race on driver status; high-frequency location writes	Advanced
Logging Framework	Configurable, extensible logging pipeline	Threshold filtering and multi-destination fan-out without a growing if/else chain	Chain of Responsibility (level filtering); Singleton (justified, contrast with Problems 1/5/11)	Async appender queue with an explicit overflow policy; thread-safe registry access	Intermediate (Pattern Showcase)
Notification System	Multi-channel event notification	Per-channel send pipeline plus dedupe/rate-limiting, reusing Problem 3's RateLimiter directly	Template Method (send pipeline); Factory (channel resolution); Bridge explicitly rejected	Idempotent dedupe under retries; rate-limiter reuse's existing concurrency guarantees	Intermediate → Advanced
Coffee Vending Machine	Physical-device state machine	Atomic, all-or-nothing ingredient reservation with rollback; Template Method explicitly rejected	State (headline); Strategy (payment)	Shared-hopper check-then-act race across brewing slots — smallest-scale instance of the recurring race	Beginner → Intermediate
File System	Hierarchical resource tree	Uniform file/directory treatment; keeping aggregate queries off the base node interface; deadlock-free cross-directory move	Composite (headline); Visitor; Iterator	Readers-writer lock per node; canonical-path lock ordering for move()	Intermediate → Advanced
Pub-Sub / Message Queue	Asynchronous fan-out messaging	Backpressure under a slow subscriber; idempotent consumers under at-least-once delivery; per-partition-only ordering	Observer (foundational, generalizing Problems 5/7/8); Strategy (overflow policy)	Bounded per-subscriber queues; retry/dead-letter handling; ordering-scope trade-off is central	Advanced + Concurrency
Elevator System	Real-time dispatch + device lifecycle	Atomic select-then-claim hall-call assignment; SCAN-style per-car scheduling	State (car lifecycle); Strategy (dispatch); Singleton explicitly rejected for Dispatcher	Double-assignment race on hall-call selection, same shape as Ride-Sharing's driver race	Intermediate → Advanced+Concurrency
Tic-Tac-Toe / Board Game Engine	Generic rule-checking over a grid	A direction-scan win-check that generalizes to K-in-a-row, not hardcoded win-lines; Player polymorphism over a boolean flag	Strategy (winning check, AI move); Template Method explicitly deferred pending a second game	None load-bearing — the pattern-boundary lessons are the point of this problem	Beginner → Intermediate (Pattern Showcase)
Chess Game	Rule-bound simulate-then-commit moves	Move as a first-class, reversible Command; check detection reusing getValidMoves() rather than a duplicate algorithm	Command (headline, undo/redo via MoveHistory); Strategy explicitly rejected for piece movement	Not the focus — single-player-turn correctness (simulate → validate → commit) is the design challenge instead	Intermediate → Advanced
ATM Machine	Cross-channel financial state machine	Debit-before-dispense ordering with compensating credit on failure; greedy denomination dispensing	State (headline, ATM lifecycle); Chain of Responsibility (denomination handlers); Strategy (transaction type)	Cross-channel check-then-act balance race, same shape as Parking Lot/Splitwise	Intermediate
Library Management System	Catalog metadata vs. per-copy lifecycle	Book/BookItem split; FIFO hold queue with availability notification	Observer (hold queue, small instance); Strategy (fines); Factory Method (catalog item type)	Check-then-act race on the last available copy of a title	Intermediate
Hotel Reservation System	Date-range availability	Availability as an interval structure, not a boolean flag; multi-part reservation request construction	Builder (headline, reservation request); Strategy (pricing); Observer (booking notifications)	Check-then-act race on overlapping date-range bookings; DB exclusion-constraint alternative discussed	Intermediate → Advanced+Concurrency
Movie Ticket Booking System	High-contention seat inventory	Seat/ShowSeat split under real contention; TTL soft lock → payment-gated hard commit; multi-seat deadlock avoidance	State (headline, ShowSeat lifecycle); Strategy (pricing); Observer (waitlist)	The concurrency showcase of the document: canonical lock ordering for multi-seat holds; idempotent payment confirmation	Advanced (Concurrency Showcase)
Restaurant / Food Delivery System	Order lifecycle + delivery dispatch	MenuItem/OrderLineItem price-snapshot split; atomic select-then-claim delivery-partner assignment	State (headline, order lifecycle); Strategy (assignment); Observer (status push, reusing Pub-Sub)	Select-then-claim race on delivery partners (Elevator's dispatcher race, reapplied); out-of-order/duplicate status events	Intermediate → Advanced
E-commerce Shopping Cart & Checkout	Composable pricing + inventory correctness	Decorator (add-ons) vs. Strategy (pricing pipeline) boundary, made fully explicit; Cart/Order mutable-vs-frozen split	Decorator (headline, add-ons); Strategy (pricing pipeline); State (order lifecycle)	Check-then-act inventory decrement race; multi-item checkout deadlock avoidance; idempotent payment webhook	Intermediate → Advanced
Chat Application (WhatsApp-style)	Real-time multi-party messaging	Conversation as both Mediator (decouples participants) and Observer subject (delivery fan-out) — the capstone of the document's Observer arc	Mediator (group chat); Observer (headline, closing the arc from Problems 5/7/10/15–18); State (per-recipient message receipts)	Server-assigned per-conversation ordering; idempotent cursor-based reconnect replay; multi-device presence race	Advanced
Stock Brokerage System	Financial account correctness under concurrency	Reserve-then-settle funds/holdings so concurrent orders on one account can't double-spend or oversell; feed-execution vs. real order-matching scope boundary	Strategy (market/limit execution); Observer (price-feed subscription); Facade (Broker)	Atomic reserve per account; cancel-vs-execute race on order status; per-account lock granularity gives free parallelism across users	Advanced (Concurrency & Consistency)

Recurring Interview Signals Across All Twenty-One

• The check-then-act race is the single most repeated concurrency bug shape in this entire document — Parking Lot's spot occupation, Ride-Sharing's driver reservation, Coffee Machine's ingredient reservation, ATM's cross-channel balance check, Library's last-copy checkout, Hotel's overlapping-date booking, Movie Ticket Booking's seat hold, E-commerce's inventory decrement, and Stock Brokerage's fund/holding reservation are the same bug in nine different domains, at wildly different scales. Naming "atomic compare-and-swap, not read-then-write" unprompted, and recognizing it as the same bug every time it recurs, is the single most transferable signal across all twenty-one problems.
• The atomic select-then-claim race is a specific, recurring variant of the above, for dispatch/assignment problems — Elevator's hall-call assignment and Food Delivery's courier assignment are the same bug: selecting a candidate and claiming them must be one atomic step, not two, or two requests can select the same "available" resource before either claim commits.
• Deadlock avoidance via canonical lock ordering is the recurring fix whenever a single operation must lock multiple resources at once — File System's cross-directory move, Movie Ticket Booking's multi-seat hold, and E-commerce's multi-item checkout all resolve the same circular-wait risk the same way: sort the resource ids and always acquire locks in that order, so every concurrent request converges on one global order.
• Idempotency under retries is the second most repeated correctness requirement — Splitwise's settle-up, Ride-Sharing's ride-accept, Notification System's dedupe, Pub-Sub's at-least-once delivery, Movie Ticket Booking's and E-commerce's payment-webhook confirmation, Food Delivery's duplicate status events, Chat's cursor-based reconnect replay, and Stock Brokerage's retried order-placement are nine instances of exactly the same lesson: once retries exist, "processed twice" is not an edge case, it's an expected event the design must tolerate, ideally by construction (a cursor, an idempotency key) rather than by a bolted-on duplicate check.
• A recurring "shared, mutable template vs. frozen, per-instance snapshot" split is the most common non-obvious modeling decision in the second half of this document — Library's Book/BookItem, Hotel's Room/RoomInventory, Movie Ticket Booking's Seat/ShowSeat, Food Delivery's MenuItem/OrderLineItem, and E-commerce's Cart/Order are five independent instances of the identical shape: a catalog/template entity that's shared and changes over time, versus a specific instance or historical record that must stay frozen once created. Collapsing the two into one entity is the most common and most damaging shortcut across these five problems specifically.
• Deliberately naming and rejecting a plausible-looking pattern is a stronger signal than reflexively applying one — this appears explicitly in nine of the twenty-one problems (Splitwise's Payment-not-a-subclass, Ride-Sharing's Decorator-over-second-Strategy, Notification System's rejected Bridge, Coffee Machine's rejected Template Method, Pub-Sub's rejected Bridge, Elevator's rejected Singleton, Chess's rejected Strategy for piece movement, E-commerce's Decorator/Strategy role-swap rejection, Stock Brokerage's rejected Singleton for Broker). The consistent shape of the argument — "this pattern's structural fit is real, but its intent doesn't match what's actually varying here" — is more valuable to demonstrate than the specific pattern each time.
• Strategy is the default answer whenever the interviewer says "what if this needs to support X differently" — but three other patterns mark its real boundaries: Decorator is for composable, stackable modifiers (Ride-Sharing's surge, E-commerce's add-ons) rather than mutually exclusive alternatives; Visitor is for a growing set of read-only operations over a fixed structure (File System); Command is for actions that must themselves be queued, logged, or reversed (Chess's Move/undo). E-commerce (Problem 19) is the one place in this document where the Strategy/Decorator boundary is made fully explicit as the central lesson of the entire problem.
• Singleton is a naive shortcut almost everywhere it appears in reference solutions — except when it isn't — Logging Framework's registry is the one legitimate case in this document, and Elevator's Dispatcher and Stock Brokerage's Broker are two more, independent instances of the naive shortcut being tempting and wrong for exactly the same reason Parking Lot's and Ride-Sharing's service classes were. Stating explicitly why the registry case differs is more valuable than either reflexively using or reflexively banning Singleton.
• Observer starts as an optional hook and ends as the structural core of an entire product — twice — the notify-interested-parties idea appears as a small, optional instance in Ride-Sharing, Notification System, Coffee Machine, Library, Hotel, Movie Ticket Booking, and Food Delivery, gets generalized fully as the entire point of Pub-Sub (Problem 10), and then converges a second time as the structural core of Chat (Problem 20) — arguably the most natural full-scale realization of exactly what Pub-Sub generalized. Recognizing this progression across ten separate problems demonstrates the pattern is understood structurally, not memorized per-problem.
• Mediator and Observer can coexist on the same class, solving different problems — Chat's Conversation is simultaneously a Mediator (decoupling participants from direct references to each other) and an Observer subject (fanning out messages to connected clients). Recognizing that these are complementary lenses, not competing pattern choices, is the clearest illustration in this document that pattern selection isn't always "pick exactly one."
• Recognizing the LLD/HLD boundary explicitly (clearest in Ride-Sharing, Pub-Sub, Movie Ticket Booking, Chat, and Stock Brokerage's feed-execution-vs-real-order-matching distinction, but present in every problem once "scale this to millions of users" or "run this across a cluster" comes up) separates strong candidates from those who either over-engineer infrastructure they weren't asked for or hand-wave scale entirely.