Анализ задачи с собеседования в Google: конь и телефонные кнопки

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

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

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

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

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

▍ Задача

Представьте, что мы помещаем шахматного коня на телефонный номеронабиратель. Эта шахматная фигура ходит буквой «Г»: две клетки по горизонтали, и одна по вертикали или одна клетка по горизонтали и две по вертикали:

Не обращайте внимания на плохо замазанные кнопки со звёздочкой и решёткой

Кнопки на номеронабирателе можно нажимать только ходом коня. Каждый раз, когда конь попадает на кнопку, мы нажимаем её и делаем ещё один ход. Начальная позиция тоже считается нажатой.

Сколько уникальных чисел можно набрать за N ходов из конкретной начальной позиции?

▍ Обсуждение

Все проводимые мной собеседования, по сути, разбиты на две части: сначала мы находим алгоритмическое решение, а затем кандидат реализует его в коде. Я говорю «мы находим», потому что я не просто бессловесный наблюдатель: 45 минут — это не так много времени, чтобы спроектировать и реализовать что-то даже в самых лучших условиях, не говоря уже о стрессовом состоянии на собеседовании. Я позволяю кандидатам брать на себя инициативу в рассуждениях, генерировать идеи, решать разные случаи задачи и так далее, но с радостью готов и подталкивать их в правильном направлении. Чем лучше кандидат, тем меньше подсказок я обычно даю, но пока я ещё не видел ни одного кандидата, которому бы вообще не требовались подсказки.

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

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

Никогда не стоит сразу браться за код! Рассмотрение маленьких примеров позволяет выявлять паттерны и пограничные случаи, а также сформулировать решение в голове. Пример: допустим, мы начинаем с 6 и можем сделать два хода. Комбинации будут такими:

• 6–1–8,
• 6–1–6,
• 6–7–2,
• 6–7–6,
• 6–0–4,
• 6–0–6.

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

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

▍ Уровень 0: сделаем следующий ход

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

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

Меня вполне устроит «давайте предположим, что есть функция, возвращающая соседей» и соответствующая заглушка. Разумеется, вероятно, я потом спрошу, сможете ли вы реализовать её, но только если у нас останется время. Вы можете просто написать такую заглушку и двигаться дальше:

def neighbors(position):
    ...

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

Учитывая, что функция поиска соседей не меняется, мы можем просто создать map и возвращать соответствующее значение:

NEIGHBORS_MAP = {
    1: (6, 8),
    2: (7, 9),
    3: (4, 8),
    4: (3, 9, 0),
    5: tuple(),  # 5 не имеет соседей
    6: (1, 7, 0),
    7: (2, 6),
    8: (1, 3),
    9: (2, 4),
    0: (4, 6),
}
def neighbors(position):
    return NEIGHBORS_MAP[position]

▍ Уровень 1: рекурсивно генерируемые числа

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

def yield_sequences(starting_position, num_hops, sequence=None):
    if sequence is None:
        sequence = [starting_position]
    
    if num_hops == 0:
        yield sequence
        return

    for neighbor in neighbors(starting_position):
        yield from yield_sequences(
            neighbor, num_hops - 1, sequence + [neighbor])

def count_sequences(starting_position, num_hops):
    num_sequences = 0
    for sequence in yield_sequences(starting_position, num_hops):
        num_sequences += 1
    return num_sequences

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

▍ Уровень 2: подсчёт без подсчёта

Как можно подсчитать телефонные номера, не генерируя их? Это возможно, но требуются дополнительные рассуждения. Обратите внимание, что количество чисел, которые можно сгенерировать из начальной позиции за N ходов, равно сумме количества ходов, которые можно сгенерировать, начиная с каждого из её соседей за N-1 ходов. Можно записать это математически как рекуррентное отношение:

Это становится интуитивно понятно, когда мы рассмотрим происходящее при только одном ходе: кнопка 6 имеет 3 соседа (1, 7 и 0), и за ноль ходов мы можем получить по одному числу на каждый, то есть набрать лишь три числа.

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

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

from neighbors import neighbors                                 
                                                                
def count_sequences(start_position, num_hops):                  
    if num_hops == 0:                                           
        return 1                                                
                                                                
    num_sequences = 0                                           
    for position in neighbors(start_position):                  
        num_sequences += count_sequences(position, num_hops - 1)
    return num_sequences                                        
                                                                
if __name__ == '__main__':                                      
    print(count_sequences(6, 2))      

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

Дальше вы часто будете слышать от меня такой вопрос: каким будет сложность («О» большое) этого решения? Если вы не знаете этого понятия, то вот неформальное объяснение: сложность алгоритма («О» большое) — это условное обозначение скорости, с которой растёт количество необходимых вычислений как функция от размера входных данных. В нашей задаче размер входных данных — это количество ходов. Если вас интересует строгое математическое определение, то его можно прочитать в Википедии.

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

Это плохо. Добавление каждого нового хода удваивает, если не утраивает время выполнения. Для небольших чисел, допустим, от 1 до 20, это приемлемо, но если количество ходов становится всё больше и больше, то рано или поздно мы уткнёмся в стену. Например, для обработки 500 ходов потребуется сильно больше времени, чем до тепловой смерти Вселенной.

▍ Уровень 3: мемоизация

Можно ли придумать что-то получше? Если не использовать ничего, кроме представленного выше математического отношения, то практически нет. Однако одна из причин моей любви к этой задаче заключается в том, что она позволяет размышлять слой за слоем, приходя ко всё более эффективным решениям. Чтобы найти следующее, давайте разложим вызовы функции, выполняемые этой функцией. Рассмотрим случай count_sequences(6, 4). Для краткости я использовал в качестве имени функции C:

