2 puzzles
It seems one with Google interview, and another with Microsoft.
The first. Google.
We have N cities (N up to 1000000) and the number K. Each city has a x coordinate. It is necessary to arrange K stations so that the maximum distance from the city to the nearest station would be minimal.
The second. Microsoft.
')
We have a list of N items. We know that the first element there is "1". We have the element function getNext (element). As for O (N) time and O (1) memory, determine if there are cycles in the list. N is not given.
Example: there is a cycle - “1” -> “2” -> “3” -> and again “1”.
Here is another cycle: “1” -> “2” -> “3” -> “2”.
In my opinion, the task of Microsoft is more fun.
The first. Google.
We have N cities (N up to 1000000) and the number K. Each city has a x coordinate. It is necessary to arrange K stations so that the maximum distance from the city to the nearest station would be minimal.
The second. Microsoft.
')
We have a list of N items. We know that the first element there is "1". We have the element function getNext (element). As for O (N) time and O (1) memory, determine if there are cycles in the list. N is not given.
Example: there is a cycle - “1” -> “2” -> “3” -> and again “1”.
Here is another cycle: “1” -> “2” -> “3” -> “2”.
In my opinion, the task of Microsoft is more fun.
Source: https://habr.com/ru/post/11405/
All Articles