Tonight's goal: choose the right graph model under a timer, explain it out loud, then code one DFS-flood problem and one BFS-shortest-path problem.
Tonight's protocol
Use the mock-day protocol: speak before typing, keep the timer honest, compare only after the timer.
0:00-0:04: Answer the warm-up MCQs below. No notes, no source lessons.
0:04-0:05: Open the first problem and a blank file. Solving starts at minute 5.
0:05-0:40: Solve Problem 1. First 2 minutes: explain node, edge, traversal, visited mark, and time/space complexity out loud. Then code. If stuck after 25 minutes on this problem, read only the pattern name from the menu and continue for 10 minutes.
0:40-1:15: Solve Problem 2 with the same rule: explain aloud first, code second, pattern-name-only hint after 25 stuck minutes.
1:15-1:25: Compare after the timer. For each problem, write the exact reasoning gap: wrong graph model, wrong traversal, missed visited mark, or implementation bug.
1:25-1:30: Encode one sentence per problem: the invariant that would have prevented the miss.
Before coding each one, say the pattern name and complexity out loud. This page is a timer, not a tutorial.
Warm-up MCQs
1. Which statement fits Number of Islands?
Invariant: “DFS floods everything reachable in one component; count how many times you must start a new flood. The grid itself is the adjacency list — mark visited in place.”
2. Bug: Clone Graph stores a clone after exploring neighbors. What breaks?
Invariant: “A hashmap from original node to its clone doubles as the visited set — create the clone on first visit, reuse it ever after.”
3. Kahn's queue empties before all courses are taken. What happened?
Invariant: “A dependency order exists iff the directed graph has no cycle — detect it with three-color DFS or Kahn's in-degree peeling.”
4. Bug: reverse flood walks from an ocean to lower neighbors. What fixes it?
Invariant: “Instead of asking where each cell drains, flood inward from each ocean and intersect the two reachable sets.”
5. Which first sentence makes Word Ladder a graph problem?
Invariant: “First decide what a node and an edge are — here words, one letter apart — then BFS finds the shortest unweighted path.”
6. Why is a normal BFS queue not enough for Network Delay?
Invariant: “Dijkstra is BFS with a priority queue: always settle the closest unsettled node, because no cheaper path to it can appear later.”
Self-check gate
Pass bar
You explained node, edge, traversal, and complexity before both attempts; Number of Islands marks each land cell once; Word Ladder uses BFS levels for the shortest unweighted path.
Fail path
If either timed attempt fails the pass bar, add that problem to the next revision queue with one line: WA: <root cause>. Re-solve it from a blank file before adding more graph problems.