Minimum Path Cost in a Hidden Grid

Minimum Path Cost in a Hidden Grid

What is this problem about?

The Minimum Path Cost in a Hidden Grid problem is an interactive challenge where you are placed at a starting cell of an unknown grid. You can move in four directions using API calls, and each move has an associated cost. You need to find the minimum-cost path from the start to the target without knowing the grid layout in advance. The Minimum Path Cost in a Hidden Grid coding problem tests graph traversal with incomplete information.

Why is this asked in interviews?

Meta and Google use this problem to evaluate whether candidates can adapt classical shortest-path algorithms to interactive, black-box environments. The skill of working with APIs that reveal the world incrementally — a common scenario in robotics, game AI, and real-time navigation — is directly tested. The shortest path, BFS, DFS, and heap interview pattern is central, and the interactive constraint adds significant difficulty.

Algorithmic pattern used

The main pattern is Dijkstra's algorithm on a dynamically explored graph. Use DFS or BFS first to map out reachable cells by making API moves, recording costs. Once the graph is partially or fully explored, apply Dijkstra's to find the shortest path. A priority queue (min-heap) guides exploration toward lower-cost frontiers. Since the grid is hidden, you must explore cells using move/unmove to backtrack.

Example explanation

Imagine you start at position (0,0). You call move(NORTH) and it returns a cost of 3. You call move(EAST) from (0,0) and get cost 5. You continue exploring and build an adjacency map. After DFS completes, Dijkstra finds that the cheapest route to target (2,2) costs 12, using the path through NORTH twice and EAST once.

Common mistakes candidates make

• Forgetting to undo moves (backtrack) after exploring a direction.
• Not memoizing visited cells, leading to infinite recursion.
• Confusing grid coordinates after multiple moves.
• Running Dijkstra before the full graph is explored.

Interview preparation tip

For interactive graph problems, practice separating two phases: exploration (DFS with backtracking to build the graph) and optimization (Dijkstra on the built graph). Treat the API as a black box and focus on correct state tracking. Draw the graph on paper as you simulate exploration to catch bugs early. Knowing Dijkstra with a min-heap fluently is essential for all shortest-path interview patterns.