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

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

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

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

Первоначальный вопрос интервью: Обход дерева

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

Приведем наш пример кода на Python. Не язык для этого алгоритма в Dropbox, но основной язык, который я видел в технических интервью.

def get_children(node):
  # type: (int) -> List[int]
  # implemented for you
def node_ids_to_delete(node):
  # type: (int) -> List[int]
  # you write this

Все идет нормально. Это могло быть упражнением на моем курсе по структурам данных в колледже. Работает любой вид обхода дерева: в глубину или в ширину, рекурсивный или итеративный. Вот один:

def node_ids_to_delete(node):
  to_delete = [node]
  for child in get_children(node):
    to_delete.extend(node_ids_to_delete(child))
  return to_delete

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

  • Использует ли рекурсия значительно больше памяти, чем итеративное решение?
  • Увеличивает ли использование extend использование времени с линейного на квадратичное?

Но давайте начнем с кроличьей норы ограничений и требований, которые превращают этот чрезвычайно простой алгоритм во что-то большее.

Последний шаг 1: устойчивость к сбоям

Инжиниринг производственного качества предполагает учет того, что сбои могут произойти в любое время. Для целей этой проблемы предположим, что сервер может выйти из строя после удаления любого количества узлов. Мы удаляем узлы по одному, в порядке, возвращаемом node_ids_to_delete. В случае сбоя процесс перезапускается заново, удаляя то же дерево из того же корня.

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

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

def node_ids_to_delete(node):
  to_delete = []
  for child in get_children(node):
    to_delete.extend(node_ids_to_delete(child))
  to_delete.append(node)
  return to_delete

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

Последний шаг 2: добиться частичного прогресса

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

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

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

def node_ids_to_delete(node, cursor):
  # type: (int, Optional[Cursor]) -> Tuple[List[int], Optional[Cursor]]
  # Input cursor is None initially.
  # Output includes a cursor to be passed in as input for the next page, or None if this is the last page.

Нам по-прежнему нужно вернуть все дерево в обратном порядке, но теперь мы должны возвращать его по частям. Вы можете спроектировать курсор так, как хотите, чтобы отслеживать состояние между вызовами. Обратите внимание, что трудно отслеживать состояние при рекурсивном обходе. Чтобы явно представить стек вызовов, давайте перепишем алгоритм как итеративный и сделаем курсор стеком. Кстати, это устраняет проблему времени с extend, которая у нас была изначально.

class CursorItem():
  def __init__(self, to_traverse=None, already_traversed=None):
    self.to_traverse = to_traverse
    self.already_traversed = already_traversed
Cursor = List[CursorItem]
page_size = 1000
def node_ids_to_delete(node, cursor):
  # type: (int, Optional[Cursor]) -> Tuple[List[int], Optional[Cursor]]
  if cursor is None:
    cursor = [CursorItem(to_traverse=node)]
  else:
    cursor = cursor.copy()
  to_delete = []
  iterations = 0
  while len(cursor) > 0 and iterations < page_size:
    iterations += 1
    item = cursor.pop()
    if item.to_traverse:
      cursor.append(CursorItem(already_traversed=item.to_traverse))
      for child in get_children(item.to_traverse):
        cursor.append(CursorItem(to_traverse=child))
    elif item.already_traversed:
      to_delete.append(item.already_traversed)
  return to_delete, (None if len(cursor)==0 else cursor)

Хочу отметить некоторые свойства нашего решения:

  • page_size ограничивает количество вызовов get_children и количество узлов, возвращаемых как to_delete, которые являются узкими местами по времени.
  • Отправка to_traverse узлов обратно в стек как already_traversed до того, как мы поместим их дочерние узлы в качестве to_traverse, гарантирует, что родители всегда будут следовать за своими дочерними элементами в to_delete, даже между страницами.
  • Курсор может стать довольно большим. Это нормально, потому что мы сосредоточены на эффективности использования времени и устойчивости к сбоям.
  • Мы делаем копию ввода cursor. Это позволяет избежать проблемы, если какой-либо вызывающий объект попытается повторить попытку страницы после get_children, вызвав исключение: если мы изменили курсор ввода, повторная попытка может привести к пропуску узлов.
  • Выполняя некоторые удаления до завершения обхода, мы можем эффективно повторить попытку, даже если мы отбрасываем курсор между попытками, потому что удаленный узел не появится при повторном обходе.

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

Продолжение 3. Оптимизация с помощью пакетной обработки

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

def get_children(nodes, cursor):
  # type: (List[int], Optional[ChildCursor]) -> Tuple[List[int], Optional[ChildCursor]]
  # implemented for you

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

def node_ids_to_delete(nodes, cursor):
  # type: (List[int], Optional[Cursor]) -> Tuple[List[int], Optional[Cursor]]
  # you implement this

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