Extend BFS maze solver with keys and arrows

Q: Extend BFS maze solver with keys and arrows

This question evaluates mastery of breadth-first search, state-space modeling for grid-based traversal, and handling augmented states like keys and one-way tiles, testing competency in algorithm design and correctness within the Coding & Algorithms domain (graph algorithms).

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Q: What difficulty level is this interview question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Meta.

Q: What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Meta during technical interviews.

Question

Loading...

Problem

You are given a rectangular maze represented as a 2D grid of characters. Implement and iteratively fix/extend a solver that finds a shortest path from S (start) to E (exit).

Movement is 4-directional (up/down/left/right) unless restricted by special tiles.

Base tiles

# = wall (cannot enter)
. = empty cell
S = start
E = exit

Additional tiles (introduced by later failing tests)

< : from this cell, you may move only left on the next step
> : from this cell, you may move only right on the next step
a - f : keys you can pick up by entering the cell
A - F : locks; you may enter only if you already have the corresponding key (e.g., a opens A )

Tasks (the test suite reveals issues incrementally)

Fix output formatting: implement a required print /render function for the maze and/or found path exactly as specified by the function contract (e.g., return a string with newline-delimited rows; if a path is found, overlay it using * except on S / E ).
Fix BFS correctness: ensure your BFS does not revisit states incorrectly (record visited properly).
Support one-way tiles: update neighbor generation to handle < and > .
Support keys and locks: update BFS to include collected keys as part of the state.

Input/Output

Implement a function with the following behavior (language-agnostic):

Input: grid: string[] (each string is a row)
Output: the length of the shortest path from S to E (number of moves), or -1 if unreachable.
Additionally, implement any required helper(s) such as render(grid, path) depending on the harness.

Constraints

1 <= rows, cols <= 200
Grid contains exactly one S and one E .
Keys are limited to a - f (at most 6 distinct keys).