"Задачки на сообразительность" на интервью

Наткнулся на интересную запись в блоге Эрика Липперта, не могу не поделиться, это волшебно :) Да, перевод взят из официальной русской версии блога Эрика.

----

Никто из моих знакомых в компании Microsoft больше не задает эти ужасные задачки «на нестандартную логику». Хотя, может быть, кто-то еще их задает, я не знаю. Но ходят слухи, что многие другие компании все еще следуют тому, как компания Microsoft проводила собеседования в 90-х. Продолжая эту старую традицию, я хочу представить продолжение истории Кейта Митчела о нестандартном мышлении. Итак, мы еще раз постараемся ответить на вопрос: «насколько успешно лауреат Нобелевской премии по физике, Ричард Филипс Фейнман прошел бы техническое собеседование в сотфверную компанию?»

Интервьюер: теперь мы переходим к той части собеседования, в которой мы проверим креативность вашего мышления. Не стоит обдумывать ответы слишком тщательно; просто используйте здравый смысл и объясните ход своих мыслей. Вот задача.

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

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

Интервьюер: Хм… Да, пожалуй, этот способ сработает. Но что, если у вас нет больших зеркал, или вы не можете установить их правильным образом?

РФФ: Тогда я достану дорогую цифровую видеокамеру, установлю ее на игрушку, и прикреплю к ней веревку достаточной длины. Я помещу видеокамеру в освещенную комнату, включу ее, и протяну другой конец веревки в комнату с выключателями. Затем, я немного поиграю с выключателями, делая пометки, в какой последовательности и в какое время я их переключал. Затем я вытяну камеру назад, в комнату с выключателями и просмотрю сделанные камерой записи. Сопоставив мои записи о порядке переключения выключателей с записью видеокамеры, я смогу определить, какой выключатель, какой лампой управляет.


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

РФФ: Это необычное ограничение, о котором вам стоило упомянуть заранее, ну да ладно. В этом случае я поступлю по-другому. Но, прежде всего, мне нужны дополнительные разъяснения. Могу ли я предполагать, что выключатели и лампы корректно подсоединены согласно национальным правилам установки электрооборудования? Т.е. к выключателям подходит фазовый провод, а не нейтраль, и что используются обычные 15 амперные, 120- вольтовые выключатели и т.д.?

Интервьюер: Думаю, да.

РФФ: И это одиночные выключатели? Или возможно, что эти выключатели являются частью совмещенных выключателей, какие можно увидеть в домах, когда два выключателя включают/выключают одну лампу, скажем, с обоих концов лестницы?

Интервьюер: А это важно?

РФФ: Конечно, важно! Вы спрашиваете меня об определении некоторых свойств стандартной электрической сети. Электрическое сопротивление человека, равно, ну, я не знаю, скажем, 1000 ом, и мы знаем, что сила тока равна напряжению, деленному на сопротивление. Это означает, что человек может получить удар током в 120 миллиампер, чего вполне достаточно для остановки человеческого сердца. Я предполагаю, что вы знаете детали системы, о которой вы меня спрашиваете; техника безопасности, которую я собираюсь описать, будет отличаться в зависимости от известных и неизвестных аспектов электрической сети.

Интервьюер: Хорошо. Предположим, что это самые обычные выключатели, ничего особенного.

РФФ: Отлично. Все три выключателя располагаются в одном корпусе, какие используются в настенных выключателях в вашем офисе, или в разных корпусах, для каждого переключателя?

Интервьюер: В одном корпусе.

РФФ: Я уверен, вы знаете, что существует два стандартных способа подключения выключателей, о которых сейчас идет речь. Первый способ следующий: мы берем фазу и нейтраль от источника питания, разделяем каждый из них на три провода, подключаем каждый из выключателей к соответствующей фазе, а затем протягиваем три пары проводов: нейтраль и коммутируемую фазу от выключателей к лампам. Второй способ противоположный первому: мы протягиваем три пары проводов от источника питания к лампе, а затем каждую нейтраль протягиваем к выключателям. Выключатель соединяет фазы, таким образом, одна из них находится под напряжением, а вторая – нет. Лампы включаются путем коммутации фазы. Какой из этих двух стандартных способов использован в этой системе?

Интервьюер: Мне кажется, что это не важно. И я, в общем-то, не знаю, как подключаются выключатели.

РФФ: Весьма странно, что вы задаете мне вопрос о свойствах электрической сети, но не знаете ее деталей.

