Банк задач для собеседований по программированию

Паттерн: Два указателя·Сложность: O(n) по времени, O(1) по памяти

Поставьте указатели на оба конца отсортированного массива. Если сумма слишком мала, сдвигайте левый указатель вправо; если слишком велика — правый влево. Отсортированность гарантирует, что вы не пропустите подходящую пару, — именно этот инвариант интервьюеры хотят услышать вслух.

Паттерн: Хеш-таблица / подсчёт·Сложность: O(n) по времени, O(1) по памяти для фиксированного алфавита

Посчитайте частоты символов первой строки, уменьшайте их при проходе по второй и проверьте, что все счётчики вернулись к нулю. Упомяните продолжение раньше, чем вас спросят: для полного Unicode массив на 26 ячеек уже не подходит — используйте хеш-таблицу.

Паттерн: Медленный и быстрый указатели Флойда·Сложность: O(n) по времени, O(1) по памяти

Сдвигайте один указатель на один узел, а другой — на два; если они когда-нибудь встретятся, цикл есть. Будьте готовы к классическому продолжению — найти вход в цикл: верните один указатель в начало списка и двигайте оба по одному узлу, пока они снова не встретятся.

Паттерн: Голосование Бойера — Мура·Сложность: O(n) по времени, O(1) по памяти

Храните кандидата и счётчик: при совпадении увеличивайте, при несовпадении уменьшайте, а когда счётчик дойдёт до нуля, меняйте кандидата. Поскольку элемент большинства встречается больше n/2 раз, он всегда выживает. Объяснить, ПОЧЕМУ он выживает, — в этом и суть собеседования.

Паттерн: Один проход, текущий минимум·Сложность: O(n) по времени, O(1) по памяти

Отслеживайте минимальную цену на данный момент и лучшую прибыль, если продать сегодня. Один проход, две переменные. Это простейший пример идеи «нести лучшее состояние префикса», которая позже появится в алгоритме Кадане, — если назовёте эту связь, получите дополнительные очки.

Паттерн: Сортировка + линейный проход·Сложность: O(n log n) по времени, O(n) по памяти

Отсортируйте интервалы по началу, затем пройдите по ним: если текущий интервал начинается после конца последнего объединённого, добавьте его; иначе продлите конец объединённого до максимума из двух. Основную работу делает сортировка — скажите об этом и правильно обработайте граничные случаи компаратора (соприкасающиеся интервалы).

Паттерн: Хеш-множество + начала последовательностей·Сложность: O(n) по времени, O(n) по памяти

Положите все числа во множество; начинайте счёт только с тех чисел, у которых нет предшественника (начала последовательностей), и идите вперёд. Каждый элемент посещается не более двух раз — так вы защитите оценку O(n) от возражения «но здесь же вложенный цикл».

Паттерн: Префиксные и суффиксные произведения·Сложность: O(n) по времени, O(1) дополнительной памяти, не считая результата

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

Паттерн: Инвариант вспомогательного стека·Сложность: O(1) на операцию, O(n) по памяти

Рядом со стеком значений храните стек минимумов, вершина которого всегда равна минимуму всего, что под ней: кладите min(новое значение, текущая вершина), извлекайте из обоих стеков синхронно. Это вопрос на проектирование: оценивают инвариант, а не объём кода.

Паттерн: Хеш-таблица + двусвязный список·Сложность: O(1) на get/put, O(capacity) по памяти

Хеш-таблица даёт доступ за O(1) к узлам двусвязного списка, упорядоченного по давности использования; при обращении перемещайте узел в голову, при переполнении вытесняйте из хвоста. Фиктивные головной и хвостовой узлы убирают все граничные случаи с проверками на null — упомяните их до того, как начнёте писать код.

Паттерн: Заливка сетки через BFS/DFS·Сложность: O(rows × cols) по времени

Пройдите по сетке; каждая непосещённая клетка суши запускает заливку (DFS или BFS), которая помечает весь остров посещённым, а вы считаете запуски. Назовите стратегию пометки посещённых клеток («затопление» на месте или отдельное множество) и риск переполнения стека рекурсии на огромных сетках — это сигнал сеньорности.

Паттерн: Топологическая сортировка / поиск цикла·Сложность: O(V + E) по времени

Представьте пререквизиты как ориентированный граф; вопрос «можно ли пройти все курсы» — это ровно вопрос «ацикличен ли граф». Подойдёт и алгоритм Кана (раз за разом удаляйте вершины с нулевой входящей степенью), и DFS с тремя цветами — выберите один и объясните, почему оставшаяся вершина означает цикл.

Паттерн: BFS со снимком уровня·Сложность: O(n) по времени, O(width) по памяти

BFS с очередью, но в начале каждого раунда запоминайте длину очереди, чтобы выдавать по одному списку на уровень. Этот приём со снимком длины — переиспользуемое ядро: зигзагообразный обход и вид справа — тот же цикл с другим шагом сбора.

Паттерн: Передача границ / симметричный обход·Сложность: O(n) по времени, O(height) по памяти

