62651

Логика в программировании: логические задачи с собеседований

Нестандартное мышление и логика в программировании – наше все. На собеседовании будьте готовы к тому, что некоторые задачи будут нетривиальными.

Логика в программировании

Полторы белки и логика в программировании

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.
  1. Умножаем количество съеденных орехов:
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. Поджечь оба конца одной веревки и только 1 конец второй веревки.
  2. Как только первая веревка сгорит (пройдет 30 минут, так как горит она с двух концов), поджигаем другой конец второй веревки, и она догорит ровно за 15 минут.[/spoiler]

Бочка с водой

Условие:

Дана пустая бочка. Нужно наполнить ее водой так, чтобы заполнена была только половина. Использовать палку или другие предметы для измерения нельзя.

[spoiler title='Решение' style='default' collapse_link='true']Да, логика в программировании может подкинуть и физику. А что? Ведь занимаются же как-то машинным обучением, и подобные вещи тоже могут пригодиться.

  1. Заполняем бочку водой (или полностью, или точно больше половины).
  2. Наклоняем бочку на 45 градусов: вся лишняя вода выливается, и остается ровно половина.[/spoiler]

Дождь и солнце

Это очень легкая задача, но горе вам, если зададут ее под конец собеседования, когда последние силы покинут, а мыслительный процесс начнет изрядно буксовать. Условие:

12 часов ночи. Идет дождь. Можно ли ожидать, что по истечении 72 часов будет солнечная погода?

[spoiler title='Решение' style='default' collapse_link='true']Ответ: нет, так как через 72 часа также будет ночь.[/spoiler]

Кофе-брейк

Условие:

В офисе расположили 3 автомата с различными напитками. В первом – кофе, во втором – чай, а в третьем – и кофе, и чай (выдает случайным образом). Для любого из них нужна 1 монета. Каждый автомат обозначен наклейкой с названием продукта, который он выдаёт. Вот только на заводе перепутали наклейки, и на каждом из трех автоматов оказалась неправильная. За сколько монет можно выяснить, где какой автомат?

[spoiler title='Решение' style='default' collapse_link='true']Здесь, как и в случае с первой задачей, нужно абстрагироваться от мнимой сложности, ведь задача легкая.

  1. Бросаем монету в автомат с надписью «чай-кофе». Так как все наклейки расположены неверно, в зависимости от того, что выдаст автомат, мы определим его в «чайный» или «кофейный».
  2. Допустим, это оказался кофейный автомат. Тогда чайный автомат не может быть ни кофейным, ни чайным: он выдает и чай, и кофе.
  3. Методом исключения определяем автомат, который выдает чай.

Ответ: за 1 монету.[/spoiler]

А вот вам еще несколько интересных задач, которые рассчитаны исключительно на программистов. Сможете их решить? ;)

  1. Сколькими способами можно разложить на 6 целых множителей 1 000 000?
  2. Имеем большой файл в несколько Гб, в котором записаны целые числа. Нужно записать в другой файл все эти числа в отсортированном порядке. Как это сделать максимально эффективно?
  3. Имеем все тот же большой файл в несколько Гб с целыми числами. Каждое число встречается дважды, но также есть 1 число, которое встречается всего 1 раз. Предложите эффективный алгоритм для поиска этого числа.

Вас также могут заинтересовать:

Комментарии

BUG
LIVE