M4 Design Trending Topics (Top-K)

From prefix lookup to real-time popularity

Dr. Wei: Today we are transitioning from a search-style problem to a measurement problem. Instead of answering, “Does this prefix exist, and what completions match it?” we are asking, “What is most popular right now, and how do we keep that answer current?”

Sam: So the goal is less about searching a static structure and more about continuously measuring what is winning over time, right? Also, in a Meta interview, what makes a trending design feel like an IC6 answer instead of IC4?

Dr. Wei: In the typeahead setting, each query is about one user input, and the work scales with the length of the prefix you type. For trending topics, the challenge flips: the data stream is continuous, and popularity needs to be tracked over sliding time windows.

Sam: My instinct is IC4 is describing a pipeline and storing counts, while IC6 is nailing sizing, freshness, and failure modes. Is that the right framing?

Dr. Wei: Our driving question is operational: if we want an updated top K list every 60 seconds, how do we maintain counts and rankings without recomputing everything from scratch, even when the system is handling massive volume?

Dr. Wei: Your framing is close. An IC6 answer makes the requirements measurable, does back-of-the-envelope math early, and articulates the tradeoffs and safety rails: approximate counting, windowing, abuse defenses, and what happens when data is late or the pipeline falls behind.

What does "trending" mean in an interview?

Dr. Wei: Before we design anything, we need to agree on what “trending” means for this product. In interviews, “trending” is not a vague buzzword; it’s a concrete definition tied to what we measure, what we return, and how fast we need to respond.

Sam: If I say “top K hashtags per region per hour,” is that specific enough, or do interviewers expect me to define whether it is by count, by growth rate, or by anomaly score?

Dr. Wei: We should clarify the entities we are ranking, like hashtags, topics, or search queries, because different entities have different data sources and different kinds of noise. Then we decide what the system outputs, such as a top K list for a particular region and category within a time window.

Sam: Got it. So a stronger answer explicitly defines the ranking function and the window, not just the endpoint shape.

Dr. Wei: Finally, we make the success metrics explicit: how quickly results must be served, and how often the rankings refresh. Those service level objectives drive the architecture choices, like whether we can compute on request or must precompute and cache.

Scale math: why exact counting gets expensive fast

Dr. Wei: Before we talk about algorithms, let’s do a quick scale check. When you’re tracking “trending,” the hard part is not the math in the formula, it’s the number of counters you’d need to keep if you tried to be exact everywhere, all the time.

Sam: Quick check: in an interview, is doing this kind of sizing what separates an IC4 from an IC6 answer? Or is it more about proposing the right approximation approach?

Dr. Wei: Both matter, but sizing is the easiest signal to demonstrate. IC4 candidates often say “use a sketch” without proving why. IC6 candidates quantify the pain of exactness first, then justify the approximation and its error tradeoffs.

Sam: So if we counted every topic exactly, how much memory are we really talking about? Like, is it gigabytes, or something way bigger?

Dr. Wei: We’ll get to the memory number next, but first anchor the inputs. Our average rate is lambda equals two point five billion divided by eighty six thousand four hundred, about twenty nine thousand events per second. Peaks can be around one hundred thousand per second. And the key space can be about ten million unique topics per day.

Sam: Ten million times 200 is about two billion, times 6 is about twelve billion counters. At 8 bytes each, that’s around ninety-six billion bytes… so maybe around one hundred gigabytes?

Dr. Wei: Good reasoning, but notice the unit conversion. It is nine point six times ten to the eleventh bytes, which is roughly nine hundred sixty gigabytes, close to a terabyte, for fully materialized exact counting across region and window.

Sam: That makes the case. For IC6, would you also call out how often we refresh and what throughput spikes do to the stream processor, not just the memory number?

Dr. Wei: And that’s before we even worry about peak throughput. The average rate is about twenty nine thousand events per second, and peaks can be around one hundred thousand per second. This is why we lean on sketches and top K structures: we want the same answers people care about, using ten to one hundred times less memory.

API surface and data contracts

Dr. Wei: Before we talk about scaling or ranking logic, we need to be clear on what our system promises to the outside world. This slide is about the API surface and the data contracts: what callers can request, what events producers must send, and what controls operators need to keep results safe and trustworthy.

Sam: When interviewers ask for APIs, do they expect only the read endpoint, or should I include operational controls like suppression and auditability too?

Dr. Wei: Keep the serving API simple; push complexity into the pipeline. The goal is a stable, easy-to-cache read path that returns trending topics for a region and category with a clear limit, while the heavy lifting happens behind the scenes in ingestion, aggregation, and filtering.

