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.

    Also popular now: