Skip to content
Tech Interview Prep
Technical interview guide

Heaps / Priority Queues

A tree-shaped structure that keeps the min (or max) element accessible in O(1), with O(log n) insert and remove.

Read
42 min
Practice MCQs
25
Interview Q&A
25
Edition
v7
Editorial status
Reviewed

Scope: Language-neutral, with library behaviour cited from CPython 3.14 heapq, the C++ standard containers, and java.util as of Java 21.

Curated: · Written: · Reviewed:

25 questions

MCQ-4A job scheduler stores pending jobs in a binary min-heap backed by the array `[4, 9, 7, 15, 11, 10, 8]`, where each value is the job's priority. A new engineer reads the array and asks what `extract-min` returns and whether the array is sorted. Which statement is correct?
MCQ-2A latency monitor keeps the last 7 request latencies in a Python min-heap `h = [12, 19, 14, 31, 25, 22, 17]`. An engineer needs the fourth-smallest latency and reads `h[3]`, which returns 31. Which statement about that read is correct?
MCQ-3A max-heap of seven elements sits in a zero-based array: [50, 30, 40, 10, 20, 35, 38]. A sift-down is called on index 1, but the routine computes child indices as left = 2*i and right = 2*i + 1. Which array does the routine leave behind?
MCQ-20A binary min-heap of n elements sits in a zero-based array. Two repairs are queued: (a) an insert appends the new element at index n-1, and (b) the root's key is overwritten with a larger value. Which pair of operations restores the heap property, and what is each one's worst-case comparison count?
MCQ-5A service rebuilds a min-heap over a batch of n = 2^20 events on every flush. Version A calls heapq.heapify(list); version B pushes each event with heapq.heappush. Profiling shows A at ~40 ms and B at ~800 ms per flush. Which diagnosis fits these numbers?
MCQ-6A service keeps the 20 slowest requests in a rolling window. Each latency is pushed into a max-heap, and whenever the heap holds more than 20 entries the root is popped. After a day, the dashboard's "slowest 20" shows latencies between 3 and 8 ms, while the window's p99 is 240 ms. What is the defect?
MCQ-7A telemetry job reads 4,000,000 sensor readings from a socket that can be consumed only once, and must emit the 25 highest values in descending order. The process is capped at 64 KB of working memory. Which approach meets the requirement?
MCQ-25A metrics service receives 10^8 latency samples one at a time and must report the 100 slowest when the stream ends. The process has an 8 MB memory budget. Which approach returns the correct 100 within the budget?
MCQ-14A rate limiter pushes requests onto a heap as (priority, request_id) tuples, where request_id is a string. Three requests arrive and are pushed in this order: (1, "req-9"), (1, "req-10"), (1, "req-2"). All three share priority 1. In what order does the heap pop them?
MCQ-15A worker pushes (priority, task) pairs into one heapq and pops between pushes; priorities come from a handful of levels, so ties are common, and task is a plain payload object with no comparison methods. Pushes fail with TypeError: '<' not supported between instances of 'Task' and 'Task'. Which entry layout fixes the crash and still returns tied jobs in the order they were pushed?
MCQ-8A merge job combines 8 sorted run files (2,000,000 records total) with heapq, pushing (timestamp, record) where record is a dict. It runs until two records share a timestamp, then raises TypeError: '<' not supported between instances of 'dict' and 'dict'. Which change fixes it?
MCQ-1A Java service processes jobs by highest priority. Priorities are signed 32-bit integers and the full range is used, including `Integer.MIN_VALUE`. The code uses `PriorityQueue<Integer>` and stores `-priority` to make the min-heap behave as a max-heap: ```java PriorityQueue<Integer> pq = new PriorityQueue<>(); pq.add(-priority); ``` A job with priority `Integer.MIN_VALUE` is added. What does the heap do with it?
MCQ-9A latency monitor keeps a running median of request latencies with two heaps: ```python import heapq lo, hi = [], [] # lo: max-heap (values negated), hi: min-heap def add(v): if not lo or v <= -lo[0]: heapq.heappush(lo, -v) else: heapq.heappush(hi, v) def median(): if len(lo) > len(hi): return -lo[0] return (-lo[0] + hi[0]) / 2 ``` Latencies arrive in descending order: 10, 9, 8, ..., 1 ms. What does `median()` return after the tenth sample?
MCQ-18A log-ingest service buffers events in a min-heap priority queue, where a smaller priority number means the event is consumed sooner. CAPACITY is 3. An arriving event is inserted while the heap has room. When the heap is full, the service compares the incoming priority against the least urgent entry it currently holds, meaning the largest priority number: if the incoming event is more urgent, that entry is evicted and the new event is inserted; otherwise the incoming event is refused and the drop counter increments. Evictions are counted separately from drops. Priorities 5, 2, 7, 1, 9 arrive in that order and the consumer removes nothing during the burst. Which state does the heap hold when the burst ends?
MCQ-24A log-analysis job keeps the 500 slowest requests in a Python `heapq` min-heap. For each of 2 million incoming requests it must check whether that request's ID is already in the heap. Roughly how many comparisons does the batch of checks cost, and what is the right remedy?
MCQ-23Two consumer threads share a Python list `q` used as a heap via `heapq`, with no lock: ```python while True: if q: item = heapq.heappop(q) handle(item) ``` Under load, one thread dies with `IndexError: index out of range` raised inside `heappop`, on an iteration where the `if q:` test passed. What is the cause, and what fixes it?
MCQ-22A scheduler dispatches the pending job with the earliest deadline, accepts cancellations by job ID at any moment, and once a night walks every pending job in deadline order. Cancellations arrive at about the same rate as dispatches, and the pending set holds tens of thousands of jobs. Which structure fits?
MCQ-11Dijkstra runs from s over this directed graph with a binary min-heap and lazy deletion: every time a shorter path to a vertex is found it pushes a new (distance, vertex) entry, and on pop it skips any entry whose vertex is already finalised. s→a = 2, s→b = 10, a→b = 3, a→c = 20, b→c = 1, b→d = 4, c→d = 1. What is the largest number of entries the heap holds at any one time?
MCQ-12A service keeps a binary min-heap in which updates and cancellations use lazy deletion: a superseded entry is left in the array as a tombstone and a fresh copy is pushed for the new value, with no immediate sift-up or sift-down removal. N is the number of live items, M is the cumulative number of insertions including tombstones, and M >> N. Compared with an exact N-item heap that maintains an index map for in-place updates, how does lazy deletion change the cost of an extract-min?
MCQ-10A team runs Dijkstra on a road network with V = 100,000 vertices and E = 500,000 edges, all weights nonnegative. They use a binary heap and see about 10^7 heap operations per run. A teammate proposes replacing the heap with a linear scan over all vertices to find the next minimum, arguing the code is simpler. What does that change for this graph?
MCQ-17A routing service runs Dijkstra over a road network with V = 1.2M nodes and E = 2.9M edges (average degree ≈ 2.4). Swapping only the priority queue, the binary-heap build finishes in 8.4 s and the Fibonacci-heap build in 27 s; both return identical shortest-path trees. Which conclusion is correct?
MCQ-16How does increasing the branching factor d in a d-ary heap affect the asymptotic time complexities of insert and extract-min operations?
MCQ-13A team benchmarks in-place heapsort against quicksort on 64-bit integers. At N = 10^7 (an 80 MB array, larger than the 32 MB L3), heapsort takes 2.9 s and quicksort 1.1 s. Re-running with N small enough that the array fits in L2 narrows the gap to 1.2x, and instrumented comparison counts for the two algorithms stay within 15% of each other at every size. Which statement about heapsort's complexity and the cause of the remaining gap is correct?
MCQ-21A scheduler holds 2 million pending jobs in one binary min-heap keyed by deadline, guarded by a single mutex. Each of 48 worker threads loops: lock, pop the earliest-deadline job, unlock, run it. Throughput is 190k pops/s with 4 threads and 205k with 48, and profiling puts 71% of cycles in the mutex on the heap root. The contract allows a job to be dispatched ahead of another whose deadline is up to 50 ms earlier; beyond that, deadline order must hold. Which change is most likely to raise throughput while keeping that contract?
MCQ-19A single-core scheduler drains one strict-priority queue. High-priority jobs arrive every 2 ms and each runs 1.9 ms; low-priority jobs arrive every 100 ms and each runs 3 ms. High-priority arrivals are steady, and the oldest low-priority item's age has passed 4 hours. What does the arithmetic say, and what is the right change?