Top-K Ranking And Selection
Asked of: Software Engineer
Last updated

What's being tested
Top-K ranking and selection tests whether you can move between single-machine order statistics and distributed real-time aggregation without losing correctness, latency, or memory control. Interviewers are probing for the right data structure under constraints: heap vs quickselect vs balanced tree vs approximate sketches vs stream-processing state. LinkedIn cares because feeds, search suggestions, job recommendations, trending entities, ads, and notifications all need fast ranking over large, changing datasets. A strong Software Engineer answer shows you can define semantics, choose algorithms, shard safely, merge partial results, and explain freshness/accuracy tradeoffs.
Core knowledge
-
Top-K selection means returning the largest or smallest
kitems by a score, while k-th order statistic means returning the item at rankk. For a static array, use quickselect for expected time and extra space, or a size-kmin-heap for time. -
Heap-based ranking is the default when
k << nand input is streaming or too large to sort. Maintain a min-heap of sizek; if a new item beatsheap[0], replace it. This avoids full ) sorting and uses memory. -
Quickselect is best for in-memory static selection when you only need the k-th element or an unordered Top-K partition. It has expected time but worst-case unless you randomize pivots or use median-of-medians with deterministic but higher constants.
-
Exact frequency Top-K over events requires maintaining counts, usually in a hash map plus heap or ordered set. For
Ndistinct keys, exact counting costs memory; once cardinality reaches tens or hundreds of millions, you usually need sharding, approximation, or offline aggregation. -
Approximate heavy-hitter algorithms reduce memory for high-cardinality streams. Count-Min Sketch estimates frequency with one-sided error: estimate is with probability using width and depth . Space-Saving and Misra-Gries track candidate heavy hitters in bounded memory.
-
Sliding-window Top-K is harder than all-time Top-K because old events expire. Common approaches include time-bucketed counters, e.g. per-minute maps for the last hour, then merge buckets at query time; or stream processors such as
Apache Flink/Kafka Streamswith windowed state and timers. -
Window granularity controls cost and freshness. If the service needs Top-K over the last 1 hour with 1-minute buckets, each query merges up to 60 bucket maps. Smaller buckets improve expiry precision but increase metadata, merge cost, and state churn.
-
Distributed aggregation usually follows a two-level plan: each shard computes local Top-K or local counts, then a coordinator merges candidates. Local Top-K alone can be incorrect for global Top-K if an item is rank
k+1on every shard but globally huge, so exact global results require merging counts for enough candidates or partitioning by key. -
Partitioning by key makes exact counts simpler: hash each normalized search term, member id, or entity id to one owner shard. All increments for that key go to the same shard, avoiding cross-shard count reconciliation. The downside is hot keys; handle them with batching, local buffering, or special hot-key splitting.
-
Ranking semantics must be explicit: all-time vs last
Nminutes, raw counts vs unique users, case folding, punctuation normalization, bot filtering, and tie-breaking. For example,"LinkedIn","linkedin", and"linked in"may or may not collapse depending on product requirements. -
Read/write path tradeoff is central. Precompute Top-K continuously for low-latency reads, or compute on demand for simpler writes but slower queries. A common design stores precomputed leaderboards in
Redissorted sets or an in-memory heap, with durable counts inCassandra,MySQL, or another backing store. -
Correctness under concurrency includes idempotency, duplicate events, eventual consistency, and monotonicity expectations. If events can be retried, count updates need dedupe keys or accepted approximate overcounting. For user-facing rankings, define whether
p99read latency or exactness is more important.
Worked example
For Design a Top-K search words service, start by clarifying scope: “Are we ranking all-time searches, last hour/day, or both? Is Top-K global or per country/language? Do we count raw searches or unique users? What latency and freshness do reads require?” Then declare assumptions, such as 1 million search events per second, Top 100 queries globally, near-real-time freshness within 10 seconds, and reads at low p99 latency.
A strong answer can be organized around four pillars: event ingestion, normalization/counting, Top-K computation, and serving. In the write path, search events are normalized consistently, assigned a key, and sent through a durable log like Kafka; consumers aggregate counts by time bucket and key. For all-time Top-K, maintain per-key counters and a candidate heap or sorted set; for sliding windows, maintain bucketed counters and periodically merge the active buckets into a materialized Top-K view.
The key design decision to flag is exact vs approximate. Exact Top-K requires retaining counts for all distinct search terms in the active window, which may be expensive with massive cardinality; approximate approaches such as Count-Min Sketch plus a candidate heap reduce memory but may include false positives near the cutoff. For a search suggestions service, approximate rankings may be acceptable if the top terms are stable and downstream filters remove bad terms; for billing or compliance-style metrics, exactness would matter more.
Close by explaining operational concerns without overbuilding: expose a read API like GET /top-searches?window=1h&k=100, cache precomputed results in Redis, monitor freshness lag, dropped events, shard hot spots, and result churn. If you had more time, add regional Top-K, per-language normalization, abuse filtering hooks, and a backfill path to recompute rankings from durable logs.
A second angle
For Find the k-th largest element in an array, the same ranking concept appears without distributed-system concerns. The main constraint is algorithmic efficiency: sorting is simple but costs , while quickselect gives expected by partitioning around a pivot until the target rank lands in place. A heap solution is still useful when the array is streamed or k is small relative to n, because it uses memory and never needs all elements sorted. The interviewer is checking whether you can pick the simplest correct technique for the constraint rather than forcing a system-design solution onto a coding problem.
Common pitfalls
Pitfall: Treating “Top-K” as “sort everything.”
Sorting the full dataset is often acceptable for small arrays, but it is the wrong default for high-volume streams or large cardinality ranking. Say explicitly when sorting is fine, then move to heaps, quickselect, sketches, or precomputation as scale grows.
Pitfall: Ignoring semantics before designing storage.
A tempting but weak answer is “count every word and store the top results in Redis.” That misses the hard parts: time window, deduplication, normalization, tie-breaking, geographic grouping, and whether rankings must be exact. Clarifying these early makes the rest of the design defensible.
Pitfall: Merging local Top-K lists as if it were always correct.
If each shard sends only its local Top 100, the true global #1,000 may be missed even if its aggregate count should place it globally in the Top 100. For exact results, partition by key or merge broader candidate sets with counts; for approximate results, state the error tradeoff.
Connections
Interviewers may pivot from this topic into leaderboard design, rate-limited stream processing, cache invalidation, consistent hashing, or ranking feed serving. Coding follow-ups often involve heaps, quickselect, sliding windows, or LRU/LFU cache design.
Further reading
-
“Finding Frequent Items in Data Streams” by Cormode and Hadjieleftheriou — survey of heavy-hitter algorithms used for approximate Top-K.
-
“Space-Saving Algorithm” by Metwally, Agrawal, and El Abbadi — classic bounded-memory frequent-items approach.
-
Designing Data-Intensive Applications by Martin Kleppmann — practical background on logs, stream processing, replication, and consistency tradeoffs.
Featured in interview prep guides
Practice questions
- Solve Cache, Window, and Heap ProblemsLinkedIn · Software Engineer · Onsite · medium
- Find the k-th largest element in an arrayLinkedIn · Software Engineer · Onsite · medium
- Design a Top-K search words serviceLinkedIn · Software Engineer · Technical Screen · medium
- Design Top K ranking systemLinkedIn · Software Engineer · Onsite · hard
Related concepts
- Heaps, Priority Queues, and Top-K SelectionCoding & Algorithms
- Top-K Selection And Order StatisticsCoding & Algorithms
- Top-K Selection, Heaps, And RankingCoding & Algorithms
- Top-K, Heaps, Quickselect, And Frequency AnalysisCoding & Algorithms
- Top-K Queries And Streaming AggregationCoding & Algorithms
- Top-K Frequency TrackingCoding & Algorithms