Top 6 Priority queue Interview Questions
Browse 6 real-world technical and behavioral interview questions about Priority queue. Review scenarios, edge cases, and architectural best practices.
Design an in-memory job scheduler that runs one-off, delayed and recurring jobs. Write the core classes.
An in-memory job scheduler keeps one queue ordered by next run time, such as a DelayQueue, and one dispatcher thread that hands due entries to a worker pool. Recurring jobs are re-queued after each run, cancellation is a generation check on dequeue, and missed runs need a stated skip or catch-up policy.
Find the cheapest route between two nodes in a weighted directed graph. Then tell me what breaks if one edge has a negative weight.
Dijkstra fails with negative edges because it finalises the current cheapest node under the assumption that no later edge can reduce it. Use Bellman-Ford when negative edges are possible, and reject graphs with negative cycles. It also connects shortest paths to the point an interviewer is testing.
You are handed k sorted lists and asked for one sorted list. What is wrong with concatenating and sorting?
Nothing about correctness - it works. It throws away the sortedness you were given and pays O of N log N to rebuild it, where merging costs O of N log k, and it requires every element resident at once where a merge requires k. On lists that arrive as streams the second objection is the one that disqualifies it outright.
Numbers arrive one at a time and after each one you must answer what the Kth largest so far is. What do you keep, and what do you deliberately throw away?
Keep a min-heap holding exactly the K largest values seen. Its root is the answer, so the query is a read rather than a search, and every value smaller than that root is discarded the moment it arrives. What you give up is the ability to answer for any K larger than the one you chose, which is why the first thing to establish is whether K is fixed.
Numbers arrive one at a time and after each one I want the running median. How would you keep it?
Split the values across a max-heap of the lower half and a min-heap of the upper half, so the median is read off one or both tops. Balancing by size alone is what breaks it: a new value has to enter through the heap it belongs to by value and be transferred across, never pushed into whichever heap is currently smaller.
Return the k most frequent elements from a large stream of values. Why not just sort by frequency?
Count occurrences, then push counts through a min-heap capped at size k, evicting the smallest whenever the heap overflows. That is O(n log k) rather than the O(n log n) of a full sort, it needs only k items resident at once, and it works on a stream you cannot re-read.