Find nearest room; extend to two users

Q: Find nearest room; extend to two users

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

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.

Find nearest room; extend to two users

Overview

Comments (0)