Extend a Maze Solver
Company: Meta
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
You are given an existing Python maze solver and a suite of unit tests. The maze is a 2D grid that uses `#` for walls, `.` for open cells, `S` for the start, and `E` for the exit. The current implementation uses BFS and reconstructs a path. Make the tests pass by fixing bugs and adding features in stages:
1. When printing the final path, mark path cells with `*` but do not overwrite `S` or `E`.
2. Prevent BFS from revisiting the same state indefinitely.
3. Support one-way chutes: a cell `>` can only be traversed from left to right, and a cell `<` can only be traversed from right to left.
4. Support keys and doors: collecting lowercase keys `a` to `z` allows passing through the matching uppercase doors `A` to `Z`. Because reachability changes after collecting keys, the visited structure must include both position and key set.
Return whether a path exists, and when requested reconstruct one valid path that satisfies all rules.
Quick Answer: This question evaluates competence in graph search and state-space modeling, specifically BFS-based pathfinding, constrained traversal rules (directional cells), and handling dynamic state such as collected keys and doors.