Читать книгу Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию - Гейл Макдауэлл - Страница 34

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

Если вам досталась головоломка, то наверняка она интересная и наверняка ее можно решить логически. Корни большинства головоломок лежат в математике или информатике.

Давайте рассмотрим основные подходы к решению головоломок.

Начните говорить

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

Правила и шаблоны

В большинстве случаев попробуйте найти и записать правила или шаблоны, которые помогут вам решить задачу. Да-да, именно записать – это поможет запомнить их и использовать при решении задачи. Давайте рассмотрим простой пример.

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

Совет: остановитесь и попытайтесь решить задачу самостоятельно. В крайнем случае, прочитайте этот раздел медленно и вдумчиво. Каждый абзац будет приближать вас к решению.

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

Правило 1: если одна веревка горит x минут, а другая горит y минут, то общее время горения составит x+y.

Что еще мы можем сделать с веревкой? Попытка поджечь веревку в любом другом месте, кроме как с концов, не даст нам дополнительной информации. Мы понятия не имеем, сколько времени она будет гореть.

Но мы можем поджечь веревку с двух концов одновременно. Огонь должен будет встретиться через 30 минут.

Правило 2: если веревка горит x минут, мы можем отсчитать интервал времени, равный x/2 минут.

Мы знаем, что можем отсчитать 30 минут, используя одну веревку. Это также означает, что мы можем вычесть 30 минут из времени горения второй веревки, если одновременно подожжем первую веревку с двух концов, а вторую только с одного.

Правило 3: если первая веревка горит x минут, а вторая веревка горит y минут, мы можем заставить вторую веревку гореть (y-x) минут или (y-x/2) минут. Теперь давайте соединим все части воедино. Мы можем превратить вторую веревку в веревку, которая горит 30 минут. Если мы теперь подожжем вторую веревку с другого конца (см. правило 2), то она будет гореть 15 минут.

Запишем получившийся алгоритм:

• Поджигаем веревку 1 с двух сторон, веревку 2 – только с одного.

• Веревка 1 сгорела, значит, прошло 30 минут, веревке 2 осталось гореть 30 минут.

• В этот момент времени поджигаем веревку 2 с другого конца.

• Чтобы веревка 2 сгорела полностью, понадобится 15 минут.

Обратите внимание, как записанные правила облегчили решение этой задачи.

Балансировка худшего случая

Большинство головоломок относятся к задачам минимизации, когда требуется уменьшить количество действий или выполнить что-либо определенное количество раз. Можно попробовать «сбалансировать» худший случай. Таким образом, если решение приведет к смещению худшего случая, можно выполнить балансировку худшего случая. Рассмотрим конкретный пример.

Задача о «девяти шарах» – классика собеседования. У вас есть 9 шаров – восемь имеют одинаковый вес, а один более тяжелый. Вы можете воспользоваться весами, позволяющими узнать, какой шар тяжелее. Требуется найти тяжелый шар за два взвешивания.

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

Это пример несбалансированного худшего случая. Чтобы определить, является ли девятый шар самым тяжелым, нужно одно взвешивание, а чтобы выяснить, где он, – три. Если мы «оштрафуем» девятый шар, отложив большее количество шаров, то можем снизить нагрузку на другие. Классический пример балансировки худшего случая.

Если мы раздели шары на группы по три шара в каждой, то достаточно одного взвешивания, чтобы понять, в какой группе находится тяжелый шар. Мы можем даже сформулировать правило: дано N шаров, где N кратно трем, за одно взвешивание можно найти группу шаров N/3, в которой находится самый тяжелый шар.

Для оставшейся группы из трех шаров нужно повторить ту же операцию: отложить один шар, а остальные взвесить. Если шары весят одинаково, значит, оставшийся шар – самый тяжелый, иначе весы «покажут» тяжелый шар.

Алгоритмический подход

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

Вопросы собеседования

6.1. Дано: 20 баночек с таблетками. В 19 баночках лежат таблетки весом 1 г, а в одной – весом 1,1 г. Даны весы, показывающие точный вес. Как за одно взвешивание найти банку с тяжелыми таблетками?

6.2. Дано: шахматная доска размером 8×8, из которой были вырезаны два противоположных по диагонали угла, и 31 кость домино; каждая кость домино может закрыть два квадратика на поле. Можно ли вымостить костями всю доску? Обоснуйте свой ответ.

6.3. У вас есть пятилитровый и трехлитровый кувшины и неограниченное количество воды. Как отмерить ровно 4 литра воды? Кувшины имеют неправильную форму, поэтому точно отмерить «половину» кувшина невозможно.

6.4. На острове существует правило – голубоглазые люди не могут там находиться. Самолет улетает каждый вечер в 20:00. Каждый человек может видеть цвет глаз других людей, но не знает цвет собственных, никто не имеет права сказать человеку, какой у него цвет глаз. На острове находится не менее одного голубоглазого человека. Сколько дней потребуется, чтобы все голубоглазые уехали?

6.5. Дано 100-этажное здание. Если яйцо сбросить с высоты N-го этажа (или с большей высоты), оно разобьется. Если его бросить с меньшего этажа, оно не разобьется. У вас есть два яйца, найдите N за минимальное количество бросков.

6.6. Дано: 100 закрытых замков расположены в длинном коридоре. Человек сначала открывает все сто. Затем он закрывает каждый второй замок. Затем он делает еще один проход – «переключает» каждый третий замок (если замок был открыт, то он его закрывает, и наоборот). На 100-м проходе человек должен «переключить» только замок № 100. Сколько замков остались открытыми?