Задача, которую предлагали разработчикам на собеседованиях в Reddit: разбор и решение от сотрудника компании

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

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

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

Игра «Жизнь»

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

1. Соседи: у каждой клетки может быть восемь соседей (сверху, снизу, справа, слева и по диагонали).
2. Изоляция: живая клетка, у которой только один живой сосед или они вообще отсутствуют, погибнет в следующем состоянии поля.
3. Выживание: живая клетка, у которой ровно два или три живых соседа, выживет в следующем состоянии поля.
4. Перенаселение: живая клетка, у которой четыре и больше живых соседей, погибнет в следующем состоянии поля.
5. Воспроизводство: мертвая клетка, у которой ровно три живых соседа оживет в следующем состоянии поля.

По часовой стрелке: воспроизводство — перенаселение — изоляция — выживание

Если повторять эти вычисления раз за разом, становится всё более и более интересно.



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

Задача у кандидата такая: у него есть массив массивов, представляющий состояние поля (где 'x' обозначает состояние живая, а ' ' – состояние мертвая), и нужно рассчитать следующее состояние.

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

Решение: часть первая

Давайте разберемся со сложностями имплементации. Задачу можно разбить на две части: сначала мы вычисляем состояние каждой отдельной клетки (живая или мертвая), а потом с опорой на эти расчеты просчитываем состояние всего поля.

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

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

LIVE_CELL = 'x'
DEAD_CELL = ' '

def update_cell(board, row, col):
    # Счётчик соседних живых клеток
    neighbor_count = 0

    for row_offset in (-1, 0, 1):
        for col_offset in (-1, 0, 1):
            if row_offset == 0 and col_offset == 0:
                continue

            new_row = row + row_offset
            if new_row < 0 or new_row >= len(board):
                continue

            # Исходя из предположения, что у всех рядов одинаковая 
            # длина, проверяем выход за границы поля.
            new_col = col + col_offset
            if new_col < 0 or new_col >= len(board[0]):
                continue

            if board[new_row][new_col] == LIVE_CELL:
                neighbor_count += 1
            elif board[new_row][new_col] != DEAD_CELL:
                raise ValueError('invalid cell value')

    if board[row][col] == LIVE_CELL:
            # Нет ни перенаселенности, ни изоляции
            if not (neighbor_count <= 1 or neighbor_count >= 4):
                return LIVE_CELL
    elif neighbor_count == 3:
            # Воспроизводство
            return LIVE_CELL

    return DEAD_CELL

Тут часто допускают несколько ошибок:

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

Решение: часть вторая (неверная)

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

def update_state_wrong(board):
    for row in range(len(board)):
            for col in range(len(board[0])):
                board[row][col] = update_cell(board, row, col)

        return board

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



Только что обновленные — Еще не обновленные

Решение: часть третья (верно, но накладно)

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

def update_state_slow(board):
    import copy
    old_board = copy.deepcopy(board)

    for row in range(len(board)):
            for col in range(len(board[0])):
                board[row][col] = update_cell(old_board, row, col)

        return board

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



Старое поле — Новое поле

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

Можно сказать, что это не слишком существенно, и, честно говоря, если бы кандидат здесь остановился, я бы не стал считать это за минус. То, что он сумел дойти до этого этапа в стрессовых условиях собеседования – уже неплохой знак. Но в реальности неоптимальные решения такого рода сказываются. Когда объем входных данных достигает определенного уровня, ненужный расход ресурсов может подорвать работоспособность системы, которая во всех остальных отношениях сделана верно и качественно. Я ставлю плюс кандидатам, которые отмечают это расточительство и хотя бы в общих чертах описывают, что с ним делать.

Решение: часть четвертая (верно и более-менее оптимально)

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



Ряды с нового поля — Ряды со старого поля — Временные ряды, которые вскоре заменят ряды в той же позиции на старом поле

Имплементация этого подхода выглядит приблизительно так:

def update_state_correct(board):
    # Сохраняем предыдущий ряд, чтобы обновить его позже.
    previous_row = None

    for row in range(len(board)):
        current_row = []

        # Записываем все обновления во временный ряд.
        for col in range(len(board[0])):
            current_row.append(update_cell(board, row, col))

        # Если в предыдущем ряду появились изменения, переносим новую версию на поле.
        if previous_row:
            board[row - 1] = previous_row

        # Записываем все изменения в текущем ряду, 
        # чтобы произвести замену в следующей итерации.
        previous_row = current_row

    # Не забываем обновить последний ряд! 
    # Это очень распространенная ошибка.
    if len(board) > 1:
            board[-1] = previous_row

    return board

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

Дополнительная часть: отрываемся по полной

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

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

Примечания

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

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

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

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

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