как сбросить яйцо с 3 этажа чтобы оно не разбилось
Собеседование для программиста — как решить задачу Google про бросание яиц со здания
Марцин Москала рассказал об алгоритмическом подходе к решению любых задач на примере задачи с собеседования в Google.
Собеседование для программиста — отличный опыт, в ходе него возникает много отличных задач. Моя любимая задача также нравится и рекрутерам Google:
Вы работаете в 100-этажном здании и у вас есть два одинаковых яйца. Вам нужно определить наивысший этаж, с которого можно уронить яйцо и не разбить его. Найдите алгоритм, который минимизирует количество бросков в худшем сценарии развития событий.
Мы можем сделать несколько предположений:
Многие люди написали алгоритм для решения этой задачи (и мы напишем свой), но здесь есть простое решение.
Простой ответ
Простой способ получить минимальный этаж — начать бросать яйцо с первого этажа, потом со второго и так далее. Когда яйцо разобьется, мы будем знать, что это этаж, который мы ищем. Это надежный способ, но в худшем случае он потребует 100 бросков.
Важно заметить, что это единственный доступный алгоритм, когда у вас есть только одно яйцо. Поэтому вам нужно начать использовать его, когда вы разобьете первое яйцо.
Интуитивный ответ
Наше первое яйцо нужно использовать, чтобы разделить сто этажей на более мелкие диапазоны как можно эффективнее. Тогда первое яйцо нужно бросить с 1/n этажа, например, ⅓. Тогда алгоритм будет выглядеть так:
В худшем случае для ⅓ (33, 24,…) — это 33. Так мы можем найти идеальный n, который оптимизирует количество бросков при помощи динамического программирования. Это хорошее решение, которое показывает программистское мышление, но оно не является оптимальным.
Идеальное решение
Чтобы понять идеальное решение, нам нужно понять равенство, которое используется для вычисления количества бросков в худшем случае:
Где F(n) — это следующий этаж, с которого мы бросаем первое яйцо.
Если мы введем такую переменную:
То равенство будет выглядеть так:
Оптимальным решением является такое, когда все аргументы этой максимальной функции равны. Как этого достичь? Если смотреть с конца, последним D(n) должно быть 1, потому что так мы дойдем до точки, в которой для первого яйца останется только один этаж. Тогда D(n-1) должна быть равна 2, потому что она отличается одним броском первого яйца.
Если первое яйцо в последний раз сбросить с 99 этажа, то до этого мы получим 99-2=97, 97-3=94, 90, 85, 79, 72, 64, 55, 45, 34, 22 и 9 этажи. Это оптимальное решение! Так, в худшем случае, нам нужно будет сделать 14 бросков (меньшая разница равна 13, но нам нужно сделать ещё один бросок с 9 этажа).
Собеседование для программиста: проверка
Ок, у нас есть решение, и мы можем вычислить его без посторонней помощи. Время проверить его правильность. Для этого мы напишем простую программу на Kotlin. Сначала выразим, как посчитать количество бросков для какого-либо решения. Когда у нас есть 2 или меньше этажей, нам нужно сделать столько бросков, сколько осталось этажей. В ином случае мы должны использовать уже представленное равенство:
Мы использовали функцию bestMaxThrows. Это гипотетическая функция, которая возвращает количество бросков, если следующие решения идеальны. Вот как мы можем её определить:
Мы делегировали обязанность оптимизации следующего этажа функции bestNextStep. Она дает нам лучший следующий шаг. Мы можем определить её просто — когда осталось 2 этажа или меньше, мы бросим яйцо с первого этажа. В ином случае нам нужно проверить все варианты и выбрать оптимальный.
Эта функция использует maxThrows, поэтому у нас возникает повторение. Это не проблема, потому что, когда bestNextStep вызывает MaxThrows, она всегда вызывает ее со значением меньше, чем floorsLeft (потому что nextFloor всегда больше нуля). Перед использованием добавим буферизацию для ускорения вычислений:
Теперь мы можем проверить, возвращает ли функция тот же результат, что мы вычислили:
Хороший ответ. Проверим следующие шаги:
Результат: 9, 22, 34, 45, 55, 64, 72, 79, 85, 90, 94, 97, 99, 100, как мы и вычислили.
Большая перспектива
Теперь у нас есть хороший алгоритм для решения похожих проблем. Например, мы можем немного изменить его, чтобы вычислить количество бросков в самом вероятном сценарии. Мы можем проверить, как минимальное число бросков будет зависеть от высоты здания. Вот график с ответом на этот вопрос:
Заключение
Теперь вы лучше подготовлены, может быть собеседование для программиста в Google пройдет проще, но, что важнее, вы лучше знакомы с общим алгоритмическим мышлением. Этот алгоритм представляет хороший функциональный подход, который можно использовать для разных проблем в нашей работе.
Логические задачи и головоломки
Как может брошенное яйцо пролететь три метра и не разбиться?
Ответ: Главное бросать его так, чтобы оно летело больше 3 метров (например, подкинуть вверх), тогда оно разобьется не когда пролетит 3м, а когда упадет.
Комментарии
яйцо не разобьется-если бросать его сразу с курицей, тобишь внутри оно
Ну-ну не факт что не разобьется =)
не яйцо надо завернуть в прочную ёмкость и дело в шляпе правда я не проверел
А мы ккк то с другом кидали яйцо, он короче со всей дури замахнулся и пнул куриное яйцо! Оно мало того, что не разбилось, дак еще подлетело на пять метров в высоту и 4-дальность, упало хоть и в навоз, но сухой и все равно не разбилось! Мы повторили и замарали кеды)))
Я,конечно,точно не знаю.Но-откуда ты знаешь,на сколько метров бросаешь это дурацкое яйцо. Можно бросить и вверх,и в длину!Главное-замахнуться хорошо,чтоб далеко полетело.Оно по-любому разобьется,только если его сварить и почистить-раскрошится.И число 3 здесь просто так взяли.Могли ведь взять и 5,и 10.И зачем его вобще кидать.
брошeнноe яйцо нe можeт дaжe пролeтeть,оно жe брошeнноe,eго дaжe кинуть нe кто нe можeт,т.к нeкому
я это знаю надо бросить с 5 метров тогда первые 3 метра оно пролетит целым
Сила поверхносного натяжения против нас (Проверено)
Или если бросать яйцо на толстый слой пароллона
да ну.Зачем его в паралон кидать?
надо подбросить яйцо вверх
а лучше вообще не кидать)))
Мне кажется что реальней его кинуть вврх на три метра
Как сбросить яйцо с 3 этажа чтобы оно не разбилось
JavaRush запись закреплена
Логическая задача на измерение высоты разбивания яйца
/*Дано 100-этажное здание. Если яйцо сбросить с высоты N-го этажа (или с большей высоты), оно разобьется. Если его бросить с любого меньшего этажа, оно не разобьется. У вас есть два яйца. Найдите N за минимальное количество бросков.
*/
Обратите внимание, что независимо от того, с какого этажа мы бросаем яйцо №1, бросая яйцо №2, необходимого использовать линейный поиск (от самого низкого до самого высокого этажа) между этажом «повреждения» и следующим наивысшим этажом, при броске с которого яйцо останется целым. Например, если яйцо №1 остается целым при падение с 5-го по 10-й этаж, но разбивается при броске с 15-го этажа, то яйцо №2 придется (в худшем случае) сбрасывать с 11-го,12-го,13-го и 14-го этажей.
Предположим, что мы бросаем яйцо с 10-го этажа, потом с 20-го…
Если яйцо №1 разбилось на первом броске (этаж 10-й), то нам в худшем случае приходится проделать не более 10 бросков.
Если яйцо №1 разбивается на последнем броске (100-й этаж), тогда у нас впереди в худшем случае 19 бросков (этажи 10-й, 20-й, …, 90-й, 100-й, затем с 91-го до 99-го).
Это хорошо, но давайте уделим внимание самому плохому случаю. Выполним балансировку нагрузки, чтобы выделить два наиболее вероятных случая.
Как и в других задачах максимизации/минимазиции, ключом к решению является «балансировка худшего случая».
Разбор взят из книги Гейл Л. Макдауэлл «Cracking the Coding Interview»
Мастерство не пропьёшь
Головоломки и задачи на сообразительность
воскресенье, 3 апреля 2011 г.
Два яйца и небоскрёб
Ещё одна довольно известная задача, которую включают почти во все сборники задач с собеседований в Гугл.
У вас есть доступ в 100-этажный небоскрёб и 2 идентичных яйца неизвестной птицы. Никаких данных о прочности скорлупы нет: яйцо может разбиться, упав с первого этажа, а может остаться целым, упав с сотого.
Очевидно, что для того, чтобы сделать не более K бросков, первый бросок должен быть не выше чем с K-го этажа. В самом деле, если мы сбросим первое яйцо с этажа M>K, и оно разобьётся, у нас не будет иного выхода кроме как методично проверять все этажи подряд начиная с первого и заканчивая M-1. В худшем случае мы проверим M-1 этажей, что в сумме с первым броском даст M>K бросков. Очевидно также, бросать в первый раз ниже чем с K-го этажа нет смысла.
Итак, в первый раз мы бросаем с этажа K. Если яйцо разбилось, то за K-1 попыток мы проверим все K-1 нижних этажей. Если же нет, у нас останется K-1 бросок в запасе на верхние этажи.
Рассуждая аналогично, мы должны будем совершить второй бросок с этажа K+(K-1). Если яйцо разобьётся, нам нужно будет проверить этажи с K+1 по 2*K-2, которых всего K-2, что в сумме с двумя первыми бросками даст искомые K бросков.
Следовательно, для того чтобы небоскрёб из N этажей можно было проверить за K бросков, должно выполняться условие K*(K+1)/2>=N. В случае N=100 получается K>=14.
Таким образом, нам нужно сделать в худшем случае 14 бросков. До тех пор, пока первое яйцо не разбивается, мы бросаем его с этажей 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100. Если оно разбивается, например, на 69-м этаже, мы начинаем бросать второе яйцо со всех этажей начиная с 61-го, т.е. с первого непроверенного.
10 cамых хитрых головоломок задаваемых при приеме на работу
Ведущие компании используют различные способы для того, чтобы отобрать из массы желающих нужного кандидата на ту или иную вакансию. Один из них — головоломка.
Для Вас мы подготовили топ-рейтинг самых популярных головоломок, задаваемых на собеседованиях в различных компаниях. Предлагаем Вам попробовать свои силы:
1.Что нужно крикнуть с окна/балкона/любого людного места, чтобы все услышали, но ни один человек после этой фразы не обернулся в эту сторону?
2. Среди пшеничного поля нашли мертвого мужчину, крепко сжимавшего в руках спичку. Отчего он умер?
3.Можно ли бросить сырое яйцо так, чтобы оно пролетело 3 метра и не разбилось?
4. Назовите самое большое число.
5. Есть ли 7 ноября в Австралии?
6. У большинства из нас 1 голова, на гербах мы видим часто по 2, у Змея Горыныча было 3, а у кого было больше 1000 голов?
7. Если бы вы вас уменьшили до размера карандаша и положили бы в блендер, что бы вы предприняли?
8. Чего у кошки 3, у собаки 3, у петуха 8, у лошади 5, у кукушки 4, у лягушки 3? Вопрос в том, сколько у осла?
9. Концы веревки завязаны в виде петель. Эти петли одеваются на левую и правую руки. Как завязать на веревке узел, не снимая петель с рук?
Так зачем же нужны все эти головоломки? Головоломки на собеседовании – это хорошая возможность проверить кандидата на сообразительность и смекалку.
Для кандидата же – это хороший шанс проявить себя, тем более, как показало исследование, отгаданная головоломка в разы увеличивает шансы на получение желаемой должности. Служба исследований нашей компании провела опрос и выяснила, что 25% работников разгадывали на собеседованиях головоломки. 73% опрошенных отметили, что успешно справились с поставленной задачей, и половине из них предложили дальнейшее трудоустройство. Среди тех, кто с головоломкой не справился, получила деловое предложение лишь пятая часть.
Чаще всего головоломки достаются айтишникам (34%), топ-менеджерам (33%), консультантам (33%) и финансистам (33%), реже – представителям сфер «Наука/Образование» (9%) и «Искусство/Развлечения/Масс-медиа» (9%).
80% респондентов понимают, что головоломки нужны для того, чтобы проверить гибкость мышления и аналитические способности, 29% считают, что их предназначение в том числе – в проверке на стрессоустойчивость, 6% полагают, что таким образом HR-менеджер просто хотел над ними поиздеваться, а еще столько же сами не знают, чего собственно от них хотели.
Несмотря на то, что наиболее популярными задачками на сообразительность являются вопросы из тестов на IQ, математические и логические ребусы, некоторые HR-менеджеры предлагают соискателям более экзотические задания: например, просят нарисовать несуществующее животное или экспромтом придумать стихотворение.
Ниже представлены примеры подобных головоломок.
«Бутылка и пробка стоят 11 копеек. Бутылка дороже пробки на 10 копеек. Сколько стоит пробка?»
«Арбуз на 99% состоит из воды. Представьте, что вода испарилась и осталось 90%. Как изменилась масса арбуза? Задача старая, но на момент собеседования я ее не знал».
«Какие 10 плюсов у полиэтиленового пакета?»
«Написать рецепт изготовления яичницы для совершенно неумелого человека».
Головоломки на собеседованиях работают только в руках знающего специалиста. Это лишь инструмент, который может как помогать рекрутеру или потенциальному руководителю составить объективное мнение о кандидате, так и запутать, причем как в одну, так и другую сторону. Полагаю, что если точно не понимать, как применять такой инструмент и что он может дать на выходе, то лучше пока его отложить. Инструмент ради инструмента – это типичная ошибка многих специалистов, не важно, в какой сфере – HR, маркетинг или любой другой.
Правильные ответы.
1. Так что же нужно крикнуть, чтобы никто не обернулся?
Вариант 1: Сынок, пора домой!
Вариант 2: В наше время можно крикнуть «Помогите!»
2. Про мертвого мужчину:
Мужчина летел в самолете с тремя попутчиками. Мотор заглох, самолет начал падать. Пассажиры обнаружили, что на четверых есть всего три парашюта и стали тянуть спички. Один из них вытянул короткую и вынужден был прыгать без парашюта.
3. Про сырое яйцо.
Главное бросать его так, чтобы оно летело больше 3 метров (например, подкинуть вверх), тогда оно разобьется не когда пролетит 3м, а когда упадет.
4. Самое большое число – 31.(календарное) Мыслите шире.
5. Конечно в Австралии есть 7 ноября.
Если встречается очевидный вопрос, отвечайте увереннее.
6. Понятное дело, что не нужно пытаться вспомнить чудо-юдо, у которого больше 1000 голов. Опять же, мыслите шире и креативнее, больше 1000 голов было у Пеле.
7. Про блендер.
Когда вопросы ставятся абстрактно, это автоматически означает, что ответ может быть таким же абстрактным. Например, таким: «Написал бы на стенке блендера «Вытащите меня отсюда!», и меня бы спасла домохозяйка». Не нужно говорить, «попытался бы выпрыгнуть или вскарабкаться вверх», это примитивно.
9. Про веревку.
Порядок действий: 1) правой рукой делаем перекрещенную петлю посередине веревки и держим её; 2) левую руку вдеваем в петлю, как бы завязывая узел так, чтобы браслет на левой руке оказался внутри петли; 3) пропускаем петлю под браслетом и вытягиваем её из под него; 4) левую руку вынимаем из этой петли, отпускаем веревку и растягиваем её. Получаем узел. Убедитесь сами.