Top 12 Queue Interview Problems: Patterns, Traps, and the Deque Trick

Queue problems trip people up because they look simple. You know what a queue is. FIFO. Like the DMV. You get it. Then the interviewer says "sliding window maximum" and suddenly the deque you forgot about is the only thing standing between you and an O(n·k) timeout.

Most engineers walk into queue interviews thinking it's just BFS. That's one-third of what shows up. The queue appears across three distinct patterns: BFS and level-order traversal, sliding-window design problems, and monotonic deque optimization. Knowing all three separates a working solution from an optimal one.

Queue Interview Problems Follow Three Patterns

Pattern	What it solves	Complexity
BFS / level-order	Shortest paths, connected regions, level grouping	O(V+E)
Sliding window with queue	Rolling aggregates, time-window design, scheduling	O(n)
Monotonic deque	Range max/min, DP optimization over a window	O(n)

The monotonic deque is the one most candidates skip. It turns an O(n·k) brute-force into O(n) by maintaining a deque of candidates that could still be the answer as the window moves. Once you see how it works, you start spotting it in DP problems, not just range queries.

The Mechanics (And What Interviewers Ask About)

1. Implement Queue using Stacks (LC 232, Easy)

Build a FIFO queue using only two stacks.

The obvious answer: push to stack 1, pop by moving everything to stack 2 then popping. Each dequeue costs O(n). This works. It also makes your interviewer quietly write "brute force" in their notes.

The correct answer: lazy transfer. Only move elements from the inbox stack to the outbox stack when the outbox is empty. Every element crosses exactly once in each direction.

class MyQueue:
    def __init__(self):
        self.inbox = []
        self.outbox = []

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

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

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

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

    def _transfer(self):
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())

What this teaches: amortized analysis. Each element does one inbox push, one inbox pop, one outbox push, one outbox pop, regardless of call order. That's O(1) amortized per operation. Interviewers who ask this often follow up with the dynamic array resizing argument, so be ready.

2. Number of Recent Calls (LC 933, Easy)

A RecentCounter class counts pings in the last 3,000 milliseconds. Given a new timestamp t, return the count of calls in [t-3000, t].

You will be tempted to store every timestamp and filter. Don't. You'll be storing the entire history of a button that someone is mashing.

The key insight: you never need calls older than t-3000. Enqueue each timestamp, then dequeue from the front while the front is out of range. The queue length is the answer.

from collections import deque

class RecentCounter:
    def __init__(self):
        self.queue = deque()

    def ping(self, t: int) -> int:
        self.queue.append(t)
        while self.queue[0] < t - 3000:
            self.queue.popleft()
        return len(self.queue)

This three-step structure (add to back, trim from front, read length) is the template for every sliding-window-with-queue problem. Memorize it. Seriously.

BFS: Level Snapshots and Multi-Source Seeding

For a deep dive on BFS pattern recognition, see BFS Pattern Recognition. These three problems focus specifically on queue mechanics.

3. Binary Tree Level Order Traversal (LC 102, Medium)

The BFS workhorse. The one trap: how do you group nodes by level?

The naive instinct is to add a separator or track depth alongside each node. Both work. Neither is what the interviewer wants to see.

Take a snapshot of the queue length at the start of each level, then loop exactly that many times. Nodes added during the current iteration belong to the next level. The length snapshot is your level boundary.

from collections import deque

def levelOrder(root):
    if not root:
        return []
    result, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):          # snapshot
            node = queue.popleft()
            level.append(node.val)
            if node.left:  queue.append(node.left)
            if node.right: queue.append(node.right)
        result.append(level)
    return result

Right-side view, zigzag traversal, level averages: all one-line modifications of this structure.

4. Rotting Oranges (LC 994, Medium)

Multi-source BFS. Every rotten orange is a source. The common mistake is seeding one rotten orange, running BFS to completion, then moving to the next. That's serial. The actual rot spreads in parallel.

Picture a bad apple (or orange, in this case). It doesn't politely infect its neighbors one at a time.

Seed all rotten oranges before the main loop begins. BFS then naturally treats each level as one elapsed minute. After BFS, scan for any remaining fresh orange and return -1 if found.

5. Shortest Path in Binary Matrix (LC 1091, Medium)

BFS on a grid with 8 directions. The rule that catches people: mark cells visited when you enqueue them, not when you dequeue them.

