Google L4 - Screening Interview Question

Problem: Robot Navigation with Circular Sensor Traps

You are given a 2D rectangular room of dimensions w × h (width × height). Inside the room are n security sensors, each located at a specific (x, y) coordinate and having a circular detection radius r.

The robot starts at the bottom-left corner (0, 0) and needs to reach the top-right corner (w, h). The robot can move in any direction, including diagonally or along a curved path, as long as it does not enter the detection zone (i.e., the circular area) of any sensor.

If the robot’s path touches or enters even one sensor’s detection zone, the alarm is triggered and the path is invalid.

Task
Implement a function:

def pathExists(positions: List[List[int]], w: int, h: int) -> bool:

• positions: A list of lists, where each element is [x, y, r], representing a sensor located at (x, y) with detection radius r.
• w: Width of the room.
• h: Height of the room.

Return:

• True if there exists a path from (0, 0) to (w, h) without entering any sensor's zone.
• False if all possible paths are blocked by sensor field

Solution:

1. Consider each sensor as a graph node.
   1. overlapping/touching sensors will have an edge between them
2. Identify sensors(nodes) whose radius crosses top/left boundary.
3. BFS/DFS through them and check if you came across any sensors whose radius crosses the other boundary such that it divides the room into 2 halves. -> Return False in this case.

Verdict: Selected for on-site rounds.