Maze Solver
Find the shortest path through a grid with obstacles, graph search with a bug → feature → scale arc.
Problem
A Maze is a 2D grid of cells (# wall, S start, E exit, lowercase = key, uppercase = locked door). The starter code has a bug.
Phase 1 — Fix the bug
Movement off the maze edge crashes — or worse, wraps around to the other side. Movement must never leave the grid.
Phase 2 — Feature
Implement shortestPath(): the shortest route from S to E, where a locked door can only be entered after collecting its key. Return the path as a list of coordinates, or null if unreachable.
Phase 3 — Scale
Mazes grow to very large sizes. BFS is correct; make sure your state — and the visited set — handles the key dimension without exploding.
What interviewers watch
Bounds-checking first, then the crucial insight: the visited state includes which keys you hold, not just the cell. The AI often gets the plain maze right and the keyed maze wrong.