Блог пользователя underdog.

Автор underdog., история, 2 года назад, По-английски

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
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Are there any constraints on the coordinates of the routers?

»
2 года назад, # |
  Проголосовать: нравится +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)

»
2 года назад, # |
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)

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    Simple and nice solution. Thanks!

  • »
    »
    10 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    How is the nearest adjacent routers whose Euclidean distance <= K be at most K*K. Because for all i from 1 to K euclidean distance, there would be i*i possible positions.

    And how would you compute those adjacent?

»
2 года назад, # |
  Проголосовать: нравится +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$$$.