[Перевод] Собеседования по алгоритмам: теория vs. практика27.01.2020 13:53

tl; dr За последние десятилетия мода на собеседования программистов менялась несколько раз, и каждая из них выглядит нелепо в ретроспективе. Либо мы наконец-то нашли настоящий секрет эффективных собеседований, либо увлеклись очередным модным течением, которое через десять-двадцать лет покажется столь же нелепым.

Когда я спрашиваю людей в модных больших технологических компаниях, почему на собеседовании так обязательно спрашивать об алгоритмах, самый распространённый ответ — что-то вроде: «У нас такой масштаб, мы не можем позволить, чтобы кто-то случайно написал функцию O(n^2) и повалил всю систему»1. Что особенно забавно, в последнее время я немало применял на практике эти алгоритмы и решал реальные проблемы, но не могу пройти собеседования, где о них спрашивают! Думаете, я проваливаю половину собеседований или что-то в этом роде? Нет, больше половины. Я участвовал примерно в 40 «настоящих» собеседованиях и прошёл, может, одно или два. Или ни одного2.

Когда я написал черновик этой статьи, друзья посчитали его занудным, потому что я провалил слишком много собеседований. Они говорят, нужно свести все неудачи в таблицу, потому что никто не станет читать десять страниц текста с длинным перечнем неудач. Хороший совет. Уже работаю над таблицей.
Рассмотрим несколько примеров.

В одной крупной компании, где я работал, команда написала базовую библиотеку с собственной реализацией динамического массива. Если во время работы размера не хватало, реализация добавляла к массиву фиксированное число строк, а затем копировала старый массив в новый массив чуть большего размера. Это классический пример неправильной реализации динамического массива, поскольку она приводит к линейному росту времени вместо амортизированного постоянного времени. Это настолько классический пример, что его часто используют в качестве канонического при объяснении амортизационного анализа.

У больших IT-компаний типичные собеседования по телефону делятся на три категории:

Один «простой» вопрос о программировании/алгоритмах, возможно, сначала с «очень простым» вопросом для разминки.
Серия «очень простых» вопросов о программировании/алгоритмах.
Куча общеизвестных фактов (редко для хороших должностей, но нередко для низкоуровневых или нетворческих позиций).

Эта проблема реализации массива считается настолько простой, что попадает в категорию «очень легко» и является либо разминкой для «реального» вопроса или идёт в комплекте с кучей таких же простых вопросов. И всё же в нашей компании такой динамический массив отвечал примерно за 1% всей нагрузки на сборщик мусора в коде JVM (это был второй по величине источник выделений памяти во всём коде), а также за значительную долю нагрузки на CPU.

К счастью, эта реализация не использовалась в качестве универсального динамического массива, а создавалась только с помощью полуспециализированной оболочки, поэтому отвечала «всего» за 1% давления на GC. Если бы вопрос задали на собеседовании, большинство членов той команды правильно ответили бы на него. Мой патч принёс работодателю за год больше денег, чем я заработал в своей жизни.

Это был второй по величине источник выделений памяти, главный же — преобразование пары значений long в массивы байт из той же базовой библиотеки. Видимо, кто-то написал или скопипастил хэш-функцию, которая брала массив в качестве входных данных, а затем изменил код, чтобы брать два массива и работать с ними в последовательности из старого интерфейса хэш-функции типа byte[], byte[]. Чтобы вызвать эту функцию на двух лонгах, они использовали удобную функцию преобразования long в byte[] в широко используемой служебной библиотеке. Кроме выделения byte[] и вставке туда long, эта функция также изменяет порядок следования байтов long (видимо, функция была предназначена для преобразования значений long в сетевой порядок байтов).

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

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

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

Ещё один пример простого вопроса по алгоритмам — реальная конфигурация для BitFunnel, поискового индекса, который используется в Bing3.

Описание полного контекста этой конкретной компании займёт слишком много времени, но вкратце, нужно настроить набор фильтров Блума. Один из способов — написать функцию оптимизации по модели чёрного ящика, которая с помощью градиентного спуска пытается нащупать оптимальное решение. Они так и сделали, однако у функции проявились какие-то странные свойства, а выходная конфигурация никогда не работала идеально. Это исправили разреживанием фильтров Блума, то есть выделив на проблему ещё больше ресурсов (и, следовательно, денег).

