Позитивная работа

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

Находка для HR-садиста

Я не буду предлагать Вам слишком простые задачи, вроде того "как взвесить Boeing-747?", или "сколько шариков для гольфа влезет в автобус?", или "сколько стоит помыть все окна в Москве?". Мы с Вами посмотрим как решаются более интересные задачи. А затем Вы узнаете, для чего такие задачи предлагают, и что требуется от Вас на самом деле.

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

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

0. Для разминки:) Есть три закрытых ящика с фруктами, в одном лежат апельсины, в другом лимоны, а в третьем смесь - апельсины и лимоны. Все надписи на ящиках перепутаны. Какие ящики (и сколько) надо открыть, и сколько фруктов достать, чтобы правильно перевесить таблички с надписями?

Решение

По условию известно, что перепутаны все надписи. Открываем тот ящик, на котором надпись "Апельсины и лимоны", и берем один фрукт, если это лимон, то перевешиваем надпись "Апельсины и лимоны" туда, где надпись "Апельсины", а надпись "Апельсины" перевешиваем туда где написано "Лимоны", а табличку "Лимоны" вешаем на открытый ящик.

1. У Вас есть наемный рабочий. Есть кусок золота, разделенный на семь соединенных сегментов. Вы должны давать рабочему по одному сегменту золота в день. Как оплатить ему семь рабочих дней, если отломать от куска золота можно только дважды?

Решение

Делим кусок золота на три части следующим образом:

|=|

|=|=|

|=|=|=|=|

Первый день: Даем рабочему самый маленький кусочек.

Второй день: Даем рабочему кусок чуть больше (на два сегмента) и забираем первый кусок (маленький).

Третий день: Даем рабочему самый маленький кусочек (теперь у него три сегмента есть).

Четвертый день: Отбираем у рабочего все золото, что давали и даем ему самый большой кусок (на четыре сегмента).

Пятый день: Вручаем рабочему маленький кусочек, в дополнение к самому большому.

Шестой день: Отбираем маленький кусок и вручаем двухсегментный. (у него на руках 6 сегментов)

Седьмой день: Отдаем обратно маленький кусочек.

Если нет ограничений на равенство сегментов, и форму куска золота, можно подумать над пересечением кривых (каждая кривая - форма разреза).

2. Имеется круглый стол с симметрично расположенными на нем 4-мя выключателями. Выключатель в состоянии вкл и выкл выглядит совершенно одинаково.
Одна из возможных комбинаций из 4-х включателей зажигает лампочку. Чтоб проверить зажглась ли лампочка или нет нам надо выйти из комнаты. Когда мы выходим - стол крутится в неизвестном направлении.
Надо зажечь лампочку как можно быстрей.

Решение

Решение: переключение каждый раз выбирается таким образом, что гарантируется включение до сих пор не включенных кнопок, НЕЗАВИСИМО от того, как повернется стол между переключениями.

То есть, пусть вначале все выключено (0000). Включаем все четыре (1111). Затем, нажимаем две кнопки по диагонали (это либо 1010, либо 0101). Потом нажимаем все четыре, получим нажатыми две ДРУГИЕ кнопки по диагонали (т.е. либо 0101, либо 1010). И так далее.

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

Взято отсюда.

3. Есть пятеро пиратов, упорядоченных от 5 до 1. Главный пират имеет право предложить, как распределить 100 золотых монет между всеми. Но остальные потом голосуют за этот план, и если меньше половины пиратов соглашаются с ним, то его убивают, и следующий по порядку становится главным. Как должен пират распределить золото, чтобы максимально увеличить свою долю, но выжить при этом?

Решение

Все просто: начинаем размышлять не с начала, а с конца. Предположим, что пираты всегда голосовали против и дошло дело до того момента, когда их осталось двое (2-ый и 1-ый соответственно). В этой ситуации главный (2-ый пират) в любом случае будет труп, т.к. оставшийся второй пират (1-ый) всегда будет голосовать против (тогда он убивает главного и забирает себе все золото, согласно условию задачи). Таким образом 2-ому пирату нельзя доводить ситуацию до того момента, когда он станет главным. Поэтому в ситуации, когда их осталось трое (3-ий главный), 2-ый будет голосовать "за" при любом раскладе, т.к. жить хочется. Если пиратов осталось четверо (4-ой главный), то голос последнего пирата (1-ого) стоит 1 монету, т.к. больше он не получит в любом случае (если проголосует против, то их останется трое, а эту ситуацию я выше описал и в ней от голоса последнего ничего не зависит, т.к. 2-ый заведомо будет "за", что обеспечит большинство). Таким же образом и в нашей ситуации, когда пиратов пять, достаточно дать последнему 1 золотой, чтобы ему было выгодно голосовать "за" и предпоследнему дать 1 золотой, чтобы тот не доводил ситуацию до вышеописанной, когда он останется вживых, но не получит ничего. От голоса второго и третьего ничего зависеть не будет.

