Distributed Counting / Top K
Difficulty: Hard | Topic #26
What to Learn
Count-Min Sketch for approximate counting, lossy counting, Space-Saving algorithm, two-stage MapReduce approach for heavy hitters; tradeoffs between exactness and memory/throughput.
Resources
- Hello Interview: Data Structures for Big Data ↗
- Gaurav Sen: Top-K Problem (Heavy Hitters) ↗
- System Design Interview: Top K Heavy Hitters ↗
Covered by Problems
| Problem | Difficulty | Link |
|---|---|---|
| Top K System | Hard | → |
| Ad Click Aggregator | Hard | → |
| Metrics Monitoring System | Hard | → |
Key Concepts to Master
- Count-Min Sketch — hash table array with minimum estimation
- Space-Saving algorithm for exact top-K with bounded memory
- Two-stage approach: local top-K per shard → global merge
- Bloom filters for membership testing without false negatives issue
- HyperLogLog for approximate cardinality (unique user counts)