Периодически интервьюеры задают различные задачи, слабо относящиеся к вашей будущей работе. Особенно этим грешат в больших компаниях. Именно там, где каждый большой или маленький начальник думает не о том, что нужно будет делать работнику, а о том, как бы проверить одно из его логических качеств, которые, возможно никогда и не пригодятся в работе. Хотя многие говорят, что интересует не решение этих задач, которые дают на собеседовании, а то, как их решает соискатель.
На собеседовании могут задать несколько типов задач, чтобы посмотреть креативность, широту взглядов и “незашоренность” Часто такие задачи не имеют единственно правильного решения и интерьвьюеру интересен путь по которому кандидат идет, например, “Посчитайте сколько заправок в стране “. Но есть и задачи, которые имеют решение. Это как раз на логику. Здесь представлено несколько логических задач у которых есть правильное решение, нужно только чуть-чуть подумать.

Задача первая: котлеты на сковородке

У вас есть три котлеты и две сковороды. Каждая сторона котлеты жарится одну минуту. На одну сковороду одновременно помещается лишь одна котлета. За какое наименьшее время можно пожарить все котлеты с обеих сторон?

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

Теперь начинаем думать креативно. У нас есть ресурс – две сковородки. Они могут жарить одновременно. Если мы начнем с двух котлет, то займем ресурс полностью, однако, половина ресурса будет простаивать, когда будет жариться третья. Т.е. для сокращения времени нужно задействовать вторую сковородку, все время. Как это сделать? У нас есть возможность разделить жарку на обжаривание с одной стороны и с другой. Т.е. все время жарки будет 3 котлеты умножить на 2 стороны  = 6 этапов. Если есть шесть этапов, которые занимают 6 минут и есть две сковородки на которых эти этапы нужно выполнить, то получается, что реально можно пожарить за три минуты, вопрос только в алгоритме. Тут и приходит решение. После одной минуты, когда пожарилась первая сторона, нужно одну котлету, наполовину пожаренную, снять и положить на ее место сырую. А на третьей минуте, уже пожаренную снять и дожарить оставшуюся на свободной сковородке.

Задача вторая: горючие веревки

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

Неравномерность горения веревок – это как раз для тех умников, которые решили веревки поделить на четыре части. Этот вариант не подходит. Т.е. нельзя просто разрезать веревку на четыре части и поджечь, это не будет точным измерением, поскольку время горения не соответствует длине. Какая-то часть веревки может сгорать быстрее, а какая-то часть – медленнее.

Продолжаем думать креативно. У нас есть единица измерения – время горения веревки. Это время  – 1 час по условиям задачи. Это время никак не соотносится с длиной. Но у нас две веревки, поэтому мы можем как-то время горения одной веревки соотнести с временем горения другой. А теперь ключ к решению задачи. Ведь если веревка горит 1 час, значит ее подожгли с одного конца, следовательно, если ее поджечь с двух концов, то она точно сгорит за 30 минут, конечно будет гореть неравномерно, но время будет точным. Все, у нас есть с чем сравнивать.  Поджигаем первую веревку с двух сторон, а вторую только с одной(чтобы засеч время). Первая спокойно горит тридцать минут, и когда она сгорела мы тушим вторую веревку. Получается, что у нас остался кусок веревки, который должен сгореть за пол-часа (какая длина-не важно). Теперь применяем к ней тот же метод, что и для первой – поджигаем с двух сторон и получаем пятнадцать минут горения.

Задача третья: комната с лампочками

Есть закрытая комната, где находятся три лампочки. Снаружи есть три выключателя. Необходимо узнать какую лампочку включает каждый выключатель, но при этом можно зайти в комнату только один раз. (Нельзя бегать и щелкать выключателями).

Конечно, как менеджер, можно привлечь помощников, но нужно использовать иной взгляд на лампочки и обойтись самому. Начинаем размышлять. Комната закрытая, лампочки снаружи не видны. Если включить одну из них, а остальные выключить, а потом пойти посмотреть, мы узнаем какой выключатель управляет горящей лампочкой. По условиям, мы должны сразу же как-то различить и остальные две. Если они не горят, то они совершенно одинаковые. Нам нужно что-то придумать, чтобы при входе в комнату сразу было понятна связь между выключателем и выключенной лампочкой.

Интересный вариант решения нашел на одном из форумов.  У нас есть два состояния горит-не горит и два состояния выключателя вкл-выкл, при этом лампочек три. Было бы две, то сложностей – никаких, одну включили, вторую выключили и пошли посмотрели. Значит одна лампочка должна быть включена, вторая выключена, а что делать с третьей? Предложили к третьему выключателю подвести 380 вольт, от которых лампочка перегорает(у ламп накаливания, хорошо видна спираль, если она перегорела, то это видно). Т.е. предложение добавить еще одно состояние исправна-не исправна. Т.е. лампочка теперь может быть в трех состояниях горит/ не горит и исправна/ не горит и неисправна. Поразмыслив над третьим состоянием можно вспомнить, что когда лампочка включена, она нагревается, а если ее выключить, то какое-то время она остается теплой, т.е. получаем разделение не горящих лампочек по теплая-холодная. Следовательно для решения задачи включаем два выключателя на некоторое время, потом выключаем один и идем смотреть. Видим одну горящую лампочку, и две не горящих, одна из которых теплее другой, что указывает на тот выключатель, который только что выключили.