Взято отсюда.

4. Один коневладелец оставил в наследство своим сыновьям конюшню. Он завещал старшему отдать половину, среднему треть, а младшему девятую часть всех лошадей.
В конюшне на момент смерти владельца осталось 17 лошадей. Как можно не нарушив завещание поделить лошадей? (Все лошади остаются живы)

Решение

1/2 + 1/3 + 1/9 = 9/18 + 6/18 + 2/18
Старший - 9 лошадей
Средний - 6 лошадей
Младший - 2 лошади

5. Ночь. Бурная река. Через реку переброшен непрочный мост. По одну сторону реки находятся четыре женщины. На всех женщин есть только один фонарик. Мост может выдержать только двоих одновременно.

Первая женщина может перейти мост за 1 минуту.
Вторая женщина может перейти мост за 2 минуты.
Третья женщина может перейти мост за 5 минут.
Четвертая женщина может перейти мост за 10 минут.

Им всем нужно переправиться на другую сторону не более чем за 17 минут. Перейти мост можно одновременно только одной или вдвоем, и обязательно с фонариком. перебрасывать фонарь по воздуху нельзя. Время переходя считается по максимальному, то есть если вместе идут первая и четвертая, то перейдут они мост за 10 минут, если четвертая вернется обратно одна, то переход туда-обратно займет 20 минут.

Есть еще вариант с другими сроками перехода (1,2,5 и 6 минут), и максимальным временем 13 минут.

Решение

Общее решение для подобных задач - результат 17 минут можно получить только следующим подбором времен перехода - 10+2+2+2+1=17, это значит, что третья (5мин) может перейти на другую сторону только вместе с четвертой (10мин), также это означает что переходов будет 5, что первая один раз пройдет мост без компаньонки, а вторая (2мин) перейдет мост трижды.

решение (после "=" общее затраченное время в минутах):

1. первая и вторая переходят мост = 2
2. вторая возвращается = 4
3. вторая передает фонарь третьей и четвертой и они переходят = 14
4. первая берет фонарь и возвращается за второй = 15
5. первая и вторая переходят мост вместе =17

другой вариант:

1. первая и вторая переходят мост = 2
2. первая возвращается = 3
3. первая передает фонарь третьей и четвертой и они переходят = 13
4. вторая возвращается с фонарем = 15
5. первая и вторая переходят мост вместе =17

В случае 13-минутной задачи решаем аналогично -
1+2+2+2+6 =13

1. первая и вторая переходят мост = 2
2. вторая возвращается =4
3. третья и четвертая идут вместе = 10
4. первая с фонарем переходит обратно = 11
5. переходят мост первая и вторая =13

6. Медведь проходит один километр на юг, затем поворачивает налево и идет один километр на восток, затем поворачивает еще раз налево, идет километр на север и возвращается в исходную точку.

Хорошо подумайте - какого цвета медведь?

Решение

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

Если еще подумать, то можно обнаружить бесконечное множество точек, расположенных на окружности, центр которой находится в точке южного полюса, а радиус её (в километрах) R = 1+1/(2*π)
маршрут:

В Антарктиде местных медведей не водится, поэтому медведь может быть как местным белым (на Северном полюсе), так и привозным Винни-Пухом на Южном полюсе. Решение задачи - множество точек возможного местонахождения медведя (точка+окружность), ответ на вопрос задачи - произвольный цвет.

7.Есть 1000 бутылок вина. Достоверно известно, что одна бутылка отравлена. Надо вычислить, какая отравлена. На это есть 10 кроликов, можно пробовать вино на них. Яд на кроликов действует даже в микродозах, но действует не сразу, а на 5й - 7й день после приема. Надо за 8 дней найти отравленную бутылку. Кроликов не жалко, количество выпитого ими вина значения не имеет.

Решение

Кролик имеет два состояния - жив или мертв (0 или 1), кроликов десять штук, это значит что в двоичной системе можно получить 1024 уникальных комбинации из живых и мертвых кроликов.
Пронумеруем бутылки в двоичной системе, всего у нас 1000 бутылок, значит на это хватит 10 разрядов:
0000000001=1
0000000010=2
0000000011=3
0000000100=4
0000000101=5
...
...
1111100110=998
1111100111=999
1111101000=1000
Кроликов нумеруем от одного до десяти.
Кроликов надо поить из тех бутылок, где в соответствующем разряде единица (или ноль, если так больше нравится, тогда все наоборот), например из первой бутылки пусть пьет только десятый кролик, а вот из 998й бутылки пусть пьют 1,2,3,4,5,8,9 кролики.
Напоили кроликов, ждем когда наступит день их гибели. Номера кроликов, которые отравились, подскажут нам разряды с "1" (или с "0", если поили нулевых).

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

Послесловие. Зачем все это нужно?

Две крупные фирмы более всего известны своими оригинальными задачами на собеседовании, это Google и Microsoft, и вот как их представители объясняют зачем им это нужно: