Задачки на собеседованиях
1.У Вас есть два яйца неизвестной птицы, и есть доступ в стоэтажное здание. Каждое из яиц имеет скорлупу из неизвестного материала, оно может разбиться при падении с первого этажа, а может и не разбиться при падении с сотогоэтажа здания. Оба яйца одинаковы. Как определить, при падении с какого этажа яйцо разобьется? Нужно постараться определить этаж за минимальное количество тестов.
Решение.
Задачи на поиск очень любят спрашивать на собеседованиях фирмы, связанные с информационными технологиями, например Google и Intel если решите задачу, вам откроется секрет поиска информации в google.
Если бы в наличии было всего одно яйцо, то пришлось бы последовательного сбрасывать его с первого этажа, потом со второго, и далее до сотого, но у нас их два, поэтому используем второе для минимизации количества тестов. Будем делить оставшееся количество этажей пополам, сначала сбросим яйцо с 50-го этажа, если разбилось, значит оставшееся яйцо надо будет последовательно сбрасывать с 1-го по 49й этаж, если не разбилось, то бросаем его снова, с 75-го этажа, и так далее. В худшем случае 50 тестов.
Это первое решение, которое пришло в голову так ищет информацию Rambler, тут коварный HR-менеджер предложит Вам улучшить своё решение, и не спешите спорить с ним на бутылку водки, что это решение и так самое лучшее.
Как Вы уже поняли, самая медленная часть в этом решении - это линейный поиск по одному этажу, поэтому надо найти оптимальное кличество отрезков, на которое надо разделить здание, чтобы сократить поиск, используя второе яйцо.
Пусть X будет необходимое количество попыток. Таким образом, если одно яйцо разобьется, то оставшееся надо будет бросить X-1 раз. Если яйцо не разбилось, то на следующем этапе (если оно разобьется) на тесты с оставшимся яйцом останется X-2 попыток. Объясню на примере - Мы решили что оптимальное количество попыток всего 16, тогда бросаем одно яйцо с шестнадцатого этажа (уже одна израсходованная попытка), и если оно разбилось, то с помощью оставшегося проверяем 16-1=15 этажей. Если оно не разбилось, то у нас осталось в запасе 15 попыток, значит на следующем этапе нужно будет бросать яйцо (и еще одна попытка будет использована) с 16+15+1=32 этажа, так как если яйцо разобьется на 32м этаже, нам хватит 14 попыток чтобы проверить этажи с 17 по 31й.
Нам нужно найти, какое количество опытов будет оптимальным, это будет такое количество, при котором на заключительном этапе понадобится 0 экспериментов. Запишем это в виде последовательности:
(1+a) + (1+(a-1))+ (1+(a-2)) + ...+ (1+0) >= 100
Где 1+p это и будет то количество опытов, которое мы ищем, обозначим его X. Тогда X(X+1)/2 >=100 в нашем случае, надеюсь, Вы не забыли как решать квадратные уравнения?;) На случай, если забыли, ответ будет 14, соответственно одним яйцом (если оно не разбивается) будем проверять 14й, 27й, 39й, 50й, 60й, 69й, 77й, 84й, 90й, 95й, 99й, 100й этажи, если на одном из этапов яйцо разобьется, то проверим этажи, от максимального, где яйцо еще не билось, до того где оно разбилось.
Получаем результат - до 14 тестов.
Если бы в здании было 36 этажей, тогда X(X+1)/2>=36, решение было бы X=8, и проверить нужно будет 8, 15, 21, 26, 30, 33, 35, 36 этажи, пока яйцо не разобьется.
2. Есть 1000 бутылок вина. Достоверно известно, что одна бутылка отравлена. Надо вычислить, какая отравлена. На это есть 10 кроликов, можно пробовать вино на них. Яд на кроликов действует даже в микродозах, но действует не сразу, а на 5й - 7й день после приема. Надо за 8 дней найти отравленную бутылку. Кроликов не жалко, количество выпитого ими вина значения не имеет.
Решение.
Кролик имеет два состояния - жив или мертв (0 или 1), кроликов десять штук, это значит что в двоичной системе можно получить 1024 уникальных комбинации из живых и мертвых кроликов.
Пронумеруем бутылки в двоичной системе, всего у нас 1000 бутылок, значит на это хватит 10 разрядов:
0000000001=1
0000000010=2
0000000011=3
0000000100=4
0000000101=5
...
...
1111100110=998
1111100111=999
1111101000=1000
Кроликов нумеруем от одного до десяти.
Кроликов надо поить из тех бутылок, где в соответствующем разряде единица (или ноль, если так больше нравится, тогда все наоборот), например из первой бутылки пусть пьет только десятый кролик, а вот из 998й бутылки пусть пьют 1,2,3,4,5,8,9 кролики.
Напоили кроликов, ждем когда наступит день их гибели. Номера кроликов, которые отравились, подскажут нам разряды с "1" (или с "0", если поили нулевых).
То есть если погибли только 8й и 10й кролики, значит яд был в пятой бутылке.
3. У Вас есть наемный рабочий. Есть кусок золота, разделенный на семь соединенных сегментов. Вы должны давать рабочему по одному сегменту золота в день. Как оплатить ему семь рабочих дней, если отломать от куска золота можно только дважды?
Решение.
Делим кусок золота на три части следующим образом:
|=|
|=|=|
|=|=|=|=|
Первый день: Даем рабочему самый маленький кусочек.
Второй день: Даем рабочему кусок чуть больше (на два сегмента) и забираем первый кусок (маленький).Третий день: Даем рабочему самый маленький кусочек (теперь у него три сегмента есть).
Четвертый день: Отбираем у рабочего все золото, что давали и даем ему самый большой кусок (на четыре сегмента).
Пятый день: Вручаем рабочему маленький кусочек, в дополнение к самому большому.
Шестой день: Отбираем маленький кусок и вручаем двухсегментный. (у него на руках 6 сегментов)
Седьмой день: Отдаем обратно маленький кусочек.
Если нет ограничений на равенство сегментов, и форму куска золота, можно подумать над пересечением кривых (каждая кривая - форма разреза).
4. Есть пятеро пиратов, упорядоченных от 5 до 1. Главный пират имеет право предложить, как распределить 100 золотых монет между всеми. Но остальные потом голосуют за этот план, и если меньше половины пиратов соглашаются с ним, то его убивают, и следующий по порядку становится главным. Как должен пират распределить золото, чтобы максимально увеличить свою долю, но выжить при этом?
Решение
Все просто: начинаем размышлять не с начала, а с конца. Предположим, что пираты всегда голосовали против и дошло дело до того момента, когда их осталось двое (2-ый и 1-ый соответственно). В этой ситуации главный (2-ый пират) в любом случае будет труп, т.к. оставшийся второй пират (1-ый) всегда будет голосовать против (тогда он убивает главного и забирает себе все золото, согласно условию задачи). Таким образом 2-ому пирату нельзя доводить ситуацию до того момента, когда он станет главным. Поэтому в ситуации, когда их осталось трое (3-ий главный), 2-ый будет голосовать "за" при любом раскладе, т.к. жить хочется. Если пиратов осталось четверо (4-ой главный), то голос последнего пирата (1-ого) стоит 1 монету, т.к. больше он не получит в любом случае (если проголосует против, то их останется трое, а эту ситуацию я выше описал и в ней от голоса последнего ничего не зависит, т.к. 2-ый заведомо будет "за", что обеспечит большинство). Таким же образом и в нашей ситуации, когда пиратов пять, достаточно дать последнему 1 золотой, чтобы ему было выгодно голосовать "за" и предпоследнему дать 1 золотой, чтобы тот не доводил ситуацию до вышеописанной, когда он останется вживых, но не получит ничего. От голоса второго и третьего ничего зависеть не будет.
5. Есть 9 монет, одна из них фальшивая и по массе меньше остальных.
Есть двое весов, одни из них точные, другие не способны определить, какая монета фальшивая.
Как за три взвешивания определить фальшивую монету?
Более легкий вариант: 9 монет, одна легкая, одни весы и 2 взвешивания.
6. Перемножаем в программе три пары целых чисел: 2*7, 1234*4567 и 123456798*987654321. перемножение компьютер выполнит за одно и то же время или за разное? Если за разное, то как они будут отличаться? Второй вопрос после ответа: как на это будет влиять ОС?
7. Представьте себе, что вы участник игрового шоу и перед вами три двери. За одной из них стоит автомобиль, за двумя другими - козлы. Вы выбираете дверь №1, но ведущий (который знает, за какой дверью стоит машина), открывает другую дверь - к примеру, №3, и за ней стоит козел. После этого ведущий говорит: "Вам разрешается поменять свой выбор. Не хотите ли открыть дверь №2?" Ну, и вопрос задачи такой: какую дверь надо выбрать и почему?
Мэрилин выбрала дверь №2, потому что, по её мнению, её шансы выиграть в этом случае составляют 2 из 3, тогда как шансы двери №1 - 1/3. Этот ответ вызвал шквал писем от читателей, уличающих её в неправильной логике и утверждающих, что шансы оставшихся двух дверей абсолютно равны между собой (50 на 50, поскольку за одной дверью машина, а за другой козел). Причем среди критиков ее решения было много ученых, занимающихся естественными науками (математиков и т.п.).
8. «Привет!» - «Привет!» - «Как дела?» - «Хорошо. Растут два сына, дошкольника». - «А сколько им лет?» - «Произведение их возрастов равно числу голубей около этой скамейки». - «Этой информации мне недостаточно!» - «Старший похож на мать». - «Вот теперь я знаю ответ на свой вопрос!» Назовите возраст сыновей.
Решение.
Задачи на поиск очень любят спрашивать на собеседованиях фирмы, связанные с информационными технологиями, например Google и Intel если решите задачу, вам откроется секрет поиска информации в google.
Если бы в наличии было всего одно яйцо, то пришлось бы последовательного сбрасывать его с первого этажа, потом со второго, и далее до сотого, но у нас их два, поэтому используем второе для минимизации количества тестов. Будем делить оставшееся количество этажей пополам, сначала сбросим яйцо с 50-го этажа, если разбилось, значит оставшееся яйцо надо будет последовательно сбрасывать с 1-го по 49й этаж, если не разбилось, то бросаем его снова, с 75-го этажа, и так далее. В худшем случае 50 тестов.
Это первое решение, которое пришло в голову так ищет информацию Rambler, тут коварный HR-менеджер предложит Вам улучшить своё решение, и не спешите спорить с ним на бутылку водки, что это решение и так самое лучшее.
Как Вы уже поняли, самая медленная часть в этом решении - это линейный поиск по одному этажу, поэтому надо найти оптимальное кличество отрезков, на которое надо разделить здание, чтобы сократить поиск, используя второе яйцо.
Пусть X будет необходимое количество попыток. Таким образом, если одно яйцо разобьется, то оставшееся надо будет бросить X-1 раз. Если яйцо не разбилось, то на следующем этапе (если оно разобьется) на тесты с оставшимся яйцом останется X-2 попыток. Объясню на примере - Мы решили что оптимальное количество попыток всего 16, тогда бросаем одно яйцо с шестнадцатого этажа (уже одна израсходованная попытка), и если оно разбилось, то с помощью оставшегося проверяем 16-1=15 этажей. Если оно не разбилось, то у нас осталось в запасе 15 попыток, значит на следующем этапе нужно будет бросать яйцо (и еще одна попытка будет использована) с 16+15+1=32 этажа, так как если яйцо разобьется на 32м этаже, нам хватит 14 попыток чтобы проверить этажи с 17 по 31й.
Нам нужно найти, какое количество опытов будет оптимальным, это будет такое количество, при котором на заключительном этапе понадобится 0 экспериментов. Запишем это в виде последовательности:
(1+a) + (1+(a-1))+ (1+(a-2)) + ...+ (1+0) >= 100
Где 1+p это и будет то количество опытов, которое мы ищем, обозначим его X. Тогда X(X+1)/2 >=100 в нашем случае, надеюсь, Вы не забыли как решать квадратные уравнения?;) На случай, если забыли, ответ будет 14, соответственно одним яйцом (если оно не разбивается) будем проверять 14й, 27й, 39й, 50й, 60й, 69й, 77й, 84й, 90й, 95й, 99й, 100й этажи, если на одном из этапов яйцо разобьется, то проверим этажи, от максимального, где яйцо еще не билось, до того где оно разбилось.
Получаем результат - до 14 тестов.
Если бы в здании было 36 этажей, тогда X(X+1)/2>=36, решение было бы X=8, и проверить нужно будет 8, 15, 21, 26, 30, 33, 35, 36 этажи, пока яйцо не разобьется.
2. Есть 1000 бутылок вина. Достоверно известно, что одна бутылка отравлена. Надо вычислить, какая отравлена. На это есть 10 кроликов, можно пробовать вино на них. Яд на кроликов действует даже в микродозах, но действует не сразу, а на 5й - 7й день после приема. Надо за 8 дней найти отравленную бутылку. Кроликов не жалко, количество выпитого ими вина значения не имеет.
Решение.
Кролик имеет два состояния - жив или мертв (0 или 1), кроликов десять штук, это значит что в двоичной системе можно получить 1024 уникальных комбинации из живых и мертвых кроликов.
Пронумеруем бутылки в двоичной системе, всего у нас 1000 бутылок, значит на это хватит 10 разрядов:
0000000001=1
0000000010=2
0000000011=3
0000000100=4
0000000101=5
...
...
1111100110=998
1111100111=999
1111101000=1000
Кроликов нумеруем от одного до десяти.
Кроликов надо поить из тех бутылок, где в соответствующем разряде единица (или ноль, если так больше нравится, тогда все наоборот), например из первой бутылки пусть пьет только десятый кролик, а вот из 998й бутылки пусть пьют 1,2,3,4,5,8,9 кролики.
Напоили кроликов, ждем когда наступит день их гибели. Номера кроликов, которые отравились, подскажут нам разряды с "1" (или с "0", если поили нулевых).
То есть если погибли только 8й и 10й кролики, значит яд был в пятой бутылке.
3. У Вас есть наемный рабочий. Есть кусок золота, разделенный на семь соединенных сегментов. Вы должны давать рабочему по одному сегменту золота в день. Как оплатить ему семь рабочих дней, если отломать от куска золота можно только дважды?
Решение.
Делим кусок золота на три части следующим образом:
|=|
|=|=|
|=|=|=|=|
Первый день: Даем рабочему самый маленький кусочек.
Второй день: Даем рабочему кусок чуть больше (на два сегмента) и забираем первый кусок (маленький).Третий день: Даем рабочему самый маленький кусочек (теперь у него три сегмента есть).
Четвертый день: Отбираем у рабочего все золото, что давали и даем ему самый большой кусок (на четыре сегмента).
Пятый день: Вручаем рабочему маленький кусочек, в дополнение к самому большому.
Шестой день: Отбираем маленький кусок и вручаем двухсегментный. (у него на руках 6 сегментов)
Седьмой день: Отдаем обратно маленький кусочек.
Если нет ограничений на равенство сегментов, и форму куска золота, можно подумать над пересечением кривых (каждая кривая - форма разреза).
4. Есть пятеро пиратов, упорядоченных от 5 до 1. Главный пират имеет право предложить, как распределить 100 золотых монет между всеми. Но остальные потом голосуют за этот план, и если меньше половины пиратов соглашаются с ним, то его убивают, и следующий по порядку становится главным. Как должен пират распределить золото, чтобы максимально увеличить свою долю, но выжить при этом?
Решение
Все просто: начинаем размышлять не с начала, а с конца. Предположим, что пираты всегда голосовали против и дошло дело до того момента, когда их осталось двое (2-ый и 1-ый соответственно). В этой ситуации главный (2-ый пират) в любом случае будет труп, т.к. оставшийся второй пират (1-ый) всегда будет голосовать против (тогда он убивает главного и забирает себе все золото, согласно условию задачи). Таким образом 2-ому пирату нельзя доводить ситуацию до того момента, когда он станет главным. Поэтому в ситуации, когда их осталось трое (3-ий главный), 2-ый будет голосовать "за" при любом раскладе, т.к. жить хочется. Если пиратов осталось четверо (4-ой главный), то голос последнего пирата (1-ого) стоит 1 монету, т.к. больше он не получит в любом случае (если проголосует против, то их останется трое, а эту ситуацию я выше описал и в ней от голоса последнего ничего не зависит, т.к. 2-ый заведомо будет "за", что обеспечит большинство). Таким же образом и в нашей ситуации, когда пиратов пять, достаточно дать последнему 1 золотой, чтобы ему было выгодно голосовать "за" и предпоследнему дать 1 золотой, чтобы тот не доводил ситуацию до вышеописанной, когда он останется вживых, но не получит ничего. От голоса второго и третьего ничего зависеть не будет.
5. Есть 9 монет, одна из них фальшивая и по массе меньше остальных.
Есть двое весов, одни из них точные, другие не способны определить, какая монета фальшивая.
Как за три взвешивания определить фальшивую монету?
Более легкий вариант: 9 монет, одна легкая, одни весы и 2 взвешивания.
6. Перемножаем в программе три пары целых чисел: 2*7, 1234*4567 и 123456798*987654321. перемножение компьютер выполнит за одно и то же время или за разное? Если за разное, то как они будут отличаться? Второй вопрос после ответа: как на это будет влиять ОС?
7. Представьте себе, что вы участник игрового шоу и перед вами три двери. За одной из них стоит автомобиль, за двумя другими - козлы. Вы выбираете дверь №1, но ведущий (который знает, за какой дверью стоит машина), открывает другую дверь - к примеру, №3, и за ней стоит козел. После этого ведущий говорит: "Вам разрешается поменять свой выбор. Не хотите ли открыть дверь №2?" Ну, и вопрос задачи такой: какую дверь надо выбрать и почему?
Мэрилин выбрала дверь №2, потому что, по её мнению, её шансы выиграть в этом случае составляют 2 из 3, тогда как шансы двери №1 - 1/3. Этот ответ вызвал шквал писем от читателей, уличающих её в неправильной логике и утверждающих, что шансы оставшихся двух дверей абсолютно равны между собой (50 на 50, поскольку за одной дверью машина, а за другой козел). Причем среди критиков ее решения было много ученых, занимающихся естественными науками (математиков и т.п.).
8. «Привет!» - «Привет!» - «Как дела?» - «Хорошо. Растут два сына, дошкольника». - «А сколько им лет?» - «Произведение их возрастов равно числу голубей около этой скамейки». - «Этой информации мне недостаточно!» - «Старший похож на мать». - «Вот теперь я знаю ответ на свой вопрос!» Назовите возраст сыновей.