Часто собеседование на должность программиста включает и алгоритмы. Рассмотрим еще 10 тем, которые почти всегда встречаются в вопросах интервьюеров.

Предыдущая статья «Вопросы по алгоритмам с собеседований».

Матрицы

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

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

rows, cols = len(matrix), len(matrix[0])
copy = [[0 for _ in range(cols)] for _ in range(rows)]

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

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

Транспонирование матрицы в Python выполняется просто:

transposed_matrix = zip(*matrix)

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

- пустая матрица (убедитесь, что ни один из массивов не имеет длины);
- матрица 1x1;
- матрица только с одной строкой или столбцом.

Рекурсия

Чаще всего рекурсия используется для обхода деревьев. И лишь изредка затрагивает задачи вроде вычисления факториала или количества ходов в головоломке «Ханойская башня». Вы обязаны понимать, как работает рекурсия и где она применяется.

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

Рекурсия неявно использует стек. Следовательно, все рекурсивные подходы могут быть перезаписаны итеративно с использованием стека. Остерегайтесь случаев, когда уровень рекурсии уходит слишком глубоко и вызывает переполнение стека (в Python предел по умолчанию равен 1000). Вы можете получить от интервьюера бонусные баллы за то, что указали на это. Рекурсия никогда не будет иметь O(1) сложность пространства, потому что задействован стек. Исключение – оптимизации хвостового вызова (ОХВ). Перед собеседованием узнайте, поддерживает ли ваш язык ОХВ.

Собеседование на должность программиста и строки

Прочтите приведенные выше советы по последовательностям, ведь они также применяются к строкам.

Спросите о наборе символов ввода и чувствительности к регистру. Чаще всего символы ограничены латинскими буквами нижнего регистра от a до z.

Когда вам нужно сравнить строки, где порядок не важен (например, анаграмма), вы можете применять HashMap в качестве счетчика. Если в вашем языке есть встроенный класс Counter, как в Python, попросите его использовать.

В случаях, когда нужно сохранить счетчик символов, скрыта распространенная ошибка. Она заключается в том, что сложность пространства, требуемая для счетчика, равна O(n). Пространство, необходимое для счетчика, равно O(1), а не O(n). Это связано с тем, что верхняя граница – диапазон символов, который обычно является фиксированной константой 26. Набор входных данных – это только строчные латинские символы.

Общими структурами данных для эффективного поиска строк являются:

1. Нагруженное/префиксное дерево.
2. Суффиксное дерево.

Общие строковые алгоритмы:

1. Робина-Карпа для эффективного поиска подстроки с использованием хеширования.
2. Кнута-Морриса-Пратта (КМП) для эффективного поиска подстроки.

Но иногда собеседование на должность программиста может поставить в тупик.

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

• строки с одним отдельным символом.

Не повторяющиеся символы

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

mask = 0
for c in set(word):
  mask |= (1 << (ord(c) - ord('a')))

Чтобы определить, содержат ли две строки общие символы, выполните & на двух битовых масках. Если результат отличен от нуля, mask_a & mask_b> 0, то две строки имеют общие символы.

Анаграммы

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

Чтобы определить, являются ли две строки анаграммами, существует несколько подходов:

1. Сортировка обеих строк должна давать одну и ту же итоговую строку. Это занимает O(nlgn) времени и O(lgn) пространства.
2. Если мы сопоставляем каждый символ с простым числом и умножаем каждое сопоставленное число вместе, анаграммы должны иметь один и тот же множитель (декомпозиция простого фактора). Занимает O(n) времени и O(1) пространства.
3. Частотный подсчет символов поможет определить, являются ли две строки анаграммами. Также занимает O(n) времени и O(1) пространства.

Палиндромы

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

Определите, является ли строка палиндромом:

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

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

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

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

Дерево

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

• Leaf It Up To Binary Trees

Собеседование на должность программиста может коснуться и Trees. Простое дерево – это неориентированный и связанный ациклический граф.

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

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

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

Возможны случаи, когда рекурсивная функция должна вернуть два значения.

Если вопрос связан с суммированием узлов, обязательно проверьте, могут ли узлы быть отрицательными.

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

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

• пустое дерево;
• единый узел;
• два узла;
• очень перекошенное дерево (например, связный список).

Двоичное дерево

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

Двоичное дерево поиска (BST)

Симметричный обход двоичного дерева поиска выдаст все элементы.

Хорошо ознакомьтесь со свойствами BST и подтвердите, что конкретное бинарное дерево является BST. Такое случается чаще, чем может показаться.

Когда вопрос связан с BST, интервьюер обычно ищет решение, которое работает быстрее, чем O(n).

Префиксное дерево

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

• Попытка понять нагруженное дерево
• Реализация Trie (префиксного дерева)

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

Иногда предварительная обработка словаря (заданного в списке) в Trie улучшает эффективность поиска слова длины k среди n слов. Поиск становится O(k) вместо O(n).

Следует ознакомиться с реализацией класса Trie и его методами добавления, удаления и поиска.

Куча

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

• Учимся любить кучи

Алгоритмы затрагивают и кучи (heaps) – структуры данных, которые позволяют реализовывать динамически распределяемую память приложения.

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

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