Heaps And Selection Algorithms
Asked of: Machine Learning Engineer
Last updated

What's being tested
Heap-based selection and sorted-structure traversal: finding top-k, kth, or median-like elements without fully sorting or materializing all candidates. Interviewers probe whether you can exploit sorted inputs, bound memory to O(k), and reason clearly about duplicates, negative values, and boundary cases.
Patterns & templates
-
Max-heap for k smallest — scan
nvalues, keep heap sizek; use negated values in Python;O(n log k)time,O(k)space. -
Min-heap k-way merge — push one head per sorted list/row, repeatedly
heappop; complexityO(k log m)formsources. -
Best-first search over pair sums — start at
(0,0), push neighbors(i+1,j)and(i,j+1); usevisitedto avoid duplicates;O(k log k). -
Sorted matrix selection — either min-heap over rows,
O(k log n), or value-space binary search with count<= mid,O(n log range). -
Quickselect — average
O(n)for kth element when input is unsorted; handle equal pivots with 3-way partitioning. -
Median of two sorted arrays — binary search partition, not heap; target left size
(m+n+1)//2, checkmaxLeft <= minRight. -
Tie and duplicate handling — duplicate values may be valid outputs, but duplicate heap states like
(i,j)should usually be suppressed.
Common pitfalls
Pitfall: Generating all pair sums or flattening a matrix is usually
O(nm log nm)orO(n^2 log n)and misses the intended selection pattern.
Pitfall: Confusing “k smallest elements” with “kth smallest element”; one returns a collection, the other returns a single rank statistic.
Pitfall: Forgetting
k == 0,k > n, empty arrays, duplicate values, and negative numbers leads to brittle code even if the core heap idea is correct.
Practice these
The practice cards below cover the canonical variants — solve all of them and time yourself.
Featured in interview prep guides
Practice questions
- Solve Three Algorithmic ProblemsMeta · Machine Learning Engineer · Onsite · hard
- Find kth smallest pair sum with heapsMeta · Machine Learning Engineer · Onsite · Medium
- Return k smallest elements using heapMeta · Machine Learning Engineer · Onsite · Medium
- Find kth smallest in sorted matrixMeta · Machine Learning Engineer · Onsite · Medium
- Solve matrix components, median, and traversalsMeta · Machine Learning Engineer · Technical Screen · Medium
Related concepts
- Heaps, Top-K, And Streaming SelectionCoding & Algorithms
- Heaps, Priority Queues, and Top-K SelectionCoding & Algorithms
- Top-K Selection, Heaps, And RankingCoding & Algorithms
- Greedy, Heaps, And Scheduling OptimizationCoding & Algorithms
- Array Search, Selection, And Dynamic ProgrammingCoding & Algorithms
- Top-K, Heaps, Quickselect, And Frequency AnalysisCoding & Algorithms