Dr. Wei: Equally important is the write-side contract: every event we ingest should carry consistent identifiers, a region, a trustworthy timestamp, and a source so we can deduplicate, apply late-event rules, and audit how a topic became trending. And we need an explicit control surface for suppressions with a reason and an expiry, so moderation decisions are traceable and reversible without redeploying code.

Sam: That makes sense. Adding suppression feels like an IC6 signal because it shows you are thinking about safety, not just correctness.

Streaming architecture: compute once, serve many

Dr. Wei: When we build trending topics, the core challenge is scale: millions of events arrive continuously, but users expect an instant answer. The key idea is to do heavy computation once in the background, and then let many clients read fast, precomputed results.

Sam: So the read path is basically a cache lookup most of the time, and the stream processor is where correctness and freshness live.

Dr. Wei: We start by collecting signals from multiple sources, like feeds, searches, and comments, and funnel them into an event bus. A stream processor consumes that shared stream and continuously updates the trending calculations.

Dr. Wei: Instead of recomputing on every request, the processor periodically writes snapshots keyed by things like region, category, and time window. The serving layer then reads those snapshots through a cache in front of a database, so most user requests are simple, low-latency lookups.

Sam: If I want to sound senior, I should probably mention snapshot cadence, cache time to live, and what happens during lag, not just draw boxes.

Count-Min Sketch: sub-linear space frequency estimates

Dr. Wei: When we track trending topics, we want good frequency estimates without storing a giant dictionary of every possible key.

Sam: For interview calibration: if I say “use Count Min Sketch,” is that enough for IC5, and for IC6 do I need to explain how to choose width and depth and what errors show up?

Dr. Wei: Count-Min Sketch is a classic tool for this: it uses multiple simple hash-based summaries to estimate how many times an item has appeared.

Sam: Let me try: we update a few counters per event, and to query a topic we look at those buckets and take the minimum so collisions only overcount.

Dr. Wei: Before we pin down formulas, predict: if we make the sketch wider, how should that change the typical additive overcount error? And if we add more hash rows, how should that change the chance we get a bad overestimate?

Dr. Wei: The rule of thumb is: width w controls additive error roughly like epsilon about e over w, while depth d controls failure probability roughly like delta about e to the minus d. So in the example with w equals one million, epsilon is on the order of about 2.7 times ten to the minus 6, and with d equals five, delta is around e to the minus five, about 0.7 percent.

Tracking top-$K$ efficiently: HeavyKeeper intuition

Dr. Wei: When we build trending topics, we do not just want raw counts; we want the current winners, and we want them to reflect what is happening recently.

Sam: So this is where we move from “estimate counts” to “actually maintain the top list,” which is often the part people hand-wave.

Dr. Wei: As a baseline, the exact way is straightforward: keep a hash map of counts for every key and a min-heap for the current top K. It works, but at streaming scale the memory and update costs blow up, especially when there is lots of churn.

Dr. Wei: So we move to bounded-memory heavy-hitter trackers like Misra Gries or SpaceSaving, which keep only a limited number of counters for candidate keys. HeavyKeeper is in that family, but tuned to be more churn-adaptive: each key is hashed into a small number of buckets, and each bucket stores a candidate key and a counter. On an update, if the bucket already holds that key, we increment; if it holds a different key, we probabilistically decrement that counter, and when it reaches zero we replace the stored key with the new one.

Sam: If I pitch this in an interview, I should probably justify why bounded memory matters under churn and how we keep the final top list stable, not just name the algorithm.

Time windows: freshness beats raw volume

Dr. Wei: Trending is time-bound: what people care about now can change fast, so we measure activity over short and long horizons and emphasize recent signals.

Sam: Is the main interview point here to show we are not using a single all-time counter, but something that reflects freshness like sliding windows or decay?

Dr. Wei: A common trick is to use a decayed count, where each new moment keeps only a fraction of the previous score, then adds the new activity.

Dr. Wei: If the decay factor is between zero and one, older events fade automatically, so a burst of fresh mentions can outrank a topic that had lots of volume yesterday.

Sam: And I should be ready to explain late events and event-time handling, because otherwise the window story is incomplete.

Trending detection: anomaly, not absolute count

Dr. Wei: When we say something is trending, we do not mean it has a big absolute count; we mean it is unexpectedly high compared to what we normally see for that same time pattern.

Sam: For an IC6 answer, is it enough to say “use z score,” or do I need to also define the baseline window, seasonality features, and how we avoid false positives?

