Логика в программировании: логические задачи с собеседований
Нестандартное мышление и логика в программировании – наше все. На собеседовании будьте готовы к тому, что некоторые задачи будут нетривиальными.
Полторы белки и логика в программировании
1,5 белки, да: такая задача действительно существует. Давайте посмотрим на условие:
1,5 белки за 1,5 минуты съедают 1,5 ореха. Сколько орехов съедят 9 белок за 9 минут?
[spoiler title='Решение' style='default' collapse_link='true']Согласитесь, что 1,5 белки сразу сбивают с толку. На это и рассчитано условие. Здесь важно абстрагироваться от привычных образов и принять во внимание тот факт, что речь идет не о последовательном, а о параллельном выполнении задач. Мне было удобнее представить себе это в виде многопоточности без монитора. Что мы имеем с таким подходом?
1. Если действие выполняется белками параллельно, а не последовательно, 1,5 белки за 1,5 минуты съедают 1,5 ореха. Стало быть, 1 белка за 1,5 минуты съедает 1 орех, а 9 белок за 1,5 минуты съедают 9 орехов.
2. Но это за 1,5 минуты, а нам нужно 9 минут:
9/1,5 = 6.
- Умножаем количество съеденных орехов:
9*6 = 54.
Ответ: 9 белок за 9 минут съедают 54 ореха.[/spoiler]
Лампочки и переключатели
Условие:
В первой закрытой комнате с низким потолком висит 3 лампы накаливания. В другой такой же комнате установлено 3 переключателя от каждой из них. Можно как угодно дергать переключатели, вот только перейти из 2-ой комнаты в 1-ую разрешено только 1 раз. Как узнать, за какую лампочку отвечает каждый из переключателей?
[spoiler title='Решение' style='default' collapse_link='true']Здесь не нужно быть математиком: достаточно немного поразмыслить. Помните, что логика в программировании – это необходимый инструмент. Так как мы можем дотянуться до лампочки рукой (низкий потолок), следует на некоторое время включить одну из них на пару минут, выключить ее и включить любую другую. Далее переходим в комнату с лампочками и проверяем:
- та, которая горит, соединена с последним переключателем, который мы трогали;
- та, которая не горит и теплая, соединена с первым переключателем, который мы трогали;
- за не горящую и холодную лампочку отвечает переключатель, который мы вообще не трогали.[/spoiler]
Бейсбольный мяч и бита
Здесь работает чистая математика. Условие:
Бейсбольный мяч с битой вместе стоят $13. Но мяч дешевле бейсбольной биты на $3. Рассчитайте стоимость каждого предмета.
[spoiler title='Решение' style='default' collapse_link='true']1. Предмета два, следовательно, делим сумму на 2:
13/2 = 6,5.
2. Мяч дешевле биты на $3, но и бейсбольная бита дороже мяча на $3. Делим разницу на 2:
3/2 = 1,5.
3. Рассчитываем стоимость каждого предмета:
- мяч – 6,5-1,5 = 5;
- бита – 6,5+1,5 = 8.
Ответ: мяч = $5, бита = $8.[/spoiler]
Задача о фальшивой монете
Логика в программировании не ограничивается только математической составляющей, но она является одной из ключевых. То же самое и в случае с монетами. Условие:
Дано 12 монет, из которых 11 – настоящие, и только 1 – фальшивая. Фальшивая монета отличается от настоящих по массе. Какое минимальное количество взвешиваний необходимо, чтобы обнаружить фальшивую монету? Для взвешивания используются чашечные весы.
[spoiler title='Решение' style='default' collapse_link='true']Задача легкая, хотя многие все равно начинают путаться, отвечая «1» или «2». Минимальное количество взвешиваний – 3, ведь даже если мы взвесим 2 раза, то как мы узнаем, какая из монет фальшивая? Большую часть монет составляют настоящие, так что 2 монеты с одинаковым весом и будут настоящими, третья с другим весом – фальшивой.
Ответ: 3 взвешивания.[/spoiler]
Сжигаем веревки
Условие:
Есть 2 веревки и неограниченное количество спичек. Каждая веревка сгорает за час, однако горят они неравномерно, так что нельзя точно узнать, за какое время сгорит определенная часть веревки. Как отмерить с помощью этих двух веревок интервал в 45 минут?
[spoiler title='Решение' style='default' collapse_link='true']Горят веревки действительно неравномерно, но полностью сгорают точно за час. Мы можем:
- Поджечь оба конца одной веревки и только 1 конец второй веревки.
- Как только первая веревка сгорит (пройдет 30 минут, так как горит она с двух концов), поджигаем другой конец второй веревки, и она догорит ровно за 15 минут.[/spoiler]
Бочка с водой
Условие:
Дана пустая бочка. Нужно наполнить ее водой так, чтобы заполнена была только половина. Использовать палку или другие предметы для измерения нельзя.
[spoiler title='Решение' style='default' collapse_link='true']Да, логика в программировании может подкинуть и физику. А что? Ведь занимаются же как-то машинным обучением, и подобные вещи тоже могут пригодиться.
- Заполняем бочку водой (или полностью, или точно больше половины).
- Наклоняем бочку на 45 градусов: вся лишняя вода выливается, и остается ровно половина.[/spoiler]
Дождь и солнце
Это очень легкая задача, но горе вам, если зададут ее под конец собеседования, когда последние силы покинут, а мыслительный процесс начнет изрядно буксовать. Условие:
12 часов ночи. Идет дождь. Можно ли ожидать, что по истечении 72 часов будет солнечная погода?
[spoiler title='Решение' style='default' collapse_link='true']Ответ: нет, так как через 72 часа также будет ночь.[/spoiler]
Кофе-брейк
Условие:
В офисе расположили 3 автомата с различными напитками. В первом – кофе, во втором – чай, а в третьем – и кофе, и чай (выдает случайным образом). Для любого из них нужна 1 монета. Каждый автомат обозначен наклейкой с названием продукта, который он выдаёт. Вот только на заводе перепутали наклейки, и на каждом из трех автоматов оказалась неправильная. За сколько монет можно выяснить, где какой автомат?
[spoiler title='Решение' style='default' collapse_link='true']Здесь, как и в случае с первой задачей, нужно абстрагироваться от мнимой сложности, ведь задача легкая.
- Бросаем монету в автомат с надписью «чай-кофе». Так как все наклейки расположены неверно, в зависимости от того, что выдаст автомат, мы определим его в «чайный» или «кофейный».
- Допустим, это оказался кофейный автомат. Тогда чайный автомат не может быть ни кофейным, ни чайным: он выдает и чай, и кофе.
- Методом исключения определяем автомат, который выдает чай.
Ответ: за 1 монету.[/spoiler]
А вот вам еще несколько интересных задач, которые рассчитаны исключительно на программистов. Сможете их решить? ;)
- Сколькими способами можно разложить на 6 целых множителей 1 000 000?
- Имеем большой файл в несколько Гб, в котором записаны целые числа. Нужно записать в другой файл все эти числа в отсортированном порядке. Как это сделать максимально эффективно?
- Имеем все тот же большой файл в несколько Гб с целыми числами. Каждое число встречается дважды, но также есть 1 число, которое встречается всего 1 раз. Предложите эффективный алгоритм для поиска этого числа.