How do you design a top-k trending system with time windows?

In this article

1. Before you start
2. Why interviewers ask this
3. Top-k and heavy hitters from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

The distributed systems interview guide shows where this design sits among the round's other questions.

Why interviewers ask this

A wrong top-k design fails quietly: the page loads, the list looks plausible, and the numbers are off. Interviewers use this question to see whether a candidate notices where the exact answer becomes too expensive, and whether the candidate can state which error is acceptable.

Candidates report versions of it for trending articles, most-shared articles, top food items per restaurant over several intervals, top exceptions in a day, and top songs. The windows reported are typically 15 minutes, 60 minutes and 24 hours, sometimes "expandable". The same question is also reported under names such as top-K service and ad click aggregator.

A weak answer says "put counts in Redis and sort." A strong answer partitions by key, buckets time, bounds memory, and explains how a window is built from buckets. A Staff-level answer adds hot keys, late events and what the error costs the product.

Top-k and heavy hitters from first principles

Heavy hitter

A heavy hitter is a key that accounts for more than a chosen fraction of all events in a stream, such as an article with over one percent of all views. Cormode and Muthukrishnan (2005) define it by multiplicity above a fraction of the total.

Time bucket

A time bucket is a fixed slice of time, such as one minute, that holds its own counts. A window answer is built by combining several buckets rather than rereading raw events.

Count-Min sketch

A Count-Min sketch is a small grid of counters, with one hash function per row, that estimates how often each key occurred without storing the keys. For streams of increments, estimates never fall below the true count.

In plain words

Picture a scoreboard at a long race with many checkpoints. Each checkpoint tallies runners by team for each minute. To find the leading teams in the last hour, you add up the last sixty minute-tallies. You never replay the whole race. The analogy breaks in one place: a real system cannot keep a tally line for every team forever, so it keeps only a bounded list and accepts small errors.

In one precise sentence, a top-k service maps each event to a key, increments a count for the pair of key and time bucket, and answers a window query by merging the buckets inside it and returning the k keys with the largest totals.

A tumbling window is the simplest case: fixed, non-overlapping blocks such as each clock hour. A sliding window moves, so it needs the buckets above.

Step 1: Partition the stream by key so shard lists can merge

Partitioning by key sends every event for one key to the same shard, a shard being one worker that owns a slice of the keys. Each shard then holds the complete count for its keys, and the global top-k is the top-k of the shards' lists.

Without it, the merge breaks. Take three shards where key x has 10 events on each shard, 30 in total, and each shard also has its own local favorite with 12. Every shard's top-1 is its favorite, so merging top-1 lists returns a favorite with 12, while the true winner is x with 30.¹ Partition by key and all 30 land on one shard, where x wins.

Skew is the cost: one celebrity key overloads one shard. A common fix splits a hot key into sub-keys, then sums them at merge time. See consistent hashing for choosing shards. You now know where counts live; next they need a time dimension.

Step 2: Count each key inside a time bucket

Each shard keeps one counter per pair of key and bucket, and the bucket comes from the event's own timestamp, called event time, rather than the arrival time. A late event then lands in the bucket where it belongs.

Choose a grace period after which a bucket is closed, because late events are accepted until then. A window answer is the sum over the buckets that fall inside it. With one-minute buckets, a 15-minute window needs 15 buckets, a 60-minute window 60 and a 24-hour window 1,440.¹

The bucket makes the window slide cheaply. In an illustrative stream with a three-bucket window, key a leads at minute 3 with 18 against 11, key b leads at minute 4 with 16 against 9, and by minute 5 b has 21 against 1.¹ No raw event was reread; the oldest bucket simply left the window. Input: events. Output: counts per key per bucket.

Step 3: Keep only a bounded top-k with a sketch and a heap

Exact counting needs one counter per distinct key, which is too much when keys number in the hundreds of millions. A Count-Min sketch bounds memory. For error fraction ε and failure probability δ, the paper sets the width to the ceiling of e divided by ε and the depth to the ceiling of the natural log of 1 over δ.

