Learnings

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

How to use these

Every case below follows this order. Extensions loop back into the design: a good design absorbs them as new classes, not edits.
StepProduceTime in a 90 min roundSenior answer adds
1. RequirementsFunctional list, constraints, out of scope, assumptions written down5 to 8Asks the one question that changes the model (see each case)
2. DesignClass diagram with key members, entity table, a state or sequence diagram8 to 12Names the variation point and the invariant that needs a lock
3. CodeEntities, one service, a demo with one failure path50 to 60Injected clock and randomness; domain errors; no dead code
4. Extensions"To add X, I add class Y"5 to 10Size 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

How to use these

CasePatternsCore skill testedConcurrency question
Parking lotStrategyEntity modelling, allocation data structureTwo cars, one spot
LRU and LFU cacheNone (data structure)O(1) design with a hash map plus linked listReads mutate order
ElevatorStrategy, StateScheduling, simulation with ticksRequests arrive while cars move
Vending machineStateLifecycle with legal and illegal actions; change-makingSingle user, hardware events
Expense sharingStrategyMoney as integers, rounding, graph simplificationConcurrent edits to one group
Movie bookingStrategy (payment port)Holds with expiry, two-phase confirmDouble booking: the headline
Rate limiterStrategy, FactoryAlgorithms behind one interface, injectable clockPer-key state under many threads
Logging frameworkChain of Responsibility, Strategy, ObserverPipelines, filtering, extensible outputsAsync sinks, ordering
Tic-tac-toeNone needed; Strategy for playersClean game loop, O(1) win checkRarely asked
Pub-sub queueObserverOffsets, delivery semantics, dead lettersProducers 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

Parking lot

  • 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.
AskWhy it mattersAssumed
What does "nearest" mean?Defines the sort key of the allocatorLowest floor, then distance to the lift
Can a car take a large spot?Best fit vs first fitYes, 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 rulesNot now; pricing must accept them later

Parking: design

Parking lot

The lot owns tickets and allocation; pricing is the one interface, because it is the rule most likely to differ per lot.
ClassKindResponsibility
ParkingLotServiceAllocate the nearest fitting spot, issue and close tickets
SpotValue (frozen)Location and size; occupancy lives in the lot's free heaps, not in the spot
Vehicle, TicketValueWhat parked, where, since when
PricingStrategyInterfaceFee from kind and duration
VehicleKind, SpotSizeEnumsFixed sets; SMALLEST_FIT maps one to the other
One min-heap per spot size keyed by (floor, distance): taking and returning a spot are O(log n), not a scan of every spot.

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

Parking lot

  • Best fit, then nearest: iterating SpotSize in 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 LotFull before any state changes.

Parking: extensions and follow-ups

Parking lot

Patterns: Strategy for pricing; a Decorator for caps and discounts on top of it.

New requirementChange
Daily cap, weekend rates, lost-ticket feeNew PricingStrategy classes; CappedPricing(inner, cap) wraps any of them
Electric spots with chargersNew SpotSize (or a features set on Spot) and a rule in SMALLEST_FIT; allocator unchanged
"Nearest to my gate" per entranceAllocation becomes a SpotFinder strategy with one heap set per entrance
Free-spot display per floorIntroduce 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_free on 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 Spot as 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.

LRU: requirements

LRU cache, then LFU

  • 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 get or a put.
  • Out of scope: TTL, size in bytes, persistence, distribution.
AskAssumed
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

LRU cache, then LFU

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.

The sentinel's next is the most recent, its prev the least recent. Eviction is head.prev; no None checks at either end.
Two private helpers do all the pointer work; get and put are written only in terms of them.
OperationStepsCost
get hitdict lookup, unlink, push frontO(1)
put existingupdate value, unlink, push frontO(1)
put new at capacityunlink head.prev, delete its key from the dict, insertO(1)

LRU: code

