Google Interview Question

Are there any constraints on the coordinates of the routers?

I think this might help Euclidean Minimum Spanning Tree You can also use a quad tree to find the nearest edges instead of generating them all. I think that would be O(n log n)

0-1 BFS should work, K is small. First put the source router in the queue then for each router, try to visit all nearest router such that the Euclidean distance <= K, there can be at most K*K (approx) nearest adjacent routers whose Euclidean distance <= K. Correct me If I am wrong. Time complexity will be O(N*K*K)

This problem can be solved with simple BFS if all coordinates are integers.

Store all coordinates in map of sets (key in map is $$$x$$$ coordinate, sets store $$$y$$$). Further you need common bfs. When you need add connected routers to queue you iterate by all suitable $$$x$$$ and find in respectives maps suitable $$$y$$$. After adding new router to the queue you remove it.

Foreach router we iterate by all suitable $$$x$$$. It's $$$O(K)$$$. Foreach $$$x$$$ we find all suitable $$$y$$$. It can be done in $$$O(log(n) + C)$$$, where $$$C$$$ is count of suitable $$$y$$$. Sum of all $$$C \le n$$$, because we remove router when we found it. Total complexity $$$O(N\cdot K \cdot log(n))$$$.

Also this problem can be solved in $$$O(N\cdot log^2(n))$$$ with some more complex data structures for non-integers coordinates or greater $$$K$$$.

for k <= 10

for a point (x , y)   , we can iterate over all possible (x1 , y1) 
such that (x1-x)^2 - (y1-y)^2 <= k^2

abs(x1 - x) <= k   or    x-k <= x1 <= x+k
                         y-k <= y1 <= y+k

Time Complexity :  n * 2k * 2k