Анализируя возможности для оптимизации, вы можете заметить, что фундаментальная операция в BitFunnel эквивалентна умножению вероятностей. Поэтому для любой конкретной конфигурации вы можете просто умножить некоторые вероятности — и определить, как будет работать конфигурация. Поскольку пространство конфигураций не так уж велико, можно циклами перебрать все возможные варианты, а затем выбрать наилучший. В реальности не совсем так, потому что умножение вероятностей предполагает некоторую независимость, которая не имеет места в реальности, но метод всё равно нормально работает по той же причине, по которой довольно хорошо работала наивная байесовская фильтрация спама, которая неправильно предполагает независимую вероятность появления в письме любых двух произвольных слов. Для полного решения можете проанализировать взаимозависимости. Хотя это, вероятно, выходит за рамки собеседования.

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

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

В начале статьи мы отметили, что крупные IT-компании задают вопросы по алгоритмам, поскольку им дорого обойдётся неэффективность в большом масштабе. Мой опыт показывает, что в каждой компании, которая проводит собеседование, миллион примеров такой неэффективности. Получается, что вопросы по алгоритмам на собеседовании не помогают решать реальные алгоритмические задачи на работе.

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

Из трёх решений для приведённых выше примеров два ушли в прод. Для меня это нормальный процент, если меня просто пригласили в случайный проект, за которым я не слежу постоянно. Циники могут сказать, что процент даже высок. В случайной команде результаты могли быть и хуже, потому что им невыгодно внедрение никакого решения, даже эффективного. Ведь оно требует от них тестирования, интеграции и развёртывания изменений. Создаются новые риски. То есть я прошу команду сделать какую-то работу и взять на себя некие риски, чтобы сделать что-то полезное для компании, но бесполезное для них самих. Несмотря на всё это, люди обычно принимают код, хотя не очень склонны тратить время на оптимизацию (их рабочее время будет потрачено на вещи, которые согласуются с целями команды)4.

Предположим, что компания откажется предлагать кандидатам головоломки на собеседованиях, а будет поощрять разработчиков использовать более простые и относительно эффективные алгоритмы. Вряд ли какой-то из приведённых примеров мог остаться незамеченным в течение многих лет. Проблему наверняка бы исправили. Какой-нибудь гипотетический разработчик в компании с профилированием кода увидел бы самые «горячие» элементы в профиле для самой ресурсоёмкой библиотеки.

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

Я действительно однажды работал в компании, которая не задавала на собеседованиях вопросов по алгоритмам, а концентрировалась на практических вопросах. За время моего пребывания там я нашёл только одну возможность для оптимизации, которая почти соответствует критериям выше (из-за небольшого размера она слегка не проходит по третьему пункту, то есть к тому времени я за свою жизнь заработал больше, чем принесла годовая экономия от исправления этого бага).

Почему в этой компании почти не было проблем с затыками в производительности? Думаю, основная причина в том, что достаточно много людей считали улучшение компании своей работой. Поэтому системы изначально были спроектированы почти оптимально. В редких исключениях находилось достаточно специалистов, которые старались и дальше принести пользу компании, а не лично себе и своей команде (что совершенно отличается от глобальной выгоды для компании). Таким образом, всегда находился тот, кто решил проблему до того, как она попадалась мне.

В крупных IT-компаниях собеседование по алгоритмам с проверкой навыков кодинга обычно проще, чем первоначальный отсев по телефону. Обычно здесь не затрагивают вопросы системного дизайна.

Некоторое время назад мы пробовали задавать вопрос по алгоритмам на очном собеседовании. Довольно жёсткий вопрос, но в рамках того, что вы могли бы встретить при телефонном скрининге в большие корпорации (но всё же проще, чем вы ожидаете от личных собеседований). Мы отказались от такой практики, потому что абсолютно все кандидаты проваливали эту часть (опытным кандидатам мы не задавали вопрос по алгоритмам). Наша фирма не такая известная, чтобы получить кандидатов-новичков, способных легко ответить на эти вопросы, поэтому эти модные фильтры отсева кандидатов у нас не работают. В современных статьях по найму персонала то, что мы сделали, часто называют «понижением планки», но мне непонятно, почему нас должна волновать максимальная высота прыжка кандидата, если его работа редко (или вообще никогда) не предусматривает прыжки в высоту. А в тех случаях, когда нужно действительно прыгнуть, планка установлена на высоте примерно пять сантиметров.

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

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