Ладно, давайте предположим, что использован первый способ подключения. Таким образом, выключатель коммутирует фазу. Это значит, что если я сниму крышку с выключателя, я могу с легкостью определить, какая из фаз подходит от источника питания, а какой провод идет к лампам. Прежде чем снимать крышку с переключателя, я найду электрический щиток и обесточу цепь питания. Если потребуется, я отключу все электричество, если по какой-то причине я не смогу определить, какой выключатель к какой цепи относится. Также, я сообщу всем поблизости, что это я выключил электричество, поскольку я работаю с электрической сетью. Я, скорее всего, оставлю какой-нибудь знак, чтобы никто не включил электричество, и если электрический щиток закрывается на ключ, то я закрою его и заберу ключ с собой. Меня уже неоднократно било током и я приму все меры предосторожности, чтобы меня не ударило током из-за вашего эксперимента.

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

Интервьюер: О чем, черт побери, вы говорите?

РФФ: Задача сводилась к определению, какой выключатель, какой лампочкой управляет. При отключенной сети, никакой из выключателей никакой лампочкой не управляет. Любой выключатель может находиться в любом положении и ни одна лампочка не загорится. Но, мне кажется, что вы имели в виду не такое решение.

Интервьюер: Да, вы правы, я имел в виду не такое решение.

РФФ: Теперь, когда питание отключено, я могу спокойно разобрать коробку с выключателями и отсоединить коммутируемые фазы от всех трех выключателей. Затем я найду стандартный медный кабель типа NM-14/3 достаточной длины, чтобы протянуть его от комнаты с выключателями в комнату с лампами. Затем я подключу белый провод к отсоединенной коммутируемой фазе первого выключателя, черный провод – к фазе второго, а красный –третьего. Затем я протащу второй конец кабеля в комнату с лампами, которые должны быть сейчас выключены. Я выкручу все лампочки и воспользуюсь кабелем, как тестером целостности цепи. Воспользовавшись девятивольтовой батареей и вольтметром постоянного тока, я смогу определить, какой выключатель включает определенную лампу.

Интервьюер: А что если у вас нет возможности достать кабель достаточной длины?

РФФ: Сама постановка задачи говорит о том, что уже существует как минимум три кабеля достаточной длины для подключения выключателей к лампам, так что у кого-то такая возможность все-таки была. Если вы, конечно, не имеете в виду, что выключатели являются частью какой-то радиоканальной системы управления. Опять-таки, вы, кажется, упоминали ранее, что система не представляет собой «ничего особенного», а содержит простые 120-вольтовые выключатели.

Интервьюер: Да, это обыкновенные выключатели. Но, мне кажется, что вы кое-что забыли.

РФФ: Ага, я понял, о чем вы. Я спросил, являются ли выключатели обыкновенными 15 амперными и 120 вольтовыми выключателями, однако я не задал аналогичного вопроса о лампах. Если лампы являются низковольтными, тогда между  высоковольтными выключателями и низковольтными лампами, к которым я подключил свой тестер, должен находиться трансформатор переменного тока. В таком случае, мой тестер не даст результатов.

Интервьюер: Вообще-то, я хотел сказать, что поскольку вы не можете вернуться в комнату с выключателями, то ваш вариант с выключением электричества и разборкой выключателей не сработает.

РФФ: Отличное замечание. Поскольку я не могу вернуться назад, мне придется найти решение, при котором выключатели останутся собранными.

Интервьюер: Да. Сможете?

РФФ: Предположим, вместо того, чтобы подключать тестер после раскручивания выключателей, я просто заменю выключатели на реостаты. Я установлю на первом реостате низкое сопротивление, на втором – среднее, а на третьем – высокое. Затем, я восстановлю питание, и когда я зайду в комнату с лампами, я пойму, какой лампе, какой выключатель соответствует, по яркости свечения.

Интервьюер, с облегчением: Ну, вот это уже кое-что. Но…

РФФ: Ага, я вижу проблему, о которой вы хотите сказать. Если лампы являются флуоресцентными, тогда две из них будут выключенными или будут мигать, и гореть будет только лампа, для которой выставлено минимальное сопротивление на реостате. А если это будут лампы накаливания, тогда их яркость будет зависеть от их мощности. В условии задачи не говорилось, чтобы все лампы были лампами накаливания одной мощности. Так что, я не решил задачу. Вместо этого, я могу выкрутить лампы и проверить вольтметром напряжение, чтобы определить у какой из них высокое, среднее и низкое напряжение. Хотя, опять-таки, я предполагаю, что между выключателями и лампами нет трансформатора напряжения.

