Shortest Path in a Hidden Grid

Shortest Path in a Hidden Grid

What is this problem about?

The Shortest Path in a Hidden Grid interview question is an interactive problem where you control a robot on an unknown grid. You can call four API functions to move the robot: move(dir) which returns true if the move succeeded (cell is open) or false (cell is blocked), and you must navigate from a starting cell to a target cell. Find the shortest path to the target without knowing the grid in advance.

Why is this asked in interviews?

Meta and Bloomberg ask this interactive graph problem because it models real-world robotics and exploration algorithms: a robot with sensor-only navigation must map its environment and find the shortest path simultaneously. It tests DFS for exploration (map the grid) followed by BFS for shortest path computation — a complete search-then-plan architecture used in autonomous navigation systems.

Algorithmic pattern used

The pattern is DFS exploration followed by BFS pathfinding. Phase 1 — DFS to build the map: start from the initial position (treat as origin (0,0)). Try all 4 directions. If move(dir) returns true, mark the cell as open in a local grid, recurse, then backtrack (move in the opposite direction). If it returns false, mark as blocked. Also mark the target cell (when isTarget() returns true). Phase 2 — BFS on the mapped grid from (0,0) to the target cell. Return the BFS distance.

Example explanation

Hidden grid:

_ S _ _
_ _ 1 _
_ _ _ T

Robot starts at S. DFS explores all reachable cells, marking open/blocked. Target T discovered at relative position (2,2).

After DFS maps the reachable area, BFS from (0,0) to (2,2) finds shortest path: 4 steps (avoiding obstacle at (1,2)).

Common mistakes candidates make

• Not backtracking correctly during DFS — after recursing into a direction, always move back to restore position.
• Not marking visited cells during DFS — without tracking, the robot revisits cells endlessly.
• Running BFS on the hidden grid API directly — BFS doesn't support backtracking, so use DFS for exploration, BFS for shortest path.
• Confusing relative coordinates — track position relative to the starting cell using a delta (dx, dy) scheme.

Interview preparation tip

For the Shortest Path in a Hidden Grid coding problem, the DFS BFS matrix interactive interview pattern is the two-phase approach. The DFS exploration phase must include careful backtracking — practice the robot's movement: move forward, recurse, then move back. Bloomberg interviewers test the "always backtrack" discipline in DFS. Use a dictionary to store discovered cells by relative coordinate. After exploration, run standard BFS on the discovered map. This "explore then plan" pattern models the robot vacuum cleaner problem — a closely related interactive interview problem worth studying alongside this one.