Skip to content

Interview PrepAlgorithms · Advanced

Distributed Algorithms ​

42. What is consistent hashing, and where is it used? ​

The short answer

Consistent hashing spreads keys across servers so that adding or removing a server moves only a small share of the keys. With plain hash(key) % N, changing N from 3 to 4 moves about three quarters of all keys, which empties every cache at once. Consistent hashing places both servers and keys on a ring of hash values; each key belongs to the next server clockwise. Adding a server only takes keys from its neighbours, about 1/N of the total. Virtual nodes, many points per server, even out the load. It is used in cache clusters, DynamoDB, Cassandra, and load balancers with sticky routing.

ABCDkeys between A and Dmove from B to the new Dall other keys stay putclockwise to thenext serveradding a 4th node, 10,000 keys:ring: 2,664 keys movedhash % N: 7,391 keys moved
A new server only takes from its neighbour. The red keys, between A and the new server D, change owner. Every other key keeps its server. The numbers come from running the code below.
ts
import { createHash } from 'node:crypto'

const h32 = (s: string) => createHash('md5').update(s).digest().readUInt32BE(0)   // (1)

export class HashRing {
  private ring: { point: number; node: string }[] = []
  private vnodes: number

  constructor(nodes: string[], vnodes = 100) {
    this.vnodes = vnodes
    nodes.forEach((n) => this.add(n))
  }

  add(node: string) {
    for (let i = 0; i < this.vnodes; i++) this.ring.push({ point: h32(`${node}#${i}`), node })   // (2)
    this.ring.sort((a, b) => a.point - b.point)
  }

  get(key: string): string {
    const p = h32(key)
    let lo = 0, hi = this.ring.length
    while (lo < hi) {                                                            // (3)
      const mid = (lo + hi) >> 1
      if (this.ring[mid].point < p) lo = mid + 1; else hi = mid
    }
    return this.ring[lo % this.ring.length].node                                 // (4)
  }
}
  1. A hash to a 32-bit number, so every key and node has a position on the ring. MD5 is fine here; it is used for spreading, not security.
  2. 100 virtual nodes per server, scattered around the ring, so each server owns many small arcs and load evens out.
  3. Binary search for the first ring point at or after the key's position.
  4. Wrap around to the first point if the key is past the last one.

The real result. With 10,000 keys on servers cache-a, cache-b and cache-c, adding cache-d moved 2,664 keys, about 27%, close to the ideal 25%. Using hash % 3 then hash % 4 instead moved 7,391 keys, about 74%.

43. What is a Bloom filter, and when can it be useful? ​

The short answer

A Bloom filter is a tiny, fast data structure that answers "have I possibly seen this item?" It can say "definitely not" or "probably yes": it never gives a false negative, but it can give a false positive at a rate you choose. It is a bit array plus several hash functions; adding an item sets a few bits, and checking an item tests those bits. It uses far less memory than storing the items. It is used to skip pointless expensive lookups: "is this username taken?" before querying the database, "is this URL already crawled?", and inside databases such as Cassandra to avoid reading files that cannot contain a key.

ts
import { createHash } from 'node:crypto'

export class BloomFilter {
  private bits: Uint8Array
  private m: number
  private k: number

  constructor(m: number, k: number) {
    this.m = m                                                                   // number of bits
    this.k = k                                                                   // number of hash functions
    this.bits = new Uint8Array(Math.ceil(m / 8))
  }

  private positions(item: string): number[] {
    const d = createHash('sha256').update(item).digest()
    const a = d.readUInt32BE(0), b = d.readUInt32BE(4)
    return Array.from({ length: this.k }, (_, i) => (a + i * b) % this.m)       // (1)
  }

  add(item: string) {
    for (const p of this.positions(item)) this.bits[p >> 3] |= 1 << (p & 7)     // (2)
  }