Интервьюер: Да забудьте вы наконец об измерении напряжения! Предположим, вы не можете достать до лампочек, чтобы измерить напряжение.

РФФ: Я снова должен указать, что кажется весьма странным, просить проверить электрическую систему и не позволять использовать стандартными инструментами. Но, в любом случае, вы сказали, что я был на правильном пути, так что, давайте двигаться в этом направлении. Мы знаем, что современные реостаты не изменяют сопротивление сигнала переменного тока; скорее, они «отрезают» его часть, а оставшуюся часть оставляют без изменения, с тем же уровнем и формой. Мы можем создать устройство, которое будет работать аналогично реостату, но значительно медленнее. Это устройство может содержать пару вращающихся кулачков, которые переключают выключатель раз в секунду. Теперь нам не нужно разбирать выключатели или полностью отключать питание. Мы подключим это устройство к первому выключателю, второй выключатель выключим, а третий – включим. Поскольку мы уже определились, что у нас есть только по одному выключателю на лампу и они соединены по всем стандартам, мы знаем, что «верхнее» положение выключателя должно включить лампу, а «нижнее» – выключить. Теперь мы пойдем в другую комнату. К выключенной лампе подключен второй выключатель, ко включенной лампе – третий, а к лампе, которая загорается и тухнет каждую секунду – первый. Этот способ будет работать не зависимо от типа ламп, конечно же, при условии, что лампы рабочие, а не сгоревшие.

Интервьюер: Да, кажется, этот вариант сработает. Все ваши решения требовали некоторого дополнительного оборудования. Можете ли вы решить эту задачу не создавая ничего и не используя специальных инструментов, а воспользовавшись каким-нибудь другим фактором?

РФФ: Каким именно?

Интервьюер: Например, тем фактом, что лампы не только освещают комнату?

РФФ: Например?

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

РФФ: И как я смогу измерить температуру ламп без специального оборудования? Вы же только что сказали, что я не могу до них добраться.

Интервьюер: Хм. Да, кажется, я об этом говорил.

РФФ: И в вашем способе я вижу ряд дополнительных проблем. Вы не уточнили расстояние между комнатами, но несколько раз подразумевали, что это значительное расстояние; я не могу видеть свет из комнаты с выключателями, я не могу установить зеркала и я не могу найти провод достаточной длины, все это говорит о значительном расстоянии между ними. За то время, которое мне потребуется, чтобы дойти из одной комнаты в другую, третья лампа может успеть остыть. Она вообще может быть не слишком теплой, поскольку вместо обычных ламп накаливания могут применяться флуоресцентные или современные светодиодные лампы, значительно меньшей мощности, нежели обычные лампы. Кроме того, мы не определились с тем, где это происходит. Если действие происходит в местности с горячим климатом, как Лос-Аламос летом, обе выключенные лампы могут быть теплыми, а если действие происходит в Аляске зимой, в незакрытой комнате, обе могут быть холодными. Ваш вариант зависит от ряда условий, которые не упоминались в постановке задачи. И обычно, это плохая идея проверять температуру чего-то горячего простым прикосновением.

Интервьюер: Хорошо, давайте закончим с этой частью интервью. Прежде чем вы уйдете, может быть у вас есть вопросы об этой компании, команде или об этой работе?

РФФ: Да, у меня есть пара вопросов. Когда вы пишете программные алгоритмы, вы создаете системы, используя известные принципы для создания программ, отвечающих индустриальным стандартам и практикам?

Интервьюер: Конечно.

РФФ: И вы используете инструменты для анализа ПО, такие как профайлеры, отладчики, системы доказательства теорем и т.д. для упрощения определения и диагностики ошибок?

Интервьюер: Да, опять-таки, конечно.

РФФ: Тогда почему вы задаете вопросы, которые подталкивают меня бросить индустриальные стандарты, общепринятые техники использования типовых инструментов для определения целостности электрической системы? И почему решение, к которому вы меня подталкиваете, основывается на недокументированных и ненадежных побочных явлениях? Неужели ваша команда пишет код, корректность которого основывается на недокументированных и ненадежных взаимосвязях, которые могут на порядок отличаться в зависимости от деталей реализации?

Интервьюер: Доктор Фейнман, спасибо, что пришли. Мы с вами свяжемся.