Skip to main content

Documentation Index

Fetch the complete documentation index at: https://resources.devweekends.com/llms.txt

Use this file to discover all available pages before exploring further.

Queue Pattern

​
What is Queue?

Queue is a FIFO (First In, First Out) data structure where elements are added at the back and removed from the front. Think of a real-world queue at a coffee shop: the first person in line is the first person served. No cutting, no skipping. In algorithm problems, queues are the workhorse behind Breadth-First Search (BFS) — processing nodes level by level guarantees shortest-path discovery in unweighted graphs. They also power sliding-window maximums (via a deque), task scheduling, and stream processing problems. Key operations and their complexity:
  • enqueue (push to back): O(1)
  • dequeue (pop from front): O(1)
  • peek (view front element): O(1)
In Python, always use collections.deque instead of a plain list for queue operations — list.pop(0) is O(n) because it shifts all elements, while deque.popleft() is O(1).

​
Pattern Recognition Cheatsheet

These exact problem-statement keywords should make you reach for a queue (or deque) within 30 seconds. A queue is the workhorse for level-order processing and stream windows.
Keyword / Shape in ProblemQueue Variant to Use
”BFS”, “shortest path in unweighted graph”Standard FIFO queue of nodes
”level order”, “level by level”, “for each level”Queue plus level_size = len(queue) snapshot
”minimum number of steps/moves”, “fewest operations”BFS with a queue (steps == levels)
“rotting oranges”, “walls and gates”, “01 matrix”Multi-source BFS (enqueue all sources first)
“rate limit window”, “requests in the last N ms”Queue of timestamps with eviction
”moving average”, “sum of last K elements”Fixed-size queue plus running sum
”sliding window maximum / minimum”Monotonic deque of indices
”first non-repeating character in a stream”Queue plus frequency map
”task scheduler”, “round robin”, “fair queue”Priority queue or multi-level queue
”design hit counter”Deque of (timestamp, count) buckets
”design recent counter (LC 933)“Deque, evict timestamps older than t - 3000
Mental shortcut: if the problem talks about order of arrival or processing nearest-first, it is a queue. If it talks about the maximum/minimum within a window of size K, it is a monotonic deque. If it talks about priority / urgency, it is a heap, not a queue.

​
Reusable Template Code

Three skeletons cover the vast majority of queue problems. 
from collections import deque

# Skeleton 1: BFS level-order traversal
def bfs_levels(root):
    if not root: return []
    queue = deque([root])
    levels = []
    while queue:
        level_size = len(queue)            # SNAPSHOT before adding next level
        level = []
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:  queue.append(node.left)
            if node.right: queue.append(node.right)
        levels.append(level)
    return levels

# Skeleton 2: Sliding window maximum (monotonic deque)
def sliding_max(nums, k):
    dq = deque()                           # stores INDICES, values decreasing
    result = []
    for i, x in enumerate(nums):
        while dq and dq[0] <= i - k:       # evict expired
            dq.popleft()
        while dq and nums[dq[-1]] < x:     # evict smaller (irrelevant) tail
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

# Skeleton 3: Sliding-time-window counter (rate limit, recent calls)
class RecentCounter:
    def __init__(self):
        self.q = deque()
    def ping(self, t):
        self.q.append(t)
        while self.q[0] < t - 3000:        # evict timestamps older than 3 seconds
            self.q.popleft()
        return len(self.q)
Python performance trap: list.pop(0) is O(n) because it shifts every remaining element left. For BFS over a tree with thousands of nodes, this turns your O(n) algorithm into O(n^2). Always use collections.deque with popleft() — it is O(1).Java idiom: prefer ArrayDeque over LinkedList. Both implement Deque but ArrayDeque has better cache locality, no per-node allocation, and is roughly 2x faster in practice. The only reason to use LinkedList is if you specifically need null elements (which ArrayDeque rejects).

​
When to Use

BFS

Level-order traversal, shortest path

Scheduling

Task queues, round-robin

Sliding Window

With deque for O(1) operations

Streaming Data

Moving averages, recent items

​
Pattern Variations

​
1. Implement Queue using Stacks

This is a classic design question that tests your understanding of FIFO vs LIFO. The trick: use two stacks. One is the “inbox” where new elements land; the other is the “outbox” from which we serve elements. When the outbox is empty, pour everything from inbox into outbox — this reverses the order, giving us FIFO behavior. Amortized complexity: Each element is moved from inbox to outbox exactly once, so all operations are amortized O(1), even though a single pop might trigger an O(n) transfer. Interview tip: Be ready to explain the amortized analysis. The key argument: every element goes through at most 2 pushes and 2 pops across both stacks during its entire lifetime. 
class MyQueue:
    """FIFO queue built from two LIFO stacks.
    
    Analogy: Think of two tubes of tennis balls. You load balls into
    tube A (inbox). When you need to serve, flip tube A upside down
    into tube B (outbox) -- the bottom ball (first in) is now on top.
    """
    
    def __init__(self):
        self.inbox = []   # New elements land here
        self.outbox = []  # Elements ready to be served (reversed order)
    
    def push(self, x):
        self.inbox.append(x)
    
    def pop(self):
        self._transfer()         # Ensure outbox has elements
        return self.outbox.pop() # Serve from the "front" of the queue
    
    def peek(self):
        self._transfer()
        return self.outbox[-1]   # Look at front without removing
    
    def empty(self):
        return not self.inbox and not self.outbox
    
    def _transfer(self):
        """Move all elements from inbox to outbox (reversing order).
        Only transfer when outbox is empty to preserve FIFO ordering."""
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())

