Heaps and Priority Queues Questions

Binary heaps and priority queues as data structures: min-heap and max-heap, array layout, sift-up and sift-down, push/pop/peek costs, build-heap (heapify) in O(n), and indexed heaps with decrease-key versus lazy deletion of stale entries. Covers the problems where a heap is the intended tool: top-K and kth largest or smallest selection (including over a one-pass stream and under inserts and deletes), sorting an array whose elements are at most k places out of order with a window heap, the two-heap pattern for running and sliding-window medians (invariants, rebalancing, lazy deletion, testing, and extensions to percentiles, weighted medians, custom orderings and merging structures), k-way merge of sorted lists, arrays, files or streams with bounded memory, scheduling by priority with cancellation and reprioritisation, stable priority queues with tie-breaking, and implementing a heap or priority queue with a language library such as heapq or PriorityQueue (including max-heap behaviour from a min-heap). Boundary: graph shortest-path algorithms, approximate quantile sketches, production streaming-system design, and heapsort and quickselect as sorting and selection algorithms are covered elsewhere.

MediumTechnical
79 practiced

Implement a function in JavaScript to find the kth most frequent element in an array of integers. Provide a solution optimized for average-case time complexity better than O(n log n) where n is array length. State assumptions and complexity.

EasyTechnical
133 practiced

Python's heapq only provides a min-heap. How do you get max-heap behaviour from it, and what pitfalls should you watch for with floats, ties, and custom objects? Show a push and pop.

MediumTechnical
80 practiced

You have written a two-heap running median. How would you test it? Describe the unit tests, the edge cases that tend to break it, how you would compare it against a simple brute-force median on random streams, and how you would check its invariants after every insertion.

EasyTechnical
70 practiced

Write a Python function that returns the k largest values from a stream of numbers, given as a generator you can read only once, in descending order. Use O(k) extra memory and O(n log k) time, and do not store the whole stream. Explain why a min-heap of size k is the right tool and what happens to each incoming value.

MediumTechnical
70 practiced

Given a stream of numbers and an integer k, maintain the kth smallest element seen so far after each new number. Which heap would you keep, what size, and what do insert and query cost? Implement it.

Unlock Full Question Bank

Get access to all 15 Heaps and Priority Queues interview questions and detailed answers.

Sign in to Continue

Join thousands of developers preparing for their dream job.