Queue Practice Problems

How to Use This Problem List

Queue problems separate cleanly into six patterns. The queue is always the right structure when you need to process things in arrival order — but the variant (plain queue, deque, priority queue, circular queue) determines which interview technique applies.

Practice by pattern — solve four or five problems from one pattern before moving to the next. After a week of this, the question "what structure does this need?" becomes automatic.

For each problem: name the pattern within two minutes of reading. The recognition clue column tells you the exact phrase that triggers the technique.

Pattern 1: Basic BFS — Shortest Path and Level Order

The fundamental use of a queue in graph and tree problems. FIFO ordering guarantees level-by-level exploration, which gives shortest-path guarantees in unweighted settings.

Complexity target: O(n) time, O(w) space where w = maximum level width.

Recognition signal: "level", "depth", "layer", "each row", "nearest", "minimum hops". The problem involves a tree or graph where arrival order equals depth order.

Pattern 2: BFS on Grids — Multi-Source and Flood Fill

BFS on a 2D matrix where cells are nodes and adjacent cells are neighbours. Multi-source BFS seeds multiple starting cells simultaneously and finds minimum distances in a single pass.

Complexity target: O(rows × cols) time and space.

Recognition signal: "grid", "matrix", "spread", "adjacent cells", "distance to nearest", "flood fill". Any time the problem involves propagation across a 2D grid.

Pattern 3: BFS on Implicit Graphs — Word Problems and State Spaces

The graph is not given explicitly — nodes are states (words, numbers, configurations) and edges are valid single-step transformations. BFS finds the fewest transformations to reach the target state.

Complexity target: O(N × M × 26) for word-type problems (N words, M characters). O(states) for state-space BFS.

Recognition signal: "minimum transformations", "minimum steps from state A to state B", "each step changes one thing". The problem has a well-defined start state, end state, and set of valid transitions.

Pattern 4: Sliding Window Deque — Monotonic Queue

A deque (double-ended queue) maintains a monotonic sequence of candidates. The front is always the current window's answer. Elements expire from the front (window slides); dominated elements are removed from the back (maintain monotonicity).

Complexity target: O(n) time, O(k) space.

Recognition signal: "maximum/minimum in every window of size k", "sliding window with extreme query". The constraint is a fixed-size window and the query is always max or min within it.

Pattern 5: Priority Queue — Greedy Order Processing

Use a heap-backed priority queue when the problem requires always processing the most/least urgent element — not the first-arrived. The heap provides O(log n) extraction of the global minimum or maximum.

Complexity target: O(n log k) for k-element heap problems, O((V+E) log V) for Dijkstra.

Recognition signal: "k-th largest/smallest", "k closest", "k most frequent", "merge sorted", "median of stream", "minimum cost/distance". Any problem requiring repeated access to the globally smallest or largest element from a dynamic collection.

Pattern 6: Queue Design — Implement and Extend

Design problems that test whether you understand the internal mechanics of queues — implementing one structure using another, or extending a queue with additional O(1) capabilities.

Complexity target: O(1) amortized for all core operations where possible.

Recognition signal: "implement X using Y", "O(1) for all operations", "sliding time window count", "circular buffer with fixed capacity". The problem tests mechanics rather than algorithms.

Recommended Study Order

Week 1 — BFS Foundations
  Pattern 1 (Tree BFS): Level Order, Right Side View, Minimum Depth
  Pattern 2 (Grid BFS): Number of Islands, Flood Fill, Rotting Oranges

Week 2 — BFS Extensions
  Pattern 2 (Multi-source): 01 Matrix, Walls and Gates
  Pattern 3 (Implicit BFS): Word Ladder, Open the Lock

Week 3 — Advanced Data Structures
  Pattern 4 (Monotonic Deque): Sliding Window Max, Jump Game VI
  Pattern 5 (Priority Queue): Kth Largest, K Closest, Merge K Sorted

Week 4 — Design and Hard Problems
  Pattern 6 (Design): Implement Queue Using Stacks, Design Circular Queue
  Pattern 5 (Hard): Find Median from Data Stream, Task Scheduler
  Pattern 3 (Hard): Bus Routes, Sliding Puzzle
  Revisit any pattern that felt unclear

Problem-Solving Checklist for Queue Problems

Before writing code, run through this for every queue problem:

1. Is this a pure ordering/scheduling problem?
   → Arrival order matters → plain Queue (FIFO)
   → Priority matters, not arrival → Priority Queue (heap)
   → Both ends of a window matter → Deque
   → Fixed-size buffer with wrap-around → Circular Queue

2. Is this a BFS problem?
   → Shortest path, fewest steps → single-source BFS + queue
   → Distance from multiple sources → multi-source BFS
   → Minimum transformations between states → implicit BFS
   → Weighted graph → Dijkstra (priority queue replaces plain queue)

3. For grid BFS:
   → Define neighbours (4-directional or 8-directional?)
   → Visited condition (mark cell value OR use separate visited matrix?)
   → Multi-source? Seed ALL source cells before starting BFS

4. For priority queue:
   → Min-heap or max-heap?
   → k-th largest/smallest → use OPPOSITE heap type (k-th largest needs min-heap)
   → Fixed-size k? Maintain heap at exactly size k

5. For monotonic deque:
   → Store INDICES (not values) — expiry check needs position
   → Expiry: front index < i - k + 1 → pop from front
   → Monotonic property: back violates order for new element → pop from back

6. Edge cases:
   → Empty input → return 0, [], or -1 depending on problem
   → Single cell/node → trivially the answer
   → Target unreachable → return -1 or 0
   → k > n for k-th problems → undefined/invalid input

Pattern Recognition Quick Reference

Difficulty Progression Reference

Common Interview Topics by Company Focus

Product-based companies (FAANG-tier):

• ›BFS shortest path and level-order — always in rotation
• ›Rotting Oranges and 01 Matrix — multi-source BFS standards
• ›Find Median from Data Stream — two-heap design
• ›Sliding Window Maximum — monotonic deque
• ›Merge K Sorted Lists — priority queue must-know
• ›Word Ladder — implicit BFS on a word graph

Service-based and on-campus:

• ›Number of Islands, Level Order, BFS traversals
• ›Kth Largest, Top K Frequent — priority queue basics
• ›Implement Queue using Stacks — design understanding

Startup and mid-size tech:

• ›Moving Average, Hit Counter — time-windowed queue
• ›Task Scheduler — practical priority queue
• ›K Closest Points — geometric priority queue

Progress Tracking

After solving each problem, record:

1. ›Pattern — which of the 6 patterns does this belong to?
2. ›Data structure — plain queue, deque, priority queue, or circular queue?
3. ›Recognition clue — what phrase triggered this pattern?
4. ›BFS variant — single-source, multi-source, or implicit graph?
5. ›Edge case missed — empty grid? Unreachable target? k > n?
6. ›Time to solve — target 20-25 minutes for medium problems under interview conditions

After 30 problems across all six patterns, the structure should become reflexive — "multi-source grid BFS" should be your first thought when you see "minimum time for something to spread across a matrix," before you have finished reading the problem.