В старые добрые времена на собеседованиях задавали «пустяковые» вопросы. Современные версии могли бы выглядеть следующим образом:

Что такое MSI? MESI? MOESI? MESIF? В чем преимущество MESIF над MOESI?
Что делает деструктор? А если это C++11? А если из деструктора верхнего уровня вызвать деструктор подобъекта, то деструкторы каких ещё подобъектов будут выполняться? А во время раскрутки стека? При каких обстоятельствах можно избежать вызова std::terminate?

Я слышал об этих простых собеседованиях ещё в школе и даже видел в некоторых компаниях «старой школы». Это было во времена лидерства Microsoft, когда все остальные равнялись на успешную компанию и копировали Microsoft. Самый читаемый блоггер в области программирования (Джоэл Сполски) говорил, что всем нужно принять некую практику разработки X, потому что так делает Microsoft. Например, в одной из самых влиятельных статей по программированию той эпохи Джоэл Сполски представил так называемый «тест Джоэла», который определяет, насколько вы идёте в ногу с такими компаниями, как Microsoft:

12 баллов — это отлично, 11 — терпимо, но с оценкой 10 или ниже у вас серьёзные проблемы. Правда в том, что большинство софтверных работают на уровне 2–3 балла, и им нужна серьёзная помощь, потому что компании вроде Microsoft работают на уровне 12 полный рабочий день.

Согласно распространённым легендам того времени, Microsoft на собеседованиях задавала примерно такие вопросы (и мне действительно на собеседовании в Microsoft в районе 2001 года задали одну из таких задачек, при полном отсутствии вопросов по алгоритмам или программированию):

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

Поскольку я проходил собеседование в эпоху перемен, мне задавали множество простых вопросов и кучу задачек (включая все вышеперечисленные). На собеседованиях того времени ещё были популярны вопросы Ферми, которые технически не являются головоломками. Другая тенденция того времени — поведенческие интервью без единого технического вопроса.

Как бы то ни было, тогда люди пытались копировать интервью в стиле Microsoft. Когда я спрашивал, чем хороши головоломки или вопросы Ферми, мне отвечали, что таким образом можно проверить, способен ли кандидат к размышлениям, в отличие от вопросов на знание, которые говорят только о том, что человек запомнил какую-то информацию. А нам нужны кандидаты, которые действительно могут думать!

Оглядываясь назад, теперь всем понятно, что это было неэффективно, а копирование каждого приёма Microsoft не сделает вашу компанию такой же успешной, потому что Microsoft использовала много других приёмов — они эффективны только все вместе за счёт сетевого эффекта. Копируя собеседования Microsoft, вы будете компанией, которая просто проводит собеседования в томже стиле, но не сможете воспользоваться сетевыми эффектами, которые использовала Microsoft.

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

В те времена интервьюеры находили вопросы для собеседований в книгах для подготовки к собеседованиям, таких как «Как переместить гору Фудзи». Эти вопросы задавали кандидатам, которые узнавали ответы в тех же книгах. Современная молодёжь находит это смешным — очевидно, что вопросы не имеют никакого отношения к работе, а вероятность хорошего ответа больше зависит от подготовки к собеседованию, чем от компетентности кандидата. Но сегодняшний подход не так уж отличается.

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

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

Вдохновлённый комментарием Уэсли Аптекар-Касселса, в последнее время я специально спрашивал у представителей работодателей, как они проверяют эффективность своих собеседований и как борются с предвзятостью. Вот что они отвечали (в порядке убывания частоты):

Что? Ничего такого, зачем это?
Мы действительно не знаем, эффективен ли наш процесс.
Мы просто знаем, что всё работает.
У нас нет предвзятости.
Мы бы заметили предвзятость, если бы существовал процесс оценки.
Кто-то изучал и/или проводил исследование, но не может сказать ничего конкретного о том, как это изучалось и по какой методологии проводилось исследование.

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

