Собеседование: логические задачи (часть 1)
Бывало ли с вами такое, что во время собеседования вам дают решить задачу на логику, а вы совершенно не готовы к такого рода вопросам и в голову, как назло, ничего не приходит? Чувствуя, что повисло неловкое молчание, вы лихорадочно пытаетесь выдавить что-то похожее на описание решения задачи. Спустя некоторое время интервью заканчивается, и, выходя из офиса, вы понимаете, что знаете как решается задча!
Ok, если вы сейчас ищете работу, то вам повезло. Эта статься содержит подборку наиболее распространенных логических вопросов с собеседований в ведущие IT-компании, так что Вам будет на чем попрактиковаться для предстоящих интервью.
У вас есть два ведра, одно емкостью 5 литров, а другое емкостью 3 литра. Вы должны отмерить 4 литра с помощью этих двух ведер. Как вы это сделаете?
Решение
Эта головоломка часто встречается среди вопросов на логику во время собеседования.
У вас есть две веревки одинаковой длины. Обе эти веревки сгорают полностью за 1 час.
Вы должны отметрить 1,5 часа, при помощи сжигания этих веревки. Учтите, что веревки имеют неравномерную толщину. То есть, может случиться так, что 60% веревки сгорят в течение получаса, а остаток — также сгорит в течение получаса.
Решение
Как только первая веревка сгорит полностью, возьмите вторую веревку и подожгите ее с одного конца. Она сгорит ровно за 1 час.
Таким образом, мы можем отмерить полтора часа, используя обе веревки.
У вас есть 8 шаров одинакового цвета и размера. Один из шаров тяжелее остальных, остальные имеют одинаковый вес. Вам дают чашечные весы. За сколько взвешивания вы сможете узнать, какой из шаров является более тяжелым чем все остальные?
Решение
Первое решение:
Разделите шары на 2 группы по 4 шара в каждой.
Взвесте эти группы на весах. Та группа, которая имеет более тяжелый шар, будет весить больше. Уберите с чаши весов ту группу, которая не содержит тяжелый шар.
Теперь снова разделите оставшиеся на весах шары на 2 группы по 2 шара.
Взвесте эти группы на весах и оставьте на весах те 2 шара, которые оказались тяжелее.
Наконец, взвесте два оставшихся шара, и вы найдете самый тяжелый шар.
В общей сложности это займет 3 взвешивания.
Второе решение:
Разделите шары на три группы — в одной группе будет 2 шара, в двух других по 3.
Теперь взвесте две группы по (те, в которых по 3 шара).
Если если их вес одинаков, то вам просто останется взвесить какой из двух шаров группы, которую не взвешивали, самый тяжелый.
Если если их вес этих двух групп разный, надо взять группу шаров, которая весит больше. Затем надо взвесить два любых шара из этой группы.
Если вес эти шаров одинаков, то шар, который не взвешивали, будет самым тяжелым.
В общей сложности это займет 2 взвешивания.
Эта задача попадалась на собеседовании в Яндексе.
У короля есть 1000 бутылок вина одного сорта. Король из соседнего королевства решает убить нашего короля и отправляет убийцу, чтобы отравить один из бутлок с вином. Убийца успел добавить яд в одну из бутылок, но был пойман стражей. Король узнал об этом, решил проверить, какая бутылка был отравлена. Наш король очень умный и поэтому он решает использовать 10 кроликов, чтобы проверить, какая бутылка содержит яд. Из бутылок можно взять немного вина. От яда кролик умирает через 1 день.
Сколько минимально дней потребуется, чтобы определить бутылку с ядом?
Решение
Пронумеруем бутылки в двоичной системе, всего у нас 1000 бутылок, значит на это хватит 10 разрядов:
0000000001=1
0000000010=2
0000000011=3
0000000100=4
…
1111100111=999
1111101000=1000
Кроликов нумеруем от одного до десяти.
Кроликов надо поить из тех бутылок, где в соответствующем разряде единица (или ноль, если так больше нравится, тогда все наоборот), например из первой бутылки пусть пьет только десятый кролик, а вот из 998й бутылки пусть пьют 1,2,3,4,5,8,9 кролики.
Напоили кроликов, ждем когда наступит день их гибели. Номера кроликов, которые отравились, подскажут нам разряды с «1» (или с «0», если поили нулевых).
То есть если погибли только 8й и 10й кролики, значит яд был в пятой бутылке.
Есть четыре человека, A, B, C и D. Им нужно пересечь мост. Каждому из этих людей необходимо разное время для пересечения моста.
Человек A: 1 минута;
человек B: 2 минуты;
человек C: 5 минут;
Человек D: 10 минут;
Дело происходит ночью и у этих людей есть только один факел. Без факела мост перейти нельзя. Два человека могут идти по мосту одновременно, но затратят на переход по мосту время, необходимое самому медленному из них. Например: если А и С хотят пересечь мост одновременно, они потратят 5 минут. Все четыре человека могут прийти к противоположной стороне за 17 минут. Можете ли вы объяснить, каким образом они могут это сделать?
Решение
1. A и B проходят мост с факелом: это займет 2 минуты. Общее время: 2 минуты.
2. A возвращается с факелом: это займет 1 минуту. Общее время: 3 минуты
3. C и D проходят по мосту c факелом: это займет 10 минут. Общее время: 13 минут
4. B возвращается с факелом: это займет 2 минуты. Общее время: 15 минут
5. A и B проходят мост: это займет 2 минуты. Общее время: = 17 минут
Следующая задача на теорию вероятности также часто встречается на собеседованиях на вакансию програмиста. В трех углах равностороннего треугольника находится по муравью. Каждый из муравьев начинает двигаться в другой случайно выбранный угол по прямой. Какова вероятность того, что ни один из муравьев не столкнется с другим муравьем?
Решение
Объяснение:
Есть два способа движения, при котором муравьи не встретятся друг с другом: они все должны двигаться по часовой
стрелке или все против часовой стрелки. В противном случае встречи им не избежать.
Выберите одного муравья и назовите его, например, Вася. После того, как Вася решил, в какую сторону двигаться
(по часовой стрелке или против часовой стрелки), другие муравьи должны двигаться в том же направлении, чтобы
избежать столкновения. Т.к. муравьи принимают решение случайным образом, шансы на то, что второй муравей
направится в ту же сторону, что и Вася, — один из двух, аналогично и для третьего муравья эта вероятность такая
же. Это значит, что вероятность избежать столкновения — один из четырех.
Есть сто пронумерованных закрытых дверей. Вы делаете 100 проходов около дверей и меняете состояние каждой двери, т.е. вы делаете закрытую дверь открытой и наоборот. После первого прохода Вы посещаете каждую 2-ую дверь (т.е. 2,4,6,8 и т.д.), на следующем проходе вы посещаете каждую 3-ю дверь и так далее. Необходимо сказать какие двери будут открыты, а какие закрыты после последнего прохода.
Решение