  mightContain(item: string): boolean {
    return this.positions(item).every((p) => (this.bits[p >> 3] & (1 << (p & 7))) !== 0)   // (3)
  }
}
  1. k bit positions from two hashes, a standard trick that behaves like k independent hash functions.
  2. Adding sets k bits. p >> 3 picks the byte and p & 7 the bit inside it.
  3. Checking needs all k bits set. Any zero bit means the item was definitely never added.

The real result. Sized for 100,000 items at a 1% false-positive rate, the filter needs about 958,506 bits and 7 hash functions, which is 117 KB. After adding 100,000 taken usernames, every one of them returned "probably yes", and checking 100,000 usernames that were never added gave 999 false positives, 0.999%. Storing the 100,000 names themselves would take megabytes.

Sizing, in words. For n items and a false-positive rate p, the number of bits is m = −n × ln(p) ÷ (ln 2)², and the best number of hash functions is k = (m ÷ n) × ln 2. For n = 100,000 and p = 0.01, that gives m ≈ 958,506 and k ≈ 7.

Limits: you cannot remove an item from a plain Bloom filter, because its bits may be shared with other items; a counting Bloom filter can. And it cannot list what it contains.

44. What are Snowflake-style distributed IDs? ​

The short answer

A Snowflake ID, a scheme Twitter introduced, is a 64-bit integer that many servers can generate independently, without coordination, that is still unique and roughly time-ordered. Its bits hold a timestamp in milliseconds since a custom epoch, 41 bits; a worker ID, 10 bits, unique per generator; and a sequence number, 12 bits, for IDs made in the same millisecond. That allows 4,096 IDs per millisecond per worker, sorting by ID roughly sorts by creation time, and the IDs fit in a database bigint. UUIDv7 follows the same idea in 128 bits.

0timestamp: 41 bitsms since a custom epoch, about 69 yearsworker: 101,024 workerssequence: 124,096 per mstime comes first, so bigger IDs are newer
Time, then who, then a counter. Putting the timestamp in the highest bits makes IDs sort by time. The worker bits keep two machines from producing the same ID in the same millisecond.
ts
const EPOCH = 1735689600000n                                                     // 2025-01-01T00:00:00Z

export class Snowflake {
  private seq = 0n
  private last = -1n
  private worker: bigint

  constructor(worker: bigint) { this.worker = worker }                          // (1)

  next(now = BigInt(Date.now())): bigint {
    if (now === this.last) {
      this.seq = (this.seq + 1n) & 4095n                                         // (2)
      if (this.seq === 0n) { while (BigInt(Date.now()) <= this.last) {} now = BigInt(Date.now()) }   // (3)
    } else {
      this.seq = 0n
    }
    this.last = now
    return ((now - EPOCH) << 22n) | (this.worker << 12n) | this.seq             // (4)
  }
}
  1. Each generator gets a unique worker ID, from 0 to 1,023, from configuration or a coordination service.
  2. Same millisecond: increment the sequence, wrapping at 4,096.
  3. Sequence exhausted: wait for the next millisecond.
  4. Pack the three parts with bit shifts. BigInt is needed because JavaScript numbers lose precision above 2 to the power 53.

The real result. Worker 7 generating two IDs at 2026-10-27T10:00:00Z produced 240776537702428672 and 240776537702428673. Decoding them gives the same timestamp and worker, with sequence 0 and 1.

Two traps. Send these IDs to browsers as strings, because JSON.parse turns large integers into imprecise numbers. And if a server's clock jumps backwards, a generator must refuse or wait, or it may repeat IDs.

45. What is leader election in a distributed system? ​

The short answer

Leader election is how a group of nodes agrees that exactly one of them is in charge of a job, such as running the nightly billing, being the database primary, or owning a Kafka partition, and quickly picks a new one if the leader dies. Nodes compete for a lease, a lock with an expiry, held in a strongly consistent store such as etcd, ZooKeeper, Consul or the Kubernetes API, and the holder keeps renewing it. If renewals stop, the lease expires and another node takes over. The danger is two nodes both believing they lead, which fencing tokens prevent (question 47).

