Ну, можна сказать, что это половина решения, причем вторая. В первой половине наиболее оптимально использовать бинарный поиск делением пополам, используя первое яйцо. Например, когда яйцо должно разбиться на 100м этаже. 1й раз Кидаем на 50м. Не разбилось. Значит кидаем с 50 + (50 mod 2) и тд 50 + (50 mod 2) + (25 mod 2) ... при этом скорость будет 1 + log 2 (N). Допустим яйцо разбивается на 70м этаже. Тогда на второй попытке (на 75м) первое яйцо разбивается. значит ответ между 50 и 74. Используем второе яйцо и предложеный вами линейный алгоритм. По времени занимает плюс ((N ост+1) mod 2)+1 Ну от части это так, но можна уточнить, например, что это будет ровно 1/4 от промежутка между 3 и 4. Тоесть в градусах по отношению к 3м - 360° / 12 / 4 = 7.5°. Как то так

Наверно мое не математическое образование меня подводит, но на сколько я знаю в "золотом сечении" е никак не учавствует, да и каким оброзом это будет быстрее?
Линейный алгоритм будет выигрывать (всего на один тик) только в первой половине. Так как на 50м первое яйцо разбивается, то начинаем со второго этажа линейный поиск одним яцом. Ближе к 100му этажу деление на два экспоненциально быстрее. Я извиняюсь за неточность, но в моем случае вопрос шел именно про градусы, про отметки это я тут дофантазировал, не точно сформулировал задачу. А градус можна довольно определенно, не вдаваясь во всякие неточности и погрешности часов, посчитать.

Вы учтите, что одно дело решать такие задачи сидя за компом. Другое дело, когда вы на собеседование под прицелом глаз и более двух-трех минут вам думать никто не даст. В большинстве случаев мозг отказывается логично думать и приходится надеятся только на природные инстинкты и безусловные рефлексы :) Мне чел который собеседовал, сказал что в 95% случаев на вопрос о часах кандидаты не думая отвечают - ровно на трех, 0 градусов ))

Вы видимо не дочитали мой пост. Вы должны комбинировать два алгоритма - бинарный поиск и линейный. Первый, чтобы быстро отсеч промежутки, где яйцо точно разбивается или не разбивается и линейный, чтобы точно определить этаж. В своих экстримах алгоритмы имеют преимущество однин над другим. Так, если яйцо разбивается на 100м, то бинарный поиск даст log 2 (N) + 1 достаточных операций, тоесть в нашем случае понадобиться только 8 бросаний, по сравнению с линейными 51. В случае с первым этажом бинарный поиск может только дать подсказку, что решение в первой половине, но применять бинарный алгоритм больше нельзя, и начиная со второго этажа используем сброс через этаж. Тоесть в этом случае у нас есть только одна лишняя операция, но, в среднем, комбинируя алгоритмы достигается оптимальный результат. В задаче есть явная подсказка - наличие двух яиц. Так как для кидания через этаж достаточно было бы только одного яйца...

Честно говоря, это первый и надеюсь единственный раз, когда меня такое спрашивали и конечно я к такому не был готов. Про часы мне чисто повезло в плане, что я знал, что это точно не ноль, осталось только додумать как это посчитать. Про люк я больше пытался полить водичку, ответа я не знал и догадаться про такое считаю нереальным. Вопрос про яйца показывает знание простых алгоритмов и я бы сказал, ответ на него есть в какой то мере показательным.
Ну а вообщем, такие вопросы несуть цель не услышать 100% правильный ответ, а то как у вас работает мышление в направлении решения задачи, поставленной в экстримальных условиях и не обязательно давать четкий и отчеканений ответ. Главное не молчать, а рассуждать. Если ваши логичные рассуждения привели вас к правильно ответу - вам плюс, нет - ну хоть пытались. Задачи на самом деле простые, и никаких сверх познаний не требуют, но поставленные в такой критический час могут сбивать с толку. А теперь еще и добавте, что разговор идет на английском языке :)

Ну, мы отталкиваемся от того, что мы не знаем заранее какие будут входные данные, но алгоритм должен работать и работать быстро.

Всем известны так называемые хєш-таблицы алгоритм которых используются в словарях (dictionary, map, etc). Это как раз и есть наша задача с яйцами. Суть в том, что ключ словаря, помимо самого значения ключа, возвращает так называемый хэшкод (целое число), который может быть не уникальным для разных значений ключа, но для более оптимального использования словаря значения должны иметь хороший диапазон уникальных значений. Словарь использует внутренний массив значений отсортированых хешей ключей и ассоциацию с букетом значений (на самом деле все немного сложнее, но не буду залазить в дебри). Так, для поиска значения по ключу применяем бинарный алгоритм поиска в массиве используя хеш. Далее, получив список ключей, которые возвращают одно и то же значение хеша искуемого, один за одним перебираем линейно и сравниваем уже действительное значение ключа.

В случае, когда ключи возвращают одинаковый хеш - вот вам экстрим, когда Словарь будет не эффективен, так как каждый раз будет проходить полный скан всех ключей (вариант, когда яйцо разбивается на 49 том этаже). При другом экстриме, когда все ключи возвращают уникальный хеш, Словарь будет работать очень быстро (яйцо разбивается на 100м этаже). Так как заранее не известно, на сколько хеши ключей в словаре будут уникальны, то и алгоритм должен быть более менее универсальным

Кстати, насколько мне известно, бинарный поиск используется в базах данных при поиске значения по существующему индексу (по b-деревьям) и используется именно основа 2 (а не "е"), так как используя деление на два, можна применять не математическую операцию деления, а более оптимальную для CPU - смещенние (сдвиг) битов вправо на одну позицию - 100 >> 1 = 50 .. 50 >> 1 = 25...