Skip to content

Algorithms You Should Know Before System Design Interviews

Companion write-ups: ByteByteGo — Algorithms you should know before you take system design interviews · EP14: Algorithms you should know for System Design

Overview

This article covers ByteByteGo's "algorithms you should know before system design interviews" list — 14 algorithms, each rated with a star priority and mapped to the real-world problem it solves. The point is not to memorise implementations: ByteByteGo's own framing is that

understanding "how those algorithms are used in real-world systems" is generally more important than the implementation details in a system design interview.

That single sentence should drive your revision. An interviewer is rarely asking you to derive consistent hashing on a whiteboard. They are waiting for you to say: "for the sharding layer I'd hash keys onto a ring with virtual nodes so that adding a node only remaps K/N keys — that's what Cassandra and DynamoDB do." The star rating tells you where that fluency is expected:

Priority Meaning (ByteByteGo) What you must be able to do
★★★★★ Very important Explain how it works, why it was chosen, and name real systems that use it
★★★☆☆ Important to some extent Know what problem it solves and when to reach for it; implementation detail optional
★☆☆☆☆ Advanced — good to know for senior candidates Recognise the name, state the use case and the trade-off in one sentence

Priority Table

ByteByteGo priority table — algorithms for system design interviews

Click the diagram to open it at full resolution.

Diagram © ByteByteGo, reproduced from the companion article for personal study.

# Algorithm Priority Use case
1 Geohash ★★★★★ Location-based service
2 Quadtree ★★★★★ Location-based service
3 Consistent hashing ★★★★★ Balance the load within a cluster of services
4 Leaky bucket ★★★★★ Rate limiter
5 Token bucket ★★★★★ Rate limiter
6 Trie ★★★★★ Search autocomplete
7 Rsync ★★★☆☆ File transfers
8 Raft / Paxos ★★★☆☆ Consensus algorithms
9 Bloom filter ★★★☆☆ Eliminate costly lookups
10 Merkle tree ★★★☆☆ Identify inconsistencies between nodes
11 HyperLogLog ★☆☆☆☆ Count unique values fast
12 Count-min sketch ★☆☆☆☆ Estimate frequencies of items
13 Hierarchical timing wheels ★☆☆☆☆ Job scheduler
14 Operational transformation ★☆☆☆☆ Collaborative editing

Tier 1 — The Five-Star Algorithms

Geohash

Encodes a (latitude, longitude) pair into a short string of base-32 characters, where a shared prefix means geographic proximity. Each extra character subdivides the cell roughly 32-fold, so precision is tunable from continent scale (1 character, ~5 000 km) down to street scale (6 characters, ~1 km × 0.6 km) and beyond.

  • Why it matters: it turns 2-D proximity search into a cheap 1-D index lookup (WHERE geohash LIKE 'u09tv%'), so any database or cache becomes a location index.
  • Real systems: Redis (GEOADD/GEOSEARCH over a sorted set), Elasticsearch geo-points, Uber/DoorDash-style driver lookup, Yelp POI search.
  • Pitfalls: fixed grid vs variable density; two points 10 m apart can fall in different cells, so query the cell + its 8 neighbours (or a bounding box) and filter precisely afterwards.
  • Interview line: "I'd bucket drivers by geohash prefix in Redis and query the 9 neighbouring cells; the last mile is refined with a Haversine distance filter."

Quadtree

Recursively splits a region into four quadrants until each leaf holds at most N points, so the grid adapts: dense cities subdivide deeply, empty ocean stays coarse.

  • Why it matters: O(log n) spatial queries without tuning a fixed grid; natural for range and nearest-neighbour search.
  • Real systems: map/POI search (Yext engineering blog, referenced by ByteByteGo), collision detection in games and simulation, image compression, spatial indexes inside databases.
  • Versus Geohash: quadtree = adaptive, in-memory, great for skewed distribution; geohash = fixed cells, trivially shardable, easy to store in a KV store.
  • Interview line: "For uneven point density (Manhattan vs rural Kansas) I'd use a quadtree rather than a uniform grid."

Consistent Hashing

