Написать пост

Логические задачи для программистов, которые бесят своей простотой

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

Логические задачи для программистов, которые бесят своей простотой

Составили список каверзных задач по программированию, которые часто встречаются на собеседованиях Software Development Engineer (SDE).

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

Испытайте себя и узнайте, сможете ли вы найти быстрое и простое решение.

Оригинальные задачки можно прочесть на сайте Geeksforgeeks. В этой статье приведен адаптированный перевод, который мы сделали куда более литературным и чуть более мемным. :)

Сталкивались ли вы с логическими и математическими задачками на собеседовании?
Да, сталкивался
Нет, не сталкивался

Последний шар в мешке

У вас есть мешок, внутри которого 20 красных и 16 синих шаров. Вы должны вытаскивать по два шара из этого мешка за один раз.

Если шары одного цвета, то вы заменяете их синим шаром, но если они разного цвета, то вы кладете в мешок красный шар. Те шары, которые вы вытащили, в мешок не возвращаются, поэтому их количество в мешке постоянно уменьшается.

Какого цвета будет последний шар в мешке?

Решение

Существует три случая.

В первом случае вы вытаскиваете два красных шара. Тогда количество красных шаров уменьшается на 2, а количество синих увеличивается на 1.

Во втором случае оба шара синий. В этом случае количество синих шаров уменьшается на 1.

В третьем случае цвета вытянутых шаров разные, а значит, количество синих шаров снова уменьшается на 1.

Количество красных шаров может уменьшиться только на 2 и только в первом случае. Синие шары могут уменьшиться на один во втором и третьем случаях.

Так как красные шары всегда уменьшаются на два, а изначально красных шаров 20, то их количество всегда будет четным. Не может возникнуть ситуация, при которой в мешке останется 1 красный шар.

Последний шар в мешке будет синим в любом случае.

Деньрожденный тортик

У вас есть День рождения! Поздравляем, черт возьми!

Гости принесли вам тортик, и его нужно разрезать на 8 равных частей, чтобы каждому гостю достался кусочек. Но вот незадача (или все же задача?..): вы можете сделать только 3 разреза. Как вы это сделаете?

Решение

Разрежьте торт на четвертинки, сделав 2 разреза: один горизонтальный, а другой вертикальный. У вас получится 4 кусочка торта.

Теперь возьмите четвертинки и поставьте их друг на друга. Сделайте третий продольный разрез, и у вас получится 8 кусков.

С Днем рождения!

Пчела и крушение поездов

Два поезда выехали из депо навстречу друг другу. К сожалению, стрелку на путях не перевели, и поезда рано или поздно столкнутся. Железнодорожники этого не заметили, зато заметила прозорливая пчелка. Она летит между поездами, от одного к другому, пытаясь предупредить машинистов.

Скорость первого поезда составляет 50 км/ч, а скорость второго поезда – 70 км/ч. На старте расстояние между поездами составляет 100 км.

Сначала пчела летит от первого поезда ко второму. Как только она достигает второго поезда, она сразу же летит обратно к первому поезду. Рассчитайте общее расстояние, которое придется пролететь пчеле. Ее скорость составляет 80 км/ч.

Решение

Пусть скорость первого поезда A равна u км/ч, а скорость второго равна v км/ч. Расстояние между поездами равно d км. Тогда время, за которое столкнутся поезда, равно d/(u+v).

Подставим значения из условия задачи и получим b*d/(u+v) = 80 * 100/(50+70) = 66,67 км.

Охранник и 100 дверей

Охранник работает в большом здании, в котором целых 100 кабинетов и 100 дверей соответственно. Все они изначально закрыты. Поскольку проверить каждый кабинет в течение ночи охранник не успеет, он придумал хитрую систему. Раз в пять минут он проходит вдоль всех кабинетов и открывает или закрывает двери в них следующим образом:

  • На первом проходе охранник открывает каждую дверь.
  • На втором проходе человек закрывает каждую вторую дверь.
  • На третьем проходе человек закрывает каждую третью дверь.
  • На 100-м проходе человек открывает или закрывает 100-ю дверь.

В конце смены охранник должен запереть все двери. Как ему рассчитать, какие двери останутся открытыми в конце?

Решение

Все проще простого. Охранник взаимодействует с дверью в том случае, если номер его прохода i делит номер двери без остатка. К примеру, дверь 45 будет открываться и закрываться на 1, 3, 5, 9, 15 и 45 проходах.

На первом проходе дверь открывается. Если количество проходов (а значит, делителей числа без остатка) будет четным, в конце дверь будет закрыта. К примеру, у двери 16 делитель без остатка равны 1, 2, 4, 8, 16. Их количество четное, а значит, дверь будет открытой в конце.