​
2. Moving Average from Data Stream

from collections import deque

class MovingAverage:
    """Calculate moving average of last n elements"""
    
    def __init__(self, size):
        self.size = size
        self.queue = deque()
        self.total = 0
    
    def next(self, val):
        self.queue.append(val)
        self.total += val
        
        if len(self.queue) > self.size:
            self.total -= self.queue.popleft()
        
        return self.total / len(self.queue)

​
3. Sliding Window Maximum (Monotonic Deque)

Finding the maximum in every window of size k is O(n * k) with brute force. A monotonic deque brings this down to O(n) by maintaining a decreasing sequence of candidate maximums. The front of the deque is always the current window’s maximum. We remove from the front when it slides out of the window, and we remove from the back when a new element makes older, smaller elements irrelevant. Complexity: O(n) time (each element is added and removed from the deque at most once), O(k) space for the deque. Why a deque and not a regular queue? We need to remove from both ends: the front (expired indices) and the back (smaller elements). 
from collections import deque

def max_sliding_window(nums, k):
    """Return the maximum value in each sliding window of size k.
    
    Example: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
    Windows:  [1,3,-1] [3,-1,-3] [-1,-3,5] [-3,5,3] [5,3,6] [3,6,7]
    Maxima:     3        3         5         5        6        7
    """
    result = []
    dq = deque()  # Stores indices; values at these indices are in decreasing order
    
    for i in range(len(nums)):
        # 1. Remove indices that have fallen out of the window
        while dq and dq[0] <= i - k:
            dq.popleft()
        
        # 2. Remove indices whose values are smaller than the new element
        #    (they can never be the maximum while the new element is in the window)
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()
        
        dq.append(i)
        
        # 3. Record the maximum once the first full window is formed
        if i >= k - 1:
            result.append(nums[dq[0]])  # Front of deque is the max
    
    return result

​
4. BFS Level Order Traversal

BFS with a queue is the natural way to process a tree (or graph) level by level. The critical trick is snapshotting the queue size at the start of each level — this tells you how many nodes belong to the current level before you start adding children from the next level. Complexity: O(n) time, O(w) space where w is the maximum width of the tree (up to n/2 for a complete binary tree). Interview tip: Many problems are disguised BFS: “minimum moves,” “rotting oranges” (multi-source BFS), “shortest path in unweighted graph.” If you see “minimum steps” or “level by level,” think queue immediately. 
from collections import deque

def level_order(root):
    """Binary tree level order traversal.
    
    Example tree:        3
                        / \
                       9   20
                          /  \
                         15   7
    Result: [[3], [9, 20], [15, 7]]
    """
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level = []
        level_size = len(queue)  # Snapshot: how many nodes in this level
        
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            
            # Enqueue children (they belong to the next level)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(level)
    
    return result

​
Classic Problems

ProblemPatternKey InsightComplexity
BFS TraversalStandard queueProcess level by levelO(n) time, O(w) space
Sliding Window MaxMonotonic dequeKeep decreasing orderO(n) time, O(k) space
Queue via StacksTwo stacksAmortized O(1) operationsAmortized O(1) per op
Moving AverageFixed-size queueRunning sum optimizationO(1) per call
Task SchedulerPriority queue + queueCool down managementO(n) time
Rotting OrangesMulti-source BFSStart from all rotten simultaneouslyO(m * n) time

​
Worked LeetCode Problems: Brute Force vs Optimized

Four canonical problems cover the queue interview surface. Each one teaches a distinct sub-pattern.

​
LC 102: Binary Tree Level Order Traversal (Medium)

Problem. Return the values of a binary tree level by level, top to bottom. Brute force. Use DFS, tag each node with its depth, group by depth at the end. Works but is O(n) extra space and obscures the level-by-level intent. Optimized BFS (O(n) time, O(w) space where w is max width). Queue with the level-size snapshot trick. 
from collections import deque
def level_order(root):
    if not root: return []
    out, q = [], deque([root])
    while q:
        level_size = len(q)             # SNAPSHOT -- this is the trick
        level = []
        for _ in range(level_size):
            node = q.popleft()
            level.append(node.val)
            if node.left:  q.append(node.left)
            if node.right: q.append(node.right)
        out.append(level)
    return out
