Алгоритмы и структуры данных на Python: подготовка к техническим интервью

Бинарный поиск и префиксные суммы

Представь: у тебя есть отсортированный список из миллиона чисел, и нужно найти, есть ли там число 7 438 291. Перебор займёт миллионы операций. Бинарный поиск справится за 20 шагов. Почему? Потому что каждый шаг делит пространство поиска пополам — и это не просто трюк, а фундаментальный принцип, на котором строятся базы данных, файловые системы и поисковые движки.

Как работает бинарный поиск

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

Инвариант бинарного поиска — ключевое понятие для интервью. Это условие, которое остаётся истинным на каждом шаге: «ответ всегда находится в диапазоне [left, right]». Если ты нарушишь инвариант — получишь бесконечный цикл или пропущенный ответ.

Обрати внимание на детали: left + (right - left) // 2 вместо (left + right) // 2 — это защита от целочисленного переполнения в языках с фиксированным размером типа. В Python это не критично, но интервьюеры замечают такие вещи.

Три варианта бинарного поиска

На практике бинарный поиск редко используется в «чистом» виде. Чаще встречаются три модификации:

| Вариант | Когда использовать | Что возвращает | |---------|-------------------|----------------| | Поиск точного значения | Найти элемент в отсортированном массиве | Индекс или -1 | | Поиск левой границы | Найти первый элемент target | Индекс вставки | | Поиск правой границы | Найти последний элемент target | Индекс последнего вхождения |

Поиск левой границы — самый частый гость на собеседованиях. Он отвечает на вопрос: «где бы стоял элемент target, если бы он был в отсортированном массиве?»

Здесь right инициализируется как len(arr), а не len(arr) - 1, потому что ответ может указывать за пределы массива. Цикл работает при left < right, а не left <= right — это классический паттерн, который стоит запомнить.

Бинарный поиск по ответу

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

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

Префиксные суммы

Теперь представь другую задачу: дан массив чисел, и нужно многократно отвечать на запросы «чему равна сумма элементов с индекса по включительно?». Линейный перебор на каждый запрос — слишком медленно. Префиксные суммы решают это за на запрос после предобработки.

Идея: строим вспомогательный массив prefix, где prefix[k] — сумма первых элементов исходного массива. Тогда сумма на отрезке равна prefix[j+1] - prefix[i].

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

Префиксные суммы на двумерных массивах

Для матриц применяется тот же принцип, но с двумерным массивом префиксных сумм. Сумма на подматрице от до вычисляется по формуле включений-исключений:

где — двумерный массив префиксных сумм. Четвёртое слагаемое добавляется обратно, потому что мы вычли его дважды.

Когда что использовать

Бинарный поиск эффективен, когда данные отсортированы или пространство ответов монотонно. Префиксные суммы — когда нужно быстро отвечать на запросы суммирования на подотрезках. Часто эти техники комбинируются: например, префиксные суммы помогают проверить кандидата в бинарном поиске по ответу.

Ловушка интервью: бинарный поиск кажется простым, но 80% ошибок — в определении инварианта и выборе между left <= right и left < right. Перед написанием кода всегда проговаривай: что инвариант, что возвращаем, что делаем при arr[mid] == target.

Техника двух указателей и скользящего окна

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

Два указателя: суть подхода

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

Классический пример — задача Two Sum II для отсортированного массива: найти два числа, сумма которых равна целевому значению.

Почему это работает? Если сумма меньше целевой — левый указатель нужно сдвинуть вправо (к большим значениям). Если больше — правый влево. Каждый элемент рассматривается не более одного раза каждым указателем, отсюда сложность .

Разделение на два подмассива

Другой мощный приём — разделительный указатель (partition pointer). Задача: переставить элементы массива так, чтобы все, удовлетворяющие условию, шли первыми. Это основа алгоритма быстрой сортировки и задач типа «удалить дубликаты».

Здесь read — быстрый указатель, который сканирует массив. write — медленный, который фиксирует позицию для записи уникального элемента. Это паттерн slow-fast pointer, который встречается и в задачах на связные списки (обнаружение цикла, поиск середины списка).

Скользящее окно: фиксированный размер

Скользящее окно — частный случай двух указателей, где мы поддерживаем «окно» между left и right и расширяем/сужаем его по определённому правилу.

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

Это как движущаяся камера на конвейере: мы видим ровно предметов, и при каждом шаге один уходит, другой приходит.

Скользящее окно: динамический размер

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

Задача: найти минимальную длину подмассива, сумма элементов которого target.