LRU cache, then LFU

  • The node stores its key so eviction can delete the dict entry; forgetting this is the most common bug.
  • __slots__ on Node cuts per-entry memory; with millions of entries that matters.
  • OrderedDict is itself a dict plus a doubly linked list in CPython, so the shortcut has the same complexity.

LRU: extensions and follow-ups

LRU cache, then LFU

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 requirementChange
Per-entry TTLStore 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 countTrack 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 missInject 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_cache enough? 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

Elevator system

  • 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.
AskAssumed
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

Elevator system

Two decisions, two owners: the strategy picks the car, the car orders its own stops.
ClassResponsibility
ElevatorSystemValidate floors, route hall calls through the strategy, advance time
CarIts floor, direction and stop set; LOOK movement in step
DispatchStrategyPick a car for a hall call; NearestCar scores by distance plus a penalty for cars that must turn round first
DirectionEnum UP, DOWN, IDLE with values +1, -1, 0, so moving is floor += direction.value
The car's lifecycle. A car never reverses between stops; it turns round only at a stop with nothing left ahead.

Elevator: code

Elevator system

  • 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 DoorsOpen state 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

Elevator system

Patterns: Strategy for dispatch; State for the car once doors, maintenance and emergency each change behaviour.

New requirementChange
Zoning: car A serves floors 0 to 20 onlyA 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 modeCar 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

Vending machine

  • 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.
AskAssumed
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

Vending machine

Every arrow is a method a state overrides; more coins or a refused select keep HasMoney. Anything not drawn, such as insert while Dispensing, raises InvalidAction.
The machine delegates every action to its current state. The base state refuses everything; each subclass overrides only its legal actions.
ClassResponsibility
VendingMachineContext: holds slots, coin box, escrow and current state; public API
State and four subclassesWhat each action does in that state, and the next state
CoinBoxCoin counts; computes change and commits it only if exact
SlotProduct, price, count

Vending: code

Vending machine

  • 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_change builds 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

Vending machine

Patterns: State; change-making as a Strategy once there are two algorithms.

New requirementChange
Card paymentsA PaymentMethod interface; a new AwaitingCard state between select and dispensing
Restock and maintenancerestock() on OutOfStock and Idle; a Maintenance state that refuses customers
Dispense jamdispense_failed() on Dispensing: refund, restore count, go to Maintenance
Sales reportStates 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

Expense sharing

  • 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.
AskAssumed
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

Expense sharing

The split rule is used once, to turn an expense into shares; what is stored is the resulting shares, so later changes to a rule never rewrite history.
ClassResponsibility
GroupMembership check, ledger of expenses, net balance per user, settlement
ExpenseImmutable ledger entry with computed shares
SplitStrategyAmount and participants to shares; validates its own inputs
UserValue object with an id; equal by id and name
Net balances of users u1 to u4 from the demo's four expenses (ten pairwise debts) settle in three transfers: largest debtor pays largest creditor, repeat.

Expense sharing: code

Expense sharing

  • 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

Expense sharing

Patterns: Strategy for split types, chosen by a Factory from the request's split code.

New requirementChange
Split by shares (2:1:1)New ShareSplit strategy; nothing else changes
Edit or delete an expenseAppend a reversing entry to the ledger, then the new one; balances follow
Multiple currenciesMoney value object with currency; balances per currency; convert only at settlement
Record a payment between usersA 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

Movie ticket booking

  • 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.
AskAssumed
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 ticket booking

The show owns its seat map and the lock; Movie, Theatre and Screen are catalogue entities outside this core.
Seat state is derived, not stored: a seat is held if a live hold covers it. Expiry needs no timer; it is checked on access.
Two short critical sections around a slow call. The second check closes the gap where the hold expires during payment.

Movie booking: code

Movie ticket booking

  • 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

Movie ticket booking

Patterns: payment behind an interface (a port; Strategy when several gateways exist); Observer for confirmation messages.

New requirementChange
Seat categories and pricesSeat value object with a category; a PricingStrategy per show
Cancellation and refund rulescancel(booking_id) frees seats; refund amount from a policy by time to show
Very popular showsLock per seat, acquired in sorted seat-id order to avoid deadlock, instead of one lock per show
Several app serversSeat 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