Также для простых чисел есть только два делителя: 1 и само простое число. К примеру, число 13 делится только на 1 и 13. Делителей два, а значит, эти двери будут закрыты.

Таким образом, ответ: 1, 4, 9, 16, 25, 36, 49, 64, 81 и 100.

Перепутанные этикетки

У вас есть 3 банки с соленьями A, B и C. Вы знаете, что этикетки на них расклеены неправильно. К примеру:

  1. На банке А висит этикетка “Соленые огурчики”.
  2. На банке В висит этикетка “Маринованные помидоры”.
  3. На банке С висит этикетка “Огурчики и помидорки”.

Вы можете только раз попробовать содержимое одной банки. К примеру, если вы взяли банку “Огурчики и помидорки” и достали помидор, достать второе соленье из той же банки уже не выйдет.

Каким будет минимальное количество солений, которые вам придется съесть, чтобы понять, как правильно пометить банки?

Решение

Вам нужно только единожды попробовать содержимое банки С “Огурчики и помидорки”. Если вы вытащите маринованный огурец, вы будете знать, что это банка только с огурцами, ведь этикетка врет. Значит, в оставшихся двух банках лежат “Маринованные помидоры” и “Огурчики и помидоры”.

Поскольку огурцы лежат в банке С, вы знаете, что в банке В могут быть либо смесь, либо помидоры. Однако на ней написано “Маринованные помидоры”, что, как мы знаем из условия, вранье. Значит, в ней находится смесь помидорок и огурчиков.

Таким образом, в банке А лежат только помидоры.

Муравьи в треугольнике

На трех углах треугольника сидят 3 муравья. Все муравьи случайным образом выбирают направление и начинают двигаться вдоль края треугольника. Какова вероятность того, что два муравья встретятся?

Решение

Они не встретятся только в двух случаях: либо все муравьи пойдут против часовой стрелки, либо по часовой.

Поскольку у каждого муравья есть два варианта (выбрать один из двух ребер, проходящих через угол, на котором муравей изначально сидит), всего существует 2*2*2 возможности, то есть 8 вариантов развития событий.

Из 8 вариантов только в двух случаях муравьи не встретятся. Таким образом, вероятность встречи равна 6/8, а вероятность невстречи равна 2/8.

Возраст дочерей

Известно, что у синьора Саши есть три дочери. Джун Илюша решил узнать, сколько лет дочкам Саши. Тогда синьор решил загадать джуну загадку, дав три подсказки:

  1. Произведение их возрастов равно 72.
  2. Сумма их возрастов равна номеру моего дома.
  3. Старшая девочка любит клубничное мороженое.

Подумав, джун Илюша смог угадать возраст. Можете ли вы угадать, сколько лет дочкам Саши?

Решение

Поскольку произведение возрастов равно 72, подберем все возможные комбинации произведения из трех чисел.

			1 * 1 * 72 = 72
1 * 2 * 36 = 72
1 * 3 * 24 = 72
1 * 4 * 18 = 72
1 * 6 * 12 = 72
1 * 8 * 9 = 72
2 * 2 * 18 = 72
2 * 3 * 12 = 72
2 * 4 * 9 = 72
2 * 6 * 6 = 72
3 * 3 * 8 = 72
3 * 4 * 6 = 72
		

Также нам нужно просчитать все суммы вероятных возрастов, которые мы вывели при первом расчете.

			1 + 1 + 72 = 74
1 + 2 + 36 = 39
1 + 3 + 24 = 28
1 + 4 + 18 = 23
1 + 6 + 12 = 19
1 + 8 + 9 = 18
2 + 2 + 18 = 22
2 + 3 + 12 = 17
2 + 4 + 9 = 15
2 + 6 + 6 = 14
3 + 3 + 8 = 14
3 + 4 + 6 = 13
		

Мы видим, что каждая сумма уникальна, кроме 14, которая встречается дважды. Поскольку Саша сделал сумму подсказкой, предполагаем, что именно 14 нужное нам число. Теперь нужно понять, что выбрать: 3, 3 и 8 или 2, 6 и 6.

Саша сказал, что старшая дочка любит мороженое. Это значит, что старшая дочка всего одна, и у него не может быть двух старших дочек. Значит, дочкам Саши 3, 3 и 8 лет.

Заключение

Надеемся, вам удалось решить все задачки. :)

Пишите в комментариях, если вы нашли другие, нестандартные решения для задач: они точно есть.

Если вы сталкивались с логическими задачками на собеседованиях, расскажите, что именно вам встречалось, обсудим! :)

Следите за новыми постами
Следите за новыми постами по любимым темам
3К открытий6К показов