Place both nodes and keys on a hash ring (e.g. 0…2³²−1); a key belongs to the first node clockwise. Adding or removing a node remaps only K/N keys instead of reshuffling everything.

  • Why it matters: it is the standard answer to "how do you shard / cache across a changing fleet of servers?"
  • Real systems: Amazon DynamoDB (the paper that popularised it), Cassandra, Riak, Redis Cluster, Memcached client-side sharding, load balancers, CDN edge selection.
  • Details worth saying out loud: virtual nodes (each physical node claims many ring positions) fix the imbalance caused by random ring placement; replication walks clockwise to the next R nodes; hopscotch/rendezvous hashing (HRW) are the two common alternatives.
  • Interview line: "Ring + virtual nodes; a node failure only moves that node's keys to its clockwise neighbours, so cache hit rate degrades gracefully."
# Consistent hashing with virtual nodes — interview-sized sketch
import bisect, hashlib

def h(key: str) -> int:
    return int(hashlib.sha1(key.encode()).hexdigest()[:8], 16)

class Ring:
    def __init__(self, nodes, vnodes=150):
        self.vnodes, self.ring, self.owner = vnodes, [], {}
        for n in nodes:
            self.add(n)

    def add(self, node):
        for i in range(self.vnodes):
            pos = h(f"{node}#{i}")
            bisect.insort(self.ring, pos)
            self.owner[pos] = node

    def remove(self, node):
        for i in range(self.vnodes):
            pos = h(f"{node}#{i}")
            self.ring.remove(pos)
            del self.owner[pos]

    def locate(self, key):
        pos = h(key) % (2**32)
        i = bisect.bisect_left(self.ring, pos) % len(self.ring)
        return self.owner[self.ring[i]]

Leaky Bucket

Requests enter a fixed-capacity queue and leave at a constant rate. A full queue means dropped (or delayed) requests.

  • Why it matters: it smooths traffic — the downstream service never sees a spike, only a steady drip.
  • Real systems: nginx limit_req, HAProxy, API gateways, traffic shaping on network interfaces, any "protect the database" limiter.
  • Trade-off: no burst tolerance. A user who has been idle for an hour still gets a flat rate, which is why most public APIs prefer the token bucket.
# Leaky bucket: constant drain rate, fixed queue depth => smooth output
import time, collections

class LeakyBucket:
    def __init__(self, capacity: int, drain_per_sec: float):
        self.capacity, self.leak, self.q = capacity, drain_per_sec, collections.deque()

    def allow(self) -> bool:
        now = time.monotonic()
        while self.q and now - self.q[0] >= 1 / self.leak:   # drain
            self.q.popleft()
        if len(self.q) < self.capacity:
            self.q.append(now)
            return True
        return False

Token Bucket

A bucket refills with tokens at rate R up to capacity B; each request consumes one token. Average rate = R, burst up to B.

  • Why it matters: the industry-default rate limiter — it enforces a sustained limit while still letting a client burst, which maps to real client behaviour.
  • Real systems: AWS API Gateway / ALB throttling, Stripe's rate limiters, Cloudflare, Google Guava RateLimiter, NGINX/Envoy limiters in token mode.
  • Say this: distributed limiting needs shared state — Redis + Lua for atomic check-and-decrement, or a small quorum; otherwise each node enforces limit / node_count and the effective limit floats.
  • Related answers: fixed window (cheap, edge spikes), sliding-window log (exact, memory-heavy), sliding-window counter (Redis sorted sets), GCRA (token bucket with no refill thread).
-- Token bucket in Redis + Lua: atomic across every gateway instance.
-- KEYS[1] = bucket key (e.g. "rl:{user_id}")
-- ARGV[1] = now (unix seconds)  ARGV[2] = rate (req/s)  ARGV[3] = burst (capacity)
local rate, burst, now = tonumber(ARGV[2]), tonumber(ARGV[3]), tonumber(ARGV[1])