The level-size snapshot insight. Without taking len(q) before the inner loop, you cannot tell where the current level ends and the next begins — adding children to the queue mid-loop confuses the boundary. Snapshot first, drain that many, then move on.

​
LC 622: Design Circular Queue (Medium)

Problem. Implement a fixed-size circular queue with enQueue, deQueue, Front, Rear, isEmpty, isFull — all O(1). Brute force. Linked list with explicit head and tail. Works but allocates per insert and lacks cache locality. Optimized — ring buffer with two pointers. Fixed array, head and tail indices, wrap with modulo. Track count (or leave one slot unused) to distinguish empty from full. 
class MyCircularQueue:
    def __init__(self, k):
        self.q = [0] * k
        self.head = 0
        self.count = 0
        self.k = k
    def enQueue(self, value):
        if self.count == self.k: return False
        tail = (self.head + self.count) % self.k
        self.q[tail] = value
        self.count += 1
        return True
    def deQueue(self):
        if self.count == 0: return False
        self.head = (self.head + 1) % self.k
        self.count -= 1
        return True
    def Front(self): return -1 if self.count == 0 else self.q[self.head]
    def Rear(self):  return -1 if self.count == 0 else self.q[(self.head + self.count - 1) % self.k]
    def isEmpty(self): return self.count == 0
    def isFull(self):  return self.count == self.k
Real-world tie-in. Linux’s sk_buff ring, Java’s ArrayBlockingQueue, the LMAX Disruptor, and audio playback buffers all use this exact pattern. The ring buffer is one of the most-used data structures in systems programming.

​
LC 933: Number of Recent Calls (Easy)

Problem. Each call to ping(t) adds a request at time t. Return the number of pings in the last 3000 ms (inclusive). Brute force. Store all timestamps in a list; on each ping, scan backward to count recent ones. O(n) per call. Optimized — deque with eviction. Append the new timestamp; pop from the front anything older than t - 3000; return the deque size. 
from collections import deque
class RecentCounter:
    def __init__(self):
        self.q = deque()
    def ping(self, t):
        self.q.append(t)
        while self.q[0] < t - 3000:
            self.q.popleft()
        return len(self.q)
Why amortized O(1). Each timestamp is appended once and popped at most once across its lifetime. The while-loop looks scary but contributes at most O(n) total across all calls.

​
LC 239: Sliding Window Maximum (Hard) — Monotonic Deque

Problem. Given nums and window size k, return the maximum of every contiguous window of size k. Brute force (O(n*k)). For each window, scan and find the max. Times out on large inputs. Optimized monotonic deque (O(n)). Maintain a deque of indices where the values are strictly decreasing. The front is always the current window’s max. On each step: evict expired indices from the front, evict smaller indices from the back, append the new index. 
from collections import deque
def max_sliding_window(nums, k):
    dq = deque()
    out = []
    for i, x in enumerate(nums):
        while dq and dq[0] <= i - k:        # expired
            dq.popleft()
        while dq and nums[dq[-1]] < x:      # smaller than new -- they cannot be max
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            out.append(nums[dq[0]])
        # NB: wrote dq[0] <= i - k (uses unicode-safe ascii), and nums[dq[-1]] < x
    return out
Why a deque, not a heap? A max-heap solves it in O(n log k) but cannot remove arbitrary expired indices in O(1) — you would need lazy deletion. The monotonic deque achieves O(n) amortized, strictly better.

​
Caveats and Traps

Bugs Every Queue Problem Hides:
  1. list.pop(0) is O(n) in Python. Iterating a BFS over 100k nodes with list.pop(0) quietly turns your O(n) algorithm into O(n^2). Always from collections import deque and use popleft().
  2. Thread safety for concurrent producers. A bare deque or ArrayDeque is not thread-safe. Multiple producers calling append/offer simultaneously can corrupt the queue. Use queue.Queue (Python) or LinkedBlockingQueue / ConcurrentLinkedQueue (Java) when crossing thread boundaries.
  3. Forgetting the level-size snapshot in BFS. Without level_size = len(queue) taken before the inner loop, you cannot tell where one level ends and the next begins. You will conflate levels and break level-by-level problems.
  4. Storing nodes by value when you need parent/depth context. Push tuples like (node, depth) or (node, parent) into the queue when the algorithm needs more than the node itself.
  5. Using a regular queue when you need ordering by priority. “Process the most urgent task first” means heap, not queue. FIFO is for arrival order; heap is for priority order.
  6. Forgetting to mark visited in graph BFS. Without a visited set, you re-enqueue the same nodes, blow up memory, and may never terminate on cyclic graphs.
  7. In sliding window max, comparing dq[0] to a stale index. Always evict from the front before doing the front-equals-max read. Otherwise you read a stale max from outside the window.