Задача четвертая: золотая цепочка

На постоялый двор приехал путешественник. Денег у него с собой не было, но была золотая цепочка из шести звеньев. Хозяин постоялого двора согласился принять в оплату комнаты за каждый день по одному колечку с этой цепочки, но так чтобы распиленных колец он получил не больше одного. Никто друг другу не доверяет и не хочет платить вперед или заплатить потом, оплата должна быть ежедневной.  Как постояльцу нужно распилить цепочку, чтобы можно было ежедневно расплачиваться на протяжении пяти дней?

Чтобы шесть звеньев разъединить и итоге осталось по одному звену, явно не получится распилить одно звено, поскольку колец 6, а соединений 5 то чтобы их разъединить все по одному, нужно как минимум три разреза (5/2 округляем до целого, получается 3).

Здесь что-то не так, начинаем думать креативно. Здесь есть понятие “оплата”, т.е. по условиям задачи нет требования, чтобы постоялец передавал хозяину по одному звену, есть требование, чтобы каждый день у хозяина становилось больше на одно звено. Теперь подходим к самой главной мысли, что хозяин и постоялец могут меняться, или, к примеру, хозяин может давать сдачу. Тогда все тривиально. Пилим одно звено – третье, чтобы была разменная монета 1, 2 и 3 звена, и в первый день турист дает хозяину одно звено, во второй меняет своих два на одно вчерашнее, в третий день может поменять два на три и т.д.  Каждый день у хозяина на одно звено больше.

Задача пятая: взвешивание
Есть восемь монет, семь из которых весят одинаково, а одна немного меньше (фальшивая, но без весов не определить). Есть весы с двумя чашками, но нет гирь. Необходимо за минимальное число взвешиваний найти фальшивую.

Начинаем с первого попавшегося алгоритма. Берем первые две монеты и кладем на противоположные чашки весов, если одна легче, то фальшивка найдена, если вес одинаков, то берем следующую пару. Проблема в том, что пар у нас четыре т.е. в самом неудачном случае, нам понадобится четыре взвешивания. Программисты, прочитав это решение, должны были хитро усмехнуться и сказать, “но есть же двоичный поиск, совсем не обязательно взвешивать все пары”.
Для тех, кто далек от программирования вот пример двоичного поиска: Чтобы поймать льва в пустыне нужно поделить пустыню пополам, посмотреть в какой половине лев, затем поделить эту половину пополам, а затем еще пополам, до тех пор пока лев не окажется в клетке. Теперь делим наши восемь монет пополам, кладем по четыре монеты с каждой стороны весов. Монеты с той стороны, которая тяжелее убираем(там нет фальшивки) и делим оставшиеся пополам, получается по две на каждую сторону, теперь осталось всего две монеты для последнего взвешивания. В итоге мы получили три взвешивания. Ура! мы победили! И тут для программистов – холодный душ. Оказывается можно решить задачу всего за два взвешивания. Придется думать…

Быстрее, чем двоичный поиск еще ничего не придумали, т.е. сократить количество взвешиваний можно только отказавшись от взвешивания. Проблемка. Но решение все-таки есть. А если взвешивать не все монеты, а поделить по три, а две отложить? Тогда в случае, если при первом взвешивании будет одинаковый вес, то вторым  взвешиванием отложенных двух монет, находим нужную. Если же вес при первом взвешивании не одинаков, то берем те три монетки, которые на легкой стороне, откладываем одну и взвешиваем две оставшихся. Если вес разный, то монета найдена, если вес одинаков, то оставшаяся монета и есть фальшивка.

Задача шестая: как разделить торт

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

Вот здесь сразу можно поставить человека в тупик, ведь на первый взгляд нужно четыре разреза, ведь частей 8. Но если посмотреть на это креативнее…

Решение простое, и можно дать как минимум два. Для начала поймем, что реально разрезать один торт на восемь равных частей тремя разрезами нельзя, по крайней мере так, как мы это себе представляем: открыли коробку с тортом и начали резать. Так не пойдет, для восьми частей, нужно четыре разреза. Но их можно сократить, если представить себе торт не как плоский круг, а привлечь пространственное мышление. Сначала делаем два разреза крест на крест, получаем четыре куска. Теперь нужно придумать, как за один раз порезать все четыре куска ровно пополам.  Если вспомнить, что никто не ограничивает нас в перестановке уже отрезанных кусков, то  просто складываем куски стопкой и режем все вместе – это первый вариант. А если все-таки вспомнить, что торт имеет определенную толщину, то последний разрез делаем не сверху как первых два, а поперек всех кусков посередине торта, отделяя верх от низа, но так, чтобы было ровно. Правда в этом случае половина гостей получит кусок без глазури, но ради науки чем-то нужно жертвовать.