Interview Walkthrough: Top-K / Trending Topics

Designing a system to show trending topics -- like Twitter Trends, YouTube Trending, or Google Trends -- is a system design interview question that tests your knowledge of streaming algorithms, approximate data structures, and real-time data pipelines. The core challenge is counting events at massive scale with bounded memory and bounded latency, then surfacing the top K items.

The naive approach is straightforward: maintain a hash map of topic-to-count and a min-heap of size K to track the top items. When an event arrives (a tweet with a hashtag, a search query, a video view), increment the topic's count in the hash map and update the heap. This works perfectly for small datasets but fails at scale. If you are tracking millions of unique topics across billions of events per day, the hash map alone consumes gigabytes of memory, and a single machine cannot process the event stream fast enough. Moreover, trends must be time-windowed -- you want to know what is trending now, not what was popular last week.

Approximate counting solves the memory problem. A Count-Min Sketch is a probabilistic data structure that uses a 2D array of counters and multiple hash functions to count item frequencies with bounded error. It uses O(1) memory per item (shared across the array) and provides counts that are always greater than or equal to the true count, with overestimation bounded by a configurable error parameter. For K=100 trending topics and a 0.01% error rate, a Count-Min Sketch needs only a few megabytes of memory regardless of how many unique topics exist. The Space-Saving algorithm is another option that maintains exact counts for the most frequent items and approximate counts for less frequent items, using a fixed-size data structure.

The streaming architecture processes events through a multi-stage pipeline. Raw events (tweets, searches, clicks) are published to Kafka topics, partitioned by event type. Counter service instances consume from Kafka partitions, each maintaining a local Count-Min Sketch for its partition. Periodically (every 5-30 seconds), the counter services export their top-K candidates to an aggregation service that merges counts across all partitions and produces the global top-K. The final top-K list is written to a Redis sorted set that powers the serving layer. The API returns the current trending topics by reading from Redis, ensuring sub-millisecond read latency regardless of the volume of events being processed.

Time windowing determines the recency of trends. A tumbling window (e.g., 5-minute non-overlapping windows) is simple to implement but produces discontinuous trends -- a topic can appear trending at 2:59 and disappear at 3:01. A sliding window (e.g., the last 60 minutes, updated every minute) produces smoother trends but requires maintaining state for the overlap period. Exponential time decay applies a decay function to older events, giving recent events more weight. Many production systems use a combination: a sliding window for the base count with exponential decay weighting, updated every few seconds.

Imagine a company with 10,000 employees submitting suggestions via a suggestion box. To find the top 10 most requested improvements, the naive approach is to read every suggestion and tally counts (exact counting). But with thousands of suggestions per day, this becomes overwhelming. An approximate approach is to keep a small board with 10 slots. Each time a suggestion arrives, check if it matches an existing slot and increment its count. If it does not match and the board is full, compare it with the lowest-count slot. If the new suggestion appears more frequently (based on a rough estimate), replace the slot. After processing many suggestions, the board reliably shows the most popular topics, even though the exact counts may be slightly off.