Module 6 · stack and queue: Last In First Out, First In First Out
CP and Interview Pack: stack and queue Patterns, Questions and the Bug Gallery
ProReading
Codeforces Beta Round 35 (Div. 2), in October 2010, had problem 35C, "Fire Again". A forest of N by M trees catches fire at K points at once. Each minute, the fire spreads from a burning tree to its four neighbours. Which tree catches fire last? Bob starts a separate search from every fire. Amara pushes all K fires into one queue first, and her whole solution is pattern 4 below.
Checking what this lesson needs for you…
What is inside CP and Interview Pack: stack and queue Patterns, Questions and the Bug Gallery
- Pattern 1: the monotonic stack
- Pattern 2: bracket partners
- Pattern 3: a queue from two stacks
- Pattern 4: multi-source BFS
- Pattern 5: an explicit stack instead of recursion
- Seven interview questions, with model answers