Google Nearest Powered-on Router Follow-up | DSA Interview Patterns - Study Chapter | QuizMaker

Course

DSA Interview Patterns Roadmap

Topic

Company Asked Variants

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

bool canReachNearest(vector<pair<int,int>>& points, int source, int dest, int radius) {
    long long r2 = 1LL * radius * radius;
    queue<int> q;
    vector<int> powered(points.size(), 1);
    q.push(source);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (!powered[u]) continue;
        powered[u] = 0;
        if (u == dest) return true;
        long long best = LLONG_MAX;
        vector<int> targets;
        auto [x1, y1] = points[u];
        for (int v = 0; v < points.size(); v++) if (powered[v]) {
            auto [x2, y2] = points[v];
            long long dx = x1 - x2, dy = y1 - y2;
            long long d = dx * dx + dy * dy;
            if (d <= r2 && d < best) best = d, targets = {v};
            else if (d == best) targets.push_back(v);
        }
        for (int v : targets) q.push(v);
    }
    return false;
}

public static boolean canReachNearest(int[][] points, int source, int dest, int radius) {
    long r2 = 1L * radius * radius;
    boolean[] powered = new boolean[points.length];
    Arrays.fill(powered, true);
    Queue<Integer> q = new ArrayDeque<>();
    q.add(source);
    while (!q.isEmpty()) {
        int u = q.poll();
        if (!powered[u]) continue;
        powered[u] = false;
        if (u == dest) return true;
        long best = Long.MAX_VALUE;
        List<Integer> targets = new ArrayList<>();
        for (int v = 0; v < points.length; v++) if (powered[v]) {
            long dx = points[u][0] - points[v][0];
            long dy = points[u][1] - points[v][1];
            long d = dx * dx + dy * dy;
            if (d <= r2 && d < best) {
                best = d;
                targets.clear();
                targets.add(v);
            } else if (d == best) {
                targets.add(v);
            }
        }
        q.addAll(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.

Tags

• dsa
• coding interview
• java
• c++
• python
• no-js
• company-asked-variants