Рекурсия с допустимым окном (min, max), которое сужается на каждом шаге, — или симметричный обход с проверкой, что последовательность строго возрастает. Классическая ловушка — сравнивать детей только с их родителем; постройте контрпример сами, раньше интервьюера.

Паттерн: Двустороннее отображение через хеш-таблицы (биекция)·Сложность: O(n) по времени, O(n) по памяти

Отображайте символы шаблона в слова И слова обратно в символы — одно направление пропустит шаблон «ab» для «dog dog». Проверка биекции в обе стороны — весь фокус; произнесите слово «биекция» и обработайте несовпадение длины до того, как начнёте писать код.

Паттерн: Поиск цикла в скрытой последовательности·Сложность: O(log n) на шаг; O(1) по памяти с методом Флойда

Если раз за разом заменять число суммой квадратов его цифр, вы либо дойдёте до 1, либо попадёте в цикл, — значит, это замаскированная Linked List Cycle. Найдите цикл с помощью множества уже встреченных значений или впечатлите медленным и быстрым указателями Флойда — O(1) по памяти. Назвать сведение к поиску цикла — ход сеньора.

Паттерн: Жадный алгоритм с обязательным доказательством·Сложность: O(n) по времени, O(1) по памяти

Если суммарный бензин ≥ суммарного расхода, ответ существует и он единственный. Пройдите один раз, отслеживая текущий запас в баке; как только он становится отрицательным, ни одна заправка на провалившемся отрезке не может быть стартовой — начинайте заново со следующей. Собеседование — это обоснование этого пропуска, а не сам цикл.

Паттерн: Жадный алгоритм / неявные слои BFS·Сложность: O(n) по времени, O(1) по памяти

Считайте индексы, достижимые за k прыжков, слоем BFS: отслеживайте правую границу текущего слоя и самую дальнюю достижимую точку; когда проходите за границу, увеличивайте число прыжков и сдвигайте границу к этой самой дальней точке. Если подать решение как BFS без очереди, становится понятно, ПОЧЕМУ жадный подход здесь оптимален.

Паттерн: Линейное слияние в три фазы·Сложность: O(n) по времени, O(n) по памяти

Выведите интервалы, которые заканчиваются до начала нового, затем поглотите новым все пересекающиеся с ним интервалы (минимальное начало, максимальный конец), затем выведите остальные. Отсортированный вход означает один проход без повторной сортировки — если спросят, почему это проще, сравните с Merge Intervals.

Паттерн: Преобразование матрицы на месте·Сложность: O(n²) по времени, O(1) по памяти

Поворот на 90° по часовой стрелке = транспонирование, затем разворот каждой строки. Два чистых прохода с O(1) дополнительной памяти лучше, чем выводить под давлением циклическую перестановку четырёх элементов, — но будьте готовы объяснить отображение координат (i,j) → (j, n−1−i), если интервьюер копнёт глубже этого приёма.

Паттерн: Пометки на месте в заимствованной памяти·Сложность: O(m×n) по времени, O(1) по памяти

Используйте первую строку и первый столбец как хранилище флагов того, какие строки и столбцы нужно обнулить, а два булевых флага запомнят их собственное состояние. Пройдите вслух по лестнице памяти — O(mn) на копию → O(m+n) на множества → O(1) на заимствованное хранилище, — потому что проверяют именно эту лестницу.

Паттерн: Сортировка / подсчёт по корзинам·Сложность: O(n log n) с сортировкой, O(n) с корзинами

Отсортируйте по убыванию и найдите наибольшее i, при котором citations[i] ≥ i+1, — или обойдитесь без сортировки с помощью корзин подсчёта, ограниченных n, за O(n). Точно сформулируйте определение до того, как начнёте писать код: большинство провалов на этой задаче — от неверного прочтения «h статей, у каждой из которых не меньше h цитирований», а не от алгоритма.

Паттерн: Топологическая сортировка с выводом порядка·Сложность: O(V + E) по времени

Тот же граф, что в Course Schedule, но теперь алгоритм Кана оправдывает себя: порядок, в котором вершины с нулевой входящей степенью покидают очередь, И ЕСТЬ допустимый порядок курсов. Если выведенный порядок короче числа курсов, есть цикл — верните пустой результат. Упомяните альтернативу — обратный порядок завершения вершин в DFS.

Паттерн: Скользящее окно со счётчиком выполненных условий·Сложность: O(n) по времени, O(alphabet) по памяти

Расширяйте правую границу, пока окно не покроет все нужные символы (ведите счётчик «собрано / требуется», а не сравнивайте целиком таблицы на каждом шаге), затем сжимайте левую границу до минимума, пока окно остаётся допустимым, запоминая лучшее. Именно оптимизация со счётчиком сохраняет O(n) — объясните её явно.

Паттерн: Два указателя по текущим максимумам·Сложность: O(n) по времени, O(1) по памяти

Вода над каждым столбиком = min(max-left, max-right) − height. Два указателя, движущиеся внутрь с обоих концов, позволяют разрешить ту сторону, где текущий максимум меньше, потому что граница этой стороны уже окончательна. Объясните, почему эта уверенность оправдана, — в этом весь вопрос.