Solutions and Idioms — Paired with the Caveats Above:
  1. Always from collections import deque at the top of any BFS or sliding-window solution. Make it muscle memory.
  2. Choose the right concurrent queue: for producer-consumer, LinkedBlockingQueue (bounded) or ConcurrentLinkedQueue (unbounded, lock-free). For Python multi-threading, queue.Queue. For asyncio, asyncio.Queue.
  3. Level-by-level BFS template: outer while queue: plus inner for _ in range(len(queue)):. Internalize this pattern — it solves Level Order, Min Depth, Right Side View, Word Ladder, and Rotting Oranges with the same skeleton.
  4. Tuple-payload trick: queue.append((node, depth, path)) — carry whatever context you need on the queue itself rather than maintaining parallel structures.
  5. When to upgrade to heap: if any node has a “cost” or “weight” that determines processing order, switch to heapq.heappush/heappop. BFS becomes Dijkstra.
  6. Visited-set discipline: visited.add(start) before the loop, visited.add(neighbor) BEFORE enqueuing (not when dequeuing), to prevent the same neighbor being added by two different parents.
  7. Sliding-deque mantra: “Evict expired front, evict useless tail, append, then read.” Always in that order.

​
Curated LeetCode Practice List

The classic queue problem set, grouped by difficulty.

​
Easy

#ProblemPattern Variant
933Number of Recent CallsTime-window deque
232Implement Queue using StacksTwo-stack amortization
225Implement Stack using QueuesReverse trick
346Moving Average from StreamFixed-size queue + running sum
1700Students Unable to Eat LunchDirect queue simulation

​
Medium

#ProblemPattern Variant
102Binary Tree Level OrderBFS with level snapshot
199Binary Tree Right Side ViewLast node of each level
994Rotting OrangesMulti-source BFS
54201 MatrixMulti-source BFS distance
622Design Circular QueueRing buffer
641Design Circular DequeRing buffer with both ends
1352Product of Last K NumbersStream queue
1696Jump Game VIDP with monotonic deque

​
Hard

#ProblemPattern Variant
239Sliding Window MaximumMonotonic deque
295Find Median from StreamTwo-heap (priority queue)
862Shortest Subarray with Sum at Least KMonotonic deque on prefix sums
218The Skyline ProblemSweep line + heap
480Sliding Window MedianTwo heaps with lazy delete

​
Interview Tips

Use a queue (BFS) when you need:
  • Shortest path in an unweighted graph
  • Level-by-level processing
  • Minimum number of steps/moves
  • “Nearest” or “closest” anything
Use a stack (DFS) when you need:
  • All paths or all solutions
  • Backtracking
  • Detecting cycles (directed graphs)
  • Topological sort
Python’s list.pop(0) is O(n) because it shifts every element left. For BFS with thousands of nodes, this turns your O(n) algorithm into O(n^2). Always use collections.deque with popleft() which is O(1).

​
Practice Problems

Sliding Window Max

Monotonic deque technique

Implement Queue

Two stacks approach

Number of Islands

BFS exploration

Rotting Oranges

Multi-source BFS

​
Interview Questions

​
1. Implement a queue using two stacks. What is the amortized time complexity of each operation?

What interviewers are really testing: Whether you understand the two-stack trick and, more importantly, whether you can analyze amortized complexity. Most candidates can implement it but stumble on proving why pop is O(1) amortized and not O(n). Strong Answer:
  • Use two stacks: an inbox for push and an outbox for pop/peek. Push always goes to inbox in O(1). For pop, if outbox is not empty, pop from it in O(1). If outbox is empty, transfer all elements from inbox to outbox (reversing the order to restore FIFO), then pop.
  • The individual transfer step is O(n), but amortized analysis shows each element is moved at most once from inbox to outbox across its entire lifetime. So n operations cost O(n) total work for transfers, making each operation O(1) amortized.
  • The key insight is lazy transfer: we only move elements when outbox is empty. This batches the expensive work. It is the same amortization argument as dynamic array resizing — occasional expensive operations spread across many cheap ones.
  • This is a real design pattern. Amazon SQS internally uses a similar two-buffer approach for message visibility. The pattern also appears in functional programming where queues are implemented using two lists.
Red flag answer: “Pop is O(n) because we might need to transfer everything.” This misses amortized analysis, which is the entire point. Another red flag is transferring on every pop instead of only when outbox is empty. Follow-ups:
  1. What if we need to support a peek operation as well? Does it change the amortized complexity?
  2. Can you implement a stack using two queues? What is the time complexity, and is it as efficient?

​
2. Explain how BFS uses a queue to traverse a graph level by level. Why can BFS not use a stack?

