Pattern #17

Queue

Important interview questions, thinking patterns, BFS queue mechanics, and rules for solving queue problems in Go.

Must Solve

15 core questions — solve these first.

1.Implement Queue using Stacks
Two stacks (inStack & outStack)easy
2.Number of Recent Calls
Queue ping timestamps within t - 3000easy
3.Moving Average from Data Stream
Fixed size sliding window queueeasy
4.Design Circular Queue
Fixed array + head/tail indices with modulo %medium
5.Rotting Oranges
Multi-source Grid BFSmedium
6.Number of Islands
Grid BFS connected componentsmedium
7.Binary Tree Level Order Traversal
Queue level size loopmedium
8.Open the Lock
State BFS with 4-wheel rotation neighborsmedium
9.Shortest Path in Binary Matrix
8-directional Grid BFS shortest pathmedium
10.Walls and Gates
Multi-source BFS from all gatesmedium
11.Perfect Squares
BFS shortest path to 0 subtract squaresmedium
12.Word Ladder
Bi-directional or standard BFS word transformationshard
13.Snakes and Ladders
Board index BFS shortest movesmedium
14.Dota2 Senate
Radiant and Dire queue simulationmedium
15.Time Needed to Buy Tickets
Queue simulation or direct matheasy

Also Important

10 more questions worth practicing.

16.First Unique Character in a Stream
Queue + Hash Map char frequenciesmedium
17.Reveal Cards In Increasing Order
Deque / Queue simulationmedium
18.Design Front Middle Back Queue
Two Deques (left & right halves)medium
19.Task Scheduler
Max Heap + Queue cooldown buffermedium
20.Jump Game III
BFS reachable indices checkmedium
21.Minimum Genetic Mutation
Gene string mutation BFSmedium
22.01 Matrix
Multi-source BFS from all 0smedium
23.As Far from Land as Possible
Multi-source BFS from all land cells (1s)medium
24.Shortest Bridge
DFS locate 1st island + Multi-source BFS to 2ndmedium
25.Number of Provinces
Graph BFS / Union Findmedium

How to Think

Need first item first?Queue (FIFO)
Need process things in arrival order?Queue
Need shortest path with equal-cost moves?BFS + Queue
Need level-by-level traversal?Queue
Need process neighbors layer by layer?BFS
Need newest item first?Stack (not Queue)

Go BFS Queue Template (Production Head Pointer Approach)

Efficient O(1) Amortized BFS Template

queue := []int{start}
visited := map[int]bool{start: true}
head := 0 // Avoids expensive slice re-allocations (queue = queue[1:])

for head < len(queue) {
    curr := queue[head]
    head++

    for _, next := range getNeighbors(curr) {
        if !visited[next] {
            visited[next] = true // Mark visited WHEN ENQUEUEING!
            queue = append(queue, next)
        }
    }
}

👉 Total Time: O(V + E) | Space: O(V)

Queue vs BFS & Circular Queue

Queue vs BFS

Queue = Data Structure
BFS   = Algorithm (uses Queue)

Queue stores the discovered nodes that BFS should visit next in arrival order.

Circular Queue

(index + 1) % capacity
Wraps around fixed array buffer

End connects back to beginning for fixed-size bounded memory buffers.

Visual Memory Rule

Enter BACK → → → → Exit FRONT
BFS Rule: Mark visited WHEN ENQUEUEING (prevents duplicate visits)
Tree Level: Process size := len(queue) before inner loop

💡 Golden Rule: "If the oldest waiting item should be handled first, think Queue."

Common Interview Mistakes

1. Using Stack Instead of Queue

Accidentally popping from the back (Stack/LIFO) turns BFS into DFS and ruins shortest path guarantees!

2. Marking Visited Too Late

Marking visited when DEQUEUEING instead of when ENQUEUEING causes identical nodes to be enqueued multiple times.

3. Forgetting Level Size in Level Order

In tree level-order traversal, compute size := len(queue) at level start to separate levels.

4. Dequeueing Empty Queue

Accessing queue[0] or queue[head] without checking length causes index out-of-bounds panic.

Interview Rules

1. Arrival order? → Queue
2. Oldest item first? → Queue
3. BFS? → Queue
4. Shortest path with equal edge cost? → BFS + Queue
5. Level order traversal? → Queue
6. Grid spreading problem? → BFS + Queue
7. Mark visited when enqueueing to prevent duplicate entries
8. Enqueue at back, dequeue from front
9. Go BFS optimization → Use head pointer index instead of queue[1:]

Small Rules

Rule 1: Main operations Enqueue, Dequeue, Front/Peek are O(1).
Rule 2: Queue processes items in first-in first-out (FIFO) arrival order.
Rule 3: Always check len(queue) > 0 before removing from front.
Rule 4: BFS almost always uses a Queue because oldest discovered nodes must be visited first.
Rule 5: For BFS, mark visited immediately upon enqueueing to avoid duplicate work.

Production Thinking

Request Processing → HTTP requests arrive & process in FIFO order (Request A -> B -> C)

Background Job Workers → Image resizing, email sending jobs wait in worker queues

Message Streaming → Kafka partitions & rabbitmq message queues deliver ordered events

Print Queue → Printer processes submitted documents in FIFO order

Rate & Sensor Buffers → Fixed-size circular queue for last 100 sensor readings with bounded memory

Remember This

First In                    → First Out
Add                         → Back
Remove                      → Front
BFS                         → Queue
Shortest unweighted path    → BFS + Queue
Tree levels                 → Queue
Grid spreading              → Queue
Fixed-size buffer           → Circular Queue

💡 Golden Rule: "If the oldest waiting item should be handled first, think Queue."