System Design Lite

Problem

Cache with a fixed capacity that evicts the least-recently-used entry on insert when full. `get` and `put` must be O(1).

Clarify first

• Is capacity fixed at construction or dynamic?
• Is access (get) thread-safe? If yes, coarse lock or lock-free?
• Are we optimizing for hit latency (in-memory) or hit rate (tiered cache)?

Approach

Reference implementation

class Node:
    __slots__ = ('key', 'val', 'prev', 'next')
    def __init__(self, k, v):
        self.key, self.val, self.prev, self.next = k, v, None, None

class LRU:
    def __init__(self, cap: int):
        self.cap = cap
        self.map: dict[int, Node] = {}
        # Sentinel head/tail — removes null-checks
        self.head, self.tail = Node(0, 0), Node(0, 0)
        self.head.next, self.tail.prev = self.tail, self.head

    def _remove(self, n: Node) -> None:
        n.prev.next, n.next.prev = n.next, n.prev

    def _add_to_front(self, n: Node) -> None:
        n.prev, n.next = self.head, self.head.next
        self.head.next.prev = n
        self.head.next = n

    def get(self, key: int) -> int:
        n = self.map.get(key)
        if not n:
            return -1
        self._remove(n); self._add_to_front(n)
        return n.val

    def put(self, key: int, val: int) -> None:
        if key in self.map:
            self._remove(self.map[key])
        n = Node(key, val)
        self.map[key] = n
        self._add_to_front(n)
        if len(self.map) > self.cap:
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.key]

Problem

Evict the least-frequently-used entry. On tie, break by recency.

Clarify first

• Is this a pure interview question or are we benchmarking? LFU hit-rate is often worse than LRU on realistic workloads
• How often do items age out? A pure frequency count never decays, so old popular items can stick forever

Approach

Problem

Reject requests that exceed a quota (e.g., 100 req / minute / user). Should work across many server instances.

Clarify first

• Per-user, per-IP, per-API-key, or per-tenant?
• Soft (429 + retry-after) or hard (drop the TCP connection)?
• Is approximate OK, or do we need exact? Distributed exact-counting is expensive

Approach

Problem

Probabilistic set membership — "is X probably in the set?" with O(1) queries and ~1 byte per element. Never false-negatives; may false-positive at a configurable rate.

Clarify first

• What false-positive rate is acceptable? 1%? 0.01%?
• Do we need to remove elements? Standard Bloom filters cannot — you need a Counting Bloom Filter

Approach

Problem

Distribute keys across N nodes. When a node is added or removed, move as few keys as possible — ideally ~1/N of them.

Clarify first

• How many nodes and how many keys? (Affects load balance)
• Is node membership static or changing frequently?
• Do we need replication? Usually yes — store at the next K nodes on the ring

Approach

Problem

Generate unique IDs across many machines without coordination. Which ID shape fits the use case?

Clarify first

• Must IDs be sortable by creation time?
• Is 128-bit OK, or do we need 64-bit for DB index efficiency?
• Must we avoid leaking cardinality (guessable IDs are an anti-pattern for public resources)?

Approach

Problem

An async workflow needs to hand off work between services. Which messaging shape fits?

Clarify first

• Exactly once? At least once? At most once? (Exactly-once is almost always a lie — aim for at-least-once + idempotent consumers)
• Do consumers need to replay old messages?
• One consumer per message, or fan-out?

Approach

Problem

A hot read path is hitting the database too hard. Where and how do you cache?

Clarify first

• Is the underlying data changing, and how stale can the cache be?
• Is write volume high? (Write-through has a write tax; cache-aside does not)
• Can two consumers read the same key concurrently? (Cache stampede)

Approach

Problem

A single database cannot hold the data or handle the load. How do you split it across many?

Clarify first

• What is the query pattern — single-entity lookups, range scans, or analytics?
• What is the natural partition key (user_id, tenant_id, region)?
• How often do you need cross-shard queries? (Expensive — design to avoid)

Approach

Problem

A set of processes must elect exactly one leader. The leader coordinates; followers replicate. What goes wrong, and how do you make it safe?

Clarify first

• Is strong consistency required, or is eventual convergence OK?
• What happens if the network splits? (Split-brain is the classic failure mode)
• How quickly must a new leader take over after a failure?

Approach