Quick Overview

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

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.

Hints

  1. Equal move cost means an unweighted graph: BFS, not Dijkstra, finds shortest distances.
  2. Mark cells visited the moment you enqueue them so you never revisit, and never step onto a wall (value 1).
  3. The first dequeued cell whose value is 2 is a nearest room — return immediately.
  4. 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.

Hints

  1. Run one BFS per user to get full distance maps; do not run a fresh search per room.
  2. Use -1 to mark unreachable cells so a single check (d1 != -1 and d2 != -1) enforces 'reachable by both'.
  3. After both BFS runs, scan every room cell once and minimize d1 + d2.
  4. 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.

Loading coding console...