local state  = redis.call('hmget', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(state[1]) or burst
local ts     = tonumber(state[2]) or now

tokens = math.min(burst, tokens + (now - ts) * rate)   -- refill
local allowed = tokens >= 1
if allowed then tokens = tokens - 1 end

redis.call('hmset', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('expire', KEYS[1], math.ceil(burst / rate) * 2)
return allowed and 1 or 0

Load it once with SCRIPT LOAD, then call EVALSHA <sha> 1 rl:{user_id} <now> 10 50 from the gateway. Keeping the check-and-decrement inside one Lua script is what makes the limit correct across N instances — a read-then-write in application code lets a burst slip through in the race window.

Trie (Prefix Tree)

A tree where each edge is a character and each path from the root spells a key. Lookup/insert cost is O(L) in the word length, independent of how many words are stored.

  • Why it matters: the canonical answer to "design search autocomplete / typeahead".
  • Real systems: search suggest (Google/Bing/Amazon bar), IP routing tables (binary/Patricia/radix tries power longest-prefix-match in routers), spell checkers, T9, dictionary compression.
  • Scaling notes to volunteer: store only top-K completions per node so you avoid walking the whole subtree; warm the trie in memory (it is read-mostly); rebuild offline from query logs; use a compressed radix tree (path compression) or a ternary search tree / DAWG to cut memory.
  • Interview line: "Prefix trie with precomputed top-10 suggestions per node, served from an in-memory cache, trained nightly on the query log — that's a typeahead in three sentences."

Tier 2 — The Three-Star Algorithms

Rsync

Transfers only the delta between two files. The receiver hashes its copy into blocks (weak rolling Adler-32 checksum + strong MD5/BLAKE2), sends the checksums, and the sender transmits only matching-block references plus the changed bytes.

  • Why it matters: it is the answer to "design file sync / backup / a large artifact delivery system" without inventing anything.
  • Real systems: rsync itself, zsync (used by Ubuntu ISOs), Dropbox/Drive-style block diffs, content-addressed chunk stores, HTTP zstd/delta patching in CI caches.
  • Details: rolling checksum makes the block scan O(n) even when insertions shift offsets; rsync is one-way and unidirectional by design — the two-way sync logic lives above it (state, conflict resolution, tombstones).
  • Interview line: "Block-level delta with rolling checksums, so a 1 GB file with 1 KB changed transfers 1 KB."

Raft / Paxos

Consensus protocols: get a majority of nodes to agree on an ordered log (Raft) or on a single value (Paxos) despite crashes and network partitions.

  • Raft in one breath: randomised election timeout → leader; the leader appends entries and commits once a majority (quorum) has replicated them; only a node with an up-to-date log can win an election. Paxos is the older, harder, quorum-based formulation (Multi-Paxos for logs).
  • Why it matters: every distributed datastore needs a "single source of truth" component, and interviewers want you to know you cannot get one for free.
  • Real systems: etcd (the brain of Kubernetes), Consul, CockroachDB, TiKV, Kafka KRaft mode, Spanner (Paxos), ZooKeeper (ZAB, a Paxos cousin).
  • Say this: quorum = floor(N/2)+1, so 3 nodes tolerate 1 failure, 5 tolerate 2; Raft needs a majority to make progress, so an even split of a 2-node cluster is unrecoverable — always run odd numbers.
  • Interview line: "I'd keep the shard map and leader leases in etcd rather than inventing consensus; a 3-node quorum tolerates one failure."

Bloom Filter

A bit array of m bits plus k hash functions. Each element sets k bits; a query returns "definitely not present" or "probably present". No false negatives, false positives tunable (~1 % with ~10 bits/element and k≈7).

  • Why it matters: it removes expensive lookups (disk/DB/network round trips) with a few kilobytes and O(k) time.
  • Real systems: Cassandra, HBase and RocksDB/LevelDB SSTable lookups, Chrome's Safe Browsing, Akamai CDN "cache one-hit wonders" prevention, spam and duplicate-URL filters.
  • Pitfalls: you cannot delete from a classic Bloom filter (use counting Bloom filters or rotate generations); a false positive means an unnecessary lookup, never a wrong "absent" answer.
  • Interview line: "A Bloom filter in front of the database eliminates ~99 % of negative lookups for one hash and 12 KB of RAM."

Merkle Tree

A hash tree: leaves hash the data blocks, parents hash their children, the root commits to everything below it. Two replicas compare roots; if they differ, walk down and find the divergent leaf in O(log n) instead of comparing all data.

  • Why it matters: cheap integrity verification and anti-entropy repair across nodes.
  • Real systems: Git object store, Bitcoin/Ethereum blocks and light clients (Merkle proofs), Cassandra/DynamoDB replica repair, IPFS content addressing, ZFS/Btrfs checksums.
  • Interview line: "Merkle trees let replicas find which ranges drifted with a log-depth walk — that's how Cassandra does anti-entropy repair."

Tier 3 — The One-Star (Advanced) Algorithms

HyperLogLog

Estimates cardinality (distinct count) using the maximum number of leading zeros observed across hashed values, with harmonic-mean correction and register bucketing. Fixed memory — 12 KB with Redis' default 2¹⁴ registers — and ~0.81 % standard error, whether you are counting thousands or billions.

  • Real systems: Redis PFADD/PFCOUNT, Google Analytics-style unique-visitor counts, Postgres hll extensions, ad-tech reach estimation.
  • Trade-off: it is an estimate; you cannot enumerate the members, and small-cardinality accuracy needs the linear-counting correction.

Count-min Sketch

A fixed 2-D array of counters: each item is hashed into one cell per row and increments them; a query returns the minimum across rows, which over-estimates but never under-estimates. Sublinear memory for frequency estimation.

  • Real systems: heavy hitters / trending topics / top-K dashboards, DDoS and anomaly detection, Redis and Cassandra frequency-tracking components, network flow monitoring.
  • Combine with a heap for exact Top-K among the sketch's candidates.

Hierarchical Timing Wheels

A bucketed timer structure: the current slot's list of timers fires when the hand passes it, and timers farther out live in coarser wheels (seconds → minutes → hours). Insert and expire are effectively O(1), which a sorted heap (O(log n)) cannot match at millions of timers.

  • Real systems: Netty HashedWheelTimer, Kafka's request purgatory, Linux kernel timers, Nginx/HAProxy connection and keepalive timeouts, CDN cache TTL eviction.
  • Interview line: "For a scheduler holding millions of delayed jobs I'd use a hierarchical timing wheel — O(1) insert/expire without a global sorted structure."

Operational Transformation (OT)

For collaborative editing, two users edit concurrently; OT transforms each operation against the other so that applying any transformed order converges to the same document. Requires a central server to define total order.

  • Real systems: Google Docs (historically), Etherpad, ShareDB/Automerge-family stacks, collaborative whiteboards.
  • Versus CRDT: CRDTs converge without a central sequencer (offline-friendly, more metadata); OT needs a server but ships smaller operations. Both are correct answers — state the trade-off, don't just name one.
  • Interview line: "Collaborative editing: OT with a central server for ordering, or CRDTs if we need peer-to-peer/offline convergence."

Interview Playbook

How to actually use this list in a 45-minute design round:

  1. Never lead with the algorithm. Lead with the requirement ("reads vastly outnumber writes", "3 billion distinct visitors a day", "edits from many users at once"), then introduce the matching algorithm as a consequence.
  2. One line per algorithm: what it does → why here → the trade-off you accept. That is enough for ★★★ and ★ algorithms.
  3. Have 3–4 ★★★★★ answers fully rehearsed, because they recur across unrelated questions: consistent hashing (sharding), token/leaky bucket (rate limiter, any API question), trie (search/autocomplete), geohash or quadtree (anything "near me").
  4. Map algorithms to classic design prompts:
Design prompt Reach for
Design a rate limiter Token bucket (bursts) vs leaky bucket (smoothing) vs sliding window
Design a sharded/cached fleet Consistent hashing with virtual nodes
Design Yelp / Uber / "find nearby" Geohash (fixed cells, shardable) or quadtree (adaptive density)
Design search autocomplete Trie with top-K per node
Design Dropbox / large file sync Rsync-style block delta + content addressing
Design a distributed lock / metadata store / leader election Raft or Paxos via etcd/ZooKeeper
Cache negative lookups / dedupe URLs Bloom filter
Replica consistency / corruption detection Merkle tree + anti-entropy
Count unique visitors at scale HyperLogLog
Trending / heavy hitters / DDoS detection Count-min sketch (+ heap for Top-K)
Millions of scheduled/delayed tasks Hierarchical timing wheel
Collaborative document editing Operational transformation or CRDT
  1. Close with the trade-off sentence. "This is approximate, that's why it's fast." Interviewers score the awareness of the trade-off, not the trivia.

Study Links (from ByteByteGo's article)

References