On this page

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

#ProblemWhat it practisesTime boxFull case study
1Elevator System (P11)Strategy (scheduling), State per car, requests arriving while cars move60 minElevator System
2Chess (P12)Polymorphic move rules, check and checkmate, Command for undo60 minChess
3KV Store with Transactions (P14)Nested transactions, Memento or undo log, TTL, isolation60 minKV Store
4Online Auction (P13)Concurrent bids, the close-versus-last-bid race, Observer60 minOnline Auction
5Minimal Web Framework (P2)Chain of Responsibility (middleware), trie routing, async errors60 min—
6Load Balancer (P8)Strategy (algorithms), atomics, draining, health state60 min—
7API Gateway (P7)Pipeline, rate limiting, circuit breaker State, routing table swap75 minRate Limiter
8Cron Scheduler (P9)Expression parsing, priority queue of next runs, one runner per job75 minTask Scheduler
9In-Memory Message Broker (P6)Partitioned log, offsets, consumer groups, rebalancing75 minPub-Sub
10Search Engine Indexer (P5)Inverted index, posting-list merges, immutable segments75 min—
11Distributed Lock Manager (P4)Leases, fencing tokens, failure reasoning75 min—
12Simple Database Engine (P1)WAL, memtable swap, SSTables, compaction90 minKV Store
13Container Runtime (P3)Lifecycle State machine, a lock per container, resource managers90 min—
14Consensus Module (P10)Raft roles, terms, log matching, single-threaded event loop90 min—

How to use this ladder

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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

OperationMemtableSSTable LookupOverall
put()O(log n)N/AO(log n) + WAL append
get()O(log n)O(log n) per levelO(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 levelsO(L * log n + k)
CompactionN/AMerge L filesO(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 put is durable once its WAL record is on disk. When must you fsync: 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 or TreeMap), 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

OperationApproachComplexity
Route matchingRadix tree (trie)O(path length)
Route matchingLinear scanO(number of routes)
Middleware executionPipeline (array iteration)O(number of middleware)
Parameter extractionRegex groupsO(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 at index + 1. Calling next(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, a headersSent flag), 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-based next. 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 for Response helpers 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 an Allow header 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.
  • create touches four subsystems (filesystem, cgroup, network, process). If step 3 fails, steps 1 and 2 must be undone in reverse order.
  • stop with 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

OperationRedisZooKeeper
AcquireO(1)O(log n) sequential nodes
ReleaseO(1)O(1) delete ephemeral node
WatchO(1) pub/subO(1) watch notification
RenewalO(1) PEXPIREN/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 LockRecord is 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

OperationComplexityNotes
Index 1 documentO(tokens in doc)Tokenize + insert into posting lists
Single term queryO(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 queryO(min(lists) * avg positions)Intersect + check adjacent positions
TF-IDF scoringO(1) per docPrecomputed 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), Query tree (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

OperationComplexity
Produce (append to partition)O(1) amortized
Consume (read at offset)O(1) random access
Rebalance (N consumers, P partitions)O(P) reassignment
Offset commitO(1)
Retention cleanupO(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 baseOffset per partition (or per segment), so offset → array index is offset − 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 maxMessages without 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), RateLimiter per (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

AlgorithmSelectAdd/Remove Backend
Round-RobinO(1)O(1)
Weighted Round-RobinO(1) amortizedO(N) rebuild weights
Least ConnectionsO(N) scan or O(log N) heapO(log N)
Consistent HashingO(log V) binary search virtual nodesO(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 AtomicInteger taken 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 < now and lastExecution < 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 * 5 means 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.
  • nextAfter can 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 plus nextAfter), 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, votedFor and 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 a Storage interface), 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 RequestVote to all peers. A majority makes you leader: initialise nextIndex = lastIndex + 1 and send heartbeats at once. Replication: for each peer, send entries from nextIndex. On a log mismatch, decrement nextIndex and retry. On success, update matchIndex, then advance commitIndex to the highest N where a majority has matchIndex ≥ N and log[N].term == currentTerm. Apply entries up to commitIndex in 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), CarState classes.
  • 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 of Piece | null), Piece (abstract, colour) with King, Queen, Rook, Bishop, Knight and Pawn, 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. Game adds the special moves, then filters out any move after which isSquareAttacked(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() and undo(), 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, extend endsAt if 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, and rollback undoes only the innermost one
  • commit() 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 → previous Entry or "absent"), Clock.
  • Single client: set writes 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. rollback pops 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 count for a value set and then deleted at the same level.
  • Full version: In-Memory KV Store.

Difficulty Progression

ProblemCore ChallengeKey Skill
Database EngineStorage I/O, immutable data structuresSystems programming
Web FrameworkMiddleware composition, routingAPI design
Container RuntimeOS abstractions, resource managementLinux internals
Distributed LockCorrectness under failureDistributed systems
Search IndexerInverted index, relevance scoringInformation retrieval
Message BrokerPartitioned log, consumer groupsStreaming systems
API GatewayPlugin pipeline, resilienceNetworking
Load BalancerSelection algorithms, health trackingNetworking
Cron SchedulerTime handling, distributed coordinationReliability
Consensus ModuleSafety and liveness guaranteesDistributed consensus
Elevator SystemScheduling under continuous requestsStrategy and State design
ChessRule validation, undo with full statePolymorphism and Command
Online AuctionOne serialisation point per auctionConcurrency in domain models
KV Store with TransactionsNested undo, isolationTransactions and MVCC basics