2 tasks
It seems like one from a Google interview, and the other from Microsoft.
First one. Google
We have N cities (N up to 1,000,000) and the number K. Each city has an x coordinate. It is necessary to arrange K stations so that the maximum distance from the city to the station nearest to it would be minimal.
The second one. Microsoft
We have a list of N items. We know that the first element there is "1". We have an element getNext (element) function. As for the time O (N) and memory O (1) determine if there are cycles in the list. N is not given.
Example: there is a cycle - “1” -> “2” -> “3” -> and again “1”.
There is another cycle: “1” -> “2” -> “3” -> “2”.
In my opinion, the task of Microsoft is more fun.
First one. Google
We have N cities (N up to 1,000,000) and the number K. Each city has an x coordinate. It is necessary to arrange K stations so that the maximum distance from the city to the station nearest to it would be minimal.
The second one. Microsoft
We have a list of N items. We know that the first element there is "1". We have an element getNext (element) function. As for the time O (N) and memory O (1) determine if there are cycles in the list. N is not given.
Example: there is a cycle - “1” -> “2” -> “3” -> and again “1”.
There is another cycle: “1” -> “2” -> “3” -> “2”.
In my opinion, the task of Microsoft is more fun.