Вроде одна с собеседования Google, а другая с Microsoft.
Первая. Google.
У нас есть N городов (N до 1000000) и число K. У каждого города координата x. Надо расставить K станций так, что бы максимальное растояние от города до ближайшей к нему станции было минимально.
Вторая. Microsoft.
У нас дан список из N элементов. Мы знаем что первый там элемент «1». У нас есть функция element getNext(element). Как за время O(N) и память O(1) определить если ли в списке циклы. N не дано.
Пример: цикл есть — «1»->«2»->«3»-> и снова «1».
Вот еще цикл есть: «1»->«2»->«3»->«2».
На мой взгляд задача Microsoft веселей.
Первая. Google.
У нас есть N городов (N до 1000000) и число K. У каждого города координата x. Надо расставить K станций так, что бы максимальное растояние от города до ближайшей к нему станции было минимально.
Вторая. Microsoft.
У нас дан список из N элементов. Мы знаем что первый там элемент «1». У нас есть функция element getNext(element). Как за время O(N) и память O(1) определить если ли в списке циклы. N не дано.
Пример: цикл есть — «1»->«2»->«3»-> и снова «1».
Вот еще цикл есть: «1»->«2»->«3»->«2».
На мой взгляд задача Microsoft веселей.
