Лучший способ поиска значения насыщенности в отсортированном списке

Question

Вопрос от Математическая битва . Этот конкретный вопрос также задавался мне в одном из моих собеседований.

"У обезьяны есть два кокоса. Она дурачится, бросая кокос с балконов м-этажного дома. Обезьяна хочет знать нижний этаж, когда кокос сломан. Какое минимальное количество попыток необходимо для установления этого факта? «

Условия: если кокос сломан, вы не можете использовать его снова. Вы остаетесь только с другим кокосом

Возможные подходы / стратегии, которые я могу придумать:

• Двоичные разбиения, и как только вы найдете площадку, на которой кокосовые орехи используют пересчет с последнего найденного нижнего индекса двоичного разбиения.
• Окно / Срезы небольших наборов этажей и использование двоичного разбиения в Окне / Срез (но с другой стороны, для этого потребуется собственный алгоритм нарезки.)

Интересно, есть ли другие способы сделать это.

Answer 1

Подобные вопросы для интервью предназначены для того, чтобы понять, как вы думаете. Поэтому я бы, вероятно, упомянул решение O (N ^ 0.5), как указано выше, но я бы также дал следующее обсуждение ...

Поскольку у кокосов со временем могут появиться внутренние трещины, результаты могут быть не столь совместимы с решением O (N ^ 0,5). Хотя решение O (N ^ 0,5) является эффективным, оно не совсем надежно.

Я бы порекомендовал линейный раствор O (N) с первым кокосом, а затем проверил результат со вторым кокосом. Где N - количество этажей в здании. Итак, для первого кокоса вы попробуете 1-й этаж, затем 2-й, затем 3-й, ...

Если предположить, что оба кокоса имеют одинаковую конструкцию и расположены под одинаковым углом, то вы можете бросить второй кокос прямо на пол, который сломал первый. Назовите этот кокосовый ломающий пол B.

Для кокоса № 2 вам не нужно тестировать на 1..B-1, потому что вы уже знаете, что первый кокос не сломался на полу B-1, B-2, ... 1. Так вам нужно только попробовать это на B.

Если 2-й кокосовый орех разбивается о B, то вы знаете, что B - это слово, о котором идет речь. Если он не сломается, вы можете сделать вывод, что с течением времени произошли внутренние трещины и разрушение кокосового ореха и что тест с самого начала имеет недостатки. Вам нужно больше кокосов.

Учитывая, что размеры зданий довольно ограничены, дополнительная уверенность в вашем решении стоит решения O (N).

Как упоминал @ Rafał Dowgird, решение также зависит от того, является ли рассматриваемая обезьяна африканской или европейской обезьяной. Общеизвестно, что африканские обезьяны бросают с гораздо большей силой. Следовательно, точность разбивающего пола B становится точной только с отклонением +/- 2 этажа.

Чтобы обезьяна не устала от всех этих ступеней, было бы также желательно прикрепить веревку к первому кокосу. Таким образом, вам не нужно делать 1 + 2 + .. + B = B * (B + 1) / 2 лестничных марша для первого кокоса. Вам нужно будет только выполнить ровно B лестничных маршей.

Может показаться, что количество лестничных пролетов не имеет отношения к этой проблеме, но если обезьяна устает в первую очередь, мы можем никогда не прийти к решению. Это дает новые соображения для проблемы остановки .

Мы также предполагаем, что здание находится на земле и сила тяжести установлена ​​на уровне 9,8 м / с ^ 2. Мы также будем предполагать, что гравитационных волн не существует.

Answer 2

Бинарный поиск не является ответом, потому что у вас есть только один шанс переоценить. Бинарный поиск требует log m максимальных завышенных оценок.

Это двухфазный подход. Первый - перебирать полы с относительно большими ступенями. После первого кокосового перерыва вторая фаза - пробовать каждый этаж, начиная с последнего безопасного этажа.

Большие шаги примерно sqrt(m), но они больше раньше и меньше позже, потому что, если первый кокос сломается рано, вы можете позволить себе больше итераций на втором этапе.

StepSize = (minimum s such that s * (s + 1) / 2 >= m)
CurrentFloor = 0

While no coconuts broken {
    CurrentFloor += StepSize
    StepSize -= 1

    Drop coconut from CurrentFloor
}

CurrentFloor -= StepSize + 1

While one remains coconut unbroken {
    CurrentFloor += 1
    Drop remaining coconut from CurrentFloor
}

// CurrentFloor is now set to the lowest floor that will break the coconut, 
// using no more total drops than the original value of StepSize

Answer 3

Поскольку это вопрос интервью, рассмотрим

1. Дорогая операция - обезьяна идет вверх и вниз по лестнице, не бросая кокос. Думая об этом таким образом, «линейный» подход на самом деле N ² .

2. Энергия, передаваемая кокосу при падении, приблизительно пропорциональна высоте капли. Если оболочка сломана после поглощения некоторого количества энергии во ВСЕХ, она падает ...

Answer 4

Лучшее решение, которое я знаю, это 2 * sqrt (n). Бросьте первый кокос из sqrt (n), 2 * sqrt (n), ... до n (или пока он не сломается). Затем опустите второй из последней известной «безопасной» точки, с шагом в один этаж, пока он не сломается. Обе стадии занимают не более sqrt (n) бросков.

Редактировать: Вы можете улучшить константу в O (sqrt (n)), см. Комментарий по рекурсии. Я думаю, что первый шаг должен быть около sqrt (2 * n) и уменьшаться на 1 с каждым броском, так что последний шаг (если высота разрушения на самом деле n) равен ровно 1. Детали, которые читатели должны понять

Answer 5

Сложный вопрос для интервью. Это заняло у меня несколько дней.

Я считаю, что количество попыток в 1,5 раза превышает SQRT числа этажей. (На 100 этажей и 2 кокоса это 15)

Мы хотим минимизировать размер каждой попытки и количество попыток, используя оба вместе, чтобы покрыть все возможные этажи. В таких случаях sqroot оказывается хорошей отправной точкой, но мы варьируем размер каждой попытки и усредняем вокруг sqroot. Таким образом, мы получаем лучшее из обоих миров: равномерное распределение размера каждой попытки по всему корню дает нам наилучшие результаты. Для 100 и 2 это 15,14,13,12,11,10,9,8,7,6 Это работает в 1,5 раза 10.