How Would You Design a Top-K Trending System?
Design a top-K trending system using sliding windows, Count-Min Sketch, per-shard top-K heaps, and periodic merge for real-time ranking.
Expected Interview Answer
A top-K trending system continuously ranks items (like hashtags or search terms) by recent activity using a streaming pipeline that maintains approximate counts per time window and a bounded top-K structure, since exact global ranking over unbounded cardinality is too expensive to compute on every event.
Events (a hashtag used, a search performed) flow through a stream processor that buckets counts into small time windows (e.g., one-minute buckets) per item, often using a probabilistic structure like Count-Min Sketch to bound memory when the item cardinality is huge, trading a small, tunable error rate for constant space. A sliding window aggregation (summing the last N buckets) approximates “trending in the last hour” while automatically aging out old activity without a separate decay job. To get the top-K from potentially millions of tracked items, each stream-processing shard maintains a local top-K (via a min-heap of bounded size K), and a merge step combines shard-level top-K lists into a global top-K, which is far cheaper than sorting every item globally on every update. The merged top-K is cached and refreshed on a short interval (e.g., every few seconds), since trending lists do not need per-event precision — read-time freshness is a UX choice, not a correctness requirement.
- Bounded memory via approximate counting (Count-Min Sketch) even with huge item cardinality
- Sliding time windows naturally age out old activity without a separate cleanup job
- Local top-K heaps per shard plus a merge step avoid globally sorting every item
- Cached, periodically-refreshed results avoid recomputing rankings on every single event
AI Mentor Explanation
A top-K trending system is like a cricket board tracking which players are “in form” over the last few matches instead of over an entire career. Each ground keeps a rolling tally of recent performances (a sliding window), automatically dropping matches from months ago as new ones are added, without a separate archival cleanup step. Rather than ranking every player in the country exactly, each region first picks its own short list of standout players (a local top-K), and a national selector merges those short lists into the final “in-form” top ten. That windowed, locally-bounded ranking merged centrally is exactly how a top-K trending system scales.
Step-by-Step Explanation
Step 1
Bucket events into time windows
Stream processors count item activity into small buckets (e.g., one-minute), often via a Count-Min Sketch for bounded memory.
Step 2
Slide the aggregation window
Sum the last N buckets per item to approximate recent activity, aging out old data automatically as the window advances.
Step 3
Maintain local top-K per shard
Each stream-processing shard keeps a bounded min-heap of its own top-K items instead of tracking every item globally.
Step 4
Merge and cache the global top-K
A merge step combines shard-level top-K lists into the global ranking, cached and refreshed on a short interval for reads.
What Interviewer Expects
- Explains why exact global ranking on every event is too expensive at scale
- Uses sliding time windows so recent activity is weighted and old activity ages out
- Proposes bounded structures (Count-Min Sketch, per-shard top-K heap) instead of tracking every item exactly
- Discusses merging shard-level top-K lists and caching/refreshing the result periodically
Common Mistakes
- Trying to maintain an exact sorted ranking of every item on every single event
- Forgetting to age out old activity, so “trending” never reflects recent behavior
- Tracking exact counts for unbounded cardinality instead of using an approximate structure
- Recomputing the full global ranking synchronously on every read instead of caching it
Best Answer (HR Friendly)
“A top-K trending system figures out what is popular right now, like trending hashtags, by counting recent activity in small time windows and keeping only a short list of top items per server, which get merged into one overall trending list every few seconds. We accept slightly approximate counts and a small delay because true trending does not need to be perfectly exact in real time.”
Code Example
import heapq
class ShardTopK:
def __init__(self, k=100):
self.k = k
self.counts = {} # item -> approximate count in current window
def record_event(self, item):
self.counts[item] = self.counts.get(item, 0) + 1
def local_top_k(self):
return heapq.nlargest(self.k, self.counts.items(), key=lambda kv: kv[1])
def merge_global_top_k(shard_top_k_lists, k=100):
merged = {}
for shard_list in shard_top_k_lists:
for item, count in shard_list:
merged[item] = merged.get(item, 0) + count
return heapq.nlargest(k, merged.items(), key=lambda kv: kv[1])
# Runs every few seconds, not on every event:
# global_top_k = merge_global_top_k([shard.local_top_k() for shard in shards])
# cache.set("trending:global", global_top_k, ttl_seconds=5)Follow-up Questions
- How would a Count-Min Sketch introduce error, and how would you bound or measure it?
- Why is per-shard local top-K sufficient even though a globally top-100 item might not be in every shard’s local top-K?
- How would you handle a sudden viral spike so it is reflected in the trending list within seconds?
- How would you weight recency, e.g. giving activity in the last 5 minutes more weight than the last hour?
MCQ Practice
1. Why use a probabilistic structure like Count-Min Sketch for tracking item counts?
Count-Min Sketch trades a small approximation error for constant, bounded memory regardless of how many distinct items are tracked.
2. Why do stream-processing shards maintain a local top-K instead of a full sorted list of all items?
A bounded per-shard top-K heap avoids the cost of globally sorting potentially millions of items on every update, and shard results are merged later.
3. Why is the global top-K result cached and refreshed periodically rather than recomputed on every read?
Since trending does not require per-event precision, periodically refreshing a cached result balances freshness against computational cost.
Flash Cards
Why use sliding time windows for trending? — They weight recent activity and automatically age out old activity without a separate cleanup job.
Why use Count-Min Sketch for item counts? — It bounds memory for huge item cardinality, trading a small error rate for constant space.
Why compute local top-K per shard first? — It avoids globally sorting every item; a merge step then combines shard-level top-K lists.
Why cache the global top-K result? — Trending lists tolerate slight staleness, so caching avoids recomputing rankings on every read.