With ε of 0.001 and δ of 0.01, the grid is 2,719 wide and 5 deep, 13,595 counters, or 54,380 bytes at four bytes each.¹ The paper's bound is that the estimate is never below the true count and, with probability at least 1 − δ, at most the true count plus ε times the total count.¹ For 1,000,000 events that is at most 1,000 extra.

The sketch holds no keys, so pair it with a min-heap of size k: update the sketch, estimate the key, and replace the heap's smallest entry when the estimate beats it. Redis Top-K is built on the HeavyKeeper algorithm, using a hash table of probabilistic counts and a min-heap of the top K.

Step 4: Merge buckets for the window and serve the result

A window answer is the merge of its buckets. The sketch paper notes that sketches are typically linear and suited to distributed settings, so two sketches with the same shape and hash functions add cell by cell. Add the window's bucket sketches, estimate every candidate key from the merged sketch, and keep the k largest.

The candidate set must not be only each bucket's top k, because that repeats Step 1's failure across time: in an illustrative case a key with 10 events in each of 60 minutes totals 600, yet it can sit below the cut in every minute, so no bucket heap holds it and the hour answer misses it.¹ Three remedies work: keep far more candidates per bucket than you return, keep every key above a fraction φ of the bucket total, or keep a running candidate heap per window, updated on each event from the merged sketch's estimate. Per-bucket candidates make the result approximate.

Storage is the design choice. One-minute sketches for 24 hours is 1,440 sketches, 78,307,200 bytes per shard at the size above. Keeping 60 minute sketches for the last hour and 24 hour sketches for the day is 84 sketches, 4,567,920 bytes, and a 24-hour query merges about 24 hour sketches instead of 1,440.¹

Serve from a cache: recompute each window when a bucket closes and store the k keys, so a read is a lookup. The Redis Top-K page gives insertion as O(K + depth), roughly O(K), and lookup as O(K), so keep k small. That structure describes counting, not window expiry, so the window logic is your design.

1 · Shard by key2 · Count per bucket3 · Bounded top-k4 · Merge and serveReplay

Step-by-step description

1. One key always goes to one shard.
2. Each key is counted in its time bucket.
3. A sketch and heap keep k keys.
4. Buckets merge into each window.

• Events are sharded by key so each shard holds complete counts.
• Counts are kept per key per time bucket.
• A window answer merges the buckets inside the window.

How does a trending list differ from a top list?

A trending list ranks keys by a trend score, not by raw count. A simple score is the current window's count plus a smoothing constant s, divided by the baseline count plus s. The baseline is the same key's count over the previous window, read from the earlier bucket sketches and estimated only for the candidate keys.

Smoothing alone is not enough: with s of 10 (illustrative), a key rising from 1 to 5 events scores about 1.36 while a giant rising from 10,000 to 11,000 scores about 1.10, so add a minimum-count floor, such as 50 events, before a key is eligible.¹ An alternative is exponentially decayed counts, where each bucket's weight shrinks with age. The candidate heap is then ordered by the trend score, and the candidate set must include rising keys, not only the biggest.

Worked example

Assume, as an illustration, 50,000 events a second. That is 4,320,000,000 events a day, and across 100 partitions each shard sees 500 events a second.¹ Applying back-of-the-envelope estimation this way tells you per-shard work is small; memory for distinct keys is the real limit.

To check the sketch, a seeded simulation sent 200,000 events over a skewed (a few keys take most events) set of 50,000 possible keys; 28,712 keys appeared (illustrative).¹ Two sketches counted them, each with five rows.

The narrow sketch used about a tenth of the memory and overcounted more, but the top 10 was the same here because the heavy keys were far above the noise.¹ The test fails when the k-th and (k+1)-th keys are within the error; say so aloud.

Text description of the diagram

• The largest overcount was 60 against a bound of 199.9 at width 2,719.
• The largest overcount was 1,050 against a bound of 1,998.7 at width 272.

Trade-offs and edge cases

