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.

Solve Matrix and Array Distance Problems | Snowflake Coding Question

Quick Overview

This question evaluates competency in graph traversal and shortest-path reasoning for grid-based problems as well as array-based distance computation and nearest-neighbor reasoning, testing skills in mapping problems to appropriate data structures, traversal algorithms, and algorithmic complexity analysis.

Solve Matrix and Array Distance Problems

Company: Snowflake

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are asked to solve two coding problems. ### Problem 1: Shortest Path in a Binary Matrix Given an `m x n` matrix containing only `0` and `1`: - `0` represents an open cell that can be entered. - `1` represents a blocked cell that cannot be entered. You are also given a start cell `(sr, sc)` and a target cell `(tr, tc)`. From any cell, you may move one step up, down, left, or right. Return the minimum number of steps required to move from the start cell to the target cell without entering any blocked cell. If the target is unreachable, return `-1`. Be prepared to explain why breadth-first search is appropriate for this problem and how it differs from depth-first search for finding the shortest path in an unweighted grid. ### Problem 2: Distances Between Values in an Array Given an array containing only `0`, `1`, and `2`, compute distances involving the positions of `1`s and `2`s. A precise version of the task is: For every index whose value is `1`, return the distance to the nearest index whose value is `2`. If there is no `2` in the array, return `-1` for that `1`. The distance between indices `i` and `j` is `abs(i - j)`.

Quick Answer: This question evaluates competency in graph traversal and shortest-path reasoning for grid-based problems as well as array-based distance computation and nearest-neighbor reasoning, testing skills in mapping problems to appropriate data structures, traversal algorithms, and algorithmic complexity analysis.

Part 1: Shortest Path in a Binary Matrix

Given a binary grid, where 0 represents an open cell and 1 represents a blocked cell, find the minimum number of steps needed to move from a start cell to a target cell. From a cell, you may move one step up, down, left, or right. You may not move outside the grid or enter blocked cells. Return the length of the shortest valid path in steps. If the target cannot be reached, return -1. If the start and target are the same open cell, return 0.

Constraints

0 <= len(grid) <= 200
If grid is non-empty, 0 <= len(grid[0]) <= 200
All rows in grid have the same length
Each grid cell is either 0 or 1
start and target are pairs of integer coordinates
Movement is allowed only in four directions: up, down, left, and right

Examples

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

Expected Output: 4

Explanation: One shortest path is right, right, down, down.

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

Expected Output: 6

Explanation: The middle column blocks the direct route, so the path must go around the bottom.

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

Expected Output: 0

Explanation: The start is already the target.

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

Expected Output: -1

Explanation: Both possible first moves are blocked, so the target is unreachable.

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

Expected Output: -1

Explanation: An empty grid has no valid cells.

Hints

Because every move has the same cost, explore cells in increasing distance from the start.
Use a queue and mark cells visited when you add them to the queue to avoid revisiting cells.

Part 2: Distances Between Values in an Array

Given an array containing only 0, 1, and 2, compute a result list for the indices whose value is 1. For every index i where arr[i] == 1, return the distance to the nearest index j where arr[j] == 2. The distance between two indices is abs(i - j). If there is no 2 in the array, return -1 for each 1. The output distances should appear in the same order as the 1s appear in the original array.

Constraints

0 <= len(arr) <= 200000
Each element of arr is one of 0, 1, or 2
The result contains one entry for each occurrence of 1 in arr
Distance is measured as absolute index difference

Examples

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

Expected Output: [2, 1]

Explanation: The 1 at index 0 is distance 2 from the nearest 2, and the 1 at index 4 is distance 1 from the 2 at index 5.

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

Expected Output: [1, 1]

Explanation: The 1 at index 1 is nearest to index 0, and the 1 at index 5 is nearest to index 4.

Input: ([1])

Expected Output: [-1]

Explanation: There is one 1 but no 2.

Input: ([])

Expected Output: []

Explanation: There are no 1s, so the result is empty.

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

Expected Output: []

Explanation: There are no indices whose value is 1.

Hints

The positions of all 1s and all 2s are naturally sorted if you scan the array from left to right.
As you move through the positions of 1s from left to right, the nearest 2 position never needs to move backward.

Quick Overview