2 Проблемы

Кажется, одно из интервью Google, а другое — Microsoft. Первый.

Google. У нас есть N городов (N до 1000000) и число K. У каждого города есть координата x. Необходимо расположить K станций так, чтобы максимальное расстояние от города до ближайшей станции было минимальным.

Второй.

Майкрософт. Нам дан список из N элементов.

Мы знаем, что первый элемент там — «1».

У нас есть функциональный элемент getNext(element).

Как за время O(N) и память O(1) определить, содержит ли список циклы.

N не указано.

Пример: есть цикл — «1» -> «2» -> «3» -> и снова «1».

Вот еще один цикл: «1» -> «2» -> «3» -> «2».

На мой взгляд, у Microsoft задача повеселее.

Теги: #задачи #microsoft #Google #спортивное программирование

• Самуэльсон, Пол

  19 Oct, 24

• Получите Американский Ip-Адрес В Канаде Для Hulu И Hulu Plus.

  19 Oct, 24

• Яндекс.маркет Начал Борьбу С «Серыми» Товарами И Скрыл Цены На Все Смартфоны Moto G

  19 Oct, 24

• Вконтакте Закрыл Собственное Сми Об Интернет-Бизнесе Live Plus

  19 Oct, 24

• Модификация Поведения Электронного Устройства-Игрушки «Лего Супер Марио» Без Использования Официальных Костюмов.

  19 Oct, 24

• .Masterhost + Reg.ru =…

  19 Oct, 24

• Роскомнадзор Признал Хентай Детским Порно, Призывает Подавать Жалобы И Обещает Пополнить Реестр Запрещенных Ресурсов В Интернете

  19 Oct, 24

• Парадигма Резервного Копирования Netapp

  19 Oct, 24

• Давайте Ударим По Безграмотности

  19 Oct, 24

• Re:re: Готово На 95% Или «Путешествие Из Москвы В Питер»

  19 Oct, 24