System design, part 11 of 12
LLD Case Studies
Ten low-level designs that come up again and again, each worked through the same four steps: requirements, design, runnable code, extensions. Each case is sized for a 45 to 90 minute round: the core is complete and runs, the rest is named and placed. The method, UML notation and concurrency tools are on Low-Level Design; pattern mechanics are on Design Patterns. All code is Python 3.9, standard library only, and every demo is deterministic.
How to use these
Part 1 of 12 · the template and the map
Read a case as a rehearsal, not a reference: cover the code, write your own from the requirements and design, then compare. The differences are your gaps.
The four-step template
| Step | Produce | Time in a 90 min round | Senior answer adds |
|---|---|---|---|
| 1. Requirements | Functional list, constraints, out of scope, assumptions written down | 5 to 8 | Asks the one question that changes the model (see each case) |
| 2. Design | Class diagram with key members, entity table, a state or sequence diagram | 8 to 12 | Names the variation point and the invariant that needs a lock |
| 3. Code | Entities, one service, a demo with one failure path | 50 to 60 | Injected clock and randomness; domain errors; no dead code |
| 4. Extensions | "To add X, I add class Y" | 5 to 10 | Size of each change; concurrency story; what breaks at scale |
Interview tip: each case's code is about 90 to 150 lines, which is roughly what fits in 60 minutes of typing. If yours is twice that, you are building features nobody asked for.
What each case exercises
| Case | Patterns | Core skill tested | Concurrency question |
|---|---|---|---|
| Parking lot | Strategy | Entity modelling, allocation data structure | Two cars, one spot |
| LRU and LFU cache | None (data structure) | O(1) design with a hash map plus linked list | Reads mutate order |
| Elevator | Strategy, State | Scheduling, simulation with ticks | Requests arrive while cars move |
| Vending machine | State | Lifecycle with legal and illegal actions; change-making | Single user, hardware events |
| Expense sharing | Strategy | Money as integers, rounding, graph simplification | Concurrent edits to one group |
| Movie booking | Strategy (payment port) | Holds with expiry, two-phase confirm | Double booking: the headline |
| Rate limiter | Strategy, Factory | Algorithms behind one interface, injectable clock | Per-key state under many threads |
| Logging framework | Chain of Responsibility, Strategy, Observer | Pipelines, filtering, extensible outputs | Async sinks, ordering |
| Tic-tac-toe | None needed; Strategy for players | Clean game loop, O(1) win check | Rarely asked |
| Pub-sub queue | Observer | Offsets, delivery semantics, dead letters | Producers and consumers in parallel |
Parking lot
Part 2 of 12 · entities, allocation, pricing
A multi-floor lot with spot sizes issues a ticket on entry, finds the nearest free spot that fits, and charges on exit. It tests whether your entities carry behaviour and whether "nearest" has a data structure behind it.
Parking: requirements
- Functional: park a vehicle and get a ticket; leave with the ticket and pay; refuse when no spot fits.
- Rules: motorbike fits small or larger, car fits medium or larger, truck fits large only. Prefer the smallest size that fits, then the nearest spot.
- Constraints: a few thousand spots, several entry gates (so allocation is concurrent), fee by duration and vehicle kind.
- Out of scope: payment methods, reservations, sensors, display boards, multiple lots.
| Ask | Why it matters | Assumed |
|---|---|---|
| What does "nearest" mean? | Defines the sort key of the allocator | Lowest floor, then distance to the lift |
| Can a car take a large spot? | Best fit vs first fit | Yes, only when no medium spot is free |
| How is the fee computed? | Is pricing a variation point? | Per started hour, rate by kind; will change per lot |
| Lost ticket, overnight cap? | Extra pricing rules | Not now; pricing must accept them later |
Parking: design
| Class | Kind | Responsibility |
|---|---|---|
ParkingLot | Service | Allocate the nearest fitting spot, issue and close tickets |
Spot | Value (frozen) | Location and size; occupancy lives in the lot's free heaps, not in the spot |
Vehicle, Ticket | Value | What parked, where, since when |
PricingStrategy | Interface | Fee from kind and duration |
VehicleKind, SpotSize | Enums | Fixed sets; SMALLEST_FIT maps one to the other |
Senior signal: say why there is no Floor class here: nothing in scope depends on a floor beyond its number. Add it when floors get behaviour (display boards, per-floor capacity, closing a floor).
Parking: code
- Best fit, then nearest: iterating
SpotSizein order gives the smallest size that has a free spot; the heap gives the nearest within it. - The clock is injected, so "130 minutes later" is one assignment, not a sleep.
- The truck is refused with
LotFullbefore any state changes.
Parking: extensions and follow-ups
Patterns: Strategy for pricing; a Decorator for caps and discounts on top of it.
| New requirement | Change |
|---|---|
| Daily cap, weekend rates, lost-ticket fee | New PricingStrategy classes; CappedPricing(inner, cap) wraps any of them |
| Electric spots with chargers | New SpotSize (or a features set on Spot) and a rule in SMALLEST_FIT; allocator unchanged |
| "Nearest to my gate" per entrance | Allocation becomes a SpotFinder strategy with one heap set per entrance |
| Free-spot display per floor | Introduce Floor with counters; the lot notifies it on park and leave (Observer) |
Concurrency: several gates call park at once. Pop-from-heap plus ticket insert is a check-then-act: guard park and leave with one lock in the lot (the work inside is microseconds). Across many lots, the source of truth moves to a database row per spot with a conditional update.
- Why not store
is_freeon the spot? Then "find nearest free" is a scan; keeping the free set in the allocator makes the query cheap and the spot immutable. - Why a frozen
Spot? It is shared by the heap and tickets; immutability means neither can corrupt the other. - How do you test pricing? Unit-test strategies alone with plain numbers; the lot test only checks the right strategy is called.
- Where do floors with different rates go? Pricing takes the
Spotas well; the interface widens, callers do not change.
LRU cache, then LFU
Part 3 of 12 · O(1) data structure design
A fixed-capacity cache with O(1) get and put that evicts the least recently used key; then the least frequently used variant. It tests whether you can combine two structures so each covers the other's weak operation.
- Requirements
- Design
- Code
- Extensions and follow-ups, including LFU
LRU: requirements
- Functional:
get(key)returns the value or a miss;put(key, value)inserts or updates; at capacity, insert evicts the least recently used key. - Constraints: both operations O(1) average; capacity at least 1; "use" means a
getor aput. - Out of scope: TTL, size in bytes, persistence, distribution.
| Ask | Assumed |
|---|---|
| Does updating a key count as a use? | Yes: it moves to most recent |
What does a miss return: None, -1, an exception? | None; a miss is an expected outcome, not an error |
Can I use OrderedDict? | Write it by hand first; show the shortcut after |
| Called from several threads? | Discuss; code single-threaded |
LRU: design
A dict gives O(1) lookup but no order; a list gives order but O(n) removal from the middle. A doubly linked list keyed by a dict of nodes gives both.
| Operation | Steps | Cost |
|---|---|---|
get hit | dict lookup, unlink, push front | O(1) |
put existing | update value, unlink, push front | O(1) |
put new at capacity | unlink head.prev, delete its key from the dict, insert | O(1) |
LRU: code
- The node stores its key so eviction can delete the dict entry; forgetting this is the most common bug.
__slots__onNodecuts per-entry memory; with millions of entries that matters.OrderedDictis itself a dict plus a doubly linked list in CPython, so the shortcut has the same complexity.
LRU: extensions and follow-ups
LFU: evict the key with the fewest uses, least recent among ties. Keep key to (value, uses), uses to an ordered set of keys, and the current minimum; a new key always resets the minimum to 1.
| New requirement | Change |
|---|---|
| Per-entry TTL | Store expiry in the node; treat expired as a miss on get (lazy), optionally a min-heap of expiries for active cleanup |
| Evict by memory, not count | Track bytes; evict in a loop until under the budget |
| Pluggable policy (LRU, LFU, FIFO) | An EvictionPolicy interface with touch, add, victim (Strategy); the cache keeps the dict |
| Load on miss | Inject a loader; see the per-key loading discussion on Low-Level Design |
Concurrency: get mutates the list, so even reads need the lock. Wrap both methods in one threading.Lock. For heavy contention, shard: N independent caches selected by hash(key) % N, each with its own lock; recency becomes approximate per shard, which is usually acceptable.
- Why doubly linked? Removing a node from the middle needs its predecessor in O(1).
- LRU vs LFU? LRU adapts fast to shifting access; LFU protects long-term hot keys but holds stale ones without ageing.
- Scan resistance? One full scan flushes an LRU; segmented LRU or admission policies (as in some modern caches) avoid that.
- Is
functools.lru_cacheenough? For memoising a pure function, yes; it has no explicit put, delete or TTL.
Elevator system
Part 4 of 12 · scheduling, state, simulation
Several cars serve hall calls (up or down at a floor) and car calls (a floor button inside). It tests separating dispatching (which car) from movement (in what order a car serves its stops), and modelling time as discrete ticks.
Elevator: requirements
- Functional: hall call assigns one car; car call adds a stop to that car; cars move one floor per tick and open doors at stops; invalid floors are refused.
- Rules: a moving car keeps its direction while it has stops ahead (SCAN / LOOK); the dispatcher prefers an idle car or one already heading to the caller in the caller's direction.
- Out of scope: door timing, weight limits, emergency mode, express zones.
| Ask | Assumed |
|---|---|
| Simulation or controller for real hardware? | Simulation with ticks; the same classes would take sensor events |
| Optimise wait time, travel time or energy? | Wait time; strategy is swappable |
| Can an assignment change after it is made? | No (simpler); mention reassignment as an extension |
Elevator: design
| Class | Responsibility |
|---|---|
ElevatorSystem | Validate floors, route hall calls through the strategy, advance time |
Car | Its floor, direction and stop set; LOOK movement in step |
DispatchStrategy | Pick a car for a hall call; NearestCar scores by distance plus a penalty for cars that must turn round first |
Direction | Enum UP, DOWN, IDLE with values +1, -1, 0, so moving is floor += direction.value |
Elevator: code
- B is at 8 and A at 0: the call at 6 goes to B (distance 2), the call at 1 to A (distance 1).
- The
DoorsOpenstate is collapsed into the tick that serves a stop; with door timing it becomes a real state with a countdown. - Ties are broken by car id, so dispatch is deterministic and testable.
Elevator: extensions and follow-ups
Patterns: Strategy for dispatch; State for the car once doors, maintenance and emergency each change behaviour.
| New requirement | Change |
|---|---|
| Zoning: car A serves floors 0 to 20 only | A serves(floor) check on Car; the strategy filters candidates |
| Peak-hour mode (lobby up-peak) | A second strategy, swapped by a schedule; no change to Car |
| Maintenance or fire mode | Car becomes a State object; Maintenance.add_stop refuses, FireMode forces floor 0 |
| Display "car arriving" | Cars publish arrival events to listeners (Observer) |
Concurrency: hall buttons fire from many threads while a controller thread ticks. Common design: buttons only enqueue requests to a thread-safe queue; one controller thread drains it and owns all car state. No locks inside Car, because only one thread ever touches it.
- SCAN vs LOOK? SCAN runs to the end floor before reversing; LOOK reverses at the last request. This code is LOOK.
- Why not nearest car by distance only? A car two floors away heading the other way may take minutes; the penalty models that.
- Starvation? LOOK bounds waiting to about two sweeps; age requests if a strict bound is required.
- How to test? Scripted calls plus ticks, assert the event log, as in the demo.
Vending machine
Part 5 of 12 · the State pattern done properly
A machine accepts coins, sells a product, returns change and refuses actions that make no sense in its current state. It is the canonical State pattern question; the trap is making change after you have already committed the sale.
Vending: requirements
- Functional: insert coins; select a product; receive the product and change; cancel for a refund; machine reports out of stock when empty.
- Rules: select needs enough money and stock; the sale happens only if exact change can be returned; no coins accepted while dispensing or out of stock.
- Out of scope: cards, notes, admin UI, telemetry. Restock is named, not coded.
| Ask | Assumed |
|---|---|
| Can the user buy several items on one credit? | No: change is returned after one sale |
| Can the inserted coins be used as change? | Yes, they join the coin box before change is computed |
| What signals the end of dispensing? | A hardware event, modelled as dispensed() |
Vending: design
| Class | Responsibility |
|---|---|
VendingMachine | Context: holds slots, coin box, escrow and current state; public API |
State and four subclasses | What each action does in that state, and the next state |
CoinBox | Coin counts; computes change and commits it only if exact |
Slot | Product, price, count |
Vending: code
- Order inside
HasMoney.select: check stock, check money, compute change, and only then decrement stock and switch state. A failed change leaves everything as it was. take_changebuilds a new counter and swaps it in only on success: raise before mutating.- Greedy change is optimal for canonical coin systems such as 10/5/2/1 with unlimited coins; with limited counts or odd denominations it can fail where a solution exists, so use a bounded-coin DP if asked.
Vending: extensions and follow-ups
Patterns: State; change-making as a Strategy once there are two algorithms.
| New requirement | Change |
|---|---|
| Card payments | A PaymentMethod interface; a new AwaitingCard state between select and dispensing |
| Restock and maintenance | restock() on OutOfStock and Idle; a Maintenance state that refuses customers |
| Dispense jam | dispense_failed() on Dispensing: refund, restore count, go to Maintenance |
| Sales report | States emit sale events to a listener (Observer) |
Concurrency: one user at a time by construction, but hardware events (coin sensor, motor) can arrive on other threads. Serialise all events through one queue or one lock on the machine; states hold no data of their own, so they can be shared singletons.
- Why not an enum and if statements? Fine for two or three states; with four states and four actions it becomes a 16-cell table spread through every method.
- Who owns transitions, state or context? Here, states set
machine.state; a transition table in the context is the alternative when transitions must be configured. - Why escrow? Inserted coins are not the machine's until a sale; cancel must return exactly those coins.
Expense sharing
Part 6 of 12 · split rules, balances, simplifying debts
Users in a group record expenses split equally, by exact amounts or by percentage, see who owes whom, and settle with few transfers. It tests money handling, a clean Strategy and a small graph algorithm.
Expense sharing: requirements
- Functional: add an expense (payer, amount, participants, split type); show net balance per member; produce a settlement plan.
- Rules: exact shares must sum to the amount; percentages to 100; everyone involved must be in the group; shares sum to the amount to the paisa.
- Out of scope: currencies, recurring expenses, notifications, payments.
| Ask | Assumed |
|---|---|
| Where does the leftover paisa go on an equal split? | To the first participants, one each; deterministic |
| Simplify across the group or keep pairwise debts? | Across the group, on request |
| Can expenses be edited or deleted? | Not now; keep a ledger so it is possible |
Expense sharing: design
| Class | Responsibility |
|---|---|
Group | Membership check, ledger of expenses, net balance per user, settlement |
Expense | Immutable ledger entry with computed shares |
SplitStrategy | Amount and participants to shares; validates its own inputs |
User | Value object with an id; equal by id and name |
Expense sharing: code
- All amounts are integer paise. Equal split of 1000.00 among three gives 333.34, 333.33, 333.33; nothing is lost to rounding.
- Shares are computed and validated before any balance changes, so a bad split leaves the group untouched.
- Balances sum to zero by construction; assert that in a test.
Expense sharing: extensions and follow-ups
Patterns: Strategy for split types, chosen by a Factory from the request's split code.
| New requirement | Change |
|---|---|
| Split by shares (2:1:1) | New ShareSplit strategy; nothing else changes |
| Edit or delete an expense | Append a reversing entry to the ledger, then the new one; balances follow |
| Multiple currencies | Money value object with currency; balances per currency; convert only at settlement |
| Record a payment between users | A payment is an expense paid by the debtor with one exact share for the creditor |
Concurrency: two members adding expenses to one group at once is a read-modify-write on balances. Lock per group; in a database, insert ledger rows and derive balances, or update balance rows in one transaction with the ledger insert.
- Minimum number of transfers? Finding the true minimum is NP-hard in general; greedy gives at most n - 1 transfers, which is what products ship.
- Why not store "A owes B" pairs? Pairs grow as O(n squared) and need netting anyway; one net number per user is enough to settle.
- Floating point? Never: integers in minor units, with an explicit rule for the remainder.
Movie ticket booking
Part 7 of 12 · holds, expiry, no double booking
Users pick seats for a show, hold them for a few minutes while paying, and get a booking. The question is really about concurrency: two users must never end up with the same seat, and a slow payment must not block everyone else.
Movie booking: requirements
- Functional: hold a set of seats for a show (all or none); confirm a hold with payment to get a booking; holds expire after 10 minutes.
- Invariant: a seat has at most one live hold or booking at any time.
- Out of scope: catalogue and search (movies, theatres, screens), pricing tiers, cancellations, notifications.
| Ask | Assumed |
|---|---|
| All-or-nothing for multiple seats? | Yes: a group wants seats together |
| Hold duration, and what if payment finishes after it? | 10 minutes; late payment is refunded |
| One process or many? | One process here; say how it changes with many |
Movie booking: design
Movie booking: code
- The race is real: two threads released together by a
Barrier. Which one wins varies; that exactly one wins does not, so the printed output is stable. - The check (no live hold or booking covers the seats) and the claim (add the hold) are inside one
with self._lock. - The clock is injected: "11 minutes later" is
now[0] = 601.0.
Movie booking: extensions and follow-ups
Patterns: payment behind an interface (a port; Strategy when several gateways exist); Observer for confirmation messages.
| New requirement | Change |
|---|---|
| Seat categories and prices | Seat value object with a category; a PricingStrategy per show |
| Cancellation and refund rules | cancel(booking_id) frees seats; refund amount from a policy by time to show |
| Very popular shows | Lock per seat, acquired in sorted seat-id order to avoid deadlock, instead of one lock per show |
| Several app servers | Seat rows in a database: conditional update WHERE status = 'free' OR hold_expired, or a unique constraint on (show, seat) |
Concurrency: one lock per show is correct and fast for an in-process design because the critical sections are microseconds. The senior points are: no I/O under the lock, re-validate after the slow step, and idempotent payment (charge with a request id so a retry does not double-charge). Python mechanics are in Python Concurrency.
- Why not lock while paying? Payment takes seconds; every other user of the show would wait.
- Why not a background thread to expire holds? Lazy expiry on access is simpler and exact; a sweeper only reclaims memory.
- Optimistic instead? Version per seat and compare-and-set; good when conflicts are rare, retry storms when a show opens.
- Payment succeeds but the server crashes before booking? Reconcile: a job matches receipts to bookings and refunds orphans.
Rate limiter library
Part 8 of 12 · algorithms behind one interface
A library that answers "may this key make a request now?" with token bucket and sliding window implementations and per-key limits. It tests interface design, time as a dependency, and per-key state.
Rate limiter: requirements
- Functional:
allow(key) -> bool; token bucket (burst plus steady rate) and sliding window log (strict count per window); limits chosen per key tier. - Constraints: O(1) or near it per call; thread-safe; deterministic tests (no sleeping).
- Out of scope: limits shared across servers (an HLD topic; one extension below), HTTP headers.
| Ask | Assumed |
|---|---|
| Are bursts allowed? | Yes for token bucket; the sliding log is strict |
| What is a key: user, IP, API key, endpoint? | An opaque string; the caller builds it, with a tier prefix |
| Does a denied request cost anything? | No |
Rate limiter: design
| Algorithm | State per key | Bursts | Accuracy | Use when |
|---|---|---|---|---|
| Token bucket | 2 numbers | Up to capacity | Exact average rate | APIs: allow short bursts, cap the average |
| Leaky bucket | Queue or 2 numbers | Smoothed out | Constant outflow | Shaping traffic to a fixed rate |
| Fixed window counter | 2 numbers | Up to 2x at window edges | Approximate | Cheap quotas (per day) |
| Sliding window log | One timestamp per request | None | Exact | Low limits where precision matters (logins) |
| Sliding window counter | 2 counters | Small | Approximate (weighted) | High limits, little memory |
Rate limiter: code
- Bucket of 3 at 1 per second: 3 allowed at t=0, 2 more after 2 seconds of refill.
- Sliding log of 2 per 10 seconds: t=10.0 is allowed because t=0.0 has left the window; t=10.5 is not because t=1.0 is still in it.
- Denial is a
False, not an exception: it is the expected, frequent outcome.
Rate limiter: extensions and follow-ups
Patterns: Strategy for the algorithm, Factory to build limiters from config, Composite for combined limits.
| New requirement | Change |
|---|---|
| Several limits at once (10/s and 1000/day) | AllOf([...]) limiter that allows only if every child allows; children must not consume when a later one denies (check, then commit) |
| Limits from a config file | Factory from {"tier": "pro", "algo": "token_bucket", ...} to instances |
| Tell the client when to retry | Return a Decision(allowed, retry_after); token bucket computes it from the deficit |
| Memory for idle keys | Evict keys idle longer than their refill time (an LRU over keys) |
| Shared across servers | Store state in Redis with an atomic script; the interface does not change |
Concurrency: refill, compare and decrement is a check-then-act; one lock per limiter is the baseline. For high throughput, stripe locks by key hash so unrelated keys do not contend.
- Why inject the clock? Tests advance time by assignment; production passes
time.monotonic, never wall-clock time, which can jump. - Fixed window edge problem? 100 at 0:59 and 100 at 1:00 gives 200 in two seconds; sliding windows fix it.
- Token bucket vs sliding log memory? Two floats vs one timestamp per allowed request.
Logging framework
Part 9 of 12 · levels, sinks, formatters, chains
A small logging library: named loggers with levels, several outputs with their own formatters and filters, records travelling up a logger hierarchy. It tests separating what is logged, where it goes and how it looks.
Logging: requirements
- Functional: log at DEBUG, INFO, WARNING, ERROR with structured context; named loggers in a dotted hierarchy; several sinks each with a minimum level, filters and a formatter.
- Constraints: a disabled level must cost almost nothing; logging must never crash the caller; safe from many threads.
- Out of scope: config files, rotation, remote shipping (named as extensions).
| Ask | Assumed |
|---|---|
| Does a child's record also reach the parent's sinks? | Yes (propagation), like most logging libraries |
| Sync or async writes? | Sync in code; async as an extension |
| Structured or text output? | Both, by formatter |
Logging: design
| Class | Responsibility |
|---|---|
Logger | Level gate, build the record, walk the parent chain |
LogRecord | Immutable: logger, level, message, time, context |
Sink | Its own level and filters, then format and write; subclasses only implement write |
Formatter | Record to string: text or JSON |
Logging: code
- The DEBUG call returns before building a record; the password line is built and then dropped by the console sink's filter.
Sink.handleis a template method: the shared level and filter logic in the base, onlywritein subclasses.- The clock is injected, so timestamps in the demo are fixed.
Logging: extensions and follow-ups
Patterns: Chain of Responsibility (logger hierarchy, filter list), Strategy (formatters), Template Method (Sink.handle), Observer (sinks subscribe to a logger).
| New requirement | Change |
|---|---|
| Async writing | AsyncSink(inner): write puts on a bounded queue.Queue; one worker thread calls inner.write. Decide drop-or-block when full; flush on shutdown |
| File rotation | RotatingFileSink subclass; nothing else changes |
| Request id on every line | A filter or the logger reads a contextvars.ContextVar and adds it to the record context |
| Configure from a file | A builder that creates loggers and sinks from a dict; loggers fetched by name from a registry |
Concurrency: two threads writing to one file can interleave partial lines. Give each sink a lock around write, or route all writes through one async worker, which also preserves order. Loggers are read-mostly; configure them at startup.
- What if a sink raises? Catch it inside
handleand report to stderr; logging must never break the request. - Why build the record lazily? Most DEBUG calls are disabled in production; string formatting is the cost.
- Why a registry instead of a Singleton logger? Many named loggers, one tree; the registry is the shared root, injected or module-level.
Tic-tac-toe
Part 10 of 12 · board, turns, win detection
An N by N tic-tac-toe for two or more players with turn management, move validation and win or draw detection. It tests a clean game loop and an O(1) win check instead of scanning the board after every move. The same skeleton fits snake and ladder (board of jumps, a dice port).
Game: requirements
- Functional: players take turns placing their symbol; a full row, column or diagonal wins; a full board without a winner is a draw; no moves after the game ends.
- Rules: off-board or occupied cells are refused and the turn does not pass.
- Constraints: board size N is a parameter; moves are scripted so tests are stable.
- Out of scope: AI player, UI, networking, undo.
| Ask | Assumed |
|---|---|
| Win needs a full line, or K in a row on a bigger board? | Full line of N; K in a row is an extension |
| More than two players? | Allowed; turns rotate |
| Who goes first? | The first player passed in |
Game: design
| Class | Responsibility |
|---|---|
Game | Turn order, status (in progress, won, draw), refusing moves after the end |
Board | Cells, bounds and occupancy checks, fullness |
WinTracker | Counts per (player, line); a count reaching N is a win. O(1) per move, O(N) memory per player |
Player | Value object: name and symbol |
Game: code
- The refused move leaves Sandhya to play: the error is raised before
_turnchanges. - Each move touches at most four counters (row, column, two diagonals), whatever N is.
- Snake and ladder reuses the shape:
Boardbecomes a map of jumps,WinTrackerbecomes "reached the last square", and an injectedDice(seeded or scripted) replaces the move input.
Game: extensions and follow-ups
Patterns: mostly none, which is the point; Strategy for player types and Command for undo when asked.
| New requirement | Change |
|---|---|
| Computer player | MoveSource interface: HumanInput, RandomBot(seed), MinimaxBot; the game asks the current player's source |
| K in a row on a large board | Replace the tracker: after a move, count matching cells outward in four directions; O(K) per move |
| Undo | Each move as a Command with undo; the tracker decrements its counters |
| Online play | The game becomes a server-side entity per match; moves arrive as commands with the player id checked against current |
Concurrency: rarely asked. For online play, serialise moves per game with one lock or a per-game queue, and reject a move whose player is not current.
- Why not check the whole board after each move? O(N squared) per move; the counter trick is O(1).
- Where does printing go? Outside:
rows()returns data, a renderer prints it. - How do you test a random game? Inject a seeded
random.Randomor a scripted dice.
In-memory pub-sub queue
Part 11 of 12 · topics, offsets, redelivery
Publishers append to topics; consumer groups each read every message in order, tracking their own offset, with retries and a dead-letter list for messages that keep failing. It tests delivery semantics and why a log with offsets beats a queue that deletes on read.
Pub-sub: requirements
- Functional: create topics; publish returns an offset; subscribe a consumer group with a handler; each group receives every message, in order.
- Delivery: at least once. The group's offset advances only after its handler succeeds; a failing message is retried, then dead-lettered after N attempts.
- Constraints: publishers and consumers on different threads; a late group can replay from the start.
- Out of scope: persistence, partitions, retention, network protocol.
| Ask | Assumed |
|---|---|
| Ordering per topic required? | Yes, so one failing message blocks its group until retried or dead-lettered |
| Push or pull? | The broker pushes in rounds; a pull API is the same offsets |
| At most, at least or exactly once? | At least once; consumers must be idempotent |
Pub-sub: design
Pub-sub: code
callsshows at-least-once: offset 1 was handled twice, the poison message twice (itsmax_attempts), the others once.- The email group stops at a failing message instead of skipping it, which preserves order; billing is not slowed by email's failures.
- Failures are scripted by attempt count, so the output is the same on every run.
Pub-sub: extensions and follow-ups
Patterns: Observer at its core, decoupled in time by the log; Iterator for a pull consumer reading from its offset.
| New requirement | Change |
|---|---|
| Parallel consumers in one group | Partitions: a topic is K logs, a key hash picks one; each partition is read by one member, so order holds per key |
| Retry with back-off | Store retry_at per group from an injected clock; skip delivery until then |
| Retention | Drop log prefix below the smallest committed offset, or by age; groups behind it jump forward |
| Message filtering per subscriber | A predicate on the group; skipped messages still advance the offset |
| Durability | Append to a file per topic and store offsets; replay on start |
Concurrency: Topic.append holds a lock so offset assignment and append are atomic; read copies a slice under the same lock. Each group is driven by one worker thread, so its offset needs no lock. A blocking pull would use a threading.Condition to wait for new messages (see the bounded queue on Low-Level Design). This mirrors the log-plus-offsets design popularised by Kafka; a real broker adds partitions, replication and persistence.
- Exactly once? Not from the broker alone: at-least-once delivery plus idempotent handlers (dedupe by message id) gives effectively-once processing.
- Queue vs log? A queue deletes on ack and spreads messages across consumers; a log keeps messages and gives each group its own cursor.
- Slow consumer? With a log it just lags; monitor lag (end offset minus committed) and alert.
- Poison message? Bounded attempts, then a dead-letter list with the error, so the group moves on.
Practice and reference
Part 12 of 12 · more questions, one-page summary
Ten more prompts with the modelling decision that defines each, then the one-table summary of the cases above.
Further questions to practise
Run each through the four steps. The decision column is the thing the interviewer is waiting for you to notice.
| Prompt | The defining modelling decision | Closest case above |
|---|---|---|
| ATM | Session as a State machine (card in, PIN ok, transaction, eject) and note dispensing as a Chain of denominations | Vending machine |
| Library management | Book (title) vs copy (physical item); loans and reservations per copy, queues per title | Low-Level Design worked example |
| Hotel booking | Availability as date ranges per room; overlap check plus hold is the double-booking problem again | Movie booking |
| Chess | Piece movement as polymorphism on Piece; the board validates check, not the piece | Tic-tac-toe |
| File system | Composite: file and directory share one interface; path resolution walks the tree | Logging (hierarchy) |
| Notification service | Channel as Strategy (email, SMS, push), templates separate from delivery, retries with idempotency keys | Pub-sub, logging |
| Inventory management | Reserved vs available stock per warehouse; reservation with expiry, atomic decrement | Movie booking |
| Food ordering | Order lifecycle as a state machine with timeouts; restaurant and delivery assignment as separate strategies | Elevator (dispatch), vending (state) |
| Cab booking | Matching driver to rider as a Strategy over a spatial index; trip state machine; driver held while offered | Elevator, movie booking |
| URL shortener (classes) | Key generation as an injected strategy (counter plus base62 or random with collision check); repository behind an interface | Rate limiter (interfaces) |
Cheat sheet
| Case | Core classes | Key pattern or structure | The trap |
|---|---|---|---|
| Parking lot | ParkingLot, Spot, Ticket, PricingStrategy | Strategy; min-heap per size | Scanning every spot; if kind == pricing |
| LRU / LFU | LRUCache, Node; LFU frequency buckets | Dict plus doubly linked list; min-frequency pointer | Node without its key; forgetting reads reorder |
| Elevator | ElevatorSystem, Car, DispatchStrategy | Strategy for dispatch; LOOK in the car | One class doing dispatch and movement; reversing mid-sweep |
| Vending machine | VendingMachine, State subclasses, CoinBox, Slot | State | Committing the sale before change is known to be possible |
| Expense sharing | Group, Expense, SplitStrategy, User | Strategy; greedy settle-up | Floats; losing the rounding paisa; storing pairwise debts |
| Movie booking | Show, Hold, Booking, PaymentGateway | Lock per show; holds with lazy expiry | Check and claim not atomic; paying under the lock; no re-check after paying |
| Rate limiter | RateLimiter, TokenBucket, SlidingWindowLog, TieredLimiter | Strategy; injected clock | Wall-clock time; sleeping in tests; fixed-window edge bursts |
| Logging | Logger, LogRecord, Sink, Formatter | Chain of Responsibility; Template Method | Building records for disabled levels; a sink exception breaking the caller |
| Tic-tac-toe | Game, Board, WinTracker, Player | Counters per line | O(N squared) board scan; passing the turn on an illegal move |
| Pub-sub | Broker, Topic, ConsumerGroup, Message | Append-only log plus offsets; Observer | Deleting on read; committing before handling; no dead-letter path |
Recurring moves across all ten: inject time and randomness, raise named errors before mutating, keep one lock around each check-then-act, and answer every extension with the class you would add.
Next: how to run the whole interview, from the first question to the wrap-up, in Senior Interview Playbook.