Marking on dequeue lets the same cell get added multiple times from different neighbors, which inflates the queue and produces wrong distances. Your BFS is now a BFS-shaped pile of redundant work.

Mark visited at enqueue time. This holds for any BFS shortest-path problem, graph or grid. Write it on a sticky note if you have to.

Design Problems: Memory Compression and Greedy Scheduling

6. Design Hit Counter (LC 362, Medium)

Count web hits in the last 300 seconds. Same shape as Recent Calls, but the follow-up changes everything: what if there are 10 million hits per second?

A queue of raw timestamps runs out of memory fast. You're essentially buffering a firehose. The fix: a queue of (timestamp, count) buckets. You only need 300 distinct buckets (one per second). When a new hit arrives at second t, pop front buckets older than t-300, then increment the matching second's count at the back.

The (timestamp, count) bucket pattern compresses memory from O(hits) to O(window_size). Interviewers who ask this as a design problem specifically want to see the compression reflex. If you reach for compression without being prompted, they write down "good instincts."

7. Task Scheduler (LC 621, Medium)

Schedule tasks with a cooling interval k between identical tasks. Find the minimum number of intervals to finish all tasks.

There's a formula: max(n, (f-1)*(k+1)+ties) where f is the max frequency and ties is the count of tasks sharing it. The formula gets you the answer. The simulation gets you the follow-up questions.

The simulation: a max-heap of task counts plus a cooldown queue of (remaining_count, available_at_time) pairs. Each tick, pop the highest-count task, decrement it, push to the cooldown queue. Move tasks back to the heap when their cooldown expires.

What this teaches: the combination of a heap for greedy choice and a queue for time-delayed readiness. This pairing shows up in CPU scheduling, rate limiters, and operating system design rounds. See the monotonic deque for the related sliding-window max pattern this builds toward.

The Deque That Makes O(n·k) Problems Trivial

The deque here is not just a double-ended queue. It's a data structure maintained in sorted order (decreasing for max, increasing for min) so the front always holds the answer to the current window.

This feels like cheating the first time you see it. It's not cheating. It's just the right tool.

Monotonic deque step trace for sliding window maximum, showing how each element is pushed and popped at most once for O(n) total

8. Sliding Window Maximum (LC 239, Hard)

Given an array and window size k, return the max in each window. Brute force is O(n·k). On LeetCode's largest test cases, that times out. Every time. Go ahead and try the brute force first if you need to see the timeout in person.

The deque solution: store indices in decreasing order of their values. For each new element, pop the back while the back's value is smaller (it can never be the maximum with a larger element already in the window). Pop the front when its index falls outside the current window.

from collections import deque

def maxSlidingWindow(nums, k):
    dq, result = deque(), []
    for i, num in enumerate(nums):
        while dq and nums[dq[-1]] < num:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

Each element is pushed and popped at most once, giving O(n) total. This is the canonical monotonic deque problem. Every problem below is a variation.

9. Longest Subarray with Absolute Difference at Most Limit (LC 1438, Medium)

Find the longest subarray where max minus min is at most limit. You need both the max and the min of the current window at all times.

One deque is not enough. Use two deques in parallel: one decreasing (for max), one increasing (for min). Shrink the window from the left whenever their difference exceeds limit. It sounds complicated. The code is actually clean.

What this teaches: two deques tracking two constraints simultaneously. The pattern generalizes to any "window satisfying multiple range conditions" problem. Once you've done this one, you'll spot the two-deque setup immediately.

10. Jump Game VI (LC 1696, Medium)

Array of scores. From position i, jump 1 to k steps forward. Maximize total score at the last index.

The recurrence is dp[i] = scores[i] + max(dp[i-k], ..., dp[i-1]). Computing the range max naively is O(n·k). A monotonic deque tracking the best dp value in the last k positions drops it to O(n). This is the moment where DP and the deque collide, and the result is beautiful.

from collections import deque

def maxResult(nums, k):
    n = len(nums)
    dp = [0] * n
    dp[0] = nums[0]
    dq = deque([0])
    for i in range(1, n):
        while dq[0] < i - k:
            dq.popleft()
        dp[i] = nums[i] + dp[dq[0]]
        while dq and dp[dq[-1]] <= dp[i]:
            dq.pop()
        dq.append(i)
    return dp[-1]

This is the canonical "deque as DP optimization" problem. Once you see it here, you recognize it in constrained subsequence problems, stock-trading variants, and interval DP.

