10 Priority Queue Interview Questions and Answers

Priority queues are a fundamental data structure in computer science, essential for efficiently managing tasks that need to be processed in a specific order. They are widely used in various applications, including operating systems for task scheduling, network routing algorithms, and simulation systems. Understanding how priority queues work and their implementation can significantly enhance your problem-solving skills and algorithmic thinking.

This article provides a curated selection of priority queue interview questions designed to test and improve your understanding of this critical data structure. By working through these questions, you will gain deeper insights into priority queue operations, their complexities, and practical applications, preparing you to tackle related challenges in technical interviews.

Priority Queue Interview Questions and Answers

1. Explain the basic concept of a Priority Queue and its common use cases.

A Priority Queue is an abstract data type that processes elements based on their priority rather than their order in the queue. Elements with higher priority are processed before those with lower priority. Common use cases include task scheduling, graph algorithms like Dijkstra’s and A*, and event simulation. Here’s a simple Python implementation using the heapq module:

import heapq

class PriorityQueue:
    def __init__(self):
        self._queue = []
        self._index = 0

    def push(self, item, priority):
        heapq.heappush(self._queue, (-priority, self._index, item))
        self._index += 1

    def pop(self):
        return heapq.heappop(self._queue)[-1]

pq = PriorityQueue()
pq.push("task1", 1)
pq.push("task2", 5)
pq.push("task3", 3)

print(pq.pop())  # Output: task2
print(pq.pop())  # Output: task3
print(pq.pop())  # Output: task1

2. What are the time complexities for insertion, deletion, and access operations in a Priority Queue implemented with a binary heap?

In a binary heap implementation of a priority queue, the time complexities are as follows:

• Insertion: O(log n) – The element is added to the end and “bubbled up” to maintain the heap property.
• Deletion: O(log n) – The root is removed, replaced with the last element, and “bubbled down” to restore the heap property.
• Access: O(1) – The highest priority element is at the root, allowing constant time access.

3. Write a function to merge two Priority Queues. Assume they are both implemented as Min-Heaps.

To merge two Min-Heaps, extract all elements from both heaps and insert them into a new Min-Heap. Here’s a Python example:

import heapq

def merge_priority_queues(heap1, heap2):
    merged_heap = []
    for element in heap1:
        heapq.heappush(merged_heap, element)
    for element in heap2:
        heapq.heappush(merged_heap, element)
    return merged_heap

heap1 = [1, 3, 5]
heap2 = [2, 4, 6]

merged_heap = merge_priority_queues(heap1, heap2)
print(merged_heap)
# Output: [1, 2, 3, 4, 5, 6]

4. Explain how a Fibonacci Heap can be used to implement a Priority Queue and discuss its advantages.

A Fibonacci Heap is a collection of trees satisfying the minimum-heap property, offering efficient amortized time complexities for various operations. Key operations include:

• Insertion: O(1) amortized time
• Find minimum: O(1) time
• Union: O(1) amortized time
• Decrease key: O(1) amortized time
• Delete minimum: O(log n) amortized time

Advantages include efficient decrease-key operations and low amortized time complexities, making Fibonacci Heaps suitable for algorithms like Dijkstra’s and Prim’s.

5. Write a function to decrease the key of an element in a Min-Heap.

To decrease the key of an element in a Min-Heap, update the key and move the element up the tree until the Min-Heap property is satisfied. Here’s an example:

