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 Google.

What role is this question designed for?

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

Compute distance to nearest taxi in grid

Q: Compute distance to nearest taxi in grid

This question evaluates understanding of graph traversal and shortest-path reasoning on grids, algorithmic problem-solving for computing distances from many targets, and the ability to manage time and space complexity on large inputs.

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given an `R x C` grid representing a city map. - `grid[r][c] = 1` means there is a taxi located at cell `(r, c)`. - `grid[r][c] = 0` means the cell is empty. - You can move from a cell to its 4-directional neighbors (up/down/left/right). Each move costs 1. Return an `R x C` matrix `dist` where `dist[r][c]` is the length of the shortest path from cell `(r, c)` to **any** taxi. If a cell cannot reach any taxi, set its distance to `-1`. ### Input - `grid`: a 2D array of 0/1 integers ### Output - `dist`: a 2D array of integers ### Constraints (typical interview bounds) - `1 <= R, C <= 2000` (or any size where an `O(R*C)` solution is expected) - There may be `0` taxis or many taxis. ### Follow-ups 1. Is DFS an appropriate alternative here if we want shortest distances? Why or why not? 2. What changes if movement is allowed in 8 directions instead of 4?

Quick Answer: This question evaluates understanding of graph traversal and shortest-path reasoning on grids, algorithmic problem-solving for computing distances from many targets, and the ability to manage time and space complexity on large inputs.

Part 1: Distance to Nearest Taxi with 4-Directional Movement

You are given a rectangular grid representing a city map. A value of 1 means a taxi is located in that cell, and a value of 0 means the cell is empty. From any cell, you may move up, down, left, or right, and each move costs 1. Return a matrix of the same size where each cell contains the shortest distance to any taxi. If there are no taxis reachable from a cell, return -1 for that cell. In this grid without obstacles, this only happens when there are no taxis.

Constraints

0 <= len(grid) <= 2000
If grid is non-empty, all rows have the same length C and 0 <= C <= 2000
grid[r][c] is either 0 or 1
An O(R*C) solution is expected

Examples

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

Expected Output: [[2,1,2],[1,0,1],[2,1,2]]

Explanation: The only taxi is in the center, so each distance is the Manhattan distance to the center.

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

Expected Output: [[0,1,2,1],[1,2,1,0],[2,3,2,1]]

Explanation: Each cell takes the smaller distance to either taxi.

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

Expected Output: [[-1,-1],[-1,-1]]

Explanation: There are no taxis, so every cell has distance -1.

Input: ([],)

Expected Output: []

Explanation: An empty grid has an empty distance matrix.

Input: ([[1]],)

Expected Output: [[0]]

Explanation: The only cell already contains a taxi.

Hints

Instead of running a search from every empty cell, start from all taxi cells at once.
Breadth-first search processes cells in increasing distance order when all moves cost 1.

Part 2: Compare Naive DFS with the True Nearest Taxi Distance

A developer proposes using depth-first search from a cell and stopping as soon as a taxi is found. This coding task demonstrates why that approach is not reliable for shortest distances. Given a grid, a starting cell, and a fixed DFS neighbor order, compute two values: the distance returned by the naive DFS that stops at the first taxi it reaches, and the true shortest distance to any taxi using 4-directional movement. Return both values as a two-element list.

Constraints

0 <= len(grid) <= 1000
If grid is non-empty, all rows have the same length C and 0 <= C <= 1000
grid[r][c] is either 0 or 1
If grid is non-empty, start is expected to be a valid cell
neighbor_order is a permutation of UDLR
An O(R*C) solution is expected

Examples

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

Expected Output: [3,1]

Explanation: DFS goes down and right first, reaching the taxi at (1,2) in 3 moves, but the nearest taxi is at (0,1) in 1 move.

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

Expected Output: [1,1]

Explanation: The DFS tries right first and immediately finds the nearest taxi.

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

Expected Output: [-1,-1]

Explanation: There are no taxis in the grid.

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

Expected Output: [0,0]

Explanation: The starting cell already contains a taxi.

Input: ([], [], 'UDLR')

Expected Output: [-1,-1]

Explanation: The empty-grid edge case has no reachable taxi.

Hints

DFS follows one branch deeply before considering other nearby branches, so the first taxi found may not be the closest one.
To reproduce recursive DFS iteratively, store each stack frame with the next neighbor index to try.

Part 3: Distance to Nearest Taxi with 8-Directional Movement

You are given a rectangular grid representing a city map. A value of 1 means a taxi is located in that cell, and a value of 0 means the cell is empty. From any cell, you may move to any of its 8 neighboring cells: up, down, left, right, or diagonally. Each move costs 1. Return a matrix of the same size where each cell contains the shortest 8-directional distance to any taxi. If there are no taxis reachable from a cell, return -1 for that cell.

Constraints

0 <= len(grid) <= 2000
If grid is non-empty, all rows have the same length C and 0 <= C <= 2000
grid[r][c] is either 0 or 1
Diagonal movement is allowed and costs the same as horizontal or vertical movement
An O(R*C) solution is expected

Examples

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

Expected Output: [[1,1,1],[1,0,1],[1,1,1]]

Explanation: With diagonal movement, every surrounding cell is one move from the center taxi.

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

Expected Output: [[0,1,2,3],[1,1,2,3],[2,2,2,3]]

Explanation: Distances from the top-left taxi follow 8-directional movement, equivalent to Chebyshev distance in an open grid.

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

Expected Output: [[2,2,1,0],[1,1,1,1],[0,1,2,2]]

Explanation: Each cell uses the closer of the two taxis under 8-directional movement.

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

Expected Output: [[-1,-1,-1]]

Explanation: There are no taxis, so all distances are -1.

Input: ([],)

Expected Output: []

Explanation: An empty grid has an empty distance matrix.

Hints

The multi-source BFS idea still works; only the neighbor list changes.
Initialize the queue with every taxi at distance 0, then expand into all 8 directions.

Quick Overview

This question evaluates understanding of graph traversal and shortest-path reasoning on grids, algorithmic problem-solving for computing distances from many targets, and the ability to manage time and space complexity on large inputs.