How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Snowflake.

What role is this question designed for?

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

Find Shortest Grid Path | Snowflake Coding Question

Find Shortest Grid Path

Company: Snowflake

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Quick Answer: This question evaluates a candidate's ability to implement and reason about grid-based shortest-path algorithms, covering graph traversal, state representation, and obstacle handling.

You are given an `m x n` grid where `0` represents an open cell and `1` represents a blocked cell. You are also given a start cell `(sr, sc)` and a target cell `(tr, tc)`. From any open cell, you may move one step up, down, left, or right, as long as the next cell is inside the grid and not blocked. Return the minimum number of moves required to reach the target from the start. If the target is unreachable, return `-1`. If the start equals the target (and is open), the answer is `0`. If either the start or the target cell is blocked, return `-1`. **Follow-up:** Describe how you could also solve the problem using recursive depth-first search with backtracking and memoization, and explain the tradeoffs compared with a breadth-first search approach. (BFS explores the grid level by level, so the first time it reaches the target is guaranteed to be along a shortest path; each cell is visited at most once, giving O(m*n) time. DFS with backtracking explores one path to its end before retreating, so to find the *shortest* path it must keep searching after the first hit and prune with the best-so-far distance; naive memoization is tricky because the shortest distance to a cell depends on the visited set along the current path, not just the cell coordinates, which can lead to exponential work or incorrect caching on grids with cycles.)

Constraints

1 <= m, n <= 1000
grid[i][j] is either 0 (open) or 1 (blocked)
0 <= sr, tr < m and 0 <= sc, tc < n
If the start or target cell is blocked, the answer is -1
Movement is only up, down, left, or right (no diagonals)

Examples

Input: ([[0,0,0],[0,1,0],[0,0,0]], 0, 0, 2, 2)

Expected Output: 4

Explanation: From the top-left to the bottom-right of a 3x3 grid with the center blocked; any shortest route around the obstacle takes 4 moves.

Input: ([[0,1],[1,0]], 0, 0, 1, 1)

Expected Output: -1

Explanation: The two open cells (0,0) and (1,1) are diagonal and separated by blocked cells; with only orthogonal moves the target is unreachable.

Input: ([[0]], 0, 0, 0, 0)

Expected Output: 0

Explanation: Start equals target on an open single cell, so zero moves are needed.

Input: ([[0,0,0,0],[1,1,1,0],[0,0,0,0]], 0, 0, 2, 0)

Expected Output: 8

Explanation: A wall on row 1 forces a detour to the right end of the grid and back down, costing 8 moves.

Input: ([[0,0],[0,0]], 0, 0, 1, 1)

Expected Output: 2

Explanation: An open 2x2 grid; the shortest path from a corner to the opposite corner is 2 moves.

Input: ([[0,1,0]], 0, 0, 0, 2)

Expected Output: -1

Explanation: A single-row corridor where the middle cell is blocked, cutting off the target.

Input: ([[1,0],[0,0]], 0, 0, 1, 1)

Expected Output: -1

Explanation: The start cell itself is blocked, so no path exists and the answer is -1.

Hints

Because every move has the same cost (1), the shortest path is exactly the BFS distance from the start cell — a uniform-cost grid is the textbook case for breadth-first search rather than Dijkstra.
Track a `visited` matrix so you never re-enqueue a cell; the first time BFS reaches the target is guaranteed to be along a shortest path.
Handle the corner cases up front: start == target returns 0, and a blocked start or target returns -1.
For the DFS follow-up, remember that the shortest distance to a cell depends on the path taken to get there (the current visited set), so a plain `dist[cell]` memo can be incorrect on grids with cycles — BFS sidesteps this entirely.

Quick Overview

This question evaluates a candidate's ability to implement and reason about grid-based shortest-path algorithms, covering graph traversal, state representation, and obstacle handling.