11. Shortest Subarray with Sum at Least K (LC 862, Hard)

Find the shortest subarray with sum at least k, where elements can be negative.

Negative elements break the standard two-pointer sliding window, because adding an element can decrease the sum. The fix: prefix sums plus a monotonic deque. Maintain a deque of prefix-sum indices in increasing order of value. For each index j, while the front satisfies prefix[j] - prefix[front] >= k, record the length and pop the front. We want the shortest subarray, so the leftmost valid starting point wins and will not improve by sliding right.

If you feel like this problem is punishing you personally, that's normal. It's punishing everyone.

Prefix-sum plus deque is the rescue pattern when sliding window breaks on negative values. This problem is a reliable Hard that tests whether you know when to upgrade your tool.

Simulation: The Queue as a Process Model

12. Reveal Cards in Increasing Order (LC 950, Medium)

You have n cards. A reveal operation: show the top card, put the next card at the bottom, repeat. Given the order of reveals must be ascending, reconstruct the deck.

Your first instinct is probably to simulate forward from some arrangement and check. That takes forever. Simulate the reveal process in reverse: sort the deck, simulate index positions with a deque, and assign each card to its revealed slot.

from collections import deque

def deckRevealedIncreasing(deck):
    n = len(deck)
    deck.sort()
    index_queue = deque(range(n))
    result = [0] * n
    for card in deck:
        result[index_queue.popleft()] = card
        if index_queue:
            index_queue.append(index_queue.popleft())
    return result

The append(popleft()) rotation models "put the top card at the bottom." What this teaches: using a queue to simulate a process, then reading off position assignments. This pattern appears in card game problems, process scheduling simulations, and any problem where an operation cycles through a list.

What Actually Goes Wrong

These four mistakes will cost you in a real interview. They are all fixable.

Multi-source BFS seeded one source at a time. Seeding sources serially produces wrong answers. Enqueue all sources before the main loop. Every time. No exceptions.

Marking visited at dequeue instead of enqueue. The queue inflates, performance collapses, and distances are incorrect on dense grids. If your BFS is mysteriously slow, this is probably why.

Not recognizing the monotonic deque signal. If the problem asks for the max or min in a sliding window, or if a DP recurrence takes the best of the last k states, the deque is likely the intended solution. The brute force passes small tests and times out on large ones. That's not a coincidence. That's the problem telling you something.

Using a list instead of a deque in Python. list.pop(0) is O(n). If you write a BFS with a plain list, your "O(V+E)" solution is secretly O(V^2). Use collections.deque. This one is free.

Work Through Them in Order

Problems 1 and 2 build vocabulary for the rest. Problems 3 through 5 cement the BFS template, and practicing them out loud forces you to articulate the queue's role rather than just code it silently. Problems 6 and 7 apply queues to design and scheduling contexts. Problems 8 through 11 build the monotonic deque from the canonical example up through DP optimization. Problem 12 is the "simulate with a queue" move that shows up in card and scheduling problems.

Queue problems in interviews test whether you narrate your queue usage or just let it appear in your code silently. Interviewers can't evaluate what you don't say. SpaceComplexity runs voice-based mock interviews where you practice naming the pattern, explaining the deque invariant, and handling follow-up questions before you touch the code.

#	Problem	Pattern	Key insight
1	Implement Queue using Stacks	Mechanics	Lazy transfer, amortized O(1)
2	Number of Recent Calls	Sliding window	Add, trim left, read length
3	Level Order Traversal	BFS	Snapshot `len(queue)` for level boundaries
4	Rotting Oranges	Multi-source BFS	Seed all sources before the loop
5	Shortest Path Binary Matrix	Grid BFS	Mark visited at enqueue, 8 directions
6	Design Hit Counter	Rolling window design	(timestamp, count) bucket compression
7	Task Scheduler	Heap + queue	Greedy choice + time-delayed readiness
8	Sliding Window Maximum	Monotonic deque	Decreasing deque, pop back on larger element
9	Longest Subarray Abs Diff	Two deques	Parallel max and min tracking
10	Jump Game VI	Deque-optimized DP	Range max over last k dp values
11	Shortest Subarray Sum K	Prefix sum + deque	Negatives break sliding window, deque fixes it
12	Reveal Cards in Order	Queue simulation	Rotation models "put top card at bottom"