Два мраморных камня и 100-этажное здание
Один из тех классических вопросов на собеседовании по программированию ...
Вам дают два шарика и говорят, что они сломаются при падении с определенной высоты (и предположительно не пострадают при падении с этой высоты). Затем вы попадаете в 100-этажное здание (предположительно выше определенной высоты) и просите найти самый высокий этаж, с которого вы можете уронить шарик, не разбивая его как можно эффективнее.
Дополнительная информация
- Вы должны найти правильный этаж (не возможный диапазон)
- Оба шарика гарантированно лопнут на одном этаже.
- Предположим, что на смену этажа у вас не требуется времени - учитывается только количество шариков.
- Предположим, что правильный этаж распределен в здании случайным образом.
Это довольно большое "ага!" фактор для тех, кто не изучал математику. Вопросы с "ага!" фактор исключительно плохи для собеседований.
@ Брэд Уилсон: это полностью зависит от интервью ... это отличный вопрос для проверки логического мышления и навыков решения математических задач.
В заголовке вопроса нет четкого указания: нужно ли нам найти максимальный этаж, с которого мы можем уронить шарик, не разбивая его, или, как подсказывает ответ, минимальное количество попыток добраться до этого этажа ...? !
Вам нужен алгоритм для эффективного поиска пола (который должен привести вас как к максимальному количеству падений, необходимых для вашего подхода, так и к набору шагов, как это сделать).
Ответы 10
Каждый из них ломается при падении с одинаковой высоты, или они разные?
Если они такие же, я иду на 50-й этаж и бросаю первый шарик. Если он не сломается, я иду на 75-й этаж и делаю то же самое, пока он не ломается, я продолжаю подниматься на 50% от того, что осталось. Когда он разбивается, я возвращаюсь на один выше, чем был раньше (поэтому, если он сломался на 75-м этаже, я возвращаюсь на 51-й этаж), бросаю второй шарик и поднимаюсь на этаж за раз, пока он не сломается, в этот момент я знаю самый высокий этаж, с которого я могу упасть без разрушения мрамора.
Наверное, не лучший ответ, мне любопытно посмотреть, как ответят другие.
Я лично не большой поклонник подобных вопросов-головоломок, я предпочитаю актуальные упражнения по программированию на собеседованиях.
Тем не менее, во-первых, это будет зависеть от того, могу ли я сказать, сломаны они или нет, с пола, на который я их бросаю. Я полагаю, что смогу.
Я бы поднялся на второй этаж, уронил первый шарик. Если бы он сломался, я бы попробовал первый этаж. Если бы он сломался, я бы знал, что это не пол.
Если бы первый не сломался, я бы пошел на 4-й этаж и упал оттуда. Если он сломается, я спущусь вниз и возьму другой шарик, а затем упаду на 3-й этаж, сломавшись или нет, я бы знал, какой предел.
Если ни один из них не сломался, я бы взял оба и проделал то же самое, на этот раз начиная с 6 этажа.
Таким образом, я могу пропустить любой второй этаж, пока не получу треснувший шарик.
Это было бы оптимизировано на случай, если мрамор сломается раньше ... Я полагаю, что, вероятно, есть оптимальное количество этажей, которое я мог бы пропустить, чтобы получить максимальную отдачу от каждого пропуска ... но тогда, если один сломается, мне придется проверять каждый этаж индивидуально с первого этажа над последним известным этажом ... что, конечно, было бы неприятно, если бы я пропустил слишком много этажей (извините, я не собираюсь сейчас определять оптимальное решение).
В идеале мне нужен целый мешок шариков, затем я мог бы использовать алгоритм двоичного поиска и делить количество этажей пополам с каждым падением ... но тогда вопрос был не в этом, не так ли?
Я думаю, что вопрос настоящий заключается в том, насколько точен вы хотите получить ответ. Потому что от этого действительно будет зависеть ваша эффективность.
Я собираюсь согласиться с Джастином, если вы хотите 100% точности на шариках, тогда, как только первый шарик сломается, вам придется подниматься на 1 этаж за раз с последнего известного «хорошего» этажа, пока вы не выясните, какой этаж является победитель." Можно даже добавить статистику и начать с 25 этажа вместо 50, чтобы в худшем случае было 24 вместо 49.
Если ваш ответ может быть плюс или минус этаж или два, возможно, есть некоторые оптимизации.
Во-вторых, ходьба вверх / вниз по лестнице влияет на вашу эффективность? В этом случае всегда бросайте оба шарика и поднимайте оба шарика при каждом движении вверх / вниз.
Здесь интересно то, как это можно сделать с минимальным количеством капель. Подняться на 50-й этаж и упасть первым будет катастрофой, если ломается 49-й этаж, в результате чего нам придется сделать 50 падений. Мы должны уронить первый шарик на этаж n, где n - максимальное количество требуемых падений. Если мрамор треснет на этаже n, возможно, после этого нам придется сделать n-1 капель. Если шарик не разбивается, мы поднимаемся на этаж 2n-1, а если он разбивается здесь, в худшем случае нам придется бросить второй шарик n-2 раз. Так продолжаем до 100 этажа и пробуем его разбить на 3н-2, 4н-3 ....
и n + (n-1) + (n-2) + ... 1 n = 14 Требуется максимальное количество капель
не могли бы вы объяснить причину уравнения n+(n-1)+(n-2)+...1 <=100?
@Geek говорит, что это наихудший из возможных исходов. Таким образом, вы пытаетесь сделать худший случай наихудшим для каждого из множества сегментов. Чтобы сохранить этот максимальный наихудший случай для каждого тестируемого сегмента, вы должны использовать на 1 падение меньше для каждого тестируемого сегмента. Проверьте первый сегмент при этом значении n, если он сломается, тогда проверьте от 1 до n-1. Таким образом, ваше окончательное максимальное количество падений равно 1 + (n-1) = n. Если он сломался не в n, а в 2n, то вы уже выполнили 1 сброс в n, поэтому, чтобы придерживаться худшего случая из n падений, у вас осталось только n-1. На 3n вы уже сделали 2 капли, так что, чтобы придерживаться худшего случая, оставьте n-2 капли.
По логике вещей, чем выше вы поднимаетесь, тем сильнее ударяется шарик о землю, поэтому вы начинаете с низкого уровня и постепенно поднимаетесь вверх. Таким образом, сегменты начинаются с низкого уровня и также растут. Чем больше сегментов вы тестируете, тем меньше остается падений, поэтому более высокие сегменты будут все меньше и меньше. Нижний отрезок самый большой, равен n. Каждый шаг вверх на один меньше, потому что вы продвигаетесь вверх.
Тогда цель состоит в том, чтобы минимизировать n. Вы можете выполнить это вручную, нанеся на диаграмму результаты каждого из них: n=100, n+(n-1)=100, n+(n-1)+(n-2)=100, n+(n-1)+(n-2)+(n-3)=100 и т. д. И т. Д. Измените каждое из этих уравнений на n=100, n=101/2, n=103/3, n=106/4. Продолжайте, значение n будет уменьшаться, пока не достигнет минимума, а затем после этого будет расти. Это минимальное решение является оптимальным. Решение - 13,64, но этажа 13,64 нет, поэтому 14. Количество требуемых сегментов совпадает с количеством членов, чтобы найти минимум, например n+(n-1) - это 2 члена ...
Я не могу редактировать этот первый комментарий. Эта часть неверна: «если бы она сломалась не в n, а в 2n». Извините, 2n неверен, он должен быть "но на n + (n-1)"
Бросьте первый шарик с 3-го этажа. Если он сломается, вы знаете, что это этаж 1 или 2, поэтому бросьте другой шарик с этажа 2. Если он не сломается, вы обнаружите, что этаж 2 самый высокий. Если он сломается, значит, этаж 1 самый высокий. 2 капли.
Если падение с 3-го этажа не разбивает мрамор, упадите с 6-го этажа. Если он сломается, вы знаете, что 4 или 5 этаж самый высокий. Бросьте второй шарик с этажа 5. Если он не разбился, вы обнаружили, что 5 - самый высокий. Если да, то 4 этаж - самый высокий. 4 капли.
Продолжать.
3 этажа - максимум 2 капли
6 этажей - максимум 4 капли
9 этажей - максимум 6 капель
12 этажей - максимум 8 капель
и Т. Д.
3 этажа - максимум 2 капли
Таким образом, для 99-этажного здания у вас будет максимум 66 капель. И это максимум. Скорее всего, у вас будет меньше капель. Да, и 66 - это тоже максимум для 100-этажного дома. Вам нужно всего 66 капель, если пол перерыва был 98 или 97. Если пол перерыва был 100, вы использовали бы 34 падения.
Даже если вы сказали, что это не имеет значения, для этого, вероятно, потребуется наименьшее количество ходьбы, и вам не нужно знать, насколько высоко здание.
Отчасти проблема в том, как вы определяете эффективность. Является ли более «эффективным» всегда иметь раствор менее чем в x каплях, или более эффективно иметь хорошие шансы получить раствор в количестве капель y, где y
Бросьте первый шарик на этаж 10, 20, 30 и т. д., Пока он не сломается, затем перепрыгните на последний известный этаж хороший и начните сбрасывать шарики оттуда по одному этажу за раз. В худшем случае 99 - это Magic Floor, и вы всегда можете найти его в 19 каплях или меньше.
Первое, что я бы сделал, это использовал мертвый простой алгоритм, который начинается с этажа 1, сбрасывает мрамор по одному этажу за раз, пока он не достигнет 100 или мрамор не расколется.
Тогда я бы спросил, зачем мне тратить время на оптимизацию, пока кто-то не покажет, что это будет проблемой. Слишком часто люди зацикливаются на поиске идеального сложного алгоритма, тогда как гораздо более простой решает проблему. Другими словами, не оптимизируйте вещи, пока это не понадобится.
Это может быть вопрос с подвохом, чтобы понять, относитесь ли вы к тем людям, которые могут сделать гору из кротового холма.
Даже если вы хотите использовать совершенно простой алгоритм, по крайней мере, используйте всю информацию, указанную в вопросе. У вас есть 2 шарика, но вы все еще используете только 1. Не позволяйте другому шарику сидеть и плакать: «Я пришел в этот мир, чтобы изменить ситуацию, а вы зря тратите мое существование :(»
Эта проблема рассмотрена в задаче 6.5 из книги «Cracking the Coding Interview (5-е)», решения которой резюмированы следующим образом:
Наблюдение:
Независимо от того, как мы отбрасываем Marble1, Marble2 должен выполнять линейный поиск. Например, если Marble1 перерывы между 10 и 15 этажами, мы должны проверить каждый этаж с помощью Marble2
Подход:
Первая попытка: Предположим, мы уронили Мрамор с 10 этажа, затем с 20,…
- В первом Мрамор ломается при первом падении (Этаж 10), тогда всего у нас есть не более 10 капель.
- Если первый мрамор разбивается на последней капле (этаж 100), то всего у нас будет не более 19 капель. (этажи с 1 по 100, затем с 91 по 99).
- Это неплохо, но все, о чем мы думаем, - это наихудший случай. Нам следует сделайте некоторую «балансировку нагрузки», чтобы уравновесить эти два случая.
Цель: Создайте систему сброса Marble1, чтобы максимальное количество требуемых падений было постоянным, независимо от того, ломается ли Marble1 при первом или последнем падении.
- Идеально сбалансированная система - это система, в которой капли мрамора1 + капли Marble2 всегда одинаков, независимо от того, где сломался Marble1.
- Для этого, поскольку каждая капля Marble1 делает еще один шаг, Marble2 допускается. на один шаг меньше.
- Следовательно, мы должны сократить количество шагов, потенциально требуемых Marble2, на один. падение каждый раз. Например, если Marble1 падает на этаж 20, а затем на этаж 30, Marble2 будет потенциально требуется сделать 9 шагов. Когда мы снова отбрасываем Marble1, мы должны уменьшить количество возможных шагов Marble2 до 8, например, мы должны сбросить Marble1 на 39 этаже.
- Поэтому мы знаем, что Marble1 должен начинаться с этажа X, затем подниматься на X-1 этажа, затем на X-2,…, пока не дойдет до 100.
- Решить относительно X + (X-1) + (X-2) +… + 1 = 100. X (X + 1) / 2 = 100 -> X = 14
Мы идем на 14-й этаж, затем на 27, затем на 39,… Это занимает максимум 14 шагов.
Код и расширение:
Для реализации кода вы можете проверить здесь.
Чтобы узнать о расширении до мрамора
Nи половM, ознакомьтесь с Глава 12: Загадка яиц и полов.
не могли бы вы прокомментировать обоснование уравнения на шаге 5 выше?
@Geek Вам просто нужно покрыть все 100 диапазонов с уменьшающимися диапазонами. Мы хотели сделать его сбалансированным, чтобы прыжки происходили по этажам: 14, 27, 39, 50, 60, 69, 77, 84, 90, 95. Каждый раз увеличивается на один этаж меньше. Таким образом, даже если мы уроним первую 10 раз, нам понадобится только 4 капли. 10 +4 = 14 точно так же, как если бы он сломался на первом этаже.
«Для этого, поскольку каждая капля Marble1 делает еще один шаг, Marble2 разрешается на один шаг меньше». . Я не понимаю этой части. Не могли бы вы объяснить?
@Dinaiz Totaldrops = Marble1Drops + Marble2Drops. Если вы хотите, чтобы значение TotalDrops оставалось неизменным (в худшем случае), тогда, когда Marble1Drops увеличивается, Marble2Drops должен уменьшаться. например Предположим, TotalDrops = 10. Если Marble1Drops = 1, то Marble2Drops = 9. Если Marble1Drops = 2, то Marble2Drops = 8 и так далее.
@Geek Вы можете начать с предположения о худшем x=100, т.е. вы собираетесь сделать 100 капель. Хуже 100 быть не может, ведь нужно тестировать только 100 этажей. Следующий шаг - попытаться разделить пространство пополам. то есть уронить примерно на полпути. Это вроде как 2x=100, но не совсем. Это действительно x+(x-1)=100, второй сегмент - x-1, потому что этажи - это два сегмента, которые будут тестироваться снизу вверх. Если шарик не сломан для первого сегмента, вы использовали 1 каплю, поэтому для верхнего сегмента оставьте на одну меньше. Чем больше сегментов, тем больше капель израсходовано. Они становятся меньше по мере того, как вы поднимаетесь.
Это можно сделать лучше всего с 7 шариками.
Итак, после проголосовавшего ответа, скажем, мрамор треснет как минимум на 49-м этаже.
- 50 этаж -> перерывы (от 1 до 50 включительно)
- 25 этаж -> не ломается (с 26 на 50)
- 37 этаж -> не ломается (с 38 на 50)
- 43 этаж -> не ломается (с 44 на 50)
- 46 этаж -> не ломается (с 47 на 50)
- 48 этаж -> не ломается (49 или 50)
- 49-й этаж -> разрывы (49-й, этот шаг действительно необходим, потому что это мог быть минимальный пол, на котором мрамор ломался, на 50-м)
Это можно представить как выполнение двоичного поиска в отсортированном наборе для некоторого k, где мы получаем половину пространства решений с каждой попыткой. Для 100 этажей нам понадобится log2 100 = 6,644 (7 попыток). Имея 7 мраморных плиток, мы можем быть уверены, что это минимальный пол, на который мрамор сможет разбить до 128 этажей.
Это была бы совсем другая проблема.
Проблема с вашим ответом заключается в том, что он НЕ гарантирует, что если яйцо разобьется, скажем, с 43-го этажа, тогда вы не узнаете, был ли пороговый этаж 38-м, 39-м ... 42-м. Также видеть это
Если вам нужно общее решение, которое даст вам результат для N этажей (в вашем случае N = 100), вы можете просто решить квадратное уравнение $ х ^ 2 + х-2 \ cdot (N-1) = 0 $, и результатом будет потолок положительного корня.
Который:
$$ f (N) = потолок \ bigg (\ frac {-1+ \ sqrt {1 + 4 \ cdot2 \ cdot (N-1))}} {2} \ bigg) $$
Вероятно, лучше не предполагать, что правильный этаж распределен случайным образом, а вместо этого просто придумать решение, минимизирующее худший случай.