Dr. Wei: Let’s make that concrete with a quick example. Here r now, mu, and sigma are all per-minute rates for the same (topic, region, hour-of-day, day-of-week) slice. Suppose right now the rate is 130 per minute, the baseline mean for this hour and day is 100, and the standard deviation is 10. If our alert threshold is a z score of 3, do you think this should trigger?

Sam: It sounds like yes, because 130 is quite a bit above 100, but I want to see how many standard deviations that is.

Dr. Wei: Compute it: z equals 130 minus 100, divided by 10, which is 3. So it is right on the threshold, and we would typically fire, or maybe require strictly greater than 3 depending on how twitchy we want the system to be.

Sam: So the IC6 add-on is stating how we pick the baseline and how we tune the threshold per slice, plus what we do when the baseline data is sparse.

Dr. Wei: This is also why seasonality matters: the baseline should match hour of day and day of week. And threshold tuning is a tradeoff: set it too low and you get noisy false positives; set it too high and you miss real spikes.

Geography and category: slice without duplicating work

Dr. Wei: Up to now, we have talked about finding what is trending overall. In practice, people care about trends inside slices: a country, a city, or a topic category. The goal is to support those slices without running a completely separate trending job for every slice.

Sam: This is where cardinality explodes, right? If we do per-region and per-category, the number of top lists multiplies quickly.

Dr. Wei: A good pattern is: compute local results first, using keys that include the slice, like topic and region. For bigger views like city to country and country to global, you typically roll up by re-aggregating from partitioned streams or from stored per-topic counts at the next tier, rather than assuming you can just combine top K candidate lists.

Dr. Wei: If you do want a mergeable path, you need mergeable summaries, like count-min sketches per region, and then you estimate counts from the merged sketch and recompute top K for the rollup. The tradeoff is cost and accuracy: re-aggregating from counts is more accurate but more expensive, while merged sketches are cheaper but approximate. And if you tag topics into categories, you can keep separate top K lists per category without duplicating the full processing pipeline.

Sam: So the key is composing summaries and rollups, not counting raw events independently for every slice.

Abuse $+$ reliability: the system must resist gaming

Dr. Wei: Trending is an adversarial surface, and it is also a reliability problem: even honest traffic spikes look like attacks, and failures look like fake trends. So we want a short, prioritized checklist that keeps the system both hard to game and steady under load.

Sam: In interview calibration terms, is abuse handling the difference between a mid-level and senior answer here? I feel like IC4 might ignore adversaries entirely.

Dr. Wei: First, the must-have abuse defenses happen before you count anything: filter obvious bot signals, use account reputation, and dedupe repeated events so one actor cannot inflate a topic just by spamming retries.

Sam: If I propose dedupe plus reputation weighting plus a suppression list, that is already pretty strong. Would you expect me to mention how we monitor for gaming and roll back bad trends too?

Dr. Wei: Second, also must-have, protect the serving path: keep a suppression list for known-bad topics, set a sensible cache time to live, and allow graceful stale reads so a partial outage does not suddenly surface junk or empty results.

Sam: So IC6 is layering in operational controls like monitoring, rate limits, and safe fallbacks, not just listing filters.

Dr. Wei: Finally, nice-to-have reliability controls help you degrade cleanly under load: if the queue is falling behind, apply backpressure and drop low-priority slices so the global list stays stable instead of thrashing. The key idea is prioritization: block gaming and protect serving first, then add smarter load shedding.

Exit ticket: can you size the sketch and explain the tradeoff?

Dr. Wei: For the exit ticket, I want you to show you can do quick sizing and make a clear tradeoff argument, like you would in a systems interview.

Sam: For IC6 calibration, do you want me to just compute the memory, or also connect it to an error target and what happens when we scale to more regions and windows?

Sam: So I should compute the memory footprint and then explain what we gain and what we give up compared with exact counting, right?

Dr. Wei: Exactly. Start by sizing one sketch from d, w, and the counter size, then scale it up across all regions and time windows. After that, explain when an approximate sketch is worth it, and when you would pay the cost for exact counts because correctness or explainability matters more than memory and speed.

Sam: Let me try to be crisp: one sketch is depth times width times 4 bytes, so with depth 5 and width one million it is about 20 megabytes, and across 200 regions and 6 windows that is about 24 gigabytes. Then I would argue sketches win when the read path needs low latency and memory is tight, but exact counts win when we need auditability and precise rankings for a small key set.

Thank you for watching!

Thanks for watching. Subscribe and share if you found this useful—see you next time!