Rate limiter library

  • 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.
AskAssumed
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

Rate limiter library

TieredLimiter is itself a RateLimiter that delegates by key prefix, so callers never know which algorithm or tier they hit.
AlgorithmState per keyBurstsAccuracyUse when
Token bucket2 numbersUp to capacityExact average rateAPIs: allow short bursts, cap the average
Leaky bucketQueue or 2 numbersSmoothed outConstant outflowShaping traffic to a fixed rate
Fixed window counter2 numbersUp to 2x at window edgesApproximateCheap quotas (per day)
Sliding window logOne timestamp per requestNoneExactLow limits where precision matters (logins)
Sliding window counter2 countersSmallApproximate (weighted)High limits, little memory
Token bucket refills lazily on each call from the elapsed time; there is no timer thread.

Rate limiter: code

Rate limiter library

  • 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

Rate limiter library

Patterns: Strategy for the algorithm, Factory to build limiters from config, Composite for combined limits.

New requirementChange
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 fileFactory from {"tier": "pro", "algo": "token_bucket", ...} to instances
Tell the client when to retryReturn a Decision(allowed, retry_after); token bucket computes it from the deficit
Memory for idle keysEvict keys idle longer than their refill time (an LRU over keys)
Shared across serversStore 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

Logging framework

  • 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).
AskAssumed
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

Logging framework

Three independent axes: which logger (hierarchy), which sink (destination), which formatter (shape). Each varies without touching the others.
The logger's level is checked before a record is built; each sink then applies its own level and filters.
ClassResponsibility
LoggerLevel gate, build the record, walk the parent chain
LogRecordImmutable: logger, level, message, time, context
SinkIts own level and filters, then format and write; subclasses only implement write
FormatterRecord to string: text or JSON

Logging: code

Logging framework

  • The DEBUG call returns before building a record; the password line is built and then dropped by the console sink's filter.
  • Sink.handle is a template method: the shared level and filter logic in the base, only write in subclasses.
  • The clock is injected, so timestamps in the demo are fixed.

Logging: extensions and follow-ups

Logging framework

Patterns: Chain of Responsibility (logger hierarchy, filter list), Strategy (formatters), Template Method (Sink.handle), Observer (sinks subscribe to a logger).

New requirementChange
Async writingAsyncSink(inner): write puts on a bounded queue.Queue; one worker thread calls inner.write. Decide drop-or-block when full; flush on shutdown
File rotationRotatingFileSink subclass; nothing else changes
Request id on every lineA filter or the logger reads a contextvars.ContextVar and adds it to the record context
Configure from a fileA 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 handle and 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

Tic-tac-toe

  • 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.
AskAssumed
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

Tic-tac-toe

The board validates cells, the tracker detects wins, the game owns turns and status. None of them knows about printing.
ClassResponsibility
GameTurn order, status (in progress, won, draw), refusing moves after the end
BoardCells, bounds and occupancy checks, fullness
WinTrackerCounts per (player, line); a count reaching N is a win. O(1) per move, O(N) memory per player
PlayerValue object: name and symbol
Validation first, then mutation; the turn passes only after a legal move.

Game: code

Tic-tac-toe

  • The refused move leaves Sandhya to play: the error is raised before _turn changes.
  • Each move touches at most four counters (row, column, two diagonals), whatever N is.
  • Snake and ladder reuses the shape: Board becomes a map of jumps, WinTracker becomes "reached the last square", and an injected Dice (seeded or scripted) replaces the move input.

Game: extensions and follow-ups

Tic-tac-toe

Patterns: mostly none, which is the point; Strategy for player types and Command for undo when asked.

New requirementChange
Computer playerMoveSource interface: HumanInput, RandomBot(seed), MinimaxBot; the game asks the current player's source
K in a row on a large boardReplace the tracker: after a move, count matching cells outward in four directions; O(K) per move
UndoEach move as a Command with undo; the tracker decrements its counters
Online playThe 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.Random or 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