Leader election with a Kubernetes Lease, the idea:

  1. Every replica tries to create or update the Lease object named billing-leader with its own name and a renew time.
  2. The Kubernetes API accepts only one update for each version of the object, so only one replica succeeds.
  3. The winner renews the lease every few seconds and runs the job.
  4. If the winner stops renewing, crashes or is cut off, others see the lease expire after, say, 15 seconds, and one of them takes over.
UseLeader does
Scheduled jobs across replicasRuns the cron job once, not once per replica
Database clustersAccepts writes as primary
Kafka and Raft groupsCoordinates replication for a partition
Controllers in KubernetesActs on resources while the others stand by

A simpler alternative for scheduled jobs: a database advisory lock, SELECT pg_try_advisory_lock(42), taken at the start of each run. Only one replica gets it.

46. What are consensus algorithms such as Raft and Paxos used for? ​

The short answer

Consensus algorithms let a group of nodes agree on a single sequence of decisions, such as the order of writes to a log, even when some nodes crash or messages are delayed, as long as a majority is working. Paxos, from Leslie Lamport, is the original and is famously hard to understand. Raft was designed to be easier: it elects a leader, the leader appends entries to its log and replicates them, and an entry counts as committed once a majority stores it. They power etcd, the store behind Kubernetes, ZooKeeper, Consul, CockroachDB, and Kafka's KRaft mode.

clientset x = 5leaderappend to logfollower: ackfollower: ackfollower: slowfollower: down3 of 5 storedcommitted
A majority makes it permanent. The leader plus two followers is three of five, so the write survives even if any two nodes fail later. The slow and down followers will receive the entry when they catch up.

Why clusters have an odd number of nodes:

NodesMajority neededFailures tolerated
321
431
532
743

A fourth node adds cost and network traffic but tolerates no more failures than three. Five is the usual size for critical clusters.

You will rarely implement Raft. You will use systems built on it, so what matters in an interview is knowing that they need a majority, that a minority partition stops accepting writes, which is a CP choice (CAP), and that writes are slower than to a single node.

47. What are distributed locks, and what failure cases must be considered? ​

The short answer

A distributed lock lets processes on different machines agree that only one of them does something at a time, such as processing one customer's payout. The simple version is Redis SET lock:payout:42 <random-token> NX PX 30000: set the key only if absent, with a 30-second expiry. Failure cases are the real topic. The holder can pause, from garbage collection or a slow network, past the expiry while another process takes the lock; the lock store can fail over and forget the lock; and clocks drift. So keep the protected work short, release the lock only if you still own it, and use fencing tokens so the resource itself rejects a stale holder.

worker Aworker Block serviceexpiry 30 sstoragehighest seen: 34① lock, token 33② pauses 40 s③ lock expired: token 34④ write with 34: accepted⑤ A wakes, writes with 33: rejected
The lock alone cannot stop a sleeper. Worker A still believes it holds the lock when it wakes. Only the storage can stop it, by refusing any token lower than the highest it has accepted.
ts
import { randomUUID } from 'node:crypto'

export async function withLock<T>(name: string, ttlMs: number, work: () => Promise<T>): Promise<T | null> {
  const token = randomUUID()
  const ok = await redis.set(`lock:${name}`, token, { NX: true, PX: ttlMs })     // (1)
  if (!ok) return null                                                          // (2)
  try {
    return await work()
  } finally {
    await redis.eval(                                                           // (3)
      "if redis.call('get', KEYS[1]) == ARGV[1] then return redis.call('del', KEYS[1]) else return 0 end",
      { keys: [`lock:${name}`], arguments: [token] })
  }
}
  1. Take the lock only if nobody has it, with an automatic expiry so a crashed holder does not block forever.
  2. Someone else holds it: skip, or retry later.
  3. Release only your own lock. Without the check, a slow holder whose lock already expired would delete the next holder's lock. The Lua script makes check and delete atomic.
FailureDefence
Holder crashesExpiry releases the lock
Holder pauses past the expiryFencing tokens checked by the resource; keep work short
Deleting another holder's lockRelease with a check of your own token
Lock store fails over and loses the keyA consensus-based store such as etcd for correctness-critical locks
Work longer than the expiryRenew the lock while working, or redesign

