Подготовка к алгоритмическим задачам
Вопросы после решения задачи: к чему готовиться на собеседовании
Коротко
Решить задачу — половина секции. Вторая половина начинается с фразы «хорошо, а теперь представьте, что...».
| Вопрос | Что проверяют |
|---|---|
| «А если данных в тысячу раз больше?» | понимание сложности и масштабирования |
| «А если данные не помещаются в память?» | внешние алгоритмы, потоковая обработка |
| «А если запросов много?» | предподсчёт, кэширование |
| «А если несколько потоков?» | конкурентность |
| «Можно ли уменьшить память?» | компромисс время/память |
Эти вопросы часто весят больше, чем само решение: они показывают, думаете вы как инженер или как решатель задач.
«А если данных станет в тысячу раз больше?»
Самый частый вопрос. Проверяет, понимаете ли вы практический смысл своей асимптотики.
Плохой ответ: «ну, будет медленнее».
Хороший ответ начинается с конкретики:
У меня решение за O(n²). При n = 10⁵ это 10¹⁰ операций — минуты. При n = 10⁸ уже невозможно. Значит нужно уходить в O(n log n) или O(n). Здесь можно заменить перебор пар на хеш-таблицу и получить линию ценой O(n) памяти.
Держите в голове ориентиры — сколько операций проходит за секунду:
| Сложность | n = 10⁴ | n = 10⁶ | n = 10⁸ |
|---|---|---|---|
| O(n) | мгновенно | мгновенно | ~1 сек |
| O(n log n) | мгновенно | ~0.1 сек | ~10 сек |
| O(n²) | ~0.1 сек | часы | нереально |
Практическое правило: около 10⁸ простых операций в секунду.
«А если данные не помещаются в память?»
Второй по частоте. Проверяет знание того, что бывает за пределами одной машины.
Направления ответа:
Потоковая обработка. Если задача позволяет один проход и константную память — скажите об этом. Пример: найти максимум, посчитать сумму, найти элемент большинства алгоритмом Бойера-Мура.
Внешняя сортировка. Разбить на куски, влезающие в память, отсортировать каждый, слить. Классика для «отсортируйте файл на 100 ГБ».
Разбиение по хешу. Разделить данные на файлы по hash(key) % k, обработать каждый отдельно. Работает для подсчёта частот и поиска дубликатов.
Вероятностные структуры. Фильтр Блума для «был ли такой элемент», HyperLogLog для подсчёта уникальных. Дают приблизительный ответ за копейки памяти.
Если файл не помещается, я бы разбил его по хешу ключа на сто частей — тогда все одинаковые ключи попадут в один файл, и каждый обрабатывается независимо. А если достаточно приблизительной оценки уникальных, взял бы HyperLogLog: он даёт около 2% погрешности при килобайтах памяти.
«А если таких запросов будет много?»
Проверяет понимание компромисса «предподсчёт против запроса».
Ключевая мысль: когда запросов много, выгодно потратиться один раз и отвечать быстро.
один запрос → считаем на лету, O(n)
много запросов → префиксные суммы, O(n) подготовка + O(1) на запрос
много + обновления → дерево Фенвика, O(log n) на всё
Тот же принцип шире: кэширование результатов, индексы в базе данных, материализованные представления.
Если запросов суммы на отрезке много, а массив не меняется, я бы предподсчитал префиксные суммы: подготовка O(n), каждый запрос O(1). Если элементы обновляются — дерево Фенвика, там и запрос, и обновление за логарифм.
«А если это будет работать в нескольких потоках?»
Проверяет, знаете ли вы про конкурентность хотя бы на уровне понятий.
Что стоит упомянуть:
Где гонка. Укажите конкретное место: «если два потока одновременно проверят и вставят в хеш-таблицу, один результат потеряется».
Как чинить. Блокировка на всю структуру — просто, но убивает параллелизм. Блокировка на корзину или конкурентная структура (ConcurrentHashMap) — лучше. Неизменяемые данные — вообще без блокировок.
Атомарность. Инкремент счётчика не атомарен: чтение, увеличение, запись — три операции.
Здесь гонка на инкременте счётчика. В однопоточном коде всё в порядке, в многопоточном нужен атомарный тип или блокировка. Если структура читается часто, а пишется редко — я бы посмотрел в сторону копирования при записи.
«Можно ли уменьшить память?»
Часто задают после решения с хеш-таблицей.
Стандартные ходы:
Сортировка вместо хеша. O(1) памяти ценой O(n log n) времени.
Два указателя. Работает на отсортированных данных.
Битовые операции. XOR для поиска непарного элемента, битовая маска вместо множества.
На месте. Использовать сам входной массив как рабочую память — если разрешено его менять. Например, помечать посещённые элементы знаком минус.
Сейчас у меня O(n) памяти под словарь. Если память критична, а время нет — можно отсортировать и пройти двумя указателями: O(n log n) времени, O(1) памяти. А если элементы гарантированно парные, кроме одного, здесь вообще хватит XOR и одной переменной.
«А если условие изменится вот так?»
Проверяет гибкость решения, а не знание алгоритмов.
Типичные модификации:
- вместо пары найти все пары;
- вместо одного ответа вернуть k лучших;
- добавить ещё одно ограничение;
- сделать данные потоковыми, без возможности вернуться назад.
Правильная реакция — не защищать старое решение, а обсудить, что придётся поменять:
С таким условием текущий подход не подойдёт: я опираюсь на возможность пройти массив дважды, а в потоке этого нет. Здесь нужна куча размера k — тогда за один проход я буду поддерживать k наибольших.
Как отвечать в целом
Не гадайте молча. Проговаривайте варианты вслух, даже отбрасываемые.
Признавайте незнание с направлением. «С распределёнными системами я работал мало, но по аналогии здесь напрашивается шардирование по ключу» — сильнее, чем молчание или выдумка.
Называйте компромиссы. Почти любой ответ на follow-up — это размен одного ресурса на другой. Явное проговаривание («платим памятью за скорость») ценится отдельно.
Не бойтесь сказать «зависит». «Зависит от того, чаще читают или пишут» — правильный ответ на многие вопросы, если вы дальше разберёте оба случая.
Как готовиться
Возьмите десять задач, которые вы уже решили, и для каждой ответьте письменно:
- Что будет при увеличении входа в тысячу раз?
- Что если данные не помещаются в память?
- Что если запросов миллион?
- Как уменьшить память?
- Что сломается при многопоточности?
Полчаса на задачу — и вы закроете большую часть follow-up вопросов, которые вообще бывают. Это одна из самых недооценённых частей подготовки: люди решают сотни задач и ни разу не думают, что будет дальше.
Что запомнить
- Follow-up вопросы часто весят больше самого решения.
- Держите в голове ориентир: около 10⁸ операций в секунду.
- «Не помещается в память» — потоковая обработка, внешняя сортировка, разбиение по хешу, вероятностные структуры.
- «Много запросов» — предподсчёт и кэширование против вычисления на лету.
- Любой ответ формулируйте как компромисс: что на что меняем.
- Прогоняйте свои решённые задачи через пять стандартных вопросов — это быстрая и недооценённая подготовка.
Решай алгоритмические задачи как профи
