Coding

Heap-based hard problem

Asked at

Google

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

Stuck? Show a way to structure it+

01Clarify whether the result needs a minimum, maximum, top k, or repeated extraction
02Choose min-heap or max-heap based on the element that should be evicted
03State the heap-order invariant and what each entry stores
04Bound heap size when only k candidates are needed
05Handle ties and stale entries explicitly

Reference answer

For “Heap-based hard problem”, identify the priority and whether work arrives as a stream. A heap is appropriate when you repeatedly need the next best item, not merely a one-time sort. Use a min-heap to keep the largest k values by evicting the smallest when size exceeds k; use a max-heap when repeatedly extracting the current maximum. In graph or scheduling variants, store enough metadata to detect stale entries and tie-break deterministically. State the invariant precisely: the root is always the least or greatest live candidate according to the comparator. Do not confuse a heap with fully sorted order; only the root is globally ordered. Test k equal to zero or input length, duplicate priorities, negative values, and ties. Building can be O(n), while each insertion or removal is O(log k) or O(log n), depending on the bounded size.

Then expect these follow-ups

What constraint would change your chosen approach?
Tests: constraint adaptation
How would you test the edge cases before implementation?
Tests: implementation extension

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question