Google Nearest Powered-on Router Follow-up

Learning Outcome

Turn the Google Nearest Powered-on Router Follow-up interview variant into a clear brute-force baseline, optimized pattern, and implementation plan.

Original Interview Statement

When a router broadcasts, only the nearest powered-on router or routers at the same nearest distance receive it.

Examples

Brute Force Approach

Reuse normal BFS edges to all in-range routers. That over-sends and violates the follow-up rule.

Optimized Approach

For each powered router that receives the message, scan remaining powered routers, find the minimum in-range distance, and enqueue all ties.

Exact Pseudocode

queue = [source]
powered = all routers
while queue:
  u = pop
  if u already off: continue
  turn u off
  if u == dest: return true
  find nearest powered routers within range
  enqueue every tie
return false
  

Reference Code

from collections import deque

def can_reach_nearest(points, source, dest, radius):
    r2 = radius * radius
    q = deque([source])
    powered = set(range(len(points)))
    while q:
        u = q.popleft()
        if u not in powered:
            continue
        powered.remove(u)
        if u == dest:
            return True
        x1, y1 = points[u]
        best = None
        targets = []
        for v in list(powered):
            x2, y2 = points[v]
            d = (x1 - x2) ** 2 + (y1 - y2) ** 2
            if d <= r2 and (best is None or d < best):
                best = d
                targets = [v]
            elif d == best:
                targets.append(v)
        q.extend(targets)
    return False
  

Complexity

Edge Cases

• Multiple nearest ties
• Nearest router already shut down
• No powered router in range

Follow-ups

• Use heap/spatial index
• What if simultaneous broadcasts reach same router?

Nearest Practice References

• BFS with dynamic state
• Nearest neighbor search

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.