Shortest Path to Get Food

Shortest Path to Get Food

What is this problem about?

The Shortest Path to Get Food interview question gives you a character matrix where '*' is your starting position, '#' represents walls, 'O' represents empty cells, and 'X' represents food. Find the shortest path (minimum number of steps) from '*' to any food cell 'X'. If no food is reachable, return -1. This is a standard multi-target BFS problem.

Why is this asked in interviews?

Meta, DoorDash, Google, and Bloomberg ask this problem because it tests multi-target BFS — finding the shortest path to ANY occurrence of a target cell type. This models real-world navigation to the nearest service point: finding the nearest coffee shop, charging station, or exit. It evaluates whether candidates can identify BFS as the correct algorithm (shortest path in unweighted grid) and handle multiple valid destinations.

Algorithmic pattern used

The pattern is BFS from the source to the nearest target. Find the starting position '*' and initialize the BFS queue. Expand in 4 directions. Skip walls ('#') and already-visited cells. When any 'X' cell is reached, immediately return the current BFS distance. If the queue is exhausted without reaching any 'X', return -1.

Example explanation

Grid:

X O O O
O # # O
* O O X

Start: (2,0). Food at: (0,0) and (2,3).

BFS from (2,0):

• Level 1: (1,0) [blocked by #], (2,1).
• Level 2: (2,2).
• Level 3: (2,3) = 'X'! Distance = 3.

Also: (0,0) reachable via longer path. Nearest food is at distance 3.

Common mistakes candidates make

• Running BFS to both food cells separately and taking the minimum — standard BFS from the source naturally finds the nearest target first.
• Forgetting to handle the case where '*' or 'X' doesn't exist — return -1 if no start or no food found.
• Not marking cells as visited when adding to the queue — causes exponential revisits.
• Using DFS instead of BFS — DFS finds a path but not necessarily the shortest.

Interview preparation tip

For the Shortest Path to Get Food coding problem, the BFS matrix interview pattern for nearest-target search is the approach. The key insight: BFS guarantees that the first time you reach any target cell is via the shortest path. DoorDash and Meta interviewers use this to test BFS vs DFS understanding — be ready to explain why BFS is correct here. Practice the "BFS to nearest of multiple targets" pattern — it's the same as multi-source BFS in reverse (single source, multiple targets). Both patterns appear frequently in grid navigation and facility location problems.