Вопросы по алгоритмам – обычное явление на собеседовании. Мы собрали для вас рекомендации, которые помогут ответить на большинство вопросов.

Если хочешь подтянуть свои знания, загляни на наш курс «Алгоритмы и структуры данных», на котором ты:

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

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

В итоге будешь браться за сложные проекты и повысишь чек за свою работу 🙂

Интересно, хочу попробовать

Последовательность

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

1. Проверяйте последовательность за пределами.
2. Помните о срезах или конкатенации последовательностей в вашем коде. Как правило, срез и конкатенация требуют O(n) времени. Используйте начальные и конечные индексы для демаркации подмассива/подстроки, где это возможно.
3. Иногда вы можете перемещаться по последовательности справа, а не слева.
4. Освойте метод скользящего окна, который применим ко многим проблемам подстрок/подмассивов.
5. Когда вам даны две последовательности для обработки, обычно имеется один индекс для каждой последовательности, чтобы сравнить их. Тот же подход используется, чтобы объединить два отсортированных массива.

Тупиковые ситуации:

• пустая последовательность;
• последовательность с 1 или 2 элементами;
• последовательность с повторяющимися элементами.

Массив

Вопросы по алгоритмам: является массив отсортированным или частично отсортированным? Должна быть какая-то форма бинарного поиска. Это также означает, что интервьюер хочет увидеть решение, которое быстрее, чем O(n).

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

Для вопросов, в которых задействовано суммирование либо умножение подматрицы, может быть полезно предварительное вычисление с использованием хэширования или префикса/суффикса sum/product.

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

Двоичный код

Полезные ссылки:

• Биты, байты, двоичный код

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

Полезные операции:

• проверка: num & (1 << k) != 0
• включение k^th битов: num |= (1 << k)
• выключение k^th битов: num &= ~(1 << k)
• переключение k^th битов: num ^= (1 << k)
• является ли число степенью двойки: num & num - 1 == 0

Тупиковые ситуации:

• выход за верхнюю/нижнюю границу;
• отрицательные значения.

Вопросы по алгоритмам и динамическое программирование

Полезные ссылки:

• Демистификация динамического программирования

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

Иногда вам не нужно хранить всю таблицу DP в памяти: достаточно двух последних значений или строк матрицы.

Геометрия

При сравнении эвклидова расстояния между двумя парами точек можно использовать dx² + dy².

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

Графы

Полезные ссылки:

• От теории к практике: представление графов
• Поиск в глубину: обход DFS
• Поиск в ширину: обход BFS

Ознакомьтесь с различными представлениями графа, алгоритмами поиска.

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

1. Матрица смежности.
2. Список примыканий.
3. Хашмап хэшмапов.

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

Алгоритмы поиска:

1. Общие – поиск в ширину, поиск в глубину.
2. Необычные – топологическая сортировка, алгоритм Дейкстры.
3. Редкие – алгоритм Беллмана-Форда, Флойда-Уоршелла, Прима, Краскала.

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

Простой шаблон для выполнения поиска в глубину выглядит следующим образом:

def traverse(matrix):
  rows, cols = len(matrix), len(matrix[0])
  visited = set()
  directions = ((0, 1), (0, -1), (1, 0), (-1, 0))
  def dfs(i, j):
    if (i, j) in visited:
      return
    visited.add((i, j))
    # Обход соседей
    for direction in directions:
      next_i, next_j = i + direction[0], j + direction[1]
      if 0 <= next_i < rows and 0 <= next_j < cols: # Проверка границы
        # Добавить любую другую проверку здесь ^
        dfs(next_i, next_j)

  for i in range(rows):
    for j in range(cols):
      dfs(i, j)

Тупиковые ситуации:

• пустой граф;
• граф с одним или двумя узлами.
• непересекающиеся графы;
• граф с циклами.

Интервалы

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

Массив интервалов: [[1, 2], [4, 7]].

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

Расскажите интервьюеру, считаются ли [1, 2] и [2, 3] перекрывающимися интервалами, поскольку это влияет на то, как вы будете писать свои проверки на равенство.

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

Проверка на перекрытие и объединение:

def is_overlap(a, b):
  return a[0] < b[1] and b[0] < a[1]

def merge_overlapping_intervals(a, b):
  return [min(a[0], b[0]), max(a[1], b[1])]

Тупиковые ситуации:

• один интервал;
• неперекрывающиеся интервалы;
• повторяющиеся интервалы.

Связные списки

Подобно массивам, связные списки используются для представления последовательных данных. Преимущество связных списков в том, что вставка и удаление из любого места в списке – это O(1), тогда как в массивах следующие элементы должны быть сдвинуты.

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

Иногда проблема связных списков решается без дополнительного хранения. Попытайтесь заимствовать идеи от обратной проблемы связного списка.

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

Для разделения связных списков создайте два отдельных списка и объедините их.

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

1. Получение k^th из последнего узла. Есть два указателя, где один на k узлов впереди другого. Когда узел впереди достигает конца, другой узел остается на k узлов позади.
2. Обнаружение циклов. Есть два указателя. Один увеличивается в два раза больше, чем другой, и если указатели встречаются – существует цикл.
3. Получение среднего узла. Есть два указателя, один из которых увеличивается вдвое больше другого. Когда быстрый узел достигает конца списка, медленный окажется посередине.

Для многих решений используется одна или несколько из представленных подпрограмм:

1. Подсчет количества узлов в связном списке.
2. Реверсирование связного списка на месте.
3. Поиск среднего узла связного списка с использованием быстрых/медленных указателей.
4. Объединение двух списков.

Тупиковые ситуации:

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

Математика

Если код включает деление или деление с остатком, не забудьте проверить случай с 0.

Когда вопрос включает «кратное число», возможно, деление с остатком может оказаться полезным.

Проверьте и обработайте переполнение/антипереполнение, если вы используете типизированный язык вроде Java и C++. По крайней мере, упомяните, что переполнение/антипереполнение возможно, и спросите, нужно ли вам его обрабатывать.

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

Если вопрос требует реализовать возведение числа в степень, извлечение квадратного корня или деление, и нужно, чтобы это было быстрее O(n), двоичный поиск – отличный вариант.

Некоторые общие формулы:

1. Сумма от 1 до N = (n + 1) * n / 2
2. Сумма GP = 2⁰ + 2¹ + 2² + 2³ + ... 2ⁿ = 2^{n + 1} - 1
3. Перестановки N = N! / (N-K)!
4. Комбинации N = N! / (K! * (N-K)!)

Следующая статья «Собеседование на должность программиста».