Google Interview Question

Revision en1, by underdog., 2021-10-21 18:43:52

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?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English underdog. 2021-10-21 18:43:52 819 Initial revision (published)