Windows trade freshness against memory. A tumbling window needs one counter set but its answer jumps at each boundary. A sliding window kept as buckets needs one set per bucket and merges them per query. An exact sliding window that keeps every event moves per event but rescans or stores the whole window, which suits only small streams.

Text description of the diagram

• A tumbling window needs one counter set but its answer jumps at each boundary.
• A bucketed sliding window needs one counter set per bucket.
• An exact sliding window keeps every event in the window.

Edge cases to name:

• Hot keys. One key can overload its shard; split it into sub-keys and sum them.
• Late events. A bucket accepts events until its grace period ends; later events are dropped or sent to a correction path.
• Ties and near ties. Sketch error can reorder keys whose counts are close; return exact counts for the final k from a second pass if order matters.
• Trending is not top. A trending list ranks a trend score, not raw volume, as in the trending section above; otherwise the same giants always win.
• Exact numbers. A common path is a fast approximate stream for live lists plus a periodic batch recount of the raw events that reconciles exact totals, such as for billing.
• Cost of exactness. Exact counts are right for money, such as billing; approximate counts suit feeds. The ad click aggregator design shows the exact case.

How to answer it in an interview

The spoken structure: partition by key, bucket the time, bound the memory, merge for the window, then name the error.

Common mistakes

• "Each shard sends its top-k and I merge them." (wrong) Without key partitioning a heavy key can sit below every local cut. (right) "I partition by key, so each shard's counts are complete."
• "The Count-Min sketch gives me the top k." (wrong) It stores counts, not keys. (right) "The sketch estimates counts; a heap of size k holds the candidate keys."
• "A window's top-k is the merge of each bucket's top-k." (wrong) A key with steady medium counts can miss every bucket's cut. (right) "I keep more candidates than k per bucket, or every key above a threshold, and estimate them from the merged sketch."
• "A sketch can undercount." (wrong) For streams of increments, the paper's estimate is never below the true count. (right) "It only overestimates, by at most ε times the total with high probability."
• "A sliding window means recomputing from raw events." (wrong) That rereads the whole window each time. (right) "I merge the buckets inside the window and drop the oldest."

Follow-up questions

How do you design a top-articles system with dynamic time windows (15 min, 60 min, 24 hours, and expandable)?

Store minute buckets for the short windows and coarser hour buckets for the long ones. A new window, such as 7 days, adds a coarser tier of day buckets, and a window is always the merge of the tier that fits it.

How do you design a trending-articles system from a continuous stream of database writes?

Read the database's change log into the stream, key each event by article, and feed the bucket counters. Rank by a smoothed trend score against the previous window, with a minimum-count floor, as in the trending section above, so the list shows what is rising.

How do you efficiently find the top N most shared articles?

Count shares per article per bucket on key-partitioned shards, keep a heap of size N, and serve cached results. If N is small, read the heap directly rather than sorting every article.

How do you stop a user seeing items they have already viewed in the top-k?

Fetch more than k candidates, filter out the items in that user's viewed set, and return the first k that remain. Size the extra candidates from how many items a typical user has already seen.

Why not keep everything in a sorted set?

A sorted set needs one entry per distinct key, so memory grows with key count. A sketch plus heap stays bounded, which the Redis documentation presents as using a fraction of a sorted set's memory.

How would you find the top k exceptions in the last 24 hours?

Treat each exception type as a key, not its message text. Count per minute bucket on key-partitioned shards, then merge the 1,440 minute buckets, or fewer coarser ones, for the day.¹ The same bucketing suits per-restaurant totals over 1 hour, 1 day and 1 week, where plain sums are exact and need no sketch. Per-key windowed counting also appears in the distributed rate limiter, and the database interview questions and backend interview questions cover the storage side.

Sources

1. Top-K | Redis documentation — Redis, 10 Sep 2026
2. An improved data stream summary: the count-min sketch and its applications — Journal of Algorithms 55(1) (Cormode and Muthukrishnan), 1 Apr 2005
3. Count-Min sketch | Redis documentation — Redis, 10 Sep 2026