Обрати внимание на структуру: внешний цикл расширяет окно (right движется всегда вперёд), внутренний while сужает (left догоняет). Это универсальный шаблон скользящего окна.

Когда два указателя, а когда окно

На интервью важно правильно классифицировать задачу:

Ловушка: в задачах на скользящее окно с подсчётом уникальных элементов часто нужен словарь (hash map) для отслеживания содержимого окна. Не забывай обновлять его при расширении и сужении — пропущенное удаление из словаря приводит к неверным ответам.

Стеки, очереди и деки

Почему оператор вызова функций в любом языке программирования — это стек? Потому что последняя вызванная функция должна завершиться первой. Этот принцип LIFO (Last In — First Out) лежит в основе одной из самых востребованных структур данных на технических интервью. А принцип FIFO (First In — First Out) — в основе очередей, без которых не работает ни один планировщик задач.

Стек: структура и применение

Стек поддерживает две операции: push (положить наверх) и pop (снять сверху). В Python стек реализуется обычным списком — append() для push, pop() для pop. Обе операции работают за .

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

Обрати внимание на финальную проверку len(stack) == 0 — она отлавливает случай, когда открывающих скобок больше, чем закрывающих. Это типичный edge case, который интервьюеры ожидают увидеть.

Монотонный стек

Гораздо более мощный приём — монотонный стек: стек, элементы в котором всегда упорядочены (по возрастанию или убыванию). Мы добавляем элемент, а перед этим удаляем из стека все элементы, которые нарушают монотонность.

Задача «Next Greater Element»: для каждого элемента массива найти первый бо́льший элемент справа. Перебор — . Монотонный стек — .

Почему это работает? Стек хранит индексы элементов, для которых мы ещё не нашли «следующий бо́льший». Когда приходит элемент больше верхушки стека — он и есть ответ для всех меньших элементов в стеке. Каждый элемент входит в стек и выходит из него ровно один раз, поэтому суммарная сложность — .

Монотонный стек решает целый класс задач: «Next Greater Element», «Largest Rectangle in Histogram», «Daily Temperatures», «Trapping Rain Water». Это один из самых ценных паттернов для интервью.

Очередь и deque

Очередь (queue) работает по принципу FIFO: добавляем в конец, извлекаем из начала. В Python для этого используется collections.deque — двусторонняя очередь с операциями на обоих концах. Обычный список тоже может充当 очередь, но pop(0) работает за , потому что все элементы сдвигаются.

Дек (deque — double-ended queue) — это обобщение стека и очереди: можно добавлять и удалять элементы с обоих концов за .

Очередь с поддержкой максимума

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

Каждый элемент максимум один раз добавляется и один раз удаляется из дека, поэтому сложность — , несмотря на вложенный while.

Стек vs Очередь vs Дек: выбор структуры

| Структура | Когда использовать | Python-реализация | |-----------|-------------------|-------------------| | Стек | Парсинг, отмена действий, DFS, монотонные структуры | list с append/pop | | Очередь | BFS, буферизация, планирование | collections.deque | | Дек | Скользящее окно, двусторонняя обработка | collections.deque |

Ловушка: не используй list как очередь — pop(0) за убьёт производительность. Всегда deque для операций на обоих концах.

Алгоритмы обхода графов: BFS и DFS

Когда навигатор строит маршрут от точки А до точки Б, он обходит граф дорог. Когда компилятор проверяет зависимости между модулями — он обходит граф импортов. Когда поисковый робот переходит по ссылкам — он обходит граф веб-страниц. Все эти задачи сводятся к двум базовым алгоритмам: BFS (Breadth-First Search, поиск в ширину) и DFS (Depth-First Search, поиск в глубину). Знание разницы между ними — обязательный минимум для технического интервью.

Представление графов в Python

Перед обходом нужно понимать, как граф хранится в памяти. Два основных способа:

На практике и интервью почти всегда используется список смежности.

DFS: погружение в глубину

DFS исследует граф, уходя как можно глубже по одному пути, прежде чем вернуться и попробовать другой. Это естественно реализуется через рекурсию (неявный стек вызовов) или явный стек.

Аналогия из жизни: лабиринт, в котором ты идёшь вперёд, пока не упрёшься в стену, затем возвращаешься до последнего перекрёстка и пробуешь другую дорогу.

DFS естественно решает задачи, где важен порядок зависимостей: топологическая сортировка, обнаружение циклов, нахождение компонент связности.

Обнаружение цикла через DFS

Для ориентированного графа цикл существует, если при обходе мы попадаем в узел, который находится в текущем стеке вызовов (не просто «посещён», а «сейчас обрабатывается»). Для этого нужен не один visited, а три состояния: не посещён, в процессе, завершён.

