Лид: теория до кода на доске
Подготовка к техническому интервью — это не только задачи на код. В продуктовых командах редко просят написать пузырёк «на бумажке». Смотрят, понимаете ли вы, почему один алгоритм быстрее другого, где кончается теория и начинается инженерия, и как выбрать структуру под задачу.
Ниже — шесть вопросов, которые часто звучат до леткода. Таблицы для быстрого ответа, не секретный банк конкретной компании. Соседний раунд — теория System Design; этап алгоритмов в воронке — в разборе Авито.
Сложность помните, а речь срывается — проговорите выбор на моке с напарником. Дыру в Big O ловит квиз. Оффер не выдаём.
1. Какие алгоритмы сортировки вы знаете?
Сортировка — базовая тема, на ней проверяют сложность и компромиссы. Три группы: простые (квадратичные), эффективные (в среднем O(n log n)) и специализированные (без сравнений).
| Алгоритм | Лучшее | Среднее | Худшее | Память | Стабильность | Когда |
|---|---|---|---|---|---|---|
| Пузырьком | O(n) | O(n²) | O(n²) | O(1) | Да | Только учёба |
| Выбором | O(n²) | O(n²) | O(n²) | O(1) | Нет | Мало обменов |
| Вставками | O(n) | O(n²) | O(n²) | O(1) | Да | Почти отсортировано |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | Нет | Общий случай |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Да | Стабильность, внешняя память |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | Нет | Гарантия худшего + память |
| Подсчётом | O(n + k) | O(n + k) | O(n + k) | O(k) | Да | Целые в узком диапазоне |
| Radix Sort | O(n · k) | O(n · k) | O(n · k) | O(n + k) | Да | Строки, фиксированная длина |
На раунде мало перечислить имена. Quick Sort берут из‑за константы и кэша, не из‑за красивого худшего случая. Merge — когда нужна стабильность или внешняя сортировка.
Что выбрать под задачу
- Массив чисел, общий случай → Quick Sort
- Нужна стабильность → Merge Sort
- Почти отсортированные данные → Insertion Sort
- Целые в узком диапазоне → Counting Sort
- Гарантия O(n log n) в худшем → Merge или Heap
- Экономия памяти → Heap Sort
2. Какие алгоритмы поиска пути в графе вы знаете?
Графы обязательны для бэкенда и системных ролей. Мало назвать алгоритм: есть ли отрицательные веса, нужен путь от одной вершины или между всеми парами.
| Алгоритм | Тип графа | Сложность | Отрицательные веса | Особенность |
|---|---|---|---|---|
| BFS | Невзвешенный | O(V + E) | — | Кратчайший по числу рёбер |
| Дейкстра | Взвешенный | O((V + E) log V) | Нет | Быстрее Беллмана-Форда |
| A* | Взвешенный | Зависит от эвристики | Нет | Эвристика направляет поиск |
| Беллман-Форд | Взвешенный | O(V · E) | Да | Ловит отрицательные циклы |
| Флойд-Уоршелл | Взвешенный | O(V³) | Да | Все пары сразу |
Дейкстра не работает с отрицательными весами: жадная фиксация ближайшей вершины перестаёт быть верной, если позже придёт отрицательное ребро.
Порядок уточнений на раунде
- Все веса равны? Да → BFS.
- Путь от одной вершины и есть отрицательные веса → Беллман-Форд.
- Путь от одной вершины, веса неотрицательные → Дейкстра.
- Нужны все пары → Флойд-Уоршелл.
Пока таблица не уехала с языка
Выбор Дейкстры vs Беллмана вслух дешевле, чем молчаливая схема. Оффер не обещаем.
3. В чём разница динамического массива и связного списка?
Классика на компромиссы. Ждут не определение из учебника, а выбор: важнее доступ по индексу или вставка в середину.
| Критерий | Динамический массив | Связный список |
|---|---|---|
| Память | Непрерывный блок | Узлы разбросаны, у каждого ссылка |
| Доступ по индексу | O(1) | O(n) |
| Вставка в начало | O(n) — сдвиг | O(1) |
| Вставка в конец | O(1) амортизированно | O(1) у двусвязного с хвостом |
| Середина | O(n) — сдвиг | O(1) операция, O(n) поиск позиции |
| Кэш | Отличный | Плохой |
| Накладные расходы | Запас ёмкости | Указатели на узел |
Практическое правило: массив — произвольный доступ и итерации. Список — частые вставки в начало или середину, индекс не критичен.
4. Чем сбалансированные BST отличаются от несбалансированных?
Обычное дерево поиска в худшем случае вырождается в список — операции становятся O(n). AVL и красно-чёрные держат высоту O(log n).
| Характеристика | Обычный BST | AVL / красно-чёрное |
|---|---|---|
| Высота | В худшем O(n) | O(log n) |
| Поиск / вставка / удаление | В среднем O(log n), худший O(n) | Гарантированно O(log n) |
| Балансировка | Нет | Повороты, перекраска |
| Где встречается | Учёба, простые случаи | std::map, TreeMap, индексы БД |
Вставка 1, 2, 3, 4, 5
Без баланса получается цепочка вправо: высота 5, как у списка. С балансом корень около тройки, высота около 3. Балансировка — страховка от порядка вставки.
5. Что называется полным бинарным деревом?
Complete binary tree: все уровни кроме последнего заполнены, узлы последнего стоят слева без дыр. На этом держится куча и пирамидальная сортировка.
| Свойство | Смысл |
|---|---|
| Уровни | Все, кроме последнего, заполнены |
| Последний уровень | Узлы слева направо, без дыр |
| Массив | Для i: дети 2i+1 и 2i+2, родитель (i−1)/2 |
| Высота | ⌊log₂ n⌋ |
| Где | Куча, Heap Sort, приоритетная очередь |
Не путать с full binary tree: там у узла ровно 0 или 2 ребёнка. Определения разные.
Как выглядит дыра
Полное: уровни 1–2 заполнены, на третьем узлы идут слева. Неполное: у правого ребёнка корня есть только правый потомок — слева дыра, в массив кучи так класть нельзя.
6. Какие подходы к разрешению коллизий в хеш-таблицах вы знаете?
Коллизия — два ключа с одним хешем. Два подхода: цепочки и открытая адресация. Компромисс между простотой, памятью и деградацией при высокой заполненности.
| Критерий | Цепочки | Открытая адресация |
|---|---|---|
| Идея | Ячейка — список | Все ключи в самом массиве |
| Свободная ячейка | Не ищем | Линейное / квадратичное пробирование, двойное хеширование |
| Кэш | Хуже | Лучше |
| Память | Ссылки | Только массив |
| Удаление | Простое | Нужна пометка «удалён» |
| При заполнении | Плавная деградация | Резкая, load factor критичен |
| Где видно | HashMap в Java (до порога дерева) | dict в Python |
Линейное пробирование даёт первичную кластеризацию: длинные занятые куски увеличивают среднее время поиска. Двойное хеширование режет кластеры, но нужны две функции.
Как это выглядит
Цепочки: ячейка 0 ведёт на key1 → key4, ячейка 1 — на key2, пустые слоты остаются пустыми.
Открытая адресация: коллизия с key1 кладёт key4 в следующую свободную ячейку того же массива.
Частые вопросы
Нажмите на вопрос — ответ откроется ниже.
Средний случай O(n log n) с низкой константой и хорошим кэшем. Худший режут медианой из трёх, случайным пивотом или intro sort.
Он жадно фиксирует расстояние. Отрицательное ребро может улучшить уже закрытую вершину. Тогда Беллман-Форд.
Когда много вставок в начало или середину, а индекс не нужен. Для обходов и random access массив выигрывает кэшем.
Нет. Complete — уровни слева без дыр, так лежит куча. Full — у узла 0 или 2 ребёнка.
Нет отдельного симулятора Яндекса или Авито. Есть мок и квиз. Бот @it_careergym_ru_bot — канал мэтча, не ментор «как в FAANG». Оффер не обещаем.
Что дальше
Теоретические вопросы — не экзамен на зубрёжку. Нужно выбрать инструмент и объяснить выбор. Таблицы выше закрывают первые минуты раунда. Дальше — код вслух и соседняя теория System Design. Это подготовка, не трудоустройство.
Пока слот не открылся
Соберите заявку на мок и закройте одну тему в квизе. Оффер мы не выдаём — формулировки к доске подтянуть можно.
Также по теме: Теория System Design · Собеседование в Авито · System Design как на Amazon · Парный мок · Плейбук последней недели