### underdog.'s blog

By underdog., history, 7 weeks ago,

# Google Interview Question

Given a set of N routers in 2-D coordinate, a source router, a destination router. The problem is to find if it is possible to transmit a signal from source to destination under the following constrain-

1. Each router can transmit messages up to Euclidean distance K.

2. Each router will shut down after transmitting a message. (In simple words, each router can be used only once.)

3. N <= 1e5, K <= 10

I have tried to make a graph with nodes as routers and add edges between 2-routers if their Euclidean distance is less than or equal to K. Now, I use normal bfs to see if it is possible to reach the destination. But the problem is The time complexity in this solution is O(N*N). I need a better solution. Does any help please?

• +12

 » 7 weeks ago, # |   0 Are there any constraints on the coordinates of the routers?
•  » » 7 weeks ago, # ^ |   0 Coordinates can be upto 1e9.
 » 7 weeks ago, # |   +3 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)
 » 7 weeks ago, # | ← Rev. 4 →   +28 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)
•  » » 7 weeks ago, # ^ |   +6 Simple and nice solution. Thanks!
 » 7 weeks ago, # |   +15 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$.
•  » » 7 weeks ago, # ^ |   0 Can you please tell the O(N * (log(n))^2) solution too?