Question 1

You need to design a real-time leaderboard for 100 million users. What data structure and approach would you use?

Accepted Answer

Redis Sorted Set (ZSET) — O(log n) rank updates with ZADD, O(log n) rank lookup with ZRANK, and O(log n) range queries with ZRANGE — partitioned by region if global scale requires it. Redis ZSET stores members with float scores in a skip list + hash table. ZADD: O(log n). ZRANK: O(log n). ZRANGE with WITHSCORES: O(log n + k). For 100M users: shard by game/region. Periodically snapshot to a DB for durability. Twitter, gaming companies, and Stack Overflow use this pattern.

Question 2

Compare token bucket and sliding window algorithms for rate limiting. Which is more appropriate for an API gateway?

Accepted Answer

Token bucket allows controlled bursting up to bucket capacity and refills at a fixed rate — simpler to implement; sliding window log is more precise but uses more memory per user. Token bucket: allows burst up to bucket size, then throttles — good for bursty-but-bounded traffic. Sliding window log: exact per-user request counts with a timestamp log — more memory. Sliding window counter: approximation using two buckets — best balance. Most API gateways use token bucket for its simplicity and burst tolerance.

Question 3

What is the difference between a B+ tree and an LSM tree, and when would you choose each for a write-heavy workload?

Accepted Answer

B+ tree performs in-place updates with write amplification; LSM tree batches writes in a memory buffer (MemTable) and flushes to sorted immutable runs (SSTables) — LSM is superior for write-heavy workloads; B+ tree for read-heavy. B+ tree: random writes hit random disk locations — high write amplification on HDD. LSM: sequential writes to SSTables — excellent write throughput. LSM read amplification is higher (must check multiple levels). RocksDB, Cassandra, LevelDB, BigTable all use LSM. MySQL InnoDB uses B+ tree.

Question 4

What is tail latency and why is it disproportionately important in distributed systems?

Accepted Answer

Tail latency is the latency at high percentiles (P99, P999) — in a distributed system, a user request that fans out to N services experiences the maximum of all service latencies, making tail latency critical for overall response time. If P99 = 1s and a request calls 100 microservices: probability at least one takes >1s ≈ 63%. The 'long tail' dominates fan-out systems. Mitigations: hedged requests (send duplicate, use first response), speculative execution, timeouts, and tail-tolerant algorithms.

Question 5

What are the advantages of immutable data structures in highly concurrent systems?

Accepted Answer

Since immutable data cannot be modified, it needs no locks for concurrent reads — safe sharing between threads, simpler reasoning about state, and structural sharing enables efficient 'copies'. Structural sharing: a new 'modified' version shares unchanged nodes with the original — no full copy needed. Clojure's persistent data structures (PersistentHashMap) achieve near-O(1) updates this way. Java's String immutability makes it safe to share across threads without synchronization.

Data Structures & Algorithms — Tech Lead Interview Questions

More Tech Lead Topics

Data Structures & Algorithms at Other Levels