What interviewers are really testing: Deep understanding of why FIFO ordering is essential to BFS’s correctness, not just the mechanics. They also want to see if you know what happens if you swap the queue for a stack. Strong Answer:
  • BFS explores nodes in order of their distance from the source. It enqueues the source, then repeatedly dequeues the front node, processes it, and enqueues all its unvisited neighbors. The FIFO property guarantees that all nodes at distance d are processed before any node at distance d+1.
  • If you replace the queue with a stack, you get DFS (depth-first search), not BFS. A stack processes the most recently added neighbor first, diving deep into one branch before backing up. This destroys the level-by-level guarantee and means you can no longer use BFS to find shortest paths in unweighted graphs.
  • The level-order trick: to know which nodes belong to which level, capture queue.size() at the start of each iteration and process exactly that many nodes. This is the pattern used in “Binary Tree Level Order Traversal,” “Minimum Depth of Binary Tree,” and “Word Ladder.”
  • Time complexity is O(V + E) for adjacency list representation. Space is O(V) in the worst case for the queue (when an entire level is in the queue at once — imagine a complete binary tree’s last level).
Red flag answer: “BFS just visits all nodes; it does not matter if you use a queue or stack.” This is fundamentally wrong and shows a misunderstanding of graph traversal guarantees. Follow-ups:
  1. In “Rotting Oranges,” why do we enqueue all initially rotten oranges at once before starting BFS? What is this pattern called?
  2. How would you modify BFS to find the shortest path in a weighted graph? What changes about the data structure?

​
3. What is a monotonic deque, and how does it solve the “Sliding Window Maximum” problem in O(n)?

What interviewers are really testing: Whether you can maintain a running invariant on a double-ended queue and understand why the deque stores indices rather than values. This is one of the hardest queue-based patterns. Strong Answer:
  • A monotonic deque maintains elements in strictly decreasing order (for the maximum variant). The front of the deque always holds the index of the current window’s maximum. When a new element arrives, we pop all elements from the back that are smaller than it — they can never be the maximum of any future window because the new element is both larger and more recent.
  • We store indices, not values, because we need to evict elements that have fallen outside the window. Before processing each new element, we check if the front index is outside the window bounds (dq[0] <= i - k) and pop it from the front.
  • Each element is pushed and popped at most once across the entire traversal, so total operations are O(n). This avoids the O(n*k) brute force of scanning each window.
  • The deque invariant after processing index i: elements are in decreasing order of value, all indices are within the current window [i-k+1, i], and the front is the maximum.
Red flag answer: “Use a max-heap for the window.” A max-heap gives O(n log k) and does not efficiently remove expired elements. The candidate should know the deque gives O(n), which is strictly better. Another red flag is storing values instead of indices and not being able to handle window expiration. Follow-ups:
  1. How would you modify this to find the sliding window minimum instead?
  2. What if the window size is not fixed but defined by a condition (like “sum of window at most target”)? Can you still use a monotonic deque?

​
4. Design a moving average calculator for a data stream with a fixed window size. What data structure do you use and why?

What interviewers are really testing: Whether you can choose the right data structure for a stream processing problem and maintain a running aggregate efficiently. Simple problem, but it reveals clean thinking. Strong Answer:
  • Use a queue (deque) of fixed maximum size and maintain a running sum. When a new value arrives, add it to the queue and add it to the running sum. If the queue exceeds the window size, dequeue the oldest element and subtract it from the running sum. The average is running_sum / queue_size.
  • Each next() call is O(1) time. Space is O(k) where k is the window size.
  • The key optimization is the running sum. Without it, you would need to sum all k elements on every call, making each next() O(k). The running sum turns it into O(1) by only tracking the delta (add the new value, subtract the evicted value).
  • Floating-point consideration: if the stream is very long and values are large, the running sum can accumulate floating-point error. In a production system, you might periodically recompute the sum from scratch or use Kahan summation for numerical stability.
Red flag answer: “Recompute the sum by iterating over the queue each time.” That is O(k) per query instead of O(1). Another red flag is using a regular list and removing from the front in O(n) instead of using a deque with O(1) popleft. Follow-ups:
  1. What if instead of the mean, you needed the moving median? How does the data structure change?
  2. How would you extend this to an exponentially weighted moving average (EWMA)? Do you still need a queue?

​
5. When would you choose a priority queue (heap) over a regular queue? Give specific problem examples.

What interviewers are really testing: Whether you understand that “queue” is not one-size-fits-all and can articulate when ordering by priority matters versus ordering by arrival time. Strong Answer:
  • A regular queue processes elements in FIFO order — first in, first out. A priority queue processes elements by priority (highest or lowest value first), regardless of insertion order. Use a regular queue when order of arrival matters (BFS, task scheduling with fairness). Use a priority queue when urgency or weight matters (Dijkstra’s shortest path, finding top-k elements, merge k sorted lists).
  • Dijkstra’s algorithm: BFS with a queue only works for unweighted graphs. For weighted graphs, we need to process the node with the smallest tentative distance next. A min-heap priority queue gives us this in O(log V) per extraction, leading to O((V + E) log V) total.
  • Merge k sorted lists: we put the head of each list into a min-heap, extract the minimum, and push the next element from that list. This runs in O(n log k) where n is total elements and k is the number of lists.
  • Top-k elements: maintain a min-heap of size k. For each element, if it is larger than the heap’s minimum, replace the minimum. After processing all elements, the heap contains the k largest. This is O(n log k) time and O(k) space.