Я уже упоминал, что почти во всех компаниях система не стимулирует людей тратить время на повышение эффективности, даже если простой расчёт показывает, что исправление багов легко сэкономит десятки или сотни миллионов долларов. И в отсутствие стимулов у разработчиков неоткуда появиться опыту выполнения такой работы. Незнакомая работа всегда кажется сложнее, чем есть на самом деле. Таким образом, даже если день работы может принести $1 млн в год в виде экономии или прибыли (такое довольно часто встречается в крупных компаниях, по моему опыту), люди не понимают, что это всего лишь один день работы и её можно сделать практически не отвлекаясь от остальных дел. Один из способов решить эту последнюю проблему — обучение. Впрочем, для менеджера его ещё труднее обосновать, чем повышение эффективности, которое не входит в основные задачи!

Например, однажды я написал небольшое руководство (4500 слов, меньше этой статьи, если не считать изображения) по поиску различных неэффективностей в системе: как использовать профайлер для выделений памяти и времени CPU, как настроить наши GC для специализированных задач, как использовать некоторые мои инструменты для автоматического поиска узких мест в конфигурациях JVM, контейнеров и т. д. В основном, это простые и очень эффективные приёмы, которые легко выполнить. Пара человек смогли отладить и исправить проблему самостоятельно, и из вторых рук я слышал, что ещё кто-то повысил эффективность своего сервиса. Хорошо, если 10% инженеров извлекли пользу из этого мануала, надеюсь, он помог десяткам инженеров, а может и больше.

Если бы вместо руководства я потратил неделю на «реальную» работу, то получил бы нечто конкретное, с количественной ценностью, что красиво выглядит в промо-пакете или обзоре производительности. Вместо этого у меня какое-то туманное достижение, что в лучшем случае можно считать отчасти «дополнительной заслугой». Я не жалуюсь — это именно тот результат, которого я ожидал. Но в среднем компании получают то, к чему они сами стимулируют сотрудников. Если они ожидают, что обучение исходит от самих разработчиков (не финансируя производство учебных материалов), но не ценят его так же, как работу разработчиков, то обучение станет редкостью.

Полагаю, несложно заметить слабое качество публичных учебных материалов из-за относительной трудности монетизации образования и обучения. Если вы хотите монетизировать учебные программы, есть несколько хороших методов. Судя по всему, неплохо работает монетизация ценных видеокурсов (сотни или тысячи долларов за короткий курс). Корпоративные тренинги, когда компании приглашают вас поговорить с 30 людьми, а вы берёте $3000 с каждого, также работают довольно хорошо.

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

Например, Джулии Эванс хватает на жизнь доходов от продажи компьютерных комиксов, которые в последнее время приносят около $100 тыс. в год. Специалист по корпоративным тренингам может заработать это за один-два дня.

Из трёх приведённых выше примеров в двух случаях я получил какое-то поощрение за то, что сэкономил деньги компании. По моему опыту, в больших компаниях такое случается редко, но даже в этом случае распределение стимулов оказалось довольно плохим. В какой-то момент, после повышения в должности и увеличения зарплаты, я вычислил соотношение моей прибавки и экономии, которую я принёс фирме. Соотношение составило примерно 0,03% напрямую в деньгах, без учёта разработанных мной инструментов, для которых трудно вычислить конкретную ценность. Вероятно, эта ценность на самом деле больше, чем значение, поддающееся количественной оценке. Поэтому можно сделать вывод, что я получил значительно меньше 0,01% от суммы, которую принёс фирме. И это ещё завышенная оценка: в реальности я сильно подозреваю, что на самом деле сделанная работа ничего мне не принесла, а повышение никак не связано с этим проектом, который сэкономил компании десятки миллионов долларов. После первых $10 млн в год или, возможно, $20 млн в год, уже нет никаких стимулов делать работу с точки зрения оценки эффективности, продвижения, повышения и т. д. Потому что в этом нет никаких плюсов, зато есть некоторые минусы (вы можете ввязаться в подковёрные интриги, случайно обрушить сайт и т. д.), так что отдача от выполнения необязательной работы, вероятно, становится отрицательной.

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

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

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

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