Возможно, вы заметили нечто любопытное: вызов C(6, 2) выполняется три раза, и каждый раз он выполняет одни и те же вычисления, возвращая одно и то же значение. Ключевой вывод здесь заключается в том, что эти вызовы функции повторяются, каждый раз возвращая одинаковое значение. После первого вычисления их результата повторно вычислять его не нужно.

Вероятно, вы задаётесь вопросом, как же прийти к этому наблюдению: проще всего это сделать при помощи старой доброй белой доски: внимательное прочтение абстрактной формулировки задачи — это, конечно, здорово, но я всегда подталкиваю кандидатов к тому, чтобы они набросали простое решение на доске. Подобный процесс решения и рисование дерева даст нам понять, что мы много раз рисуем поддерево для C(6, 2), что сложно не заметить. Иногда этого наблюдения даже достаточно, чтобы кандидаты полностью пропустили решения 1 и 2, напрямую перейдя к этому этапу. Не нужно и говорить, что это сильно экономит время собеседования, в котором на решение задачи выделено всего 45 минут.

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

def count_sequences(start_position, num_hops):
    cache = {}

    def helper(position, num_hops):
        if (position, num_hops) in cache:
            return cache[ (position, num_hops) ]

        if num_hops == 0:
            return 1

        else:
            num_sequences = 0
            for neighbor in neighbors(position):
                num_sequences += helper(neighbor, num_hops - 1)
            cache[ (position, num_hops) ] = num_sequences
            return num_sequences

    res = helper(start_position, num_hops)
    return res

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

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

Линейное время! Совсем неплохо. На самом деле, замечательный результат: добавление простого кэша изменило время выполнения алгоритма с экспоненциального на линейное. На моём старом MacBook Air выполнение рекурсивной реализации для двадцати ходов занимает около 45 секунд. Новая реализация способна обработать 500 ходов примерно за 50 миллисекунд. Отлично!

Ну так что, мы на этом закончили? Не совсем. Это решение имеет два недостатка: один серьёзный (более-менее), другой не особо. Серьёзный недостаток заключается в рекурсивности. Большинство языков накладывает ограничение на размер своего стека вызовов, то есть существует максимальное количество ходов, которое может поддерживать реализация. На моей машине ошибка возникает примерно после 1000 ходов. Я называл это ограничение «более-менее» серьёзным, потому что любую рекурсивную функцию можно реализовать итеративным образом, но повозиться всё равно придётся. Что же касается несерьёзного ограничения, то оно приводит нас к следующему решению…

▍ Уровень 4: динамическое программирование

Несущественное ограничение рекурсивного решения с мемоизацией становится очевидным, если взглянуть на показанное выше рекуррентное отношение:

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

Что тут происходит? Как всегда, результат становится очевидным, если взглянуть на расписанное решение и на код. Обратите внимание, что код начинается с наибольшего количества ходов и рекурсивно спускается до наименьшего:

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

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

Однако можно обратить порядок: посещать слои с N ходов только после того, как мы посетили слои с N-1 ходов. Если вы изучали или изучаете дискретную математику, то уже заметили все необходимые ингредиенты для индукции: мы знаем, что значения вызовов функции для нулевых ходов всегда равны единице (базовый случай). Также мы знаем, как комбинировать значения N-1 ходов для получения значений N ходов при помощи рекуррентного отношения (шаг индукции). Мы можем начать с базового случая с нулём ходов и индукцией получить все значения больше нуля. Вот реализация:

def count_sequences(start_position, num_hops):                
    prior_case = [1] * 10                                     
    current_case = [0] * 10                                   
    current_num_hops = 1                                      
                                                              
    while current_num_hops <= num_hops:                       
        current_case = [0] * 10                               
        current_num_hops += 1                                 
                                                              
        for position in range(0, 10):                         
            for neighbor in neighbors(position):              
                current_case[position] += prior_case[neighbor]
        prior_case = current_case                             
                                                              
    return current_case[start_position]   

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

▍ Оценка

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

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

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

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

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

Любого, кому могу сказать подобное, я буду считать отличной кандидатурой для найма (Strong Hire). Однако «подходит для найма» (Hire) и «умеренно подходит для найма» (Leaning Hire) — тоже положительные характеристики. Если вы слабы в одной области, но демонстрируете талант в другой, то я, вероятно, тоже дам положительную рекомендацию.

▍ Подведём итог

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

В связи с этим приведу список навыков, охватываемых этой задачей, и привычек, которые вам стоит развить:

• Всегда начинайте с решения вручную небольшого примера задачи. В этой задаче рекуррентное отношение и повторение вызовов функции становятся гораздо очевиднее, если решить её вручную.
• Обращайте внимание на те места, где ваше решение вычисляет то, что вам не понадобится, например, как в примере решения с наивным подсчётом: последовательности чисел генерируются, но мы их не используем. Редуцирование ненужных вычислений часто приводит к нахождению более простых решений, а то и открывает двери к созданию более эффективных.
• Освойте рекурсию. По большей мере в коде продакшена она бесполезна, потому что активно использует стек, но это очень мощная тактика проектирования алгоритмов. Рекурсивные решения часто можно адаптировать и улучшить: разница между наивным решением с экспоненциальным временем и почти оптимальным решением с мемоизацией и линейным временем минимальна.
• Освойте анализ «О» большого! Вам практически гарантированно зададут вопрос о нём на каком-то этапе процесса собеседования.
• Всегда ищите возможности мемоизации. Если ваша функция детерминирована и вы будете вызывать её много раз с одними и теми же входными данными, то решение может выиграть от мемоизации.
• Найдите и запишите рекуррентное отношение. В данном случае, когда мы записали его, стало очевидным, что количества для N ходов зависят только от количеств для N-1 ходов.