def decrease_key(heap, index, new_key):
    if new_key > heap[index]:
        raise ValueError("New key is greater than the current key")
    
    heap[index] = new_key
    while index > 0 and heap[(index - 1) // 2] > heap[index]:
        parent = (index - 1) // 2
        heap[index], heap[parent] = heap[parent], heap[index]
        index = parent

# Example usage
heap = [1, 3, 6, 5, 9, 8]
decrease_key(heap, 4, 2)
print(heap)  # Output: [1, 3, 6, 5, 2, 8]

6. Explain the role of Priority Queues in Dijkstra’s algorithm.

Dijkstra’s algorithm uses a priority queue to manage and retrieve the next node with the smallest tentative distance, ensuring the shortest path is extended first. Here’s a Python example using the heapq module:

import heapq

def dijkstra(graph, start):
    priority_queue = []
    heapq.heappush(priority_queue, (0, start))
    distances = {node: float('inf') for node in graph}
    distances[start] = 0

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        if current_distance > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

print(dijkstra(graph, 'A'))
# {'A': 0, 'B': 1, 'C': 3, 'D': 4}

7. Design a concurrent Priority Queue that supports thread-safe operations. Provide a high-level overview and some pseudocode.

A concurrent priority queue allows multiple threads to perform operations in a thread-safe manner. One approach is to use a heap-based priority queue with a lock. Here’s a high-level overview and pseudocode:

• Use a heap to maintain priority queue properties.
• Use a lock to synchronize access to the heap.
• Implement thread-safe methods for insertion and deletion.

Pseudocode:

class ConcurrentPriorityQueue:
    def __init__(self):
        self.heap = []
        self.lock = Lock()

    def insert(self, item):
        with self.lock:
            heapq.heappush(self.heap, item)

    def delete_min(self):
        with self.lock:
            if self.heap:
                return heapq.heappop(self.heap)
            else:
                return None

8. Describe how a Priority Queue can be implemented using a linked list.

A priority queue can be implemented using a linked list by maintaining the list in a sorted order based on priority. Here’s an example in Python:

class Node:
    def __init__(self, data, priority):
        self.data = data
        self.priority = priority
        self.next = None

class PriorityQueue:
    def __init__(self):
        self.head = None

    def insert(self, data, priority):
        new_node = Node(data, priority)
        if not self.head or self.head.priority < priority:
            new_node.next = self.head
            self.head = new_node
        else:
            current = self.head
            while current.next and current.next.priority >= priority:
                current = current.next
            new_node.next = current.next
            current.next = new_node

    def delete(self):
        if self.head:
            self.head = self.head.next

# Example usage
pq = PriorityQueue()
pq.insert('task1', 1)
pq.insert('task2', 3)
pq.insert('task3', 2)

while pq.head:
    print(pq.head.data)
    pq.delete()

9. Explain the amortized time complexity of operations in a Fibonacci Heap.

The amortized time complexity of operations in a Fibonacci Heap is:

• Insert: O(1) – Adding a new element is done in constant time.
• Find Minimum: O(1) – The minimum element is always at the root.
• Union (Meld): O(1) – Merging two heaps is done by concatenating their root lists.
• Extract Minimum: O(log n) – Involves removing the root and consolidating the trees.
• Decrease Key: O(1) – Done in constant time, with potential cascading cuts.
• Delete: O(log n) – Decreasing the key to negative infinity and extracting the minimum.

These complexities are achieved through lazy operations and potential functions, ensuring low average costs over a sequence of operations.

10. Write a function to find the k-th largest element in a stream of numbers using a Priority Queue.

To find the k-th largest element in a stream of numbers using a priority queue, use a min-heap of size k. Here’s a Python implementation:

import heapq

class KthLargest:
    def __init__(self, k, nums):
        self.k = k
        self.min_heap = nums
        heapq.heapify(self.min_heap)
        while len(self.min_heap) > k:
            heapq.heappop(self.min_heap)

    def add(self, val):
        if len(self.min_heap) < self.k:
            heapq.heappush(self.min_heap, val)
        elif val > self.min_heap[0]:
            heapq.heapreplace(self.min_heap, val)
        return self.min_heap[0]

# Example usage:
kth_largest = KthLargest(3, [4, 5, 8, 2])
print(kth_largest.add(3))  # returns 4
print(kth_largest.add(5))  # returns 5
print(kth_largest.add(10)) # returns 5
print(kth_largest.add(9))  # returns 8
print(kth_largest.add(4))  # returns 8