Подготовка к алгоритмическим задачам
Структуры данных на собеседовании: что спрашивают и как отвечать
Коротко
Главный вопрос интервьюера — не «что такое хеш-таблица», а «какую структуру вы возьмёте и почему». Ниже таблица, которую стоит держать в голове.
| Структура | Поиск | Вставка | Удаление | Порядок |
|---|---|---|---|---|
| Массив | O(n) | O(n) | O(n) | сохраняется |
| Динамический массив | O(n) | O(1) в конец | O(n) | сохраняется |
| Связный список | O(n) | O(1) по ссылке | O(1) по ссылке | сохраняется |
| Хеш-таблица | O(1) | O(1) | O(1) | нет |
| Множество | O(1) | O(1) | O(1) | нет |
| Сбалансированное дерево | O(log n) | O(log n) | O(log n) | отсортированный |
| Куча | O(n) | O(log n) | O(log n) | только минимум |
| Стек / очередь | — | O(1) | O(1) | LIFO / FIFO |
Как выбирать структуру
Схема из четырёх вопросов, которую полезно проговаривать вслух на собеседовании.
1. Нужен ли быстрый поиск по ключу? → хеш-таблица.
2. Нужен ли порядок? → отсортированный массив или сбалансированное дерево.
3. Нужны ли только минимум или максимум? → куча.
4. Важен ли порядок обработки? → стек для LIFO, очередь для FIFO.
Если ни один пункт не подходит, обычно достаточно массива.
Массив против связного списка
Классический вопрос, который задают почти всегда.
Массив: доступ по индексу за O(1), данные лежат непрерывно, отлично работает с кешем процессора. Вставка в середину O(n) из-за сдвига.
Связный список: вставка и удаление за O(1), если ссылка на узел уже есть. Доступа по индексу нет — только последовательный обход.
Сильный ответ включает практическую поправку: на реальных данных массив обычно быстрее даже там, где теория обещает обратное. Причина в локальности памяти: элементы массива подгружаются в кеш блоками, а список разбросан по куче, и каждый переход по указателю может стоить обращения к оперативной памяти.
Связный список выигрывает в узкой нише: частые вставки и удаления в середине при наличии ссылки на узел. Именно поэтому он лежит в основе LRU-кэша.
Хеш-таблица
Вторая по частоте тема после массивов.
Что должен содержать ответ
Массив корзин. Ключ прогоняется через хеш-функцию, остаток от деления на размер даёт номер корзины. При совпадении корзин — коллизия.
Два способа разрешения:
- цепочки — в корзине связный список или дерево;
- открытая адресация — ищем следующую свободную ячейку.
При заполнении выше порога (обычно 0.75) таблица увеличивается вдвое, и все элементы перераспределяются.
Почему O(1) «в среднем»
Потому что в худшем случае все ключи попадут в одну корзину, и поиск выродится в O(n). Современные реализации это смягчают: в Java при восьми элементах в корзине список превращается в красно-чёрное дерево, что даёт O(log n) вместо O(n).
Упоминание худшего случая — признак понимания, а не заучивания.
Что может быть ключом
Только неизменяемые объекты с корректными hashCode и equals. Если объект изменится после вставки, его хеш изменится, и найти его станет невозможно.
Отсюда классический вопрос: «что будет, если переопределить equals без hashCode». Ответ: объект не найдётся в хеш-таблице, потому что поиск пойдёт не в ту корзину.
Решай алгоритмические задачи как профи
Стек и очередь
Простые структуры, но задачи на них дают часто.
Стек нужен, когда обработка идёт в обратном порядке или есть вложенность: скобки, обход в глубину, отмена действий, вычисление выражений.
Очередь — когда порядок поступления важен: обход в ширину, планировщики, буферы.
Практическая деталь, которую ценят: в Python для очереди нужен collections.deque, а не список. list.pop(0) работает за O(n), и цикл превращается в скрытый квадрат.
Деревья
Двоичное дерево поиска
Левое поддерево меньше, правое больше. Даёт O(log n) на поиск — но только если дерево сбалансировано.
Обязательное дополнение к ответу: на отсортированных данных обычное дерево поиска вырождается в связный список и деградирует до O(n). Отсюда самобалансирующиеся деревья — АВЛ и красно-чёрное.
Что где применяется
TreeMap в Java и std::map в C++ — красно-чёрные деревья. Индексы баз данных — B+ деревья, у которых узел размером с дисковый блок содержит сотни ключей и высота падает до 3–4 уровней.
Куча
Отвечает на один вопрос — «какой элемент минимальный» — и делает это за O(1).
Ключевые факты для ответа:
- это полное двоичное дерево, хранящееся в массиве без указателей;
- дети узла
iлежат на позициях2i+1и2i+2; - вставка и извлечение — O(log n);
- построение из готового массива — O(n), а не O(n log n);
- найти произвольный элемент нельзя быстрее O(n).
Последний пункт важен: куча не заменяет дерево поиска, порядок между «братьями» в ней не определён.
Типичные вопросы-ловушки
«Какая сложность у поиска в хеш-таблице?» Ответ «O(1)» неполный. Правильно: O(1) в среднем, O(n) в худшем случае при плохой хеш-функции.
«Массив или список для стека?» Массив. Операции идут с одного конца, а локальность памяти даёт выигрыш.
«Как найти k-й наибольший элемент?» Три варианта с разной сложностью: сортировка O(n log n), куча размера k — O(n log k), quickselect — O(n) в среднем. Хороший ответ перечисляет все три и объясняет, когда что выгоднее.
«Чем множество отличается от словаря?» Множество хранит только ключи, словарь — пары. Внутри устроены одинаково.
«Где применяется стек в реальном коде?» Стек вызовов функций, обход DOM, отмена действий, парсеры.
Как отвечать
Не заучивайте определения. Спросят «когда применять», а не «что это».
Всегда называйте сложность — по времени и по памяти.
Упоминайте худший случай. Это отличает понимание от зубрёжки.
Приводите примеры из практики. «Мы взяли множество вместо списка, и проверка дубликатов ускорилась с секунд до миллисекунд» весит больше теории.
Обсуждайте компромиссы. Почти всегда речь идёт о размене памяти на скорость, и явное упоминание этого ценится.
Что запомнить
- Ключевой вопрос — не «что это», а «какую структуру выбрать и почему».
- Хеш-таблица даёт O(1) в среднем и O(n) в худшем случае — говорите про оба.
- Массив на практике обгоняет связный список из-за локальности памяти.
- Дерево поиска без балансировки вырождается в список на отсортированных данных.
- Куча отвечает только за минимум; произвольный поиск в ней O(n).
- В Python для очереди используйте
deque, а не список.