Red flag answer: “A priority queue is just a faster queue.” No — it serves a fundamentally different purpose: ordering by value rather than arrival. Another red flag is not being able to name a concrete problem that requires a priority queue. Follow-ups:
  1. What is the time complexity of building a heap from n elements? Why is it O(n) and not O(n log n)?
  2. In Dijkstra’s algorithm, what happens if you use a regular queue instead of a priority queue? Does the algorithm still produce correct results?

​
6. Explain how a circular queue (ring buffer) works. Where is it used in real systems?

What interviewers are really testing: Systems-level understanding and whether you know that the “queue” abstraction has different implementations with different trade-offs for different use cases. Strong Answer:
  • A circular queue uses a fixed-size array with two pointers: head (front) and tail (back). Both wrap around using modular arithmetic: tail = (tail + 1) % capacity. Enqueue places at tail and advances it; dequeue reads from head and advances it. When head == tail, the queue is either empty or full (distinguished by tracking count or leaving one slot empty).
  • The advantage over a linked-list queue: no memory allocation on enqueue, no garbage collection pressure, cache-friendly contiguous memory. The disadvantage: fixed capacity — you must decide the size upfront or handle resizing.
  • Real-world uses: network packet buffers (Linux kernel’s sk_buff ring), producer-consumer patterns in concurrent systems (Java’s ArrayBlockingQueue, LMAX Disruptor), audio/video streaming buffers, and the CPU’s reorder buffer in out-of-order execution.
  • The LMAX Disruptor (used in high-frequency trading) achieves millions of messages per second using a ring buffer with careful lock-free design. It avoids cache-line bouncing by padding entries and uses sequence numbers instead of head/tail pointers.
Red flag answer: “I have never used a circular queue; linked-list queues are fine.” This shows a lack of systems awareness. In performance-sensitive code, the choice between ring buffer and linked-list queue can be the difference between microsecond and millisecond latency. Follow-ups:
  1. How do you handle the case where the circular queue is full? What are the options, and which would you choose for a real-time system?
  2. How does a lock-free ring buffer work in a multi-threaded producer-consumer scenario?

​
7. In the “Rotting Oranges” problem, all initially rotten oranges rot their neighbors simultaneously. How do you model this with BFS, and why is this different from standard BFS?

What interviewers are really testing: Understanding of multi-source BFS — a critical variant where BFS starts from multiple sources at once. This pattern appears in many graph problems (0-1 BFS, shortest distance from any gate, etc.). Strong Answer:
  • This is multi-source BFS. Instead of starting from a single source, we enqueue all initially rotten oranges into the queue before starting the BFS loop. This is equivalent to adding a virtual super-source connected to all rotten oranges with zero-cost edges.
  • The BFS then expands level by level. Each “level” corresponds to one minute of time. After processing all nodes at the current level (using the level_size = len(queue) trick), we increment the time counter. When the queue is empty, we have the minimum time.
  • After BFS completes, check if any fresh oranges remain (cells with value 1 that were never reached). If so, return -1 — not all oranges can be rotted.
  • This same multi-source BFS pattern solves: “Walls and Gates” (distance from each empty room to nearest gate), “01 Matrix” (distance from each cell to nearest 0), and “Pacific Atlantic Water Flow” (start BFS from ocean borders).
Red flag answer: “Run BFS from each rotten orange separately and take the minimum.” That is O(mn * number_of_rotten), not O(mn). The multi-source approach processes every cell at most once, giving O(m*n) total. The difference between single-source and multi-source BFS is exactly what the interviewer is probing. Follow-ups:
  1. What if some oranges rot faster than others (different weights)? Can you still use BFS, or do you need Dijkstra?
  2. How would you modify this approach if oranges could also become “unrotten” after a certain time?

​
Interview Q&A Deep-Dive

The four questions below mirror the rich AccordionGroup format you will see in our microservices and other DSA chapters. Each one includes a strong answer framework, a real LeetCode example with full code, three senior follow-ups, common wrong answers, and further reading.
Strong Answer Framework:
  1. Clarify constraints first. “Are values guaranteed to be integers? Is the window size fixed at construction or dynamic? What is the expected call volume — millions per second or hundreds?”
  2. State the data structure choice. A deque (double-ended queue) of size at most k, plus a running sum scalar.
  3. Walk through the invariant. “After each call, the deque holds the last k values seen so far — or all values if fewer than k have arrived. The running sum equals the sum of the deque.”
  4. Code the O(1) update. Append the new value, add to running sum. If size exceeds k, popleft and subtract from running sum. Return running_sum / size.
  5. Discuss numerical stability. Floating-point error accumulates over very long streams. Mention Kahan summation or periodic full-recompute as production-grade options.
