TL;DR: Count with a Counter, then select the top k with a size-k heap via heapq.nlargest at O(n log k). Mention bucket sort by count for O(n) when frequencies are bounded.
How to approach it Two phases: count, then select. Counting is always a hashmap (Counter). Selection has three options, and a strong candidate names all three with costs before picking: full sort O(n log n), heap of size k O(n log k), bucket sort by count O(n). Ask the calibrating question: how big is k relative to n? For "top 10 of 10 million log lines" the heap is the obvious choice, and that's exactly the shape of the log-parsing questions later in these loops.
A strong answer Lead with the heap version since it generalizes to streams and big data:
import heapq
from collections import Counter
def top_k_frequent(nums: list[int], k: int) -> list[int]:
counts = Counter(nums)
# nlargest keeps a min-heap of size k internally: O(n log k)
return [x for x, _ in heapq.nlargest(k, counts.items(), key=lambda kv: kv[1])]
Knowing that heapq.nlargest exists, instead of hand-rolling push/pop, is an idiomatic-Python signal these loops reward. If asked for the O(n) version, sketch bucket sort: index buckets by count (count is at most n), then walk from the highest bucket down:
def top_k_frequent_buckets(nums: list[int], k: int) -> list[int]:
counts = Counter(nums)
buckets: list[list[int]] = [[] for _ in range(len(nums) + 1)]
for x, c in counts.items():
buckets[c].append(x)
out = []
for c in range(len(buckets) - 1, 0, -1):
out.extend(buckets[c])
if len(out) >= k:
return out[:k]
return out
What nlargest does internally is worth tracing once, because "min-heap of size k" confuses people until they see that the smallest element guards the door. Take k = 2 over counted items a:5, b:2, c:8, d:1, e:7 (traced by running it):
| Incoming | Heap before (min on left) | Decision | Heap after |
|---|---|---|---|
| a:5 | empty | fill | [a:5] |
| b:2 | [a:5] | fill | [b:2, a:5] |
| c:8 | [b:2, a:5] | 8 > 2, replace min | [a:5, c:8] |
| d:1 | [a:5, c:8] | 1 < 5, skip | [a:5, c:8] |
| e:7 | [a:5, c:8] | 7 > 5, replace min | [e:7, c:8] |
Each newcomer fights only the weakest current member, one O(log k) operation, and everything that cannot beat the weakest is discarded in O(1). That is why the memory never exceeds k and why the pattern survives streams: nothing about the loop needs to see the data twice. It is the same shape as "keep the 10 slowest queries seen so far" in a log tail, which is where this warm-up actually reappears in FDE work.
Tests, including the tie case (clarify: is any tie order acceptable?):
assert top_k_frequent([1, 1, 1, 2, 2, 3], 2) == [1, 2]
assert top_k_frequent([7], 1) == [7]
assert set(top_k_frequent([1, 2], 2)) == {1, 2} # tie, order unspecified
assert top_k_frequent([], 0) == []
The three selection approaches, and when each one wins:
| Approach | Time | Space | Reach for it when |
|---|---|---|---|
| Full sort by count | O(n log n) | O(n) | k is close to n, or you want the full ranking anyway |
| Min-heap of size k | O(n log k) | O(k) | Default. k is much smaller than n (top 10 of 10M) |
| Bucket by frequency | O(n) | O(n) | Frequencies are bounded and you want linear time |
What interviewers probe next (1) Deterministic tie-breaking? Change the key to (count, value) or (count, -first_seen_index), and note that the requirement should come from the user, not from you. (2) Streaming, can't hold all counts? Honest answer first: exact top-K over an unbounded stream needs all counts; then name Count-Min Sketch / lossy counting as approximations, one sentence each, don't derive them. (3) Top-K per group (per hour, per user): dict of Counters, then per-group nlargest; this is the bridge to the log-parser question and saying so shows you see the pattern. (4) Why not Counter.most_common(k)? It's fine: it does sort-or-heap internally; knowing it exists is a plus, knowing its cost is a bigger plus.
Common mistakes Sorting the entire count table when k is tiny and saying nothing about it: the answer "sort works, heap is better when k is much smaller than n" costs one sentence. Building a max-heap of all n items (O(n) memory) when a size-k min-heap was the point. Hand-implementing heap mechanics badly under time pressure instead of using heapq's batteries. And forgetting that ties exist until a test fails: clarifying tie semantics up front is the cheap, senior-looking move.