Ask whether you need a lock at all. A database row lock, SELECT … FOR UPDATE, a unique constraint, or an idempotent operation often does the job more safely (pessimistic locking).

48. How would you design a distributed rate limiter? ​

The short answer

Keep counters in a shared fast store, usually Redis, so every API instance counts against the same limit. Pick an algorithm: fixed window counters, simplest; sliding window, smoother; or token bucket, which allows short bursts at a steady average rate. Update atomically, with INCR and an expiry or a Lua script, so concurrent requests cannot both slip through. Key the limit by API key, user or IP, return 429 with Retry-After, put a coarse limit at the edge, and decide what happens if Redis is down, usually allowing traffic with a local fallback limit.

A token bucket in one atomic Lua script:

ts
const TOKEN_BUCKET = `
local tokens = tonumber(redis.call('HGET', KEYS[1], 't') or ARGV[1])
local last   = tonumber(redis.call('HGET', KEYS[1], 'ts') or ARGV[3])
local refill = (tonumber(ARGV[3]) - last) / 1000 * tonumber(ARGV[2])
tokens = math.min(tonumber(ARGV[1]), tokens + refill)
local allowed = tokens >= 1
if allowed then tokens = tokens - 1 end
redis.call('HSET', KEYS[1], 't', tokens, 'ts', ARGV[3])
redis.call('PEXPIRE', KEYS[1], 60000)
return allowed and 1 or 0`

export async function allow(apiKey: string, capacity = 20, perSecond = 5) {
  const ok = await redis.eval(TOKEN_BUCKET, {
    keys: [`rl:${apiKey}`],
    arguments: [String(capacity), String(perSecond), String(Date.now())],       // (1)
  })
  return ok === 1                                                               // (2)
}
  1. Capacity 20, refilling at 5 tokens a second. A client can burst 20 requests, then sustain 5 per second. The script refills based on the time since the last request, then spends one token.
  2. The whole read-refill-spend runs atomically inside Redis, so two instances can never spend the same token.
AlgorithmAllows burstsPrecisionStorage per key
Fixed windowUp to double at the window boundaryLowOne counter
Sliding window logNoExactOne entry per request
Sliding window counterLittleGoodTwo counters
Token bucketYes, up to capacityGoodTwo numbers

The single-service version, with express-rate-limit and a Redis store, is in the rate limiting question.

49. What trade-offs arise when choosing consistency and availability? ​

The short answer

Strong consistency means every read sees the latest write, which requires coordination: waiting for replicas, a majority, or a single leader. That costs latency on every write, and during a network partition some requests must fail. Choosing availability means always answering, from whichever copy is reachable, at the cost of stale reads and conflicting writes that must be merged later. The right answer is per operation, not per system: payments, stock and bookings need consistency; feeds, likes, carts and recommendations can be available and eventually consistent.

OperationChooseWhy
Charge a card, move moneyConsistencyDoing it twice or wrongly is costly
Book the last seatConsistencyTwo people cannot both get it
Username uniquenessConsistencyMust be decided once
Shopping cart contentsAvailabilityMerge two devices' carts later
Likes and view countsAvailabilitySlightly wrong for a moment is fine
Product pageAvailabilityServe a cached copy rather than an error

Tools on each side:

For consistencyFor availability
Single-leader database, synchronous replicationMulti-region replicas, eventual reads
Transactions and row locksCaches and stale-while-revalidate
Consensus stores such as etcdQueues that accept writes and apply them later
Quorum reads and writesConflict resolution: last write wins, merge, or CRDTs

CRDTs in one sentence. Conflict-free replicated data types are data structures, such as counters and sets, designed so that copies updated separately can always be merged into the same result, which is how collaborative editors and offline-first apps stay available (CAP).

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Interview Prep
Architecture & Distributed Systems
Structure
Data across services
Resilience
Communication
Security between services
Algorithms
Other topics
Nothing picked yet