Real LeetCode Example — LC 346: Moving Average from Data Stream
from collections import deque

class MovingAverage:
    def __init__(self, size: int):
        self.size = size
        self.q = deque()
        self.total = 0.0

    def next(self, val: int) -> float:
        self.q.append(val)
        self.total += val
        if len(self.q) > self.size:
            self.total -= self.q.popleft()
        return self.total / len(self.q)
Each call is O(1) time, O(k) space. The running-sum optimization is what turns a naive O(k)-per-call solution into O(1).
Senior Follow-up 1: “What if instead of the mean, you needed the moving median?” — The data structure changes fundamentally: you need two heaps (a max-heap for the lower half and a min-heap for the upper half) plus lazy deletion when the window slides. This is LC 480 (Sliding Window Median) and is materially harder than the average case.
Senior Follow-up 2: “How would you extend this to an exponentially weighted moving average (EWMA)?” — EWMA is new_avg = alpha * val + (1 - alpha) * prev_avg. You do not need a queue at all — just one floating-point variable. EWMA forgets old values gradually rather than via a hard cutoff, which is what financial time series and metric pipelines (Datadog, Prometheus rate functions) actually use.
Senior Follow-up 3: “Across millions of calls, your floating-point sum drifts. How do you handle that in production?” — Use Kahan summation (a compensation variable that tracks lost low-order bits). Alternatively, recompute the sum from the deque every N calls — amortizes to constant overhead and bounds error.
Common Wrong Answers:
  • “Recompute the sum by iterating the queue every call.” That is O(k) per call instead of O(1). Fails the implicit performance bar.
  • “Use a Python list and pop(0).” That is O(n) per pop and quietly turns the solution into O(n^2) over n calls.
Further Reading:
Strong Answer Framework:
  1. Name the structures. inbox for incoming pushes, outbox for outgoing pops/peeks.
  2. Push. Always to inbox — O(1).
  3. Pop / peek. If outbox is empty, transfer everything from inbox to outbox (which reverses order, restoring FIFO). Then pop from outbox.
  4. Prove the amortized O(1). Each element is pushed onto inbox, transferred once to outbox, and popped from outbox — 4 operations total over its lifetime. Across n operations, total work is O(n), so each is O(1) amortized.
  5. Critical detail. Only transfer when outbox is empty. Transferring on every pop destroys the amortization and makes pop O(n) worst-case AND average-case.
Real LeetCode Example — LC 232: Implement Queue using Stacks
class MyQueue:
    def __init__(self):
        self.inbox = []   # for push
        self.outbox = []  # for pop/peek

    def push(self, x: int) -> None:
        self.inbox.append(x)

    def pop(self) -> int:
        self._shift()
        return self.outbox.pop()

    def peek(self) -> int:
        self._shift()
        return self.outbox[-1]

    def empty(self) -> bool:
        return not self.inbox and not self.outbox

    def _shift(self):
        if not self.outbox:           # ONLY transfer when outbox is empty
            while self.inbox:
                self.outbox.append(self.inbox.pop())
Senior Follow-up 1: “Can you implement a stack using two queues? What is the time complexity, and is it as efficient?” — Yes, but the asymmetry is interesting: making push O(n) (rotate the queue so the new element is at the front) lets you keep pop and top at O(1). Alternatively, make pop O(n). Unlike the queue-via-stacks case, there is no clever amortization — one operation is always O(n).
Senior Follow-up 2: “What if multiple threads call push and pop simultaneously?” — The two-stack invariant breaks under concurrency: a pop thread can observe outbox empty and start transferring while a push thread mutates inbox. You need a single lock around the whole class, or switch to LinkedBlockingQueue (Java) / queue.Queue (Python) for thread safety. Two stacks plus a lock is rarely worth it — just use a real concurrent queue.
Senior Follow-up 3: “What is the worst-case latency of a single pop? Why might that matter in production?” — Worst case is O(n): if the inbox has accumulated many pushes since the last pop, the next pop triggers a full transfer. For real-time systems with strict latency tails (trading, gaming), amortized O(1) is not good enough — you need worst-case O(1), which requires a different structure (linked list or ring buffer).
Common Wrong Answers:
  • “Pop is O(n).” Misses the amortized argument — this is the entire point of the question.
  • “Transfer on every pop.” Doubles the work and breaks the amortization.
  • “Use Java’s Stack class.” Stack extends Vector and is synchronized; use ArrayDeque instead.
Further Reading:
Strong Answer Framework:
  1. State the brute force. For each of n - k + 1 windows, scan k elements — O(n * k). Times out on large inputs.
  2. Compare two optimized approaches. Max-heap gives O(n log k). Monotonic deque gives O(n) — strictly better.
  3. Explain the deque invariant. Indices in the deque correspond to values in strictly decreasing order. The front is always the index of the current window’s maximum.
  4. Walk through the three steps per element. (a) Evict expired indices from the front. (b) Evict useless tail indices whose values are smaller than the new element. (c) Append the new index. Read max from front once the window has formed.
  5. Justify “indices, not values”. Without indices you cannot tell whether the front has fallen out of the window.
