Google Router Broadcast Reachability

Learning Outcome

Turn the Google Router Broadcast Reachability interview variant into a clear brute-force baseline, optimized pattern, and implementation plan.

Original Interview Statement

Routers are points. A powered router broadcasts to every router within range, then shuts down. Decide if source can reach destination.

Examples

Brute Force Approach

Simulate every possible message order recursively. It repeats states and does not add value because broadcasting all reachable neighbors is deterministic.

Optimized Approach

Build reachability on the fly with BFS. Distance is compared using squared values to avoid precision.

Exact Pseudocode

queue = [source]
visited[source] = true
while queue:
  u = pop
  if u == dest: return true
  for every unvisited router v:
    if dist2(u,v) <= range2: visit v
return false
  

Reference Code

from collections import deque

def can_reach(points, source, dest, radius):
    r2 = radius * radius
    q = deque([source])
    seen = {source}
    while q:
        u = q.popleft()
        if u == dest:
            return True
        x1, y1 = points[u]
        for v, (x2, y2) in enumerate(points):
            if v not in seen and (x1 - x2) ** 2 + (y1 - y2) ** 2 <= r2:
                seen.add(v)
                q.append(v)
    return False
  

Complexity

Edge Cases

• Source equals destination
• No routers in range
• Distance exactly equal to range

Follow-ups

• Precompute graph if many queries
• Spatial index for large n

Nearest Practice References

• Detonate the Maximum Bombs
• Number of Provinces

Common Mistakes

• Copying the nearest LeetCode solution without checking the changed rule.
• Skipping duplicate or boundary cases.
• Not stating the brute force before the optimized approach.