Design a Top K Heavy Hitters Service

• Design YouTube's Top K Videos Feature
• Design Spotify Top K Songs

Requirements

Core Entites & APIs

High-Level Design

Deep Dive

Questions

What is Count-Min Sketch?

Answer

Count-Min Sketch is a probabilistic data structure used to estimate the frequency of elements in a data stream using sublinear space. It trades off accuracy for memory efficiency.

It works by hashing each incoming element with multiple hash functions and incrementing corresponding counters in a 2D array. To estimate the frequency of an element, it takes the minimum count across all its hash positions—hence the name. It's commonly used for approximate counting in streaming systems, like estimating top-k queries or detecting heavy hitters.