Real LeetCode Example — LC 239: Sliding Window Maximum
from collections import deque

def maxSlidingWindow(nums, k):
    dq = deque()              # holds INDICES; values at those indices strictly decrease
    result = []
    for i, x in enumerate(nums):
        # 1. evict expired
        while dq and dq[0] <= i - k:
            dq.popleft()
        # 2. evict useless tail
        while dq and nums[dq[-1]] < x:
            dq.pop()
        # 3. append
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result
Senior Follow-up 1: “How would you modify this for the sliding window minimum instead?” — Flip the comparison: maintain a strictly increasing deque, evict tail indices whose values are larger than the new element. Front is now the window minimum. Same O(n).
Senior Follow-up 2: “Why does a max-heap not achieve O(n)?” — A heap can extract the max in O(log k), but it cannot remove an arbitrary element when it expires from the window. You either accept O(n) lazy deletion (peek the max, discard if out of window, repeat) or use a removable heap with a hashmap of (value, count) which is more complex. The monotonic deque sidesteps this entirely.
Senior Follow-up 3: “What if the window size is dynamic — determined by a condition like prefix-sum at most target?” — The deque approach generalizes via LC 862 (Shortest Subarray with Sum at Least K), where you use a monotonic deque on prefix sums. The eviction rule becomes “front is too small to be useful” rather than “front is out of window.” Same O(n) amortized.
Common Wrong Answers:
  • “Use a max-heap.” Gets O(n log k); strictly worse than the deque’s O(n).
  • “Store values in the deque, not indices.” Cannot detect window expiration — the algorithm produces wrong results when the max value sits before the window starts.
  • “Use a SortedList.” O(n log k) and library-dependent.
Further Reading:
Strong Answer Framework:
  1. Recognize the multi-source signature. Multiple starting points expand simultaneously. Single-source BFS would over-process.
  2. Pre-load the queue. Before the BFS loop starts, scan the grid and enqueue every initial source (every rotten orange) along with their starting time of 0.
  3. Process by levels. Use the level_size = len(queue) snapshot trick to advance “minutes” one level at a time.
  4. Bookkeep fresh count. Track how many fresh oranges remain. Each successful infection decrements it. If non-zero at the end, return -1.
  5. Why not run single-source BFS from each rotten orange? That is O(grid * num_rotten) — with 10x10 grid and 50 rotten oranges, that is 500x slower than multi-source.
Real LeetCode Example — LC 994: Rotting Oranges
from collections import deque

def orangesRotting(grid):
    rows, cols = len(grid), len(grid[0])
    q = deque()
    fresh = 0
    # 1. seed the queue with ALL rotten oranges at time 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                q.append((r, c, 0))
            elif grid[r][c] == 1:
                fresh += 1

    if fresh == 0:
        return 0                              # nothing to rot

    minutes = 0
    directions = [(-1,0),(1,0),(0,-1),(0,1)]
    while q:
        r, c, t = q.popleft()
        minutes = t
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                grid[nr][nc] = 2
                fresh -= 1
                q.append((nr, nc, t + 1))

    return minutes if fresh == 0 else -1
Senior Follow-up 1: “What if some oranges rot faster than others (different weights)?” — You can no longer use plain BFS because the path with the fewest hops is no longer the shortest path. You must upgrade to Dijkstra with a min-heap priority queue. The structural change is the data structure, not the algorithm shape.
Senior Follow-up 2: “What other problems share this multi-source BFS pattern?” — LC 542 (01 Matrix — start BFS from every 0, find distance to nearest 0 for each cell), LC 286 (Walls and Gates — start from every gate), LC 417 (Pacific Atlantic Water Flow — start from every ocean border). The pattern’s signature is “compute distance from any source” rather than “compute distance from a specific source.”
Senior Follow-up 3: “What if oranges can become unrotten after a delay?” — Now you have a temporal dependency: BFS no longer suffices because state can revert. You need a simulation with a discrete-time loop, or model it as a state-space search (BFS over (grid_state, time) pairs) — which is exponential and infeasible for non-trivial grids. The conversation often pivots to “is there a smarter formulation,” like detecting periodicity.
Common Wrong Answers:
  • “Run BFS from each rotten orange separately and take the min over each cell.” Correct answer, wrong complexity — O(grid * num_rotten) instead of O(grid).
  • “Use DFS instead of BFS.” DFS does not guarantee shortest path / minimum time — it can revisit cells with longer paths first.
  • “Forget to check for unreachable fresh oranges.” Returns wrong answer when the grid has isolated fresh oranges.
Further Reading: