MySmartCoPilot
Ask Passes Your pass 7 days left 1 day left Last day

Your country

Tools that support it use your country for local currency, number formats, units and paper size. Your choice is saved only in this browser.

Data Structures & Algorithms (DSA) Module 10

Heaps and priority queues interview questions

Interview questions on heaps and priority queues: short warm-ups, then what each harder question tests, the first step of a good answer and its follow-ups.

19 questions: 5 warm-ups and 14 with model answers · Levels: Fresher to staff

Warm-up questions

Short questions with short answers, each answered in full.

  1. Fresher to mid

    Why is a binary heap stored in an array instead of in nodes with pointers?

    Answered in the lesson Binary heaps: the heap property in an array

  2. Fresher

    Where is the largest item of a min-heap, and how long does it take to find it?

    Answered in the lesson Binary heaps: the heap property in an array

  3. Fresher to mid

    In bottom-up heapify, why does the loop run from index n // 2 − 1 down to 0, and what goes wrong if it runs from 0 upwards?

    Answered in the lesson Heapify and heapsort: building a heap in O(n)

  4. Fresher to mid

    What is the difference between a priority queue and a heap?

    Answered in the lesson Priority queues: records, ties and decrease-key

  5. Mid to senior

    What does an indexed priority queue add to a binary heap, and what does it cost?

    Answered in the lesson Indexed, d-ary and Fibonacci heaps

Questions with model answers

What each question tests, the first step of a good answer and the follow-ups to expect.

  1. Fresher to mid

    A job scheduler receives 100,000 jobs a second and always runs the most urgent one next; about 50,000 jobs wait at any moment. A colleague proposes a sorted array instead of a binary heap, since both show the most urgent job in O(1). Compare the two with numbers.

    What it tests
    Turning big-O into work per second, seeing that a sorted array pays O(n) moves per insert, and knowing when that cost is still acceptable.
    First step
    Count the work per job for each structure. A heap push or pop walks at most about log₂ 50,000 ≈ 16 levels. A sorted-array insert finds its place by binary search but then shifts every job after that place, about 25,000 on average. Multiply both by 100,000 jobs a second.
    Follow-ups

    From the lesson Binary heaps: the heap property in an array

    Opening the model answers with your pass…

    Model answers open with any MySmartCoPilot pass.

    • Pro pass · 1 week₹79$2.99
    • 30 days₹179$5.99
    • 1 year₹1,699$45

    One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

    Choose a passI have a licence key

    It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  2. Fresher to mid

    A hand-written min-heap passes its unit tests, but in production pop sometimes returns the second-smallest item. Its sift-down swaps with the left child when that child is smaller than the item, and otherwise with the right child when that one is smaller. Find an input that breaks it, and say how you would catch such bugs.

    What it tests
    Reasoning from the heap property to a counterexample, and testing heaps against a trusted reference on every short input.
    First step
    Find the case the rule gets wrong: both children are smaller than the item, and the right child is the smaller of the two. Swapping with the left child then puts a larger item above a smaller one. Build the smallest heap where a pop meets that situation.
    Follow-ups

    From the lesson Binary heaps: the heap property in an array

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  3. Mid to senior

    A microcontroller must sort 50,000 sensor records of 16 bytes in place, with 8 KB of spare RAM, and the control loop needs a guaranteed worst-case time. Quicksort, merge sort or heapsort: which do you choose, and how many comparisons do you budget for?

    What it tests
    Matching worst-case time, extra memory and stack depth to hard limits, and estimating comparisons for n = 50,000.
    First step
    Write down what each sort needs beyond the array: merge sort a buffer of n records, 800 KB here; quicksort a recursion stack and good pivots, with O(n²) as its worst case; heapsort O(1) extra memory and O(n log n) on every input. Then turn heapsort's bound into a comparison budget.
    Follow-ups

    From the lesson Heapify and heapsort: building a heap in O(n)

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  4. Mid to senior

    A game keeps 1,000,000 scores in an array and must list the top 100, in order, after each nightly batch. You may rearrange the array. Estimate the comparisons of heapify followed by 100 pops against a full sort, and say which you would ship.

    What it tests
    Using the linear cost of heapify, counting k pops, and comparing with n log n sorting and with a heap of size k.
    First step
    Heapify the million scores into a max-heap: fewer than 2n = 2 × 10⁶ comparisons. Each pop costs at most about 2 log₂ n ≈ 40 comparisons, so 100 pops add about 4,000. Then estimate a full sort, about n log₂ n ≈ 2 × 10⁷.
    Follow-ups

    From the lesson Heapify and heapsort: building a heap in O(n)

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 2 minutes

  5. Mid to senior

    A payroll job heapsorts 10 million employee records by salary, but auditors require employees with equal salaries to stay in employee-ID order, the order of the input file. What goes wrong, and which fixes would you consider, with their extra memory?

    What it tests
    Knowing that heapsort is unstable and why, and weighing fixes: a composite key, a stable sort and its buffer, with memory estimates.
    First step
    Say why heapsort reorders equal keys: the first extraction swaps the root with the last item, which can move a record past others with the same salary. Then notice that the input order is employee-ID order, so the ID already in every record can break the ties.
    Follow-ups

    From the lesson Heapify and heapsort: building a heap in O(n)

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 2 minutes

  6. Mid to senior

    A ride-hailing dispatcher keeps about 200,000 waiting requests in a binary heap ordered by waiting time, and 30 % of requests are cancelled before a driver accepts them. Compare deleting cancelled requests from the heap with lazy deletion: the cost per cancel, the memory, and when the heap must be rebuilt.

    What it tests
    Costing deletion from a heap with and without an index, the memory growth of lazy deletion, and a compaction rule with its amortised cost.
    First step
    Name what each approach must do. Deleting from a plain heap first has to find the request, a scan of up to 200,000 entries, before an O(log n) repair. Lazy deletion marks the request cancelled in O(1) and leaves its entry until it reaches the top. Then estimate how many dead entries can pile up.
    Follow-ups

    From the lesson Priority queues: records, ties and decrease-key

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 2 minutes

  7. Fresher to mid

    A Java job scheduler orders its queue with comparingInt on the priority, then thenComparingLong on the submission time, and reversed() called last. Higher priority should run first and, among equal priorities, the job submitted first. Users report that equal-priority jobs run newest first. Explain the bug, fix it and describe a test that would have caught it.

    What it tests
    Reading comparator chains, knowing that reversed() reverses the whole comparator built so far, and writing a test with ties.
    First step
    Work out what reversed() applies to. It is called on the comparator built so far, priority and then submission time, so it reverses both keys: higher priority first, as wanted, but also later submission first, which was not. Rewrite the chain so that only the priority key is reversed.
    Follow-ups

    From the lesson Priority queues: records, ties and decrease-key

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 2 minutes

  8. Senior to staff

    A live game leaderboard holds 2 million players, shows the top 10 at all times and receives 50,000 score changes a second for any player. Would you use a binary heap with lazy deletion, an indexed heap or a balanced search tree? Defend your choice with numbers.

    What it tests
    Matching the operation mix to a structure: arbitrary updates, reading the top ten, memory per player and the growth of stale entries.
    First step
    List the operations and their rates: 50,000 updates of arbitrary players a second, and frequent reads of the top 10. Then cost each structure: what one update costs, how the top 10 is read without destroying the queue, and how memory behaves after an hour of updates.
    Follow-ups

    From the lesson Priority queues: records, ties and decrease-key

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  9. Mid to senior

    A stream of 10⁸ hashtag events contains 5 × 10⁶ distinct hashtags. Every hour you must report the 100 most used hashtags so far, on a machine with 1 GB of memory. What do you keep in memory, which heap do you use, and what does each report cost?

    What it tests
    Separating counting from selection, sizing a hash map, using a min-heap of size k for the top 100, and estimating time and memory.
    First step
    Split the job in two, counting and choosing. Counting needs one counter per distinct hashtag, so estimate the memory of a map with 5 × 10⁶ entries. Choosing the top 100 is then a top-k problem over 5 × 10⁶ counts, not over 10⁸ events.
    Follow-ups

    From the lesson Heap applications: top-k, merging, running median

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 2 minutes

  10. Senior to staff

    A monitoring service must show the median latency of the last 10,000 requests, updated on every request, at 50,000 requests a second. Two heaps handle a stream that only grows. What changes when old requests leave the window, and what does each update cost?

    What it tests
    Extending the two-heap median to deletions with lazy deletion and size bookkeeping, or choosing another order-statistic structure, and costing the updates.
    First step
    Note what the window adds: every new request also removes the request 10,000 places back, which can sit anywhere inside either heap. Decide how to delete it: mark it for lazy deletion and count the valid items of each half, or use a structure that can delete any value in O(log n).
    Follow-ups

    From the lesson Heap applications: top-k, merging, running median

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  11. Senior to staff

    5,000 sensors each send readings in time order, and a service must merge them into one time-ordered stream with at most 2 seconds of delay. Some sensors go quiet for minutes. What does your heap hold, how do you avoid waiting for a quiet sensor, and what does each reading cost?

    What it tests
    Running a k-way merge on live streams: the heap of fronts, watermarks or heartbeats for quiet inputs, a bounded delay and the cost per reading.
    First step
    Start from the offline merge: a heap holding the next reading of each sensor. Then find where it blocks: it may emit the smallest reading only when no sensor can still send something earlier, and a quiet sensor never says so. Decide what each sensor can promise about its future readings.
    Follow-ups

    From the lesson Heap applications: top-k, merging, running median

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 3 minutes

  12. Senior to staff

    You run Dijkstra's algorithm on a road network with 2 × 10⁷ vertices and 5 × 10⁷ edges, many times a day. Lazy deletion, an indexed binary heap, an indexed 4-ary heap or a Fibonacci heap: which do you choose? Defend it with estimates of memory and work.

    What it tests
    Estimating heap sizes and operation counts for Dijkstra on a sparse graph, and weighing measured behaviour against asymptotic bounds.
    First step
    Estimate the operations first: V = 2 × 10⁷ pops and at most E = 5 × 10⁷ decrease-keys, though in practice far fewer edges improve a distance. Then cost each queue in entries held and comparisons, starting with the worst case of lazy deletion, one entry per edge.
    Follow-ups

    From the lesson Indexed, d-ary and Fibonacci heaps

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 2 minutes

  13. Senior to staff

    A discrete-event simulator pushes about 8 future events for every event it pops, and its queue holds about 10⁶ events. Which d would you choose for a d-ary heap, and why? Show the arithmetic of comparisons per popped event.

    What it tests
    Building a cost model of a d-ary heap from the ratio of pushes to pops, solving it for d, and knowing what the model leaves out.
    First step
    Write the cost per popped event: one pop of about d·log_d n comparisons plus 8 pushes of at most log_d n each, so (d + 8)·log_d n with n = 10⁶. Evaluate it for d = 2, 4, 8 and 16 before thinking about caches.
    Follow-ups

    From the lesson Indexed, d-ary and Fibonacci heaps

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 2 minutes

  14. Senior to staff

    A teammate wants to switch the route planner's Dijkstra queue to a Fibonacci heap, because the bound drops from O((V + E) log V) to O(E + V log V). When is that argument right, and what would you measure before switching?

    What it tests
    Separating asymptotic bounds from constant factors, knowing when decrease-keys dominate, and designing a fair benchmark.
    First step
    Compare the bounds term by term. Both pay about V log V for the pops; the Fibonacci heap saves only on decrease-keys, E log V against E. So the switch can help only when decrease-keys are a large share of the work, which depends on how many edges actually improve a distance.
    Follow-ups

    From the lesson Indexed, d-ary and Fibonacci heaps

    In the answer:

    • Model answer
    • Follow-up answers
    • Common mistakes
    • Rubric
    • Variants
    • about 2 minutes

All Data Structures & Algorithms (DSA) interview questions · The Data Structures & Algorithms (DSA) track