In-memory pub-sub queue

  • 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.
AskAssumed
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

In-memory pub-sub queue

The topic is an append-only log; a group's whole state is one offset plus a retry count. Adding a group costs nothing to the others.
Topic orders, a snapshot after the first round: one log, three groups at different positions. Consuming moves a pointer; it never deletes, so a new group can replay.
Commit after handling gives at-least-once; committing before handling would give at-most-once.

Pub-sub: code

In-memory pub-sub queue

  • calls shows at-least-once: offset 1 was handled twice, the poison message twice (its max_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

In-memory pub-sub queue

Patterns: Observer at its core, decoupled in time by the log; Iterator for a pull consumer reading from its offset.

New requirementChange
Parallel consumers in one groupPartitions: 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-offStore retry_at per group from an injected clock; skip delivery until then
RetentionDrop log prefix below the smallest committed offset, or by age; groups behind it jump forward
Message filtering per subscriberA predicate on the group; skipped messages still advance the offset
DurabilityAppend 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

Practice and reference

Run each through the four steps. The decision column is the thing the interviewer is waiting for you to notice.

PromptThe defining modelling decisionClosest case above
ATMSession as a State machine (card in, PIN ok, transaction, eject) and note dispensing as a Chain of denominationsVending machine
Library managementBook (title) vs copy (physical item); loans and reservations per copy, queues per titleLow-Level Design worked example
Hotel bookingAvailability as date ranges per room; overlap check plus hold is the double-booking problem againMovie booking
ChessPiece movement as polymorphism on Piece; the board validates check, not the pieceTic-tac-toe
File systemComposite: file and directory share one interface; path resolution walks the treeLogging (hierarchy)
Notification serviceChannel as Strategy (email, SMS, push), templates separate from delivery, retries with idempotency keysPub-sub, logging
Inventory managementReserved vs available stock per warehouse; reservation with expiry, atomic decrementMovie booking
Food orderingOrder lifecycle as a state machine with timeouts; restaurant and delivery assignment as separate strategiesElevator (dispatch), vending (state)
Cab bookingMatching driver to rider as a Strategy over a spatial index; trip state machine; driver held while offeredElevator, movie booking
URL shortener (classes)Key generation as an injected strategy (counter plus base62 or random with collision check); repository behind an interfaceRate limiter (interfaces)

Cheat sheet

Practice and reference

CaseCore classesKey pattern or structureThe trap
Parking lotParkingLot, Spot, Ticket, PricingStrategyStrategy; min-heap per sizeScanning every spot; if kind == pricing
LRU / LFULRUCache, Node; LFU frequency bucketsDict plus doubly linked list; min-frequency pointerNode without its key; forgetting reads reorder
ElevatorElevatorSystem, Car, DispatchStrategyStrategy for dispatch; LOOK in the carOne class doing dispatch and movement; reversing mid-sweep
Vending machineVendingMachine, State subclasses, CoinBox, SlotStateCommitting the sale before change is known to be possible
Expense sharingGroup, Expense, SplitStrategy, UserStrategy; greedy settle-upFloats; losing the rounding paisa; storing pairwise debts
Movie bookingShow, Hold, Booking, PaymentGatewayLock per show; holds with lazy expiryCheck and claim not atomic; paying under the lock; no re-check after paying
Rate limiterRateLimiter, TokenBucket, SlidingWindowLog, TieredLimiterStrategy; injected clockWall-clock time; sleeping in tests; fixed-window edge bursts
LoggingLogger, LogRecord, Sink, FormatterChain of Responsibility; Template MethodBuilding records for disabled levels; a sink exception breaking the caller
Tic-tac-toeGame, Board, WinTracker, PlayerCounters per lineO(N squared) board scan; passing the turn on an illegal move
Pub-subBroker, Topic, ConsumerGroup, MessageAppend-only log plus offsets; ObserverDeleting 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.