Micro-questions over the top-k pattern. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. Why it exists
1. Top 10 from a million items — what does sorting cost?
Answer
time and space — and you only need 10 of the million.
2. State the better idea.
Answer
Maintain a collection of the 10 largest seen so far. If a new item beats the smallest in the collection, replace it. time, space.
3. Define the pattern.
Answer
Find the largest (or smallest) elements without fully sorting. A heap is the tool that makes this cheaper than sorting everything just to look at the top of it.
B. The counterintuitive part
4. To find the largest, which heap do you use?
Answer
A min-heap of size .
5. Why is that the right way round?
Answer
The root is the smallest of your current top- — so it is exactly the thing to compare against and evict. If a new element beats the root, it is bigger than the current worst of your top-.
6. To find the smallest?
Answer
A max-heap of size — mirror image. In Python, negate on the way in and out.
7. Write the loop.
Answer
heap = []
for num in nums:
heapq.heappush(heap, num)
if len(heap) > k:
heapq.heappop(heap)
return heap[0] # k-th largest8. Trace [3,2,1,5,6,4], .
Answer
[3] → [2,3] → push 1, pop 1 → [2,3] → push 5, pop 2 → [3,5] → push 6, pop 3 → [5,6] → push 4, pop 4 → [5,6]. Root = 5, the 2nd largest.
9. What does the root hold at the end?
Answer
The -th largest element overall, and the heap holds the top (in no particular order).
C. Costs
10. Why is it rather than ?
Answer
insertions and removals, each because the heap never grows past size .
11. When does it beat sorting?
Answer
Whenever is meaningfully smaller than .
12. When does sorting win instead?
Answer
When is close to — sorting has better cache locality and lower constant overhead.
D. Extensions
13. What is quickselect, and what does it cost?
Answer
A quicksort-style partition that recurses into only the side containing the -th element. Expected .
14. Why only one side?
Answer
After partitioning, the pivot is in its final position — so you know which side the -th element is on and can discard the other entirely.
15. What is quickselect’s worst case, and what fixes it?
Answer
with bad pivots. Median of medians — take medians of groups of 5, recursively find the median of those, and use it as pivot — guarantees worst case.
16. Quickselect is and the heap is . Why use the heap?
Answer
Quickselect mutates the array and needs it all in memory; the heap is a single streaming pass with space, so it works on data that never fits at once.
17. What does k-most-frequent need in addition?
Answer
A hash map to count occurrences first, then the heap over the (count, item) pairs.
18. Summarise the pattern in one sentence.
Answer
Keep a size- heap ordered the opposite way to what you are looking for, so the root is always the weakest member and the thing to evict.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Top K Elements — the pattern
- Heaps — Question Bank
- Quicksort — Question Bank — where quickselect’s partition comes from
Software engineering
Infrastructure & security
Computer science
Hardware & engineering