Алгоритмы для собеседования: минимум для новичка

Сколько нужно на самом деле

Гораздо меньше, чем пугают. Новичку на собеседовании дают задачи, которые решаются за пятнадцать-двадцать минут и не требуют знания хитрых структур данных.

Готовиться месяцами по толстому учебнику не нужно. Двадцати-тридцати простых задач достаточно, чтобы чувствовать себя уверенно.

Что надо знать

Массивы и строки. Перебор, поиск, разворот, подсчёт, удаление повторов. Это основа большинства задач для новичков.

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

Сортировку — на уровне пользователя. Знать, что она есть, уметь сортировать по своему условию. Писать быструю сортировку с нуля не просят.

Сложность — на пальцах. Достаточно понимать разницу между «проходим один раз» и «для каждого элемента проходим весь список ещё раз». Про логарифмы можно ответить в общих чертах.

Рекурсию — базово. Понимать идею и уметь написать простое: факториал, обход дерева.

Чего знать не надо

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

Типовые задачи

Прорешайте по два-три примера каждого вида:

1. Развернуть строку или массив.
2. Найти повторяющиеся элементы.
3. Посчитать частоту символов или слов.
4. Проверить, что скобки расставлены правильно.
5. Найти два числа с заданной суммой.
6. Слить два отсортированных списка.
7. Проверить палиндром.
8. Найти самое частое значение.
9. Убрать повторы, сохранив порядок.
10. Посчитать что-нибудь в тексте.

Этого набора хватает для подавляющего большинства собеседований на начальные позиции.

Как готовиться

Решайте вслух. Главный навык — не решить, а объяснить. Тренируйтесь проговаривать: что понял из условия, какой подход, почему такой, на чём проверю.

Записывайте себя. Неприятно, но полезно: услышите, где мямлите и где проглатываете рассуждение.

Не заучивайте решения. Заученное видно сразу, и на изменённом условии вы поплывёте.

На самом собеседовании

1. Уточните условие. Что если пустой ввод? Могут ли быть отрицательные числа? Один вопрос перед началом производит очень хорошее впечатление.
2. Проговорите подход до кода. «Пройду один раз, буду складывать в словарь, потом выберу максимум».
3. Пишите и объясняйте одновременно. Молчание — худшее, что можно делать.
4. Проверьте на крайних случаях. Пустой ввод, один элемент, все одинаковые. Про это забывают почти все, а вспомнить — заметный плюс.

Задача на собеседовании — это разговор, а не экзамен. Оценивают собеседника, а не олимпиадника.