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

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Snapchat during technical interviews.

Find nearest room; extend to two users | Snapchat Coding Question

Find nearest room; extend to two users

Company: Snapchat

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

You are given an m×n grid where 1 is a wall (impassable), 0 is an empty cell, and 2 is a meeting room. From a starting coordinate [r, c], you may move up, down, left, or right with cost 1 per step. Return the coordinates of the closest meeting room reachable from the start; if none are reachable, return [-1, -1]. Use the example grid [[0,0,1,0],[0,2,1,0],[0,2,1,0]] with start [0,0] where the expected output is [1,1]. Discuss your algorithm and time/space complexity. Follow-up: given two starting users s1 and s2, return the meeting room that minimizes the sum of their shortest-path distances (consider only rooms reachable by both) and also return that minimum total distance. Explain your approach and complexity.

Quick Answer: This question evaluates competency in grid-based shortest-path algorithms, graph traversal, reachability analysis, and distance aggregation for multiple sources.

Nearest Meeting Room (BFS)

You are given an `m x n` grid where `1` is a wall (impassable), `0` is an empty cell, and `2` is a meeting room. Starting from coordinate `[r, c]`, you may move up, down, left, or right with cost 1 per step (you cannot step onto walls). Return the coordinates `[row, col]` of the closest meeting room reachable from the start. If no room is reachable, return `[-1, -1]`. Because every move costs 1, the grid is an unweighted graph, so a Breadth-First Search from the start visits cells in nondecreasing distance order. The first cell with value `2` that BFS dequeues is a closest room. If multiple rooms are tied for the minimum distance, the one returned is the first reached in BFS order using the neighbor order down, up, right, left. Example: for grid `[[0,0,1,0],[0,2,1,0],[0,2,1,0]]` and start `[0,0]`, the output is `[1,1]`.

Constraints

1 <= m, n <= 1000
grid[i][j] is one of 0 (empty), 1 (wall), 2 (meeting room)
start is within bounds; if start is on a wall, return [-1, -1]
If the start cell itself is a room (value 2), distance is 0 and that cell is returned

Examples

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

Expected Output: [1, 1]

Explanation: From [0,0], BFS reaches room [1,1] at distance 2; the rooms in column 1 are the only reachable rooms (column 2 is a wall).

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

Expected Output: [2, 2]

Explanation: The only room is at [2,2], reachable around the central wall at distance 4.

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

Expected Output: [-1, -1]

Explanation: Walls completely seal off the room at [0,2] from the start, so no room is reachable.

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

Expected Output: [0, 0]

Explanation: The start cell itself is a room, so distance is 0 and [0,0] is returned.

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

Expected Output: [-1, -1]

Explanation: There are no rooms anywhere in the grid, so the answer is [-1, -1].

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

Expected Output: [0, 2]

Explanation: The start cell is a room, returned immediately at distance 0.

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

Expected Output: [2, 0]

Explanation: From [2,2], room [2,0] is distance 2 while room [0,2] is sealed behind walls (distance 6), so [2,0] is closest.

Hints

Equal move cost means an unweighted graph: BFS, not Dijkstra, finds shortest distances.
Mark cells visited the moment you enqueue them so you never revisit, and never step onto a wall (value 1).
The first dequeued cell whose value is 2 is a nearest room — return immediately.
Handle the edge cases: start on a wall, start already on a room, and no room reachable at all (return [-1, -1]).

Best Meeting Room for Two Users (Min Distance Sum)

Same grid encoding as before: `1` is a wall, `0` is empty, `2` is a meeting room, and moves cost 1 step in the four cardinal directions. Now you are given two starting coordinates, `s1` and `s2`. Return the meeting room that minimizes the sum of the two users' shortest-path distances to it, considering only rooms reachable by BOTH users, together with that minimum total distance. Return the answer as `[[row, col], totalDistance]`. If no room is reachable by both users, return `[[-1, -1], -1]`. Approach: run one BFS from each start to compute every cell's shortest distance (`-1` for unreachable cells). Then scan all room cells; for each room reachable by both (`d1 != -1` and `d2 != -1`), compute `d1 + d2` and keep the minimum. Ties are broken by row-major scan order (smallest row, then smallest column). Example: for grid `[[0,0,1,0],[0,2,1,0],[0,2,1,0]]` with `s1 = [0,0]` and `s2 = [2,0]`, room `[1,1]` gives total distance `2 + 2 = 4`, the minimum, so the output is `[[1,1], 4]`.

Constraints

1 <= m, n <= 1000
grid[i][j] is one of 0 (empty), 1 (wall), 2 (meeting room)
s1 and s2 are within bounds (each may coincide with a room or with each other)
Only rooms reachable by BOTH users are candidates
Ties in total distance are broken by row-major order (smallest row, then column)

Examples

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

Expected Output: [[1, 1], 4]

Explanation: Room [1,1] is distance 2 from each user (total 4); room [2,1] is distance 3 + 1 = 4 as well but [1,1] wins on row-major order.

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

Expected Output: [[0, 0], 6]

Explanation: Both corner rooms give total 2 + 4 = 6; the tie is broken by row-major order, so [0,0] is returned.

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

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

Explanation: The two rooms in the top row are walled off from the bottom row where both users start, so no room is reachable by either user.

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

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

Explanation: Both users start on the only room, so the total distance is 0.

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

Expected Output: [[0, 0], 6]

Explanation: Room [0,0] costs 2 + 4 = 6; room [0,2] costs 4 + 2 = 6; tie broken row-major to [0,0].

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

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

Explanation: There are no rooms in the grid, so no room is reachable by both users.

Hints

Run one BFS per user to get full distance maps; do not run a fresh search per room.
Use -1 to mark unreachable cells so a single check (d1 != -1 and d2 != -1) enforces 'reachable by both'.
After both BFS runs, scan every room cell once and minimize d1 + d2.
If no room is reachable by both, the answer is [[-1, -1], -1] — initialize the best total to -1 and only update on a valid candidate.

Quick Overview

This question evaluates competency in grid-based shortest-path algorithms, graph traversal, reachability analysis, and distance aggregation for multiple sources.