Queues Interview Questions & Tips
Understanding queues, a fundamental data structure, is crucial to preparing for technical interviews. Queues, designed around the FIFO (First-In, First-Out) principle, play an essential role in various real-world scenarios, from managing print jobs in a printer to handling requests in a web server. They facilitate operations in operating systems, network traffic management, and memory allocation, and they’re also integral to certain algorithms in data science and machine learning.
The key to acing technical interviews lies in not just understanding the theory behind queues but also being able to apply that knowledge practically. It sets the stage for impressive, comprehensive responses instead of just adequate answers. In the upcoming sections, we'll deep-dive into the concept of queues, their implementation, usage scenarios, and common pitfalls in interviews. We aim to equip you with the knowledge to tackle any queue-related questions in your interviews confidently.
What is a Queue?
You may not have realized it, but we interact daily with queues. Have you ever been to a coffee shop during rush hour? That's your real-world experience with a queue. The first person who arrives early (hopefully, after a good morning jog) gets their coffee first, and you, who hit the snooze button one too many times, must wait for your turn at the end. Just like in programming, nobody likes a queue jumper!
In technical terms, a queue is a collection of items we maintain in a specific order. Items are added (we call this 'enqueue') at one end - the 'rear', and removed ('dequeue') from the other end - the 'front', following the principle of "First In First Out" (FIFO).
Queue Compared to a Stack
Similar to a queue, a stack is also an abstract data type that stores a collection of elements. However, unlike a queue, a stack follows the LIFO (Last In First Out) principle – the last element added to the stack is the first to be removed. If a queue is like a line at a coffee shop, a stack is like a stack of plates. You can only add or remove plates from the top of the stack.
Queue Operations
A queue supports the following operations:
enqueue: Add an element to the end of the queuedequeue: Remove an element from the front of the queuepeek: Return the first element in the queue without removing itisEmpty: Check if the queue is emptysize: Return the number of elements in the queue
All of these operations are performed in constant time - O(1).
Queues in Different Programming Languages
Let's see how we can create and manipulate a queue in three programming languages - Java, Python, and JavaScript.
Java
Java provides a Queue interface that can be implemented using various classes like LinkedList, PriorityQueue, and ArrayDeque. For instance:
Queue<Integer> queue = new LinkedList<>();
queue.add(1); // enqueue
queue.remove(); // dequeue
queue.peek(); // peek
queue.isEmpty(); // check if the queue is empty
queue.size(); // get the queue size1Queue<Integer> queue = new LinkedList<>();
2queue.add(1); // enqueue
3queue.remove(); // dequeue
4queue.peek(); // peek
5queue.isEmpty(); // check if the queue is empty
6queue.size(); // get the queue sizeJava also provides the ArrayDeque class that can serve as a queue. LinkedList implements Queue as a doubly-linked list, and ArrayDeque uses a resizable array or circular buffer. While both are efficient, using ArrayDeque is often faster for queues as it does not have to maintain separate references for next and previous nodes like LinkedList, making it more memory efficient.
Python
In Python, the most recommended way to implement a queue is by using the built-in collections.deque data structure, which is designed to allow fast appends and pops from both ends. It is implemented with a doubly-linked list under the hood, providing efficient queue operations. Another option, though less commonly used, is Python's queue.Queue class, which is designed for multi-threading and includes locking semantics for concurrent producers and consumers.
from collections import deque
queue = deque()
queue.append('a') # enqueue
queue.append('b')
queue.append('c')
print(queue.popleft()) # dequeue, prints 'a'
1from collections import deque
2
3queue = deque()
4queue.append('a') # enqueue
5queue.append('b')
6queue.append('c')
7print(queue.popleft()) # dequeue, prints 'a'
8Though you can use a Python list to perform queue-like operations with append() and pop(0), it is not efficient because popping the first element requires shifting all other elements by one. Therefore, it's not recommended for queue implementations.
On the other hand, if you are working in a language that doesn't offer native queue support or you need to implement a queue for learning or specific customization purposes, you can do so using an array or a linked list.
JavaScript
JavaScript doesn't have a native queue implementation. So, similar to Python's list, you can use an array to implement a queue in JavaScript. However, it is not recommended for the same reason as Python - popping the first element requires shifting all other elements by one. This results in a time complexity of O(n) for dequeue operations, which is not ideal. However, if you are working with a few elements, this might not be a problem.
const queue = [];
queue.push('a'); // enqueue
queue.push('b');
queue.push('c');
queue.shift(); // dequeue, returns 'a'
1const queue = [];
2queue.push('a'); // enqueue
3queue.push('b');
4queue.push('c');
5queue.shift(); // dequeue, returns 'a'
6Array vs. Linked List Implementation
If you are working in a language that doesn't offer native queue support, or you need to implement a queue for learning or specific customization purposes, you can do so using an array or a linked list.
Array Implementation (Circular Buffer)
A simple way to implement a queue is by using a circular buffer technique with an array. The technique is an example of the "Two Pointers" approach often seen in interview questions.
This method treats the array as if it were connected end-to-end. Once the end of the array is reached, the next element to be inserted goes at the beginning of the array, thus forming a 'circle'. We use two pointers (one for the front and the other for the rear) to track where to enqueue and dequeue. When the queue is full, and we want to add more elements, we can either throw an error or resize the array. The resize operation is expensive, so it's better to use a linked list implementation if the size of the queue is unknown.
Linked List Implementation
A queue can also be implemented using a linked list, with the front of the queue represented by the head of the list and the rear of the queue represented by the tail of the list. Enqueue operations add elements to the end (tail), and dequeue operations remove elements from the start (head). Unlike the array-based implementation, linked list implementation doesn't require size definition at the onset, making it more memory efficient. However, it is not cache-friendly and can result in frequent memory allocation and deallocation, which can be expensive.
I would recommend reading this Stack Overflow thread, which provides a detailed discussion on implementing queues and stacks using arrays and linked lists.
When to Use Queues in Interviews
Queues can be handy in many types of problems in coding interviews. Below, we'll discuss the most common categories where queues are utilized:
Graph Algorithms (Breadth-First Search and Level Order Traversal)
Queues are fundamental for graph traversal algorithms, especially Breadth-First Search (BFS) and level order traversal of trees. Unlike Depth-First Search (DFS) that utilizes a stack (or recursion) for traversal, BFS specifically employs a queue. In a queue, the first element we add (enqueue) is the first one we remove (dequeue). This approach is ideal for BFS because it mirrors how BFS visits nodes: the first node discovered is the first one explored.
As BFS moves through each level, it uses a queue to keep track of the next nodes to visit. When it finishes with one node, it simply dequeues it. As it discovers new nodes, it enqueues them. This system ensures that BFS explores all nodes on one level before moving to the next, precisely the behavior we want.
Example: Given a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).
from collections import deque
def levelOrder(root):
if not root:
return []
# initialize a queue with the root node
result, queue = [], deque([root])
while queue:
level = []
for _ in range(len(queue)):
# pop the first element from the queue
node = queue.popleft()
level.append(node.val)
if node.left:
# append left child
queue.append(node.left)
if node.right:
# append right child
queue.append(node.right)
# append the current level list to the final result
result.append(level)
return result1from collections import deque
2def levelOrder(root):
3 if not root:
4 return []
5 # initialize a queue with the root node
6 result, queue = [], deque([root])
7 while queue:
8 level = []
9 for _ in range(len(queue)):
10 # pop the first element from the queue
11 node = queue.popleft()
12 level.append(node.val)
13 if node.left:
14 # append left child
15 queue.append(node.left)
16 if node.right:
17 # append right child
18 queue.append(node.right)
19 # append the current level list to the final result
20 result.append(level)
21 return resultUsing queues for BFS in this way is clean, efficient, and intuitive, demonstrating why this combination is so common in coding interviews.
Sliding Window Problems
In these problems, we are given an array or list of elements, and we need to find or calculate something among all contiguous subarrays of a given size. Here, a queue (or deque, i.e., double-ended queue) can efficiently keep track of the elements in the current window, adding new ones to the end and removing old ones from the front. For a more comprehensive understanding of sliding window problems using queues, please refer to our guide on sliding window questions.
Example: Given an array of integers and a number x, determine the smallest subarray with a sum greater than the given value.
from collections import deque
def smallest_subarray_with_sum(arr, target):
queue = deque()
min_length = float('inf')
current_sum = 0
for num in arr:
queue.append(num)
current_sum += num
while current_sum > target:
min_length = min(min_length, len(queue))
current_sum -= queue.popleft()
return min_length if min_length != float('inf') else -1
1from collections import deque
2
3def smallest_subarray_with_sum(arr, target):
4 queue = deque()
5 min_length = float('inf')
6 current_sum = 0
7
8 for num in arr:
9 queue.append(num)
10 current_sum += num
11
12 while current_sum > target:
13 min_length = min(min_length, len(queue))
14 current_sum -= queue.popleft()
15
16 return min_length if min_length != float('inf') else -1
17In this solution, we iterate over the array, maintain a running sum and continuously add numbers to a queue. When the sum exceeds the target, we remove elements from the front of the queue until it's no longer the case, keeping track of the smallest length of such a subarray. This approach uses O(n) time and O(n) space.
This problem can also be solved using a sliding window approach with two pointers, which does not require extra space for a queue and has a space complexity of O(1). This would be a more space-efficient solution, especially for larger inputs.
Advanced Queue Structures (Priority Queues)
Priority Queues are a type of queue where instead of being FIFO, elements are removed based on their priority. They are used in more complex algorithms like Dijkstra's and Heap Sort. Priority queues are often implemented using heaps where every enqueue, and dequeue operation takes O(log n) time. The element with the highest priority is always at the front of the queue.
Priority Queues Across Languages
The methods for implementing priority queues can differ across programming languages. In Python, the heapq library is a popular choice for creating binary heaps and, thus, implementing priority queues. This library provides functions like heapify to convert a regular list into a heap, heappush to add an element to the heap, and heappop to remove the smallest element from the heap.
Java, on the other hand, offers a PriorityQueue class, which provides similar functionality. It's part of Java's Collections Framework and can be conveniently used out of the box to handle heap-like structures.
JavaScript, however, does not have a built-in Priority Queue implementation. During interviews, candidates using JavaScript often simulate a priority queue for problem-solving. It's crucial to note this during the interview and clarify that your solution is simulating priority queue functionality, not using a native language feature.
Example: Given an array of integers, return the k smallest elements in the array.
In the following Python solution, we use a max heap to keep track of the k smallest elements. We iterate over the array and add the first k elements to the heap. For each subsequent element, we check if it is smaller than the maximum element in the heap. If so, we remove the maximum element and add the new element to the heap. In the end, we return the heap as a list.
import heapq
def k_smallest(nums, k):
# Create a max heap
heap = [-num for num in nums[:k]]
heapq.heapify(heap)
# For each number in the array
for num in nums[k:]:
# If the number is smaller than the maximum number in the heap
if -heap[0] > num:
# Remove the maximum number and insert the new number
heapq.heappop(heap)
heapq.heappush(heap, -num)
# The heap now contains the k smallest numbers, return them as a list
return [-num for num in heap]1import heapq
2
3def k_smallest(nums, k):
4 # Create a max heap
5 heap = [-num for num in nums[:k]]
6 heapq.heapify(heap)
7
8 # For each number in the array
9 for num in nums[k:]:
10 # If the number is smaller than the maximum number in the heap
11 if -heap[0] > num:
12 # Remove the maximum number and insert the new number
13 heapq.heappop(heap)
14 heapq.heappush(heap, -num)
15
16 # The heap now contains the k smallest numbers, return them as a list
17 return [-num for num in heap]In this example, heapify transforms the list into a heap in O(n) time. This operation is crucial to enable the efficient extraction of minimum elements (in the case of a min-heap) or maximum elements (in the case of a max-heap). Subsequent removal of the maximum element (heappop) and insertion of a new element (heappush) both take O(log k) time.
A naive solution to this problem would be to sort the array and return the first k elements. However, this would take O(n log n) time. We can solve this problem using a priority queue in O(n log k) time.
Queues in Multi-threaded Environments
Queues are often used in multi-threaded environments as a safe way to exchange data between threads. They are used to implement buffers, task queues, etc. The queue module in Python, provides the Queue class that is thread-safe.
Example: Implement a multi-threaded program where one thread generates data and puts it in a queue, and another thread takes data from the queue and processes it.
from queue import Queue
from threading import Thread
import time
# Producer function: generates data and puts it on a queue
def producer(q):
for i in range(5):
print('Produced:', i)
q.put(i)
time.sleep(1) # Simulates time taken to produce the data
q.put(None) # Adds poison pill to the queue to signal the consumer to stop
# Consumer function: consumes data from a queue
def consumer(q):
while True:
data = q.get()
if data is None: # If the poison pill is found, terminate the loop
break
print('Consumed:', data)
q = Queue()
t1 = Thread(target=producer, args=(q,))
t2 = Thread(target=consumer, args=(q,))
t1.start()
t2.start()
t1.join()
t2.join()1from queue import Queue
2from threading import Thread
3import time
4
5# Producer function: generates data and puts it on a queue
6def producer(q):
7 for i in range(5):
8 print('Produced:', i)
9 q.put(i)
10 time.sleep(1) # Simulates time taken to produce the data
11 q.put(None) # Adds poison pill to the queue to signal the consumer to stop
12
13# Consumer function: consumes data from a queue
14def consumer(q):
15 while True:
16 data = q.get()
17 if data is None: # If the poison pill is found, terminate the loop
18 break
19 print('Consumed:', data)
20
21q = Queue()
22
23t1 = Thread(target=producer, args=(q,))
24t2 = Thread(target=consumer, args=(q,))
25
26t1.start()
27t2.start()
28
29t1.join()
30t2.join()In this example, we create a queue and pass it to two threads. The producer thread generates data and puts it in the queue, while the consumer thread consumes data from the queue. The queue handles all the necessary locking to ensure multiple threads can safely add or remove items.
Queues in System Design Interviews
In system design interviews, we use queues to ensure reliable processing and sequencing of messages in distributed systems. Queues also play a role in asynchronous processing, load balancing, batch processing, and resilience against failure. For example, in designing a messaging app like WhatsApp, you could use a queue to hold messages for delivery, ensuring they are sent in the order they were created, even if the user is temporarily offline.
Many popular software solutions, such as RabbitMQ, Apache Kafka, Amazon SQS, and Redis, are used in the industry for queue management.
We have published a detailed guide on system design interviews. You can read more about queues and other system design concepts here.
Common Mistakes in Interviews Featuring Queues
Using an Array Like a Queue and Popping from the Front
While arrays can be used to implement a queue, using array methods such as shift (JavaScript), pop (Python) or remove (Java) to pop an item from the front can be inefficient. This is because such operations require shifting all elements to fill the gap, resulting in a time complexity of O(n).
let queue = [1, 2, 3, 4, 5];
queue.shift(); // removes the first element, but has to shift all other elements1let queue = [1, 2, 3, 4, 5];
2queue.shift(); // removes the first element, but has to shift all other elementsInstead, do the following:
Queue<Integer> queue = new LinkedList<>();
queue.add(1);
queue.add(2);
queue.add(3);
queue.add(4);
queue.add(5);
queue.remove(); // removes the first element in O(1) time1Queue<Integer> queue = new LinkedList<>();
2
3queue.add(1);
4queue.add(2);
5queue.add(3);
6queue.add(4);
7queue.add(5);
8queue.remove(); // removes the first element in O(1) timePlease note that JavaScript does not have a built-in queue data structure. You can use an array as a queue, but you should always say it upfront and mention that you know the performance implications. The alternative is implementing a custom queue class using a linked list.
Trying to Use Libraries Without Knowing the API Methods Well
Candidates often attempt to use library functions without understanding their underlying mechanisms. Knowing which methods are available and when to use them is important.
For example, in Java, when implementing queues, you must be aware of a few potential pitfalls or errors:
-
Queue is Empty: When a queue is empty, invoking
remove()throws aNoSuchElementException. To avoid this, usepoll()orpeek(), which returns null when the queue is empty. -
nullElements: In Java, you cannot add null to a queue (forArrayDequeandPriorityQueueimplementations). Trying to addnullthrows aNullPointerException.LinkedListimplementations allow null elements, but it's best to avoid them. -
Capacity Restrictions: If you're using a bounded queue implementation like
ArrayBlockingQueue, you must be careful about capacity restrictions. Theadd()method throws anIllegalStateExceptionwhen you try to add an element to a full queue. To avoid this, use theoffer()method, which simply returnsfalsewhen the queue is full.
Similarly, in Python, when a queue is empty, invoking popleft() throws an IndexError. To avoid this, check if the queue is empty with len before calling popleft().
In JavaScript, it's worth noting that there isn't a native heap data structure or priority queue implementation in the language. However, during an interview, you might be asked to solve problems as if there were. It can be challenging to pretend a working heap when unfamiliar with its interface. In such situations, you can refer to Python's heapq library or Java's PriorityQueue class to get an idea of the methods and behaviors a heap implementation might provide. For example, Python's heapq.heappush() to add an item, heapq.heappop() to remove and return the smallest item, and in Java's PriorityQueue, add() to insert elements, peek() to view the head element, poll() to remove and return the head element.
Not Knowing How to Implement a Queue from Scratch
Regardless of the language, understanding how to create a basic queue from scratch is a key skill. Some candidates might not be able to implement a queue without the help of built-in methods or classes. For example, a queue can be implemented from scratch in JavaScript using an object and two pointers (there could be other implementations as well).
class Queue {
constructor() {
this.storage = {};
this.head = 0;
this.tail = 0;
}
enqueue(item) {
this.storage[this.tail] = item;
this.tail++;
}
dequeue() {
let removed = this.storage[this.head];
delete this.storage[this.head];
this.head++;
return removed;
}
}
let queue = new Queue();
queue.enqueue("first");
queue.enqueue("second");
console.log(queue.dequeue()); // outputs "first"1class Queue {
2 constructor() {
3 this.storage = {};
4 this.head = 0;
5 this.tail = 0;
6 }
7
8 enqueue(item) {
9 this.storage[this.tail] = item;
10 this.tail++;
11 }
12
13 dequeue() {
14 let removed = this.storage[this.head];
15 delete this.storage[this.head];
16 this.head++;
17 return removed;
18 }
19}
20
21let queue = new Queue();
22queue.enqueue("first");
23queue.enqueue("second");
24console.log(queue.dequeue()); // outputs "first"Not Using an Array When It's Easier and More Efficient
There are scenarios where simple array operations can lead to a more efficient and cleaner solution compared to a queue. A classic example is the problem of finding a continuous subarray in an array that sums up to a given target. This can be solved more efficiently using two pointers instead of a queue, leading to the space complexity of O(1), which is more optimal than using a queue.
def find_subarray_with_sum(nums, target):
left, right = 0, 0
current_sum = 0
while right < len(nums):
current_sum += nums[right]
while current_sum > target and left <= right:
current_sum -= nums[left]
# move the left pointer forward
left += 1
# check if current sum equals target
if current_sum == target:
return (left, right)
# move the right pointer forward
right += 1
return None
print(find_subarray_with_sum([1, 4, 20, 3, 10, 5], 33))
# outputs (2, 4)1def find_subarray_with_sum(nums, target):
2 left, right = 0, 0
3 current_sum = 0
4
5 while right < len(nums):
6 current_sum += nums[right]
7
8 while current_sum > target and left <= right:
9 current_sum -= nums[left]
10 # move the left pointer forward
11 left += 1
12
13 # check if current sum equals target
14 if current_sum == target:
15 return (left, right)
16
17 # move the right pointer forward
18 right += 1
19
20 return None
21
22print(find_subarray_with_sum([1, 4, 20, 3, 10, 5], 33))
23# outputs (2, 4)Not Knowing How to Use Queues for BFS
Breadth-First Search (BFS) is a core algorithm in computer science, and it's a staple in many coding interviews. It is crucial in solving problems such as finding the shortest path in an unweighted graph, serializing and deserializing a tree, or even spreading infection in a grid.
Without a firm grasp of how to use queues for BFS, a candidate can miss out on efficiently solving these problems and more, which can make all the difference in a competitive interview scenario.
When heading into coding interviews, it's always a good idea to have a standard BFS algorithm using a queue, coded up and well-practiced, in your mental toolbox.
What to Say in Interviews to Show Mastery Over Queues
Understanding the Time Complexity Depending on the Underlying Structure
Discuss the time complexity of different queue operations, such as enqueuing and dequeuing, and how these complexities can change depending on the underlying structure (array, linked list, etc.) used to implement the queue. Demonstrating this understanding shows that you can consider and select the most appropriate data structure for a given problem.
Ask Clarifying Questions
Asking clarifying questions during the interview will help you better understand the problem and demonstrate your analytical skills and attention to detail. For example:
- Is the queue bounded or unbounded?
- What is the maximum size of the queue?
- What are the elements of the queue?
- Are they integers, strings, or objects?
- What is the maximum size of the elements?
- Are there any other constraints?
These questions are not exhaustive, but they are a starting point. Tailoring your questions based on the specific problem discussed in the interview will demonstrate your problem-solving approach and ability to focus on the finer details.
Demonstrate Knowledge of Use Cases
Demonstrating knowledge of where and why queues are used can set you apart. If the problem involves traversing a graph or a tree, mention that a queue would be perfect for a Breadth-First Search (BFS) because it naturally facilitates level-by-level traversal.
If the problem hints towards processing elements in a rolling window of a certain size, articulate that a queue can help manage this 'sliding window' scenario effectively. Additionally, while discussing the implementation, highlight the reasons to use a singly-linked list over a doubly-linked list (saving memory, simpler implementation) unless backward traversal is required.
Consider Optimal Solutions
Demonstrate a willingness to question your initial solution and strive for optimality. If you propose a solution using a queue, take a moment to evaluate whether a queue is necessary. Sometimes, problems can be solved more efficiently without queues or by using a simpler data structure. For example, many sliding window problems can be solved using a simple array and two-pointers. This is more efficient than using a queue, which would require additional space and operations.
Showcase Your Advanced Knowledge
Demonstrating knowledge beyond the basics always earns extra points. If you understand more complex data structures or concepts like XOR-deques (which use XOR operations to save memory) or ring buffers (which are perfect for handling 'recent activity' in a fixed amount of memory), bring them up in the interview. Explain why they're efficient and the specific scenarios where they can be advantageous.
Walls and Gates
You are given a m x n 2D grid initialized with these three possible values. Fill each empty room with the distance to its nearest gate.
Even Odd Tree
Given a tree, verify that on even levels, all values in the level are strictly increasing and even. On odd levels, verify all values in the level are strictly decreasing and odd.
Infinite Binary Print
Print out all numbers in binary, preserving leading zeros.
Transformation Dictionary
Given a dictionary of words, determine whether it is possible to transform a given word into another with a fixed number of characters.
About the Author
Jai is a software engineer and a technical leader. In his professional career spanning over a decade, he has worked at several startups and companies such as SlideShare and LinkedIn. He is also a founder of a saas product used by over 10K companies across the globe. He loves teaching and mentoring software engineers. His mentees have landed jobs at companies such as Google, Facebook, and LinkedIn.
About interviewing.io
interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.
