We use analytics cookies.We use cookies to analyze site traffic and improve your experience.
Loading...
System Design and AI Engineering, by Roni Das. 984 interactive lessons.
Start LearningSystem design interview guide
Short answer
A top-k system finds the k items that occur most often in a stream, such as the 10 most-viewed videos in the last hour. These frequent items are called heavy hitters. A fast path reads view events from Kafka, sends every view of one video to the same worker by hashing its id, and counts with a count-min sketch, a small table of counters that can only overcount, plus a min-heap of size k that keeps the current leaders. A merger combines the workers' lists into the global top k. A slow path recounts each hour exactly from stored events and replaces the estimate.
in this guide
8 parts open to everyone · 3 with a free account · 3 with the course
You can read 8 of 14 parts. A free account opens the deep dive; the course opens all of it.
The problem looks easy: count views and sort. The interviewer wants to see where that breaks and what you do next. First, can you estimate the load and the memory before you pick a tool? Second, do you know when exact counting is enough, and when an approximate structure such as a count-min sketch is worth its error? Third, can you state that error exactly, and explain why a sketch alone does not give you the top k? Fourth, do you understand time windows, and why a sliding window costs more than a tumbling one? Fifth, can you spot the trap in merging partial top-k lists from many machines, and fix it? Strong candidates also raise hot keys (one item that gets far more traffic than the rest) without being asked, and they offer a slow exact path next to the fast approximate one.
This page is the free part.
₹1,111 in India$25 everywhere elseonce, for the whole course
The System Design course covers the Top-K System design across a run of lessons, not one page. These 4 alone are about 99 minutes of step-by-step reading, every one with a quiz.
Always clarify these in the first 5 minutes of the interview. Do not start drawing boxes until both lists are agreed.
This guide is built on these 6 lessons. Each one teaches one piece of the Top-K System design above, step by step.
Lifetime access for ₹1,111 in India or $25 elsewhere. Interactive diagrams, quizzes, and 20 capstone projects to practise on.
This one question is not enough for the interview.
Each question has why it is asked, a full answer, what the interviewer listens for, the follow-ups, the common mistakes and a diagram (268 diagrams in all). A PDF you keep, junior to staff level.
Two courses by the author of this page:
770 lessons · 18 free to read
₹1,111 in India · $25 elsewhere, once
Get System DesignYou own this course
214 lessons · 10 free to read
₹1,333 in India · $35 elsewhere, once
Get Generative AI and Agentic AIYou own this course
Save your progress and get the interview checklist PDF
Suppose a video site records 10 billion views a day and wants a list of the 10 most-viewed videos in the last hour, the last day and all time. That is about 116,000 views every second on average, and close to 350,000 at the busiest time of day. Most videos get a handful of views. A few get millions. You cannot sort every video every second, and keeping an exact count for every video in every window costs a lot of memory. This page shows how to find the few big ones cheaply, and how to be honest about the error.
A top-k system finds the k items that occur most often in a stream of events, such as the 10 most-viewed videos in the last hour. The items that occur most often are called heavy hitters. The usual design has two paths. The fast path reads view events from a log such as Kafka, sends each video to one counting worker by hashing its id, and counts views per time window. To save memory, each worker counts with a count-min sketch: a small table of counters, d rows by w columns, where each row hashes the video to one counter. To add a view, add 1 to one counter in every row. To read a count, take the smallest of those d counters. The answer is never too low. With width w = e/ε and depth d = ln(1/δ), it is too high by more than ε times the total number of views only with probability δ. A sketch cannot list its videos, so each worker also keeps a min-heap of size k: a small list that always knows its smallest member, so a new video replaces that member when its estimate is larger. The workers send their lists to one merger, which builds the global top k. The slow path stores every view and recounts them exactly every hour, then replaces the estimates. The traps are merging lists from partitions that split a video's views (the true winner can vanish), sliding windows, and one viral video overloading one worker.
Where it shows up
This is a standard question in system design interview preparation. Hello Interview, for example, teaches it as 'Top K YouTube videos' over the last hour, day, month and all time. It also hides inside other questions: trending hashtags, the most-searched queries for autocomplete, the busiest IP addresses for attack detection, and the top ads in an ad click aggregator. Interviewers like it because it tests counting at scale, stream windows and approximate data structures in one problem.
Spec sheeta Top-K System
worked through below, with the maths
The hard parts of this design are taught step by step in the System Design course: Stream Processing, Tumbling Windows and Hopping Windows.
Process data as it arrives, real-time analytics, fraud detection, and event-driven architectures.
Fixed-size, non-overlapping time windows, count events per minute, average per hour.
Fixed-size windows that overlap, sliding averages with configurable hop interval.
Windows that slide with every event, continuous recalculation over the most recent N events or T time.
all part of
System Design Masterclass
770 lessons · about 287 hours · 18 free to read
₹1,111in India, by UPI
$25everywhere else, by PayPal
You own this course
Continue with Stream Processingpay once,
yours for life
Live from the course bench
Real interview questions, live diagrams and measured lab results, pulled at random from the lessons. A new set every time you come back.
Show your math. Pulling numbers from thin air signals you have not thought about the load.
View events per second
about 116,000 average, 350,000 peak
Assume 10 billion views a day. These are assumptions for the interview; say them out loud before you use them. 10,000,000,000 / 86,400 seconds = 115,741 views per second on average. Assume the busiest hour runs 3 times the average: 3 x 115,741 = 347,222, about 350,000 per second.
Raw event log
about 1 TB a day
Assume each view event is about 100 bytes (video id, time, region, a few ids). 10,000,000,000 x 100 bytes = 1,000,000,000,000 bytes = 1 TB a day. The slow exact path keeps this in cheap object storage.
Exact counts for one day
about 32 GB
Assume 500 million different videos get at least one view in a day. An exact hash map (a table from video id to count) needs about 64 bytes per entry once you include the id, the count and the table's own overhead. 500,000,000 x 64 bytes = 32 GB. Spread over 14 machines that is about 2.3 GB each, which is possible. It grows with every extra window and every extra breakdown, such as one count per country.
Count-min sketch for one day
about 152 MB
Pick ε = 0.000001 (one in a million) and δ = 0.001. Width w = e / ε = 2,718,282 rounded up. Depth d = ln(1 / 0.001) = 6.9, rounded up to 7. 2,718,282 x 7 = 19,027,974 counters. At 8 bytes each (a day's total of 10 billion does not fit in 4 bytes): 152 MB. Error: at most ε x 10,000,000,000 = 10,000 views too high, with probability at least 0.999.
Sliding last hour, from 5-minute slices
about 183 MB
One hour is 10,000,000,000 / 24 = 416.7 million views. With ε = 0.00001 the error is at most 4,167 views. Width 271,829, depth 7, 8 bytes: 15.2 MB per sketch. A sliding hour kept as 12 five-minute sketches of that size: 12 x 15.2 = 183 MB. The top-1,000 heap itself is tiny: 1,000 x 16 bytes = 16 KB.
Counting workers
about 7 at peak, run 14
Assume one worker can count 50,000 events per second. Measure this on your own machines. 347,222 / 50,000 = 6.9, so 7 at peak. Run about twice that, 14, so a lost machine or a viral video does not push the others past their limit.
Draw two paths that start from one log. The log is Kafka, a service that stores events in the order they arrive and lets many readers read them at their own pace. A topic (one named stream) is split into partitions, and all events that share a key go to one partition. This works because a hash function turns the key into a partition number, and a given key always produces one fixed number. Video players send one view event per view, and the key is the video id. The fast path is a set of stream workers, for example Apache Flink jobs. A stream worker is a program that reads events one by one, as they arrive, and keeps running state in memory. Each worker reads some of the partitions, so it owns every view of its own videos. For each window (last hour, last day), it keeps a count-min sketch to count views and a min-heap that holds its top 1,000 videos by estimated count. Every few seconds each worker sends its list to a small merge step, which builds the global top 1,000 and writes it to Redis, an in-memory data store that answers simple reads very fast. The top-k API only reads Redis, so a request never touches the counting. The slow path copies every event into object storage, cheap storage for large files, such as Amazon S3. Once an hour has passed, plus some time for late events, a batch job (a program that processes a large stored set of data in one run) counts that hour exactly: group by video id, count, keep the top 1,000. The exact list replaces the estimate in Redis. The all-time list is the stored all-time count of each video plus the exact hours that are done. This pairing, a fast layer for the newest data and a batch layer that later corrects it, is what Nathan Marz called the lambda architecture.
In a real interview, sketch this on the whiteboard before diving into any single box.
Follow a single view of video v42 through both paths. This is a good order to explain it in.
The player sends a view event: video v42, time 10:07:31, region eu. The ingest service writes it to the Kafka topic views, with the key v42.
Kafka hashes the key, and the hash picks one partition. Every view of v42 lands in that partition and is read by one worker.
The worker adds 1 to one counter in each row of the sketch for the current 5-minute slice, then reads the hour's estimate for v42: its estimate in each of the last 12 slice sketches, added together.
If v42 is already in the worker's heap, its count is updated. If not, and its estimate beats the smallest count in the heap, v42 replaces that video.
Every few seconds, each worker sends its top 1,000 with counts. The merge step keeps the largest 1,000 overall. This is exact for the estimates, because no video's views are split across workers.
The merged list goes into Redis under a key such as top:1h. GET /top?window=1h&k=10 reads the first 10 entries.
This event is also written to object storage, in a folder for its hour.
After the hour closes and late events have had time to arrive, a batch job counts every view of that hour exactly and writes the exact top 1,000.
The exact hourly counts replace the estimates. Daily and all-time totals are built by adding exact hourly counts per video, never by adding hourly top-k lists.
Walk through each service. The interviewer wants to hear what each one owns, not just the names.
The ingest service accepts view events from players and writes them to a Kafka topic keyed by video id. Kafka can keep the events for days (how long is a setting), so any worker that crashes can start reading again from the last position it saved. Keying by video id puts all views of one video in one partition.
Each worker reads its partitions and keeps, per window, a count-min sketch and a min-heap of its top 1,000 videos. It saves its state and its read position in the log together, regularly, so after a crash it reloads the state and replays only the events after that position. Saving both together is what stops a replay from losing views or counting them twice.
A fixed-size table of counters, d rows by w columns, with one hash function per row. It answers 'about how many views did this video get?' in fixed memory, however many different videos there are. The answer can be too high, never too low.
A small structure that holds k videos and can always tell you the smallest of them in one step. A new video gets in only if its count beats that smallest one, which is then removed. It holds the video ids, which the sketch cannot list.
Collects each worker's top list every few seconds and keeps the largest k' overall (k' is a longer list than the k anyone asks for, here 1,000). Because each video lives on one worker, this merge is exact for the estimates. It is one small process per window, with a standby copy.
Redis holds the latest top 1,000 for each window as a ranked list. The merge step writes each new list under a new key and then switches the window's name to point at that key in one step, so a reader never sees half a list. The API reads the first k entries and marks each count as an estimate or exact. A list that changes every few seconds is also easy to cache in front of the API.
Every event is stored in hourly folders. A batch job counts each closed hour exactly and writes exact hourly counts per video, which replace the estimates and feed the daily and all-time totals. If the fast path had a bug, the slow path fixes the numbers.
views (Kafka topic). The log of every view. The key decides the partition, so all views of one video are read by one worker. Events are kept for several days so workers can replay them.
Every table for a Top-K System, its keys, and which store fits it and why.
The two paths: fast estimates and a slow exact recount. Two needs pull against each other. Viewers want the trending list to move within a minute. The business wants the numbers to be right, because people may be paid by…
8 deep dives on the parts that break at scale, with 8 diagrams: The two paths: fast estimates and a slow exact recount; Exact counting first, and where it gets expensive; The count-min sketch and its error bound.
Exact counts vs a count-min sketch. Exact counts are simplest to explain and have no error, and with partitioning they fit for one or two windows. A sketch keeps memory fixed however many videos there are…
6 decisions an interviewer expects you to defend, each with the alternative and why it loses here.
Why is the count-min estimate never too low?
6 follow-up questions with model answers, the interview scorecard for this question, and a mock interview on Design a Top-K System with the AI tutor.
Every method on this page is published and in use. The count-min sketch is defined in Cormode and Muthukrishnan's paper (Journal of Algorithms, 2005): width e/ε, depth ln(1/δ), and an estimate that is never below the truth and, with probability at least 1 - δ, at most ε times the total too high. That paper also finds heavy hitters by pairing the sketch with a heap. Redis offers both pieces. Its count-min sketch commands size a table from an error and a probability; with 0.001 and 0.002 it builds a table 2,000 wide and 9 deep. Its Top-K structure is based on the HeavyKeeper algorithm (USENIX ATC 2018), which decays the counters of small items, and it keeps the leaders in a min-heap. Misra and Gries published their counter-based method in 1982, and Metwally, Agrawal and El Abbadi published Space-Saving in 2005, where no count is more than n/m too high with m counters. Apache DataSketches ships a mergeable Frequent Items sketch built on Misra-Gries, with a documented bound of 3.5/M times the total count. For windows, Apache Flink defines tumbling and sliding windows, runs non-keyed windows on a single task, drops late events by default, and warns against tiny slides on long windows. Kafka Streams calls overlapping fixed windows hopping windows. The fast-plus-batch layout is Nathan Marz's lambda architecture (2011), in which the batch layer later replaces whatever the realtime layer computed. Across all of them, one lesson repeats: approximate counting is safe at the top of a list where a few items get most of the events and unreliable in the tail, so build the system so that the error lands where nobody looks.
Sources
If any of these topics are fuzzy, the interviewer will catch it. Each lesson is 15 to 60 minutes with diagrams, code, and a quiz.
Stream Processing
advanced / stream batch processing
Tumbling Windows
advanced / stream batch processing
Hopping Windows
advanced / stream batch processing
Sliding Windows
advanced / stream batch processing
Stateful Stream Processing
advanced / stream batch processing
Watermarking
advanced / stream batch processing
Lambda Architecture
advanced / stream batch processing
Kappa Architecture
advanced / stream batch processing
Bloom Filters
intermediate / database types storage
Hash Partitioning
foundation / database fundamentals
Consistent Hashing
intermediate / data replication distribution
Redis Cache
foundation / caching strategies
Design a Real-Time Analytics Dashboard
capstone / capstone
Design YouTube/Netflix
capstone / capstone
interview readiness
Three questions from this guide. Answer them without scrolling up, the way you would have to in the room.
India: UPI, cards or netbanking through Razorpay. Elsewhere: card or PayPal. Download at once from My packs.
NEWSystem Design Hands-On
Postgres Sharding: Complete Hands-On (PgBouncer + Citus). 2 h 36 min and 20 chapters: one PostgreSQL loaded until it breaks, then four shards behind a router you write, PgBouncer and Citus, with the 139-page slide deck. The first 15 minutes are free to watch.
Free PDF · 79 pages
25 real tech interview questions, answered in full
Five from each of our AI, GenAI, Inference, Maths for ML and Forward Deployed packs. Each with a diagram and a model answer. Free by email.
free tool
Check these numbers yourself
Put in your own guesses for a Top-K System and see requests per second, storage, bandwidth and servers, with every sum written out.
Open the Capacity EstimatorIt is really nice and good Please join the course