1. Во-первых, собеседования Google зачастую копируют маленькие компании, для которых этот аргумент неуместен. Но даже никто из крупных компаниях не разрабатывает и не внедряет крупномасштабные алгоритмы (возможно, последней это делала Google примерно в 2003 году, но в современных крупных IT-компаниях никто особенно не сосредоточен на разработке алгоритмов). [вернуться]

2. «Настоящих» взято в кавычки, потому что несколько собеседований я прошёл по причинам, не связанным с процессом самого собеседования. Может, у меня были очень хорошие рекомендации, а может кто-то прочитал мой блог или навёл справки от бывших коллег, или посмотрел мои опенсорсные проекты (насколько я знаю, такое случалось один или два раза). Обычно после явного провала на собеседовании я спрашиваю, почему мне предложили работу, поэтому собрал уже коллекцию таких причин.

Я также предполагаю возможность нулевого результата, потому что единственное «настоящее» собеседование по программированию было в Google, но меня пришли собеседовать неправильные ребята. Я шёл на работу с железом, а меня интервьюировали программисты, поэтому я получил по сути стандартное программистское интервью, за исключением того, что один интервьюер задал несколько вопросов о машине состояний и когерентности кэша (или что-то в этом роде). Затем мне организовали телефонное собеседование с инженером-аппаратчиком, чтобы убедиться, что я не врал о работе в аппаратном стартапе с 2005 по 2013 годы. Вполне возможно, что я провалил программистскую часть интервью и был нанят только благодаря последующему телефонному разговору.

Обратите внимание, что мои слабые результаты относятся только к собеседованиям по программированию, а не по железу. В собеседованиях по железу я действительно хорош, хотя в настоящей работе давно не практиковался. Один мой знакомый говорит, что аппаратные интервью мне так хорошо даются из-за специфического жаргона: я «говорю как инженер по аппаратному обеспечению» и фактически мы с инженерами-электронщиками говорим на одном языке. С другой стороны, некоторые вещи мы высказываем таким образом, что они звучат невероятно глупо для большинства программистов, но проблема именно с лексикой, жаргоном, а не фактическими знаниями или навыками. [вернуться]

3. Это немного более сложный вопрос, чем вы могли ожидать по телефону и такой вопрос вполне можно ожидать на очном собеседовании. Хотя моему другу на телефонном собеседовании с Google однажды задали вопрос с мирового финала Google Code Jam, так что для максимальной сложности действительно нет предела, смотря кто вас спрашивает.

Кстати, если вам интересно, мой друг на самом деле знал ответ, потому что решал эту задачу на Google Code Jam. На самом конкурсе он не нашёл правильный ответ, но позже посмотрел его для забавы. Однако он не счёл разумным сразу выдавать ответ по телефону, а попросил интервьюера задать другой вопрос. Тот отказался, так что мой друг провалил телефонное собеседование. Хотя я сомневаюсь, что в мире найдётся больше пары сотен человек, способных правильно ответить на такой вопрос по телефону, и почти все они, вероятно, поняли бы абсурдность ситуации. Провалив собеседование, мой друг почти полгода искал работу, прежде чем пройти собеседование для стартапа, для которого он в конечном итоге разработал несколько ключевых систем (с точки зрения как влияния на бизнес, так и технических трудностей). Он и сейчас продолжает там работать после того, как компания провела IPO более чем на миллиард долларов. Компания понимает, как трудно заменить этого человека, и очень хорошо к нему относится. [вернуться]

4. Помимо вопиющих архитектурных проблем, которые просто приведут к падению сервиса, есть ещё один момент. Команды зачастую решают проблемы эффективности просто запрашивая дополнительные вычислительные ресурсы. Некоторые компании пытаются каким-то образом бороться с этим. Я слышал, что в Facebook многие команды, работающие над повышением эффективности, рапортуют в специальный отдел, который позволяет им блокировать запросы на расширение ёмкости, если они замечают у какой-то команды крайнюю неэффективность, которую те отказываются исправить. Но лично мне не попадались такие компании. В Google эту проблему пытались решать системой, которая, среди прочего, соотносила численность персонала с вычислительными ресурсами, но я слышал, что от неё в итоге отказались в пользу более традиционной системы по некоторым причинам. [вернуться]