LLD Practice: Hard
These problems represent infrastructure-level components that software engineers build internally at companies like Google, Cloudflare, and Stripe. Each problem requires understanding of concurrency, I/O, networking, or storage internals. Target 60-90 minutes per problem. The focus shifts from "correct OOP" to "correct under concurrency and failure."
The page started with 10 infrastructure problems (Problems 1–10). Problems 11–14 add the four hardest classic case studies (elevator, chess, online auction, and a key-value store with transactions) as a bridge from domain design to infrastructure. The ladder below orders all 14. Finish the Easy and Medium ladders first.
The ladder
| # | Problem | What it practises | Time box | Full case study |
|---|---|---|---|---|
| 1 | Elevator System (P11) | Strategy (scheduling), State per car, requests arriving while cars move | 60 min | Elevator System |
| 2 | Chess (P12) | Polymorphic move rules, check and checkmate, Command for undo | 60 min | Chess |
| 3 | KV Store with Transactions (P14) | Nested transactions, Memento or undo log, TTL, isolation | 60 min | KV Store |
| 4 | Online Auction (P13) | Concurrent bids, the close-versus-last-bid race, Observer | 60 min | Online Auction |
| 5 | Minimal Web Framework (P2) | Chain of Responsibility (middleware), trie routing, async errors | 60 min | — |
| 6 | Load Balancer (P8) | Strategy (algorithms), atomics, draining, health state | 60 min | — |
| 7 | API Gateway (P7) | Pipeline, rate limiting, circuit breaker State, routing table swap | 75 min | Rate Limiter |
| 8 | Cron Scheduler (P9) | Expression parsing, priority queue of next runs, one runner per job | 75 min | Task Scheduler |
| 9 | In-Memory Message Broker (P6) | Partitioned log, offsets, consumer groups, rebalancing | 75 min | Pub-Sub |
| 10 | Search Engine Indexer (P5) | Inverted index, posting-list merges, immutable segments | 75 min | — |
| 11 | Distributed Lock Manager (P4) | Leases, fencing tokens, failure reasoning | 75 min | — |
| 12 | Simple Database Engine (P1) | WAL, memtable swap, SSTables, compaction | 90 min | KV Store |
| 13 | Container Runtime (P3) | Lifecycle State machine, a lock per container, resource managers | 90 min | — |
| 14 | Consensus Module (P10) | Raft roles, terms, log matching, single-threaded event loop | 90 min | — |
How to use this ladder
- Rungs 1–4 are domain problems with a hard core. Each has a full case study with runnable code in three languages. Do them as 60-minute whiteboard rounds.
- Rungs 5–14 are infrastructure. Don't try to write all of it. Pick the one or two classes that carry the hard logic (the router, the compactor, the vote handler), write those properly, and leave the rest as interfaces.
- For every rung, say the failure modes out loud: crash mid-operation, two threads at once, a slow dependency. At this level that's most of the score.
- Open "Hints" after ten minutes stuck, "Solution outline" after the timer. The outlines name the one invariant each design must protect. If you didn't name it, that's your gap.
- Going back down is fine. If a rung exposes a gap in basics, redo the matching rung in Medium or Easy. For example, Pub-Sub on Easy comes before the message broker here.
Problem 1: Simple Database Engine
Design a key-value database engine with a write-ahead log, memtable, and SSTable-based storage (simplified LSM tree).
Requirements
put(key, value),get(key),delete(key)operations- Write-ahead log (WAL) for crash recovery
- In-memory memtable (sorted) for recent writes
- Flush memtable to immutable SSTable files on disk
- Compaction: merge multiple SSTables to remove duplicates
- Bloom filter per SSTable to skip unnecessary reads
- Range queries:
scan(startKey, endKey)
Key Classes
classDiagram
class DBEngine {
-wal: WriteAheadLog
-memtable: Memtable
-sstables: SSTable[]
-compactor: Compactor
+put(key, value)
+get(key): value?
+delete(key)
+scan(start, end): Entry[]
}
class WriteAheadLog {
-file: FileHandle
+append(entry: WALEntry)
+recover(): WALEntry[]
+truncate()
}
class Memtable {
-tree: RedBlackTree
-size: number
+put(key, value)
+get(key): value?
+flush(): SSTable
+isFull(): boolean
}
class SSTable {
-dataFile: FileHandle
-indexFile: FileHandle
-bloomFilter: BloomFilter
+get(key): value?
+scan(start, end): Entry[]
+mightContain(key): boolean
}
class Compactor {
+compact(tables: SSTable[]): SSTable
}
DBEngine --> WriteAheadLog
DBEngine --> Memtable
DBEngine --> SSTable
DBEngine --> Compactor
Complexity Analysis
| Operation | Memtable | SSTable Lookup | Overall |
|---|---|---|---|
put() | O(log n) | N/A | O(log n) + WAL append |
get() | O(log n) | O(log n) per level | O(log n * L) where L = levels |
delete() | O(log n) | N/A (tombstone) | O(log n) + WAL append |
scan() | O(log n + k) | Merge-sort across levels | O(L * log n + k) |
| Compaction | N/A | Merge L files | O(N) where N = total entries |
Correction (2026-11-10): merging k sorted SSTables with a min-heap costs O(N log k), not O(N). It's linear only when two files are merged at a time, and then you need log k rounds. Compaction is also dominated by sequential disk I/O in practice. Tombstones can only be dropped when the merge reaches the oldest level that might still hold the key.
Concurrency Considerations
- WAL: append-only, single writer (lock or lock-free append)
- Memtable: concurrent reads are safe during writes if using a concurrent skip list (like LevelDB)
- SSTable: immutable after creation — reads are always safe, no locks needed
- Flush: swap active memtable atomically — new writes go to fresh memtable while old one flushes to disk
- Compaction: runs in background thread, atomically swaps old SSTables for new merged one
See our Storage Engines and Write-Ahead Logging pages.
Hints
- Write the read path first: memtable → immutable memtable being flushed → SSTables from newest to oldest. Stop at the first hit, and a tombstone counts as a hit that means "deleted".
- A
putis durable once its WAL record is on disk. When must youfsync: on every write, or batched (group commit)? Name the trade-off. - You may only truncate the WAL after the memtable it covers is safely written as an SSTable and that file is fsynced and recorded in a manifest.
- Keep SSTables in memory in your answer (a sorted array plus a Bloom filter). The design matters, not the file format.
Solution outline
- Entities:
DBEngine,WriteAheadLog,Memtable(sorted map: a skip list orTreeMap),SSTable(immutable sorted entries, sparse index, Bloom filter, min and max key),Manifest(the current list of live SSTables),Compactor,Entry(key, value or tombstone, sequence number). - Write: take a sequence number, append to the WAL, insert into the active memtable. If the memtable is full, freeze it as the immutable memtable, start a new one plus a new WAL segment, and flush the frozen one in the background. After the flush, add the SSTable to the manifest and delete the old WAL segment.
- Recovery: load the manifest, then replay the WAL segments newer than the last flush into a fresh memtable.
- Scan: a k-way merge iterator over the memtables and every overlapping SSTable. On equal keys, keep the newest sequence number and skip tombstones.
- Patterns: Iterator (merging iterators are the heart of scans and compaction). Strategy for compaction policy (size-tiered or leveled). Proxy for the Bloom filter in front of each table.
- Concurrency: one writer appends to the WAL under a lock. Readers grab an immutable snapshot of the current memtable, immutable memtable and SSTable list in one atomic read of a version object. Flush and compaction publish a new version by swapping one reference. Old SSTables are deleted only when no reader still holds a version that uses them (reference counting).
- Edge cases: a crash in the middle of a flush (the WAL still covers it), a torn final WAL record (checksum each record and stop replay at the first bad one), deleting a key that only exists in an old SSTable (the tombstone must outlive it), and a scan whose range spans a running compaction.
- Related case study: KV Store builds the in-memory API (TTL, transactions) that would sit on top of an engine like this.
Problem 2: Minimal Web Framework
Design a web framework (like a simplified Express.js) with routing, middleware pipeline, request/response abstraction, and error handling.
Requirements
- HTTP method-based routing: GET, POST, PUT, DELETE
- Route parameters:
/users/:id - Middleware pipeline: each middleware can modify request/response or short-circuit
- Error handling middleware
- Request body parsing (JSON, form data)
- Response helpers:
json(),send(),status(),redirect() - Static file serving
Key Classes
interface Framework {
get(path: string, ...handlers: Handler[]): void;
post(path: string, ...handlers: Handler[]): void;
use(middleware: Middleware): void;
use(path: string, middleware: Middleware): void;
listen(port: number): void;
}
type Handler = (req: Request, res: Response, next: NextFunction) => void | Promise<void>;
type Middleware = Handler;
type NextFunction = (error?: Error) => void;
interface Router {
addRoute(method: string, path: string, handlers: Handler[]): void;
match(method: string, url: string): RouteMatch | null;
}
interface RouteMatch {
handlers: Handler[];
params: Record<string, string>; // { id: "123" }
}
Complexity Analysis
| Operation | Approach | Complexity |
|---|---|---|
| Route matching | Radix tree (trie) | O(path length) |
| Route matching | Linear scan | O(number of routes) |
| Middleware execution | Pipeline (array iteration) | O(number of middleware) |
| Parameter extraction | Regex groups | O(path length) |
Concurrency Considerations
- Each request runs in its own context — no shared mutable state between requests
- Middleware must call
next()or respond — framework should detect stuck middleware (timeout) - Async handlers: wrap in try/catch, pass errors to error-handling middleware
- Static file serving: use streaming (not loading entire file into memory)
Hints
- Build
next()as a closure over an index into the handler array. Each call runs the handler atindex + 1. Callingnext(err)jumps to the next error handler (one that takes 4 parameters in Express's convention). - Calling
next()twice from one middleware is a real bug in the wild. Detect it and throw. - Routing: static segments win over
:params, which win over*wildcards. Use a trie where each node has static children, at most one param child and at most one wildcard child. - Async errors: a rejected promise from a handler must reach the error middleware. Wrap each call and catch.
Solution outline
- Entities:
App(global middleware, router),Router(a trie per HTTP method),RouteNode(static children, param child with name, wildcard child, handlers),Request(method, path, params, query, headers, body),Response(status, headers,json,send,redirect, aheadersSentflag),Layer(path prefix plus handler). - Dispatch: match the route to get params and handlers. Build the chain
[...globalMiddleware matching the path prefix, ...routeHandlers]and run it with the index-basednext. If the chain ends without a response, send 404. If an error escapes, run the error handlers, and if none responds, send 500 without leaking the stack trace. - Patterns: Chain of Responsibility for middleware. Composite for routers mounted inside routers (
app.use('/api', apiRouter)). Facade forResponsehelpers over the raw socket. Strategy for body parsers by content type. - Concurrency: handlers share nothing per request, but the route table is shared. Freeze it when
listen()is called, or rebuild and swap it atomically if hot reload is supported. Middleware that keeps a cache or counter is shared state. Say so. - Edge cases: trailing slashes, URL-encoded params (
%20), the same path with different methods (405 with anAllowheader instead of 404), and writing to the response after headers were sent.
Problem 3: Container Runtime (Simplified)
Design a simplified container runtime that manages container lifecycle, resource isolation, and networking.
Requirements
- Create, start, stop, remove containers
- Image management: pull, list, layer-based storage
- Resource limits: CPU, memory
- Container networking: bridge mode, port mapping
- Volume mounting: host path → container path
- Container logs: stdout/stderr capture
- Health checks with configurable intervals
Key Classes
classDiagram
class ContainerRuntime {
+create(config: ContainerConfig): Container
+start(containerId)
+stop(containerId, timeout)
+remove(containerId)
+exec(containerId, command): ExecResult
+logs(containerId, follow?): Stream
}
class Container {
-id: string
-pid: number
-state: ContainerState
-config: ContainerConfig
-namespaces: Namespace[]
-cgroups: CgroupConfig
}
class ImageStore {
+pull(imageName, tag): Image
+list(): Image[]
+getLayer(layerId): Layer
}
class NetworkManager {
+createBridge(name): Bridge
+attachContainer(containerId, bridgeId)
+addPortMapping(containerId, hostPort, containerPort)
}
class CgroupManager {
+setMemoryLimit(containerId, bytes)
+setCPULimit(containerId, shares)
+getStats(containerId): ResourceStats
}
ContainerRuntime --> Container
ContainerRuntime --> ImageStore
ContainerRuntime --> NetworkManager
ContainerRuntime --> CgroupManager
Complexity Analysis
- Container creation: O(number of layers) for overlay filesystem setup
- Start/stop: O(1) — send signal to process
- Image pull: O(total layer size) — network-bound
- Layer deduplication: O(1) lookup by content hash (content-addressable storage)
Concurrency Considerations
- State machine for container lifecycle:
CREATED -> RUNNING -> STOPPED -> REMOVED(Correction (2026-11-10): that's the happy path, not the whole machine. A stopped container can be started again (STOPPED → RUNNING), a created container can be removed without ever running (CREATED → REMOVED), and real runtimes add PAUSED (RUNNING ⇄ PAUSED) and an exit without a stop request (RUNNING → EXITED, when the main process dies).) - Container state transitions must be atomic — use locking per container ID
- Multiple containers share the same network bridge — bridge management needs synchronization
- Health check runner: single goroutine/thread per container, or shared pool with scheduling
- Log streaming: ring buffer per container, readers can attach/detach without affecting the container
See our Docker Internals and Containers from Scratch pages.
Hints
- You won't write namespace syscalls in an interview. Put the OS behind interfaces (
ProcessLauncher,CgroupManager,NetworkManager,FilesystemManager) and design the orchestration around them. createtouches four subsystems (filesystem, cgroup, network, process). If step 3 fails, steps 1 and 2 must be undone in reverse order.stopwith a timeout means: send SIGTERM, wait up to the timeout, then send SIGKILL. The wait mustn't block other containers' operations.- Port mappings are a shared, exclusive resource: two containers can't both bind host port 8080.
Solution outline
- Entities:
ContainerRuntime(facade),Container(id, config, state, pid, exit code, timestamps),ContainerConfig(image, command, env, limits, mounts, ports),ImageStore(images → ordered layer ids),Layer(content hash),FilesystemManager(overlay: lower layers plus a writable upper layer),CgroupManager,NetworkManager(bridges, IP allocation, port table),LogBuffer(ring buffer),HealthChecker. - Create: resolve the image's layers, prepare the overlay, create the cgroup with limits, allocate an IP and reserve the host ports. Record each completed step and undo the completed ones in reverse on failure. The state ends as CREATED. Start: launch the process in the namespaces, attach stdout and stderr to the log buffer, and set RUNNING. A watcher thread waits on the pid and moves the container to EXITED with the exit code.
- Patterns: State for the lifecycle, with each state rejecting illegal operations. Facade over the subsystems. Command with undo for the create steps. Observer for events (
docker events) and log followers. Flyweight thinking for shared read-only image layers. - Concurrency: a lock per container id for state transitions, never a global lock held across slow operations. The port table and the IP allocator are shared, so guard them with their own locks and keep those critical sections tiny. The ring buffer supports one writer and many readers, and slow readers lose old lines instead of blocking the container.
- Edge cases: removing a running container (refuse, or force-stop first), a process exiting during
stop(both paths must agree on the final state), a pull interrupted halfway (layers are content-addressed, so the next pull reuses finished ones), and a health check that hangs (give it its own timeout).
Problem 4: Distributed Lock Manager
Design a distributed lock service that provides mutual exclusion across multiple processes/machines.
Requirements
- Acquire lock with timeout (blocks until acquired or timeout)
- Try-acquire (non-blocking, returns immediately)
- Release lock
- Lock expiry: auto-release if holder crashes
- Reentrant locks: same owner can acquire multiple times
- Fencing tokens: monotonically increasing token to prevent stale holders
- Watch mechanism: notify when lock becomes available
Key Classes
interface DistributedLockManager {
acquire(lockId: string, options?: LockOptions): Promise<LockHandle>;
tryAcquire(lockId: string): Promise<LockHandle | null>;
release(handle: LockHandle): Promise<void>;
isLocked(lockId: string): Promise<boolean>;
watch(lockId: string, callback: () => void): Unsubscribe;
}
interface LockHandle {
lockId: string;
owner: string; // Process/node identifier
fencingToken: number; // Monotonically increasing
expiresAt: number;
renewalInterval: NodeJS.Timeout;
}
interface LockOptions {
ttl: number; // Lock expiry in ms
timeout?: number; // Wait timeout in ms
retryInterval?: number;
reentrant?: boolean;
}
// Redis-based implementation sketch
class RedisLockManager implements DistributedLockManager {
// Uses SET NX EX for atomic acquire
// Uses Lua script for atomic release (check owner then delete)
// Uses WATCH + MULTI for fencing token generation
}
Complexity Analysis
| Operation | Redis | ZooKeeper |
|---|---|---|
| Acquire | O(1) | O(log n) sequential nodes |
| Release | O(1) | O(1) delete ephemeral node |
| Watch | O(1) pub/sub | O(1) watch notification |
| Renewal | O(1) PEXPIRE | N/A (session-based) |
Concurrency Considerations
- Fencing tokens prevent the critical bug: Process A acquires lock, gets paused by GC, lock expires, Process B acquires lock, Process A resumes and thinks it still holds the lock. With fencing tokens, the resource rejects operations with stale tokens.
- Lock renewal: background thread extends TTL periodically while lock is held
- Redlock controversy: single Redis instance is simpler and sufficient for most use cases. Redlock (multi-node) is debated — see Martin Kleppmann's analysis.
- Split-brain: if network partitions the lock service, two holders might exist simultaneously. Accept this limitation or use consensus-based locks (ZooKeeper, etcd).
See our Distributed Locking page.
Hints
- Start with a single-node lock server in memory (a map of lockId → holder, expiry and token). Then ask what changes when clients and the server can fail independently.
- Release must check ownership atomically: "is this still my lock?" then "delete" as two steps lets you delete someone else's lock after yours expired.
- Fencing only works if the protected resource checks the token. The lock service alone can't enforce it.
- Reentrancy needs a hold count per owner, and the owner id must identify a thread or task, not just a process.
Solution outline
- Entities:
LockManager,LockRecord(lockId, owner, hold count, fencing token, expiresAt, a FIFO queue of waiters),LockHandle(what the client holds),TokenCounter(monotonic, survives restarts),LeaseRenewer,Watcher. - Acquire: atomically, if the lock is free or expired, set the owner, increment the global token and set the expiry. If it's held by the same owner and reentrant, increment the hold count. Otherwise enqueue a waiter, or return null for
tryAcquire. Release: atomically check the owner and token, decrement the hold count, and when it reaches 0, clear the lock and wake the first waiter. Renew: extend the expiry only if the owner and token still match. - Patterns: Proxy (the client-side handle that renews its lease in the background). Observer for watches. Strategy for the backend (in-memory, Redis, etcd).
- Concurrency: inside the server, every operation on one
LockRecordis atomic (a lock per record, or a single-threaded actor). Across the network, assume the client can pause for longer than its lease. The token is the only defence, so the storage layer must reject writes carrying a token lower than one it has already seen. - Edge cases: the clock jumping on the server (use a monotonic clock for expiry), renewal failing while the client is mid-work (the client must stop or rely on fencing), a waiter whose wait times out (remove it from the queue), and lock service restarts (the token counter must persist, or tokens could repeat).
Problem 5: Search Engine Indexer
Design the indexing component of a search engine that builds and queries an inverted index.
Requirements
- Index documents: extract tokens, build inverted index
- Query types: single term, AND, OR, phrase queries
- TF-IDF scoring for relevance ranking
- Incremental indexing: add/update/delete documents without rebuilding
- Index segments: write-once segments, merge in background
- Tokenization: lowercase, stemming, stop word removal
Key Classes
classDiagram
class Indexer {
+indexDocument(doc: Document)
+deleteDocument(docId: string)
+search(query: Query): SearchResult[]
+optimize()
}
class InvertedIndex {
-postingLists: Map~string, PostingList~
+addPosting(term, docId, positions)
+getPostings(term): PostingList
+merge(other: InvertedIndex)
}
class PostingList {
-docIds: number[]
-frequencies: number[]
-positions: number[][]
+intersect(other: PostingList): PostingList
+union(other: PostingList): PostingList
}
class Tokenizer {
+tokenize(text: string): Token[]
}
class Scorer {
+tfidf(term, docId, index): number
+bm25(term, docId, index): number
}
Indexer --> InvertedIndex
Indexer --> Tokenizer
Indexer --> Scorer
InvertedIndex --> PostingList
Complexity Analysis
| Operation | Complexity | Notes |
|---|---|---|
| Index 1 document | O(tokens in doc) | Tokenize + insert into posting lists |
| Single term query | O(posting list length) | Iterate posting list, score each |
| AND query (2 terms) | O(min(list1, list2)) | Intersect sorted posting lists (Correction (2026-11-10): a plain two-pointer merge is O(list1 + list2). You get close to O(min · log(max)) only with skip pointers or galloping search into the longer list.) |
| OR query (2 terms) | O(list1 + list2) | Union sorted posting lists |
| Phrase query | O(min(lists) * avg positions) | Intersect + check adjacent positions |
| TF-IDF scoring | O(1) per doc | Precomputed term frequency + IDF |
Concurrency Considerations
- Index segments are immutable after creation — reads need no locks
- Write buffer (in-memory index) handles new documents, periodically flushed to new segment
- Segment merge runs in background — atomically swap old segments for new merged one
- Search queries fan out across all segments, merge results by score
- Delete: mark document as deleted in a bitset, filter during search, physically remove during merge
See our Elasticsearch Internals page.
Hints
- Map external string document ids to dense internal integers. Sorted integer posting lists are what make intersection and compression cheap.
- An "update" is delete plus re-add. Segments are immutable, so you can't edit a posting list in place.
- IDF depends on the whole collection, but segments are separate. Compute it from collection-wide statistics, or accept a small per-segment skew and say so.
- For AND queries, start the intersection from the rarest term.
Solution outline
- Entities:
Indexer,Analyzer(tokenizer → lowercase → stop words → stemmer, as a pipeline),Segment(immutable: term dictionary →PostingList, per-document lengths, a deleted-docs bitset),WriteBuffer(mutable in-memory segment),PostingList(doc ids, term frequencies, positions),Querytree (TermQuery,AndQuery,OrQuery,PhraseQuery),Scorer(TF-IDF or BM25),SegmentMerger. - Index: analyse the text, add postings to the write buffer, and flush it to a new segment when it's full. Delete: set the bit in the deleted set of whichever segment holds the doc. Search: for each segment, evaluate the query tree into a doc-id iterator, skip deleted docs, score them and keep a top-k heap. Then merge the per-segment heaps.
- Patterns: Interpreter or Composite for the query tree. Chain of Responsibility-style pipeline for analysis filters. Strategy for scoring. Iterator for posting-list traversal.
- Concurrency: searchers take a snapshot of the current segment list (one atomic reference). Merges build a new segment off to the side and publish a new list. Deletions flip bits in a copy-on-write bitset, or a concurrent one, per segment. One writer thread owns the write buffer. Refresh makes it searchable by turning it into a segment.
- Edge cases: a phrase query with a repeated word ("to be or not to be"), a query of only stop words (return nothing, or skip stop-word removal for it), very common terms with huge posting lists, and deleting a document still in the write buffer.
Problem 6: In-Memory Message Broker
Design a message broker (simplified Kafka) with topics, partitions, consumer groups, and offset management.
Requirements
- Topics with configurable number of partitions
- Producers append messages to partitions (by key hash or round-robin)
- Consumer groups: each message consumed by exactly one consumer in the group
- Offset tracking: consumers commit offsets, can replay from any offset
- Retention: time-based or size-based message expiry
- At-least-once delivery semantics
- Rebalancing when consumers join/leave a group
Key Classes
interface Broker {
createTopic(name: string, partitions: number): void;
produce(topic: string, key: string | null, value: Buffer): ProduceResult;
subscribe(topic: string, groupId: string, handler: MessageHandler): Consumer;
commitOffset(groupId: string, topic: string, partition: number, offset: number): void;
seekToOffset(groupId: string, topic: string, partition: number, offset: number): void;
}
interface Partition {
id: number;
log: Message[]; // Append-only log
highWatermark: number; // Last committed offset. Correction (2026-11-10): in Kafka the high watermark is the offset up to which the log is replicated to all in-sync replicas, i.e. what consumers may read; consumer-committed offsets live in ConsumerGroup.offsets below)
retentionMs: number;
}
interface ConsumerGroup {
id: string;
members: Consumer[];
assignments: Map<number, Consumer>; // partition -> consumer
offsets: Map<number, number>; // partition -> committed offset
rebalance(): void;
}
Complexity Analysis
| Operation | Complexity |
|---|---|
| Produce (append to partition) | O(1) amortized |
| Consume (read at offset) | O(1) random access |
| Rebalance (N consumers, P partitions) | O(P) reassignment |
| Offset commit | O(1) |
| Retention cleanup | O(expired messages) |
Concurrency Considerations
- Each partition is single-writer: producer writes are serialized per partition
- Multiple consumers read different partitions concurrently — no contention
- Rebalancing: stop consumption, reassign partitions, resume — use a coordinator lock
- Offset commits: per-consumer-group, per-partition — no cross-partition coordination needed
- Message retention: background cleaner thread trims old messages per partition
See our Kafka Internals page.
Hints
- The broker doesn't delete a message when it's consumed. Each group just remembers how far it has read. That one idea gives you replay, many groups reading the same topic, and cheap consumption.
- Retention removes messages from the front, but offsets must stay stable. Keep a
baseOffsetper partition (or per segment), so offset → array index isoffset − baseOffset. - At-least-once comes from the order: process, then commit. A crash between them means re-delivery, never loss.
- During a rebalance, a partition must have exactly one owner. Bump a generation number, and reject commits from the old generation.
Solution outline
- Entities:
Broker,Topic(partitions),Partition(append-only log, baseOffset, logEndOffset, retention),Message(offset, key, value, timestamp),ConsumerGroup(members, generation, assignment partition → member, committed offsets),Consumer(member id, assigned partitions, fetch positions),Partitioner(hash of key mod N, or round-robin),AssignmentStrategy(range, round-robin, sticky). - Produce: the partitioner picks a partition, the message is appended under the partition's lock and gets the next offset, which is returned. Fetch: read from the consumer's position up to
maxMessageswithout removing anything. Commit: store the offset for (group, partition) if the generation matches. Join or leave: increment the generation, recompute assignments with the strategy, and tell members to restart from the committed offsets. - Patterns: Strategy for partitioning and assignment. Observer for push-style handlers on top of a pull loop. Mediator for the group coordinator.
- Concurrency: a lock per partition for appends (single writer), and lock-free reads of an immutable prefix (readers only look below
logEndOffset, published with a volatile write). Group membership changes go through one coordinator lock per group. Offset commits are per-key atomic puts. - Edge cases: a consumer committing an offset beyond the log end (reject), a seek to an offset already removed by retention (reset to earliest or latest, by policy), a slow consumer whose partitions are reassigned while it's still processing, and a key whose partition count changes (ordering breaks, so warn about it).
- Related case study: Pub-Sub is the simpler in-process broker to build first.
Problem 7: API Gateway
Design an API gateway that routes requests, handles authentication, rate limiting, and circuit breaking.
Requirements
- Route requests to backend services based on path, method, headers
- Authentication: JWT validation, API key lookup
- Rate limiting per client, per route
- Circuit breaker per backend service
- Request/response transformation
- Load balancing across backend instances
- Request logging and metrics
Key Classes
interface APIGateway {
registerRoute(route: RouteConfig): void;
handleRequest(req: IncomingRequest): Promise<GatewayResponse>;
}
interface RouteConfig {
path: string; // "/api/v1/orders/*"
methods: string[];
backend: BackendConfig;
middleware: MiddlewareConfig[];
rateLimit?: RateLimitConfig;
auth?: AuthConfig;
circuitBreaker?: CircuitBreakerConfig;
transform?: TransformConfig;
}
// Middleware pipeline: Auth -> RateLimit -> Transform -> CircuitBreaker -> Proxy -> Transform Response
type MiddlewarePipeline = (req: GatewayRequest) => Promise<GatewayResponse>;
Concurrency Considerations
- Request handling must be fully concurrent — thousands of simultaneous requests
- Rate limiter state must be thread-safe (atomic counters or Redis)
- Circuit breaker state transitions must be atomic (compare-and-swap)
- Route table updates (hot reload) must be atomic — swap entire routing table, no mid-request inconsistency
- Connection pooling to backends — reuse TCP connections per backend
See our API Gateway vs Service Mesh page.
Hints
- Build the middleware chain for each route once, when routes are registered, not on every request.
- Order matters. Authenticate before rate limiting by client id (otherwise you can't tell clients apart), but put a cheap per-IP limit before authentication so a flood of invalid tokens can't burn CPU.
- The circuit breaker is a three-state machine per backend. HALF_OPEN should let one probe request through, not a stampede.
- Timeouts belong in the proxy step, and each retry must fit inside the caller's overall deadline.
Solution outline
- Entities:
Gateway,RouteTable(immutable: a matcher by path, method and headers),Route(config plus its pre-built pipeline),Filter(Auth,RateLimit,Transform,CircuitBreaker,Proxy),BackendPool(instances plus a load-balancing strategy),CircuitBreaker(state, failure counter, open-until time),RateLimiterper (client, route). - Request: match the route with one read of the current table, run the pipeline (each filter can short-circuit with a response, for example 401, 429 or 503), proxy to a backend instance chosen by the balancer, run response transforms on the way back, and record metrics.
- Patterns: Chain of Responsibility for filters. State for the circuit breaker. Strategy for load balancing and for auth schemes (JWT, API key). Proxy in the literal sense. Decorator is the other way to see the filter stack.
- Concurrency: the route table is published through an atomic reference, so a hot reload builds a new table and swaps it in. In-flight requests finish on the old one. Rate-limiter state lives in a concurrent map with atomic per-key updates. The circuit breaker moves between states with compare-and-set, and only the thread that wins the OPEN → HALF_OPEN change sends the probe.
- Edge cases: a route matching two patterns (longest prefix wins, decided at load time), a backend pool with every instance unhealthy (fail fast with 503), a JWT signing key rotating (cache keys by key id), and request bodies too large to buffer (stream them through).
- Related case study: Rate Limiter for the limiter class used here.
Problem 8: Load Balancer
Design an L7 load balancer with multiple algorithms, health checking, session affinity, and graceful draining.
Requirements
- Algorithms: round-robin, weighted round-robin, least connections, consistent hashing
- Health checking: active (periodic HTTP checks) and passive (track failure rates)
- Session affinity: sticky sessions by cookie or IP
- Connection draining: stop sending new requests to a backend, wait for existing to complete
- Dynamic backend registration/deregistration
- Request queuing when all backends are busy
Key Classes
interface LoadBalancer {
addBackend(backend: Backend): void;
removeBackend(backendId: string): void;
selectBackend(request: Request): Backend;
drain(backendId: string, timeout: number): Promise<void>;
}
interface LoadBalancingAlgorithm {
select(backends: Backend[], request: Request): Backend;
}
interface HealthChecker {
start(backends: Backend[]): void;
isHealthy(backendId: string): boolean;
onHealthChange(callback: (backendId: string, healthy: boolean) => void): void;
}
interface Backend {
id: string;
address: string;
port: number;
weight: number;
activeConnections: number;
healthy: boolean;
draining: boolean;
}
Complexity Analysis
| Algorithm | Select | Add/Remove Backend |
|---|---|---|
| Round-Robin | O(1) | O(1) |
| Weighted Round-Robin | O(1) amortized | O(N) rebuild weights |
| Least Connections | O(N) scan or O(log N) heap | O(log N) |
| Consistent Hashing | O(log V) binary search virtual nodes | O(V log V) rebuild ring |
Concurrency Considerations
- Backend selection must handle concurrent requests — atomic counter for round-robin
- Active connection tracking: atomic increment/decrement per backend
- Health check results: eventually consistent is fine — a few requests to an unhealthy backend is acceptable
- Connection draining: mark backend as draining, track in-flight requests, complete when all finish or timeout
See our Load Balancing Algorithms and Health Checks pages.
Hints
- Every algorithm takes the eligible backends (healthy and not draining). Compute that list in one place, not inside each algorithm.
- Weighted round-robin done naively (A, A, A, B) sends bursts to one backend. "Smooth" weighted round-robin, as nginx does it, spreads them out.
- Least-connections needs an accurate in-flight count, so the decrement must run however the request ends: success, error or timeout.
- Consistent hashing: adding or removing a backend should move only about 1/N of the keys. Virtual nodes even out the load.
Solution outline
- Entities:
LoadBalancer,Backend(id, address, weight, an atomic active-connection count, health, draining flag),BackendSet(immutable snapshot),LoadBalancingAlgorithm(RoundRobin,SmoothWeightedRoundRobin,LeastConnections,ConsistentHash),HealthChecker(active probes plus passive failure counting),AffinityTable(session → backend, with a TTL). - Select: if there's an affinity key mapped to a backend that's still eligible, use it. Otherwise ask the algorithm for a backend from the eligible snapshot, increment its active count and record the affinity. Release decrements the count. Drain: mark the backend draining (it leaves the eligible set at once), then wait until its active count is 0 or the timeout passes, then remove it.
- Patterns: Strategy for algorithms. Observer for health changes rebuilding the eligible set. Proxy for the balancer as a whole.
- Concurrency: backend set changes build a new immutable snapshot and swap it in (copy-on-write), so selection never locks. The round-robin index is an
AtomicIntegertaken modulo the snapshot size. Smooth weighted round-robin updates several counters at once, so put a small lock around it (or one per worker thread). Connection counts are atomics. - Edge cases: no eligible backends (queue with a timeout, or return 503), a backend flapping between healthy and unhealthy (needs N consecutive results to change state), affinity pointing at a draining backend (keep existing sessions, send no new ones), and a weight of 0.
Problem 9: Cron Scheduler
Design a cron scheduler that manages scheduled jobs with cron expressions, persistence, and distributed execution.
Requirements
- Parse cron expressions (minute, hour, day, month, day-of-week)
- Register/unregister jobs
- Execute jobs at scheduled times with second-level precision
- Missed job detection: if scheduler was down, run missed jobs on startup
- Distributed: multiple scheduler instances, each job runs on exactly one instance
- Job history: track execution results, duration, failures
- Retry failed jobs with configurable policy
Key Classes
interface CronScheduler {
schedule(jobId: string, cronExpr: string, handler: JobHandler): void;
unschedule(jobId: string): void;
getNextRunTime(jobId: string): Date;
getJobHistory(jobId: string, limit?: number): JobExecution[];
pause(jobId: string): void;
resume(jobId: string): void;
}
interface CronExpression {
minutes: Set<number>; // 0-59
hours: Set<number>; // 0-23
daysOfMonth: Set<number>; // 1-31
months: Set<number>; // 1-12
daysOfWeek: Set<number>; // 0-6
nextAfter(date: Date): Date;
matches(date: Date): boolean;
}
interface JobExecution {
jobId: string;
scheduledAt: Date;
startedAt: Date;
completedAt?: Date;
status: 'running' | 'completed' | 'failed';
result?: unknown;
error?: string;
executorId: string; // Which scheduler instance ran it
}
Complexity Analysis
- Cron expression parsing: O(1) — fixed 5-field format
- Next run time calculation: O(days in search range) worst case, O(1) average
- Job selection: O(N) scan all jobs, or O(log N) with priority queue ordered by next run time
- Distributed lock acquisition: O(1) with Redis
Concurrency Considerations
- Distributed execution: use a distributed lock per job — only one instance executes each job
- Leader election alternative: elect one scheduler as leader, it assigns jobs to workers
- Missed jobs: on startup, check for jobs whose
nextRunTime < nowandlastExecution < nextRunTime - Clock skew: in distributed mode, use a shared time source or accept small windows of overlap
- Idempotent jobs: since distributed locks can fail, jobs should be safe to run twice
Hints
- Standard cron has a trap: when both day-of-month and day-of-week are restricted, a time matches if either one matches, not both.
0 0 13 * 5means every 13th and every Friday. - Don't scan every job every second. Keep a min-heap of (next run time, job). Sleep until the top is due, run it, compute its next time and push it back.
nextAftercan step minute by minute, but that's slow for rare schedules like February 29th. Skip whole months, days and hours that can't match.- The "exactly one instance runs it" requirement is really "one instance claims the (job, scheduled time) pair". A unique claim key works better than a long-held lock.
Solution outline
- Entities:
CronScheduler,Job(id, expression, handler, time zone, a paused flag, a retry policy),CronExpression(parsed sets plusnextAfter),ScheduleQueue(a min-heap by next run),JobExecution(history),ClaimStore(claims on (jobId, scheduledAt)),Clock. - Loop: peek the heap and wait until the top is due (wake early if a job is added or removed). Pop it, try to claim (jobId, scheduledAt) in the claim store, and on success run it on a worker pool with retries. Always compute the next time and push the job back, whether or not this instance won the claim.
- Startup: for each job, compute the runs between its last recorded execution and now, and apply a misfire policy: run once, run all, or skip.
- Patterns: Interpreter for parsing the cron mini-language. Command for jobs. Strategy for misfire and retry policies. Observer for execution events.
- Concurrency: one scheduler thread owns the heap, and other threads add or remove jobs through a lock plus a condition variable that wakes it. Handlers run on a separate pool so a slow job doesn't delay the next one. Across instances, the claim store's insert-if-absent is the single point of agreement.
- Edge cases: daylight saving changes (02:30 may happen zero times or twice, so pick a policy), a job still running when its next run is due (skip, queue or allow overlap, configured per job), an unschedule while the job is running, and expressions that never match (
0 0 30 2 *), which must be rejected at registration time. - Related case study: Task Scheduler for delayed and recurring jobs, priorities and the worker pool.
Problem 10: Consensus Module
Design a simplified Raft consensus module that achieves agreement across a cluster of nodes.
Requirements
- Leader election with randomized timeouts
- Log replication from leader to followers
- Commit entries when majority acknowledges
- Handle leader failure and re-election
- Handle network partitions
- Snapshot and log compaction
- Membership changes (add/remove nodes)
Key Classes
classDiagram
class RaftNode {
-state: NodeState
-currentTerm: number
-votedFor: string?
-log: LogEntry[]
-commitIndex: number
-lastApplied: number
+requestVote(request): VoteResponse
+appendEntries(request): AppendResponse
+propose(command): ProposeResult
}
class LeaderState {
-nextIndex: Map~nodeId, number~
-matchIndex: Map~nodeId, number~
+sendHeartbeats()
+replicateLog(entry: LogEntry)
}
class ElectionTimer {
-timeout: number
-onTimeout: Function
+reset()
+start()
+stop()
}
class StateMachine {
<<interface>>
+apply(command: Command): Result
+snapshot(): Snapshot
+restore(snapshot: Snapshot)
}
RaftNode --> LeaderState
RaftNode --> ElectionTimer
RaftNode --> StateMachine
Key Data Structures
interface LogEntry {
term: number;
index: number;
command: Command;
}
interface RequestVoteRPC {
term: number;
candidateId: string;
lastLogIndex: number;
lastLogTerm: number;
}
interface AppendEntriesRPC {
term: number;
leaderId: string;
prevLogIndex: number;
prevLogTerm: number;
entries: LogEntry[];
leaderCommit: number;
}
type NodeState = 'FOLLOWER' | 'CANDIDATE' | 'LEADER';
Concurrency Considerations
- Single-threaded event loop per node: process one RPC at a time to avoid concurrency bugs in state transitions
- Election timeout: randomized (150-300ms) to avoid split votes
- Log persistence: entries must be fsynced to disk before acknowledging — crash recovery depends on it
- Committed entries: once committed (majority acknowledged), they are never lost — this is the core safety guarantee
- Membership changes: use joint consensus (Raft Section 6) — never have two independent majorities
See our Raft Full Walkthrough page.
Hints
- Two rules settle most bugs: any message with a higher term makes you a follower with that term, and you reject any message with a lower term.
- A vote is granted only if the candidate's log is at least as up to date as yours: compare last log term first, then last log index. This rule is what keeps committed entries safe.
- A leader may only count replicas toward committing entries from its own current term. Older entries become committed indirectly (Raft paper, Figure 8).
- Persist
currentTerm,votedForand the log before replying to any RPC. Everything else can be rebuilt after a restart.
Solution outline
- Entities:
RaftNode(role, persistent state, volatile state),PersistentState(currentTerm, votedFor, log, saved through aStorageinterface),LeaderState(nextIndex and matchIndex per peer),ElectionTimer(randomised),Transport(sends RPCs, delivers responses as events),StateMachine(applies committed commands),Snapshot. - Election: on timeout, increment the term, vote for yourself, persist, and send
RequestVoteto all peers. A majority makes you leader: initialisenextIndex = lastIndex + 1and send heartbeats at once. Replication: for each peer, send entries fromnextIndex. On a log mismatch, decrementnextIndexand retry. On success, updatematchIndex, then advancecommitIndexto the highest N where a majority hasmatchIndex ≥ Nandlog[N].term == currentTerm. Apply entries up tocommitIndexin order. - Patterns: State for follower, candidate and leader, each handling the same RPCs differently. Command for log entries. Strategy for the transport and storage (in-memory ones make a deterministic test harness possible). Observer for clients waiting on a proposal to commit.
- Concurrency: one event loop per node processes timer ticks, incoming RPCs and RPC responses one at a time from a single queue. That removes almost all locking. Network I/O happens on other threads, which only post events to the queue. Test it by running several nodes in one process with a simulated network that drops, delays and reorders messages.
- Edge cases: a stale leader in a minority partition (it can't commit, and steps down when it sees a higher term), a follower log with extra uncommitted entries (they get truncated), duplicate client proposals after a leader change (deduplicate with client id and sequence number), and a snapshot install racing with log appends.
Problem 11: Elevator System
Design the control software for a bank of elevators in one building.
Requirements
- N elevator cars serving floors 0..F
- Hall calls (up/down buttons on a floor) and car calls (floor buttons inside a car)
- A dispatcher assigns each hall call to one car
- Each car moves, stops, opens and closes doors, and serves its stops in a sensible order
- Support different dispatching strategies; handle a car going out of service
- Requests keep arriving while cars are moving
Hints
- Separate the dispatcher (which car takes this hall call?) from the car controller (in what order does this car visit its stops?). They are two different strategies.
- A car's own movement is a state machine: IDLE, MOVING_UP, MOVING_DOWN, DOORS_OPEN, OUT_OF_SERVICE.
- The SCAN / LOOK idea: keep going in the current direction while there are stops ahead, then reverse. Two sorted sets (stops above, stops below) make this cheap.
- Simulate time with a
tick()method instead of real sleeps. Tests become deterministic.
Solution outline
- Entities:
Building,ElevatorCar(id, current floor, direction, state, up-stops and down-stops as sorted sets, capacity),HallCall(floor, direction),CarCall(car, floor),Dispatcher,DispatchStrategy(Nearest,LeastLoaded,ZoneBased,DestinationDispatch),CarStateclasses. - Hall call: the dispatcher scores every in-service car (distance, whether the car is already moving towards the call in the same direction, current load) and adds the stop to the best car. Tick: each car moves one floor towards its next stop. On arrival, it opens its doors, removes the stop, and after a dwell time picks the next stop by LOOK.
- Patterns: Strategy for dispatching and stop ordering. State for the car. Observer for floor displays and hall lanterns. Command for requests, if they're queued or logged.
- Concurrency: button presses come from many threads while the cars advance on a simulation thread. Put requests on a thread-safe queue that the control loop drains each tick, so all state changes happen on one thread. Or give each car its own lock and keep the dispatcher's reads of car state to short snapshots.
- Edge cases: a hall call on the floor where an idle car already is (just open the doors), a car going out of service with assigned calls (reassign them), a full car (skip hall calls until someone gets out), and the top and bottom floors (only one direction button).
- Full version: Elevator System.
Problem 12: Chess
Design a two-player chess game that validates every move, detects check, checkmate and stalemate, and supports undo.
Requirements
- 8×8 board with the standard pieces and starting position
- Validate moves per piece, including blocking pieces and captures
- A move that leaves your own king in check is illegal
- Detect check, checkmate and stalemate after every move
- Undo and redo moves
- Extensions: castling, en passant, pawn promotion, move history in algebraic notation
Hints
- Each piece knows its movement pattern. The board knows what's in the way. The game knows the rules that need history (castling rights, en passant, whose turn it is).
- Legality is "pseudo-legal move, and your king is not attacked afterwards". The simplest correct check is to apply the move, test whether the king is attacked, then undo it.
- Checkmate and stalemate are the same question: does the side to move have any legal move? They differ only in whether the king is in check now.
- Undo needs to restore captured pieces and special state (castling rights, en passant square), not just move a piece back.
Solution outline
- Entities:
Game(board, players, turn, status, move history, castling rights, en passant square),Board(8×8 grid ofPiece | null),Piece(abstract, colour) withKing,Queen,Rook,Bishop,KnightandPawn,Position(value object),Move(from, to, piece, captured, promotion, special flags),GameStatus. - Validation:
piece.candidateMoves(board, from)produces pseudo-legal moves. Sliding pieces walk each direction until blocked, and knights and kings use fixed offsets.Gameadds the special moves, then filters out any move after whichisSquareAttacked(kingPos, opponent)is true. - Patterns: polymorphism over pieces, or a table of direction vectors per piece type. Know both and the trade-off: classes are clearer, a table is more compact and faster. Command for moves with
execute()andundo(), plus undo and redo stacks. State for game status. Memento is the alternative for undo (snapshot the board), simpler but heavier. - Concurrency: usually none. For online play, the server serialises moves per game and checks the turn inside that lock. A clock per player is a scheduled timeout.
- Edge cases: castling through or out of check, en passant only on the very next move, promotion to a piece other than a queen, threefold repetition and the fifty-move rule (needs position hashing), and discovered check from a piece that didn't move.
- Full version: Chess.
Problem 13: Online Auction
Design an online auction system where sellers list items and bidders place bids until the auction closes.
Requirements
- Sellers create auctions with a starting price, optional reserve price and an end time
- Bidders place bids; each bid must beat the current highest by a minimum increment
- Show the current price and leader in real time to everyone watching
- Auction closes at the end time; highest bid at or above reserve wins
- Optional: proxy (automatic) bidding up to a bidder's maximum, and anti-sniping extension of the end time
- Thousands of bids may arrive in the last seconds
Hints
- The race everyone misses: a bid arriving at the same instant the auction closes. Who decides whether it counted? There must be exactly one serialisation point per auction.
- "Check the highest bid, then accept" is check-then-act. Make it one atomic step per auction.
- Proxy bidding is a small algorithm: when a new bid arrives, the system bids for each proxy up to its maximum. The price ends at second-highest maximum plus one increment, capped at the highest maximum.
- Anti-sniping: a bid in the last N seconds extends the end time. So the close timer must re-check the end time when it fires.
Solution outline
- Entities:
Auction(item, seller, start price, reserve, increment rule, endsAt, status: SCHEDULED, OPEN, CLOSED, CANCELLED, highest bid, version),Bid(bidder, amount, time, sequence number),ProxyBid(bidder, maximum),User,AuctionService,CloseScheduler,BidIncrementPolicy. - Place bid: under the auction's lock (or one actor per auction): reject the bid if the status isn't OPEN or
now ≥ endsAt, reject it if it's below the current price plus the increment, otherwise record it, run proxy resolution, extendendsAtif the bid is within the sniping window, then publish the new state. - Close: when the timer fires, take the same lock. If
now < endsAt(it was extended), reschedule. Otherwise set CLOSED and decide the winner against the reserve. Because bids and the close share one lock, every bid is clearly before or after the close. - Patterns: Observer for live updates to watchers. State for the auction lifecycle. Strategy for increment rules and auction types (English, Dutch, sealed-bid).
- Concurrency: a lock per auction, never a global one. Thousands of auctions bid in parallel, and only bids on the same item contend. In a database: a version column with compare-and-set on
(highestAmount, version), retrying on conflict. Fan out the notifications after releasing the lock. - Edge cases: a seller bidding on their own item (reject), two identical bids (the earlier sequence number wins), a bidder retracting a bid, and the winner not paying (offer the item to the runner-up).
- Full version: Online Auction.
Problem 14: Key-Value Store with Transactions
Design an in-memory key-value store with GET, SET, DELETE, per-key TTL, and nested transactions.
Requirements
get(key),set(key, value, ttl?),delete(key),count(value)(how many keys hold a value)- Expired keys behave as missing
begin(),commit(),rollback(); transactions can nest, androllbackundoes only the innermost onecommit()makes all open transactions permanent (or only the innermost — clarify)- Optional: multiple clients with isolation between their transactions
Hints
- Nested transactions are a stack. Each level records how to undo what it changed: the previous value of each key the first time it's touched at that level.
count(value)in O(1) needs a second map, value → number of keys. Every write updates both maps, and rollback must too.- Undo log or a copy-on-write overlay per transaction? An overlay makes reads walk the stack. An undo log keeps reads O(1) but writes the base map directly.
- With several clients, the questions become: does client B see client A's uncommitted write, and what happens when both commit changes to the same key?
Solution outline
- Entities:
KVStore(data map key →Entry, value-count map, transaction stack),Entry(value, expiresAt),Transaction(undo log: key → previousEntryor "absent"),Clock. - Single client:
setwrites the data map directly, updates the value counts and, if a transaction is open and the key isn't yet in its undo log, saves the old entry.rollbackpops the top transaction and restores each logged key, fixing the counts.commit(all levels) clears the stack. Committing only the innermost level merges its undo log into the parent's, keeping the parent's older entry when both have one. - TTL: lazy expiry on read, plus a periodic sweep using a min-heap of (expiresAt, key) that skips stale heap entries.
- Patterns: Command (each write with its inverse) or Memento (saved previous values). Both fit, so say which and why. Proxy or Decorator for a TTL layer over a plain map.
- Concurrency (multi-client): simplest is one global lock, which is serialisable and slow. Better: each client transaction writes to a private overlay, and on commit it validates that the keys it read haven't changed (versions per key), then applies its writes under a short lock. That's optimistic concurrency control. MVCC with per-key version chains gives snapshot reads without locking.
- Edge cases: rollback or commit with no open transaction (return an error, don't crash), deleting a key that doesn't exist inside a transaction (the undo log must record "absent"), a TTL expiring during a transaction, and
countfor a value set and then deleted at the same level. - Full version: In-Memory KV Store.
Difficulty Progression
| Problem | Core Challenge | Key Skill |
|---|---|---|
| Database Engine | Storage I/O, immutable data structures | Systems programming |
| Web Framework | Middleware composition, routing | API design |
| Container Runtime | OS abstractions, resource management | Linux internals |
| Distributed Lock | Correctness under failure | Distributed systems |
| Search Indexer | Inverted index, relevance scoring | Information retrieval |
| Message Broker | Partitioned log, consumer groups | Streaming systems |
| API Gateway | Plugin pipeline, resilience | Networking |
| Load Balancer | Selection algorithms, health tracking | Networking |
| Cron Scheduler | Time handling, distributed coordination | Reliability |
| Consensus Module | Safety and liveness guarantees | Distributed consensus |
| Elevator System | Scheduling under continuous requests | Strategy and State design |
| Chess | Rule validation, undo with full state | Polymorphism and Command |
| Online Auction | One serialisation point per auction | Concurrency in domain models |
| KV Store with Transactions | Nested undo, isolation | Transactions and MVCC basics |
Related Pages
- LLD Practice: Easy — foundational patterns
- LLD Practice: Medium — domain-level problems
- LLD Interview Guide — methodology and approach
- Common LLD Mistakes — especially "ignoring concurrency", which costs the most at this level
- Machine Coding Rounds — for rungs 1–4 as 90-minute coding rounds
- Storage Engines — LSM trees and B-trees in detail
- Kafka Internals — real-world message broker
- Raft Full Walkthrough — consensus in depth
- Docker Internals — real container runtime