Серый цвет (GRAY) означает «в текущем пути». Если мы натыкаемся на серый узел — нашли обратное ребро, а значит, цикл.

BFS: исследование по слоям

BFS обходит граф по уровням: сначала всех соседей стартового узла, потом их соседей и так далее. Реализуется через очередь — это ключевое отличие от DFS.

Аналогия: бросаешь камень в воду — волны расходятся концентрическими кругами. Каждый круг — один «уровень» BFS.

BFS гарантирует нахождение кратчайшего пути в невзвешенном графе — это его главное преимущество. DFS такой гарантии не даёт.

BFS для кратчайшего пути

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

BFS vs DFS: когда что выбирать

| Критерий | BFS | DFS | |----------|-----|-----| | Структура данных | Очередь | Стек (рекурсия) | | Кратчайший путь | Да (в невзвешенном графе) | Нет | | Память | Может быть большой (все узли уровня) | Глубина рекурсии | | Топологическая сортировка | Модификация (Kahn's) | Стандартный подход | | Обнаружение цикла | Сложнее | Естественно через цвета |

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

Ловушка: забыть visited — и оба алгоритма зациклятся на графе с циклами. Всегда добавляй узел в visited в момент помещения в очередь/стек, а не при извлечении. Иначе один и тот же узел может оказаться в очереди несколько раз, что резко увеличивает потребление памяти.

Практика решения алгоритмических задач

Теория без практики — как карта без маршрута. Ты знаешь, что бинарный поиск работает за , а BFS находит кратчайший путь, но на интервью нужно за 20–30 минут превратить это знание в работающий код. Эта статья — системный разбор пяти задач, каждая из которых комбинирует техники из предыдущих статей. Именно комбинирование — то, что отличает уверенного кандидата от того, кто зубрит шаблоны.

Задача 1: Поиск в матрице (бинарный поиск + префиксные суммы)

Условие: дана матрица , каждая строка отсортирована по возрастанию. Определить, содержится ли заданное значение в матрице.

Ключевое наблюдение: можно рассматривать матрицу как один отсортированный массив длины и применить бинарный поиск. Индекс в плоском массиве соответствует ячейке [k // n][k % n].

Сложность: . Это пример того, как умение переформулировать структуру данных (матрица → плоский массив) открывает путь к оптимальному решению.

Задача 2: Максимальная сумма подмассива фиксированного размера (скользящее окно + префиксные суммы)

Условие: дан массив и число . Найти подмассив длины с максимальной суммой.

Два подхода. Первый — префиксные суммы: sum(i, j) = prefix[j+1] - prefix[i], перебираем все окна. Второй — скользящее окно: поддерживаем сумму текущего окна и обновляем её за при сдвиге.

Скользящее окно — это по сути оптимизированная версия подхода с префиксными суммами: мы не храним весь массив префиксных сумм, а поддерживаем только текущее «окно» из него.

Задача 3: Валидация стека (стек)

Условие: дана последовательность операций push и pop. Определить, может ли данная последовательность pop быть результатом корректной работы стека.

Идея: симулируем процесс. Идём по последовательности push, и каждый раз, когда верхушка стека совпадает с ожидаемым элементом из pop-последовательности — выполняем pop.

Элегантность в том, что жадный подход (pop, как только можем) не влияет на корректность — стек не «потеряет» возможность выполнить нужный pop позже.

Задача 4: Островные территории (BFS/DFS на сетке)

Условие: дана бинарная матрица, где 1 — суша, 0 — вода. Посчитать количество островов (связных компонент из единиц).

Это классическая задача на flood fill. Каждый раз, когда находим непосещённую 1, запускаем обход (BFS или DFS) и помечаем весь остров.

Здесь DFS предпочтительнее BFS, потому что рекурсия проще записывается для flood fill. Но для очень больших матриц BFS безопаснее — нет риска переполнения стека вызовов.

Задача 5: Комбинированная — минимальное окно с покрытием (скользящее окно + хеш-таблица)

Условие: даны строка s и строка t. Найти минимальное по длине подокно в s, которое содержит все символы t (включая дубликаты).

Это одна из самых частых задач на интервью в крупных компаниях. Решение — скользящее окно с двумя словарями: один хранит частоты символов в t, другой — в текущем окне.

Эта задача комбинирует скользящее окно, хеш-таблицу и счётчик — типичная комбинация для интервью уровня middle/senior.

Стратегия подготовки

Разбор пяти задач — это отправная точка. Эффективная подготовка строится на трёх принципах: