Алгоритмы на Python для алгоритмического собеседования в Яндекс

Формат собеседования, шаблон решения и анализ сложности

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

В этом курсе мы будем решать задачи в формате, максимально похожем на реальный: ограничения по времени, ввод-вывод как в контестах, обязательное объяснение решения и оценка сложности.

!Схема идеального процесса решения задачи на собеседовании

Как обычно устроено алгоритмическое собеседование в Яндекс

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

Вам дают задачу и несколько минут на чтение.

Вы задаёте уточняющие вопросы (про ограничения, формат ввода, крайние случаи).

Вы предлагаете идею решения и обосновываете корректность.

Вы оцениваете сложность по времени и памяти.

Вы пишете код и проговариваете детали реализации.

Вы прогоняете решение на примерах и крайних случаях.

При необходимости оптимизируете или исправляете.

Полезно заранее привыкнуть к контестному вводу-выводу, потому что часто задачи близки к формату Яндекс Контеста: чтение из стандартного ввода и печать в стандартный вывод.

Как читать условие и не пропустить важное

Большинство провалов происходит не из-за алгоритма, а из-за невнимания к деталям.

Выпишите, что дано (входные данные) и что нужно получить (выходные данные).

Найдите ограничения:

1. Максимальный размер входа (например, число элементов массива). 2. Диапазон значений (например, числа до миллиарда, строки до 10^5 символов). 3. Ограничения по времени/памяти (если указаны).

Отметьте важные свойства:

1. Отсортированы ли данные. 2. Есть ли повторяющиеся элементы. 3. Нужно ли сохранять порядок. 4. Есть ли несколько тестов.

Сразу составьте 2–3 крайних случая:

1. Минимальный размер (пусто, один элемент). 2. Все элементы одинаковые. 3. Строго возрастающая/убывающая последовательность. 4. Максимальный размер.

Шаблон ответа на собеседовании

Ниже — универсальный шаблон коммуникации. Он помогает выглядеть уверенно и снижает риск забыть важное.

Переформулировать задачу своими словами

1. Коротко: что дано и что требуется. 2. Уточнить неоднозначности.

Предложить подход

1. Идея на высоком уровне. 2. Какие структуры данных используете и почему.

Доказать корректность

1. Почему алгоритм всегда находит правильный ответ. 2. Инвариант или логика выбора (жадность, динамика, граф и т.д.).

Оценить сложность

1. Время: от чего зависит (например, от числа элементов n). 2. Память: какие дополнительные структуры.

Реализация

1. Псевдокод или план. 2. Аккуратный код.

Проверка

1. Пройти по маленькому примеру руками. 2. Проверить крайние случаи.

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

Контестный шаблон кода на Python

На собеседовании часто ожидают стиль, близкий к контестному: быстрое чтение, solve() и минимальные побочные эффекты.

Почему это удобно:

sys.stdin.buffer.read() читает весь ввод быстро и стабильно на больших данных.

.split() превращает ввод в список токенов (байтовых строк). Для чисел обычно делаем int(token).

solve() упрощает структуру, позволяет легко тестировать локально.

Документация:

sys — System-specific parameters and functions

Если вход построчный и вам важна читаемость, можно использовать sys.stdin.readline, но в задачах на большие объёмы ввод целиком часто быстрее.

Анализ сложности: что от вас ждут

Обычно от кандидата ждут оценку:

сложности по времени: как растёт количество операций при росте размера входа

сложности по памяти: сколько дополнительной памяти нужно (помимо входных данных)

Асимптотика простыми словами

Сложность записывают как O(...). Смысл такой:

мы смотрим, как ведёт себя время/память при больших размерах входа

константы и мелкие добавки обычно игнорируем

Примеры:

O(n): один проход по массиву длины n

O(n log n): сортировка (обычно так)

O(n^2): двойной цикл по всем парам

Как быстро прикидывать, что пройдёт по ограничениям

В интервью обычно достаточно грубой оценки.

Если n около 10^5–2·10^5:

1. O(n) и O(n log n) обычно подходят. 2. O(n^2) почти всегда слишком медленно.

Если n около 10^3–5·10^3:

1. O(n^2) иногда допустимо.

Если есть два параметра (например, n и m):

1. оценка часто выглядит как O(n + m) или O(n log n + m)

Это не «железное правило», но хороший ориентир для разговора.

Что говорить про память

Обычно важно назвать:

храните ли вы дополнительные массивы размера n

используете ли словарь/множество, которые в худшем случае тоже растут до n

есть ли рекурсия (глубина стека)

Примеры формулировок:

По памяти O(n), потому что храню словарь частот для всех элементов.

По памяти O(1) дополнительной, потому что использую только несколько переменных и прохожу массив на месте.

Частые сложности операций в Python (практический минимум)

Таблица ниже — не формальное доказательство, а удобная шпаргалка для интервью.

| Операция | Обычно по времени | Комментарий | |---|---|---| | Проход по списку for x in a | O(n) | n — длина списка | | Доступ по индексу a[i] | O(1) | для списков | | append в список | амортизированно O(1) | иногда список расширяется и операция дороже, но в среднем дёшево | | Проверка x in set | в среднем O(1) | в худшем случае может деградировать, но в интервью обычно говорят «в среднем» | | Проверка x in list | O(n) | линейный поиск | | Сортировка sorted(a) / a.sort() | O(n log n) | одна из самых частых «легальных» оптимизаций |

Если вы используете специальные структуры, полезно упомянуть их назначение:

очередь/двусторонняя очередь: collections.deque

приоритетная очередь (куча): heapq

Типовые ошибки в оценке сложности

Забыли про сортировку

1. Часто решение выглядит как «сначала отсортируем», а дальше линейно. 2. Итоговая сложность будет O(n log n), а не O(n).

Считаете, что x in list — это O(1)

1. Для списка это линейный поиск O(n). 2. Для множества/словаря обычно говорят «в среднем O(1).

Перепутали худший и средний случай

1. На собеседовании лучше явно говорить: в среднем O(1), в худшем может быть хуже.

Как это будет использоваться дальше в курсе

Дальше мы будем разбирать основные паттерны решения задач и каждый раз закреплять привычку:

Выделять ограничения и выбирать класс сложности.

Подбирать структуру данных под нужные операции.

Формулировать корректность и оценку сложности.

Писать аккуратный Python-код в контестном стиле.

Массивы, строки, два указателя и скользящее окно

В прошлой статье мы зафиксировали формат интервью: внимательно читаем условие, уточняем ограничения, формулируем идею, доказываем корректность, оцениваем сложность и только потом пишем код.

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

два указателя

скользящее окно

Оба паттерна особенно важны для задач в стиле Яндекс Контеста, где вход может быть до – элементов, и квадратичные решения не проходят.

Массивы и строки в Python как «последовательности»

На интервью от вас ждут не глубоких знаний всех методов Python, а уверенного владения базовыми операциями и понимания их стоимости.

Массив (список) list

Типичные операции:

a[i] — доступ по индексу, обычно

a.append(x) — амортизированно

проход for x in a —

a[l:r] — срез создает новый список, обычно по времени и памяти

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

Документация: Типы последовательностей

Строка str

Строки в Python неизменяемые. Это влияет на производительность:

s[i] —

s[l:r] — новый объект строки, обычно

конкатенация в цикле ans += ch может дать (из-за постоянных пересозданий)

Если нужно собирать строку по кусочкам, используйте список символов и "".join(...).

Документация: str — текстовые последовательности

Паттерн «два указателя»

Два указателя — это техника, где вы поддерживаете две позиции в последовательности и двигаете одну или обе, чтобы обработать данные за один проход.

Когда подходит:

массив (или строка) уже отсортирован

нужно искать пары/отрезки с условием

нужно «сжимать» массив, удаляя дубликаты или элементы по условию

нужно сравнивать элементы с двух концов

!Как работают два указателя: движение L и R в зависимости от условия

Классический кейс: найти пару с заданной суммой в отсортированном массиве

Условие: дан отсортированный массив a и число target. Нужно понять, есть ли пара a[i] + a[j] == target.

Идея:

ставим l = 0, r = n - 1

считаем сумму a[l] + a[r]

если сумма слишком маленькая — двигаем l вправо

если слишком большая — двигаем r влево

Почему это работает:

массив отсортирован

при фиксированном r увеличение l только увеличивает сумму

при фиксированном l уменьшение r только уменьшает сумму

Сложность:

по времени , потому что каждый указатель двигается максимум раз

по памяти

Вариант «медленный/быстрый» указатели

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

Примеры задач:

удалить элементы по условию «на месте»

удалить дубликаты в отсортированном массиве

разделить элементы на две группы (похожие на partition)

Идея обычно такая:

write показывает, куда писать следующий «хороший» элемент

read пробегает весь массив

Собеседнику важно услышать, что:

вы явно контролируете, что пишете в начало массива

вы не используете срезы и не делаете лишних копий

Паттерн «скользящее окно»

Скользящее окно — техника для задач про подотрезки/подстроки, где нужен лучший (максимальный/минимальный) отрезок, удовлетворяющий условию.

Окно обычно задается двумя границами:

l — левая граница

r — правая граница (часто растет слева направо)

!Как скользящее окно расширяется и сжимается, чтобы поддерживать условие

Два основных типа окон

фиксированное окно: размер всегда равен k

переменное окно: размер меняется, но окно должно удовлетворять условию (например, сумма не превышает лимит)

#### Фиксированное окно: максимум суммы на отрезке длины k

Идея:

сначала считаем сумму первых k

потом двигаем окно на 1: добавляем новый элемент и вычитаем ушедший

Сложность .

Замечание: здесь a[:k] создаёт срез, но он делается один раз, поэтому не ломает асимптотику. Если хотите быть максимально строгими по памяти, можно посчитать сумму без среза циклом.

#### Переменное окно: самый длинный подотрезок с суммой не больше S (только неотрицательные числа)

Это типовая задача, где можно получить , если числа неотрицательные.

Идея:

двигаем r вправо и увеличиваем текущую сумму

если сумма стала больше S, двигаем l вправо, уменьшая сумму, пока условие не восстановится

обновляем ответ

Сложность:

по времени, потому что l и r каждый сдвигаются не больше раз

по памяти

Важный нюанс для интервью:

если в массиве могут быть отрицательные числа, это окно может перестать быть корректным, потому что при расширении окна сумма может уменьшаться, и простой принцип «нарушили — сжали» уже не гарантирует правильность. Тогда обычно нужны другие техники (например, префиксные суммы и структуры данных).

Скользящее окно по строке: частоты символов

В строковых задачах окно часто требует поддерживать информацию о текущем наборе символов:

множество set (если нужен только факт наличия)

словарь частот dict или collections.Counter (если важны количества)

Документация: Типы отображений dict

Пример часто встречающегося условия: «в окне все символы уникальны» или «в окне не более различных символов». Тогда при сдвиге l нужно аккуратно обновлять частоты.

Как это рассказывать на собеседовании

Для двух указателей и окон хорошо работает один и тот же шаблон объяснения:

что означают l и r

какое условие (инвариант) вы поддерживаете

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

итоговая сложность

Пример формулировки-инварианта:

Я поддерживаю, что текущая сумма элементов на отрезке не превышает S. Когда добавление нового элемента нарушает условие, я двигаю l вправо, пока условие снова не выполнится.

Частые ошибки и как их избегать

Ошибки границ: забыли, что отрезок обычно считается как включительно, и пишут r - l вместо r - l + 1.

Неправильный порядок обновлений: например, сначала обновили ответ, а потом сжали окно (или наоборот), из-за чего окно может быть «некорректным» в момент обновления.

Срезы в цикле: a[i:j] внутри цикла часто делает решение .

Конкатенация строк в цикле: res += s[i] на больших входах может стать узким местом.

Неприменимость окна: если условие не монотонно при расширении/сжатии (например, массив с отрицательными числами для суммы), стандартное окно может не работать.

Минимальный контестный каркас для задач на массивы и окна

Ниже — удобный стартовый шаблон, совместимый с форматом контестов.

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

Хеш-структуры и множества: частотные задачи и индексация

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

Эту роль на собеседованиях чаще всего играют хеш-структуры:

множество set для быстрого ответа на вопрос есть ли элемент в наборе

словарь dict для сопоставления ключ → значение (частота, последний индекс, счётчик, агрегат)

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

!Интуитивная схема, почему dict и set дают быстрый доступ по ключу

Что такое хеш-таблица и что важно говорить на интервью

И dict, и set в Python реализованы на базе хеш-таблицы.

Практически полезные утверждения для интервью:

операции x in set, x in dict, d[key], d[key] = value обычно работают за среднее

по памяти set и dict растут примерно пропорционально количеству хранимых ключей

Корректная формулировка про скорость:

В среднем на операцию, потому что доступ идёт по хешу; в худшем случае может деградировать, но для задач интервью обычно достаточно среднего случая.

Ссылки на документацию:

dict — встроенный тип отображений

set — встроенный тип множеств

Множество set: уникальность и быстрые проверки принадлежности

Когда set почти всегда правильный выбор

нужно быстро проверять, встречался ли элемент ранее

нужно оставить только уникальные значения

нужно быстро считать количество различных элементов

нужно делать пересечения, объединения, разности множеств

Частые паттерны

#### Удалить дубликаты и посчитать уникальные

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

#### Проверка существования пары с заданной суммой (массив не отсортирован)

Если массив отсортирован, мы часто делаем два указателя. Если он не отсортирован, удобнее set.

Идея:

идём слева направо

для текущего x хотим найти target - x среди уже виденных

Сложность:

по времени обычно

по памяти в худшем случае (если все элементы разные)

Частые ошибки с set

пытаться положить в set изменяемый объект, например list

- в set можно добавлять только хешируемые объекты - хешируемые обычно означают неизменяемые (например, int, str, tuple)

Словарь dict: частоты, последний индекс, агрегации

dict хранит соответствие ключ → значение. В интервью чаще всего значение — это:

частота встречаемости

последний индекс/позиция

накопленная сумма/какой-то агрегат

Частотные задачи: считаем, сколько раз встречается каждый элемент

Самая базовая форма:

Здесь cnt.get(x, 0) означает:

если ключ x уже есть, взять его значение

иначе вернуть 0

Это часто быстрее и чище, чем писать if x in cnt: ... else: ....

#### defaultdict для частот

Иногда удобнее defaultdict(int): отсутствующий ключ автоматически имеет значение 0.

Документация:

collections.defaultdict

#### Counter: когда нужно быстро и выразительно

Counter полезен для задач вроде сравнить мультимножества или взять топ частотных.

Документация:

collections.Counter

На собеседовании важно помнить:

Counter читается отлично, но может быть тяжелее по константам

если важна максимальная производительность, иногда пишут ручной dict.get

Индексация: храним позиции элементов

Очень распространённый приём: хранить в dict, где мы последний раз видели элемент.

#### Two Sum: вернуть индексы пары (массив не отсортирован)

Задача: дан массив a и target. Найти индексы i и j, такие что a[i] + a[j] = target.

Идея:

идём слева направо по i

хотим найти need = target - a[i] среди элементов слева

в словаре храним значение → индекс, который уже встречался

Что важно проговорить:

мы не используем один и тот же элемент дважды, потому что ищем пару только среди уже пройденных индексов

сложность обычно по времени и по памяти

#### Связь со скользящим окном: самый длинный участок без повторов

Это мостик к прошлой теме скользящего окна: часто окно по строке делают через словарь последних позиций.

Задача: найти длину самой длинной подстроки без повторяющихся символов.

Инвариант:

поддерживаем окно , в котором нет повторов

last[ch] хранит последний индекс, где встречался символ ch

когда видим повтор внутри окна, двигаем l вправо

Ключевой нюанс: l = max(l, last[ch] + 1).

если просто написать l = last[ch] + 1, можно случайно сдвинуть l назад, нарушив корректность

По сложности:

по времени , потому что r движется один раз, а l не убывает

по памяти , где m — число различных символов

Хешируемость ключей: что можно использовать как ключ в dict и элемент set

Правило, полезное в интервью:

ключи dict и элементы set должны быть хешируемыми

почти всегда это означает неизменяемые объекты

Примеры:

можно: int, str, tuple (если внутри тоже хешируемые)

нельзя: list, dict, set

Если нужно использовать набор как ключ, есть вариант frozenset (неизменяемое множество), но в интервью он встречается реже.

Типовые задачи, которые почти всегда решаются через dict/set

найти первый элемент, который встречается дважды

проверить, что все элементы уникальны

найти пересечение двух массивов

найти элементы, которые встречаются чаще всего

группировать элементы по ключу (например, сгруппировать слова по длине)

задачи на подстроки с условиями вида не более различных символов (скользящее окно + частоты)

Практические советы для собеседования на Python

Как выбирать между set и dict

если нужно только наличие элемента, берите set

если нужно хранить дополнительную информацию (частота, индекс, сумма), берите dict

Не забывайте про память

Решение через хеш-таблицу часто выигрывает время, но тратит память.

Корректная формулировка:

Память , где — количество различных ключей (в худшем случае ).

Если ключей мало и они ограничены

Иногда быстрее использовать массив частот вместо dict.

Пример: строка состоит только из маленьких латинских букв a..z.

можно сделать список из 26 счётчиков

это даст предсказуемую память и маленькие константы

Но на собеседовании это стоит делать только если ограничение явно дано.

Как это связывается с курсом дальше

Хеш-структуры — фундамент для следующих тем:

префиксные суммы и поиск подотрезков через словарь

более сложные окна по строкам через частоты

графы: хранение списков смежности в dict или defaultdict(list)

Если вы уверенно владеете dict и set, многие задачи Яндекс-уровня становятся вопросом правильного инварианта и аккуратной реализации.

Стеки, очереди, deque и монотонные структуры

После паттернов два указателя/скользящее окно и хеш-структур (dict/set) следующий базовый блок для алгоритмического интервью — линейные структуры данных, которые управляют порядком обработки элементов:

стек: последний пришёл — первый вышел

очередь: первый пришёл — первый вышел

deque: двусторонняя очередь, где эффективно работать можно с обоих концов

монотонный стек и монотонная очередь: специализированные паттерны, которые дают линейное решение там, где наивно получается квадратичное

Эти структуры часто встречаются в задачах Яндекс-формата, потому что позволяют за один проход поддерживать контекст (что было “рядом”, “до”, “последнее подходящее”, “лучшее в окне”).

!Сравнение принципов работы стека, очереди и deque

Стек

Стек (LIFO) поддерживает две основные операции:

push(x) — положить элемент наверх

pop() — снять верхний элемент

Где стек появляется на собеседовании

проверка корректности скобочных последовательностей

вычисление выражений (например, обратная польская запись)

поиск ближайшего большего/меньшего элемента слева/справа

обходы графов/деревьев (DFS) итеративно

Реализация стека в Python

Самый частый вариант — обычный список list:

append(x) работает быстро

pop() с конца работает быстро

Важно: удаление/добавление в начало списка (pop(0), insert(0, ...)) обычно медленное, потому что требуется сдвиг элементов.

Что проговаривать на интервью:

Стек хранит ещё не закрытые открывающие скобки.

При встрече закрывающей проверяем, что верх стека — соответствующая открывающая.

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

Очередь

Очередь (FIFO) поддерживает:

enqueue(x) — добавить в конец

dequeue() — удалить из начала

Где очередь появляется

обход в ширину (BFS) в графах и на решётках

симуляции процессов (обработка событий в порядке поступления)

задачи “обрабатываем поток, поддерживаем окно/буфер”

Почему нельзя делать очередь через list.pop(0)

Если реализовать очередь как список и делать pop(0), то каждый раз все элементы будут сдвигаться влево. На больших входах это часто превращает хорошую идею в медленное решение.

collections.deque: практический стандарт для очередей

deque — двусторонняя очередь из стандартной библиотеки, оптимизированная для операций на концах.

Типовые операции:

append(x) — добавить справа

pop() — убрать справа

appendleft(x) — добавить слева

popleft() — убрать слева

Ссылка: collections.deque

Мини-шаблон очереди на deque

Здесь важна не “задача”, а привычка: если вам нужна очередь, в Python почти всегда выбирайте deque.

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

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

для каждого элемента найти ближайший больший справа

для каждого элемента найти ближайший меньший слева

посчитать, сколько подотрезков удовлетворяют условию “минимум/максимум находится здесь”

Идея монотонности:

вы выкидываете из стека элементы, которые больше не могут быть ответом для будущих позиций

каждый элемент добавляется в стек один раз и удаляется из стека максимум один раз

Из-за этого алгоритм обычно получается линейным.

!Как монотонный стек находит ближайший больший элемент справа

Пример: ближайший больший элемент справа (Next Greater Element)

Дано a. Для каждого i найти индекс j > i минимальный, такой что a[j] > a[i], или -1.

Инвариант:

в стеке храним индексы элементов, для которых ответ ещё не найден

значения на этих индексах идут по убыванию (сверху — самый маленький из “ожидающих”), чтобы при встрече большого значения быстро “закрыть” ответы

Что сказать на собеседовании:

Как только пришёл элемент x, он является ближайшим большим справа для всех элементов на вершине стека, которые меньше x.

Мы их вытаскиваем, потому что дальше вправо “ближайшим” для них уже будет текущий i, и они больше не нужны.

Типовые ошибки:

перепутать строгий знак < и <= при наличии равных элементов

хранить в стеке значения вместо индексов и потерять информацию о позиции

Монотонная очередь (монотонный deque)

Монотонная очередь чаще всего нужна для задач скользящего окна, где требуется:

максимум (или минимум) на каждом окне длины k

Наивное решение “пересчитывать максимум на каждом окне” может быть медленным. Монотонный deque даёт линейный проход.

Пример: максимум на каждом окне длины k

Идея:

храним в deque индексы элементов

значения по этим индексам поддерживаем в порядке убывания

голова очереди всегда содержит индекс текущего максимума

Правила обновления при добавлении a[r]:

пока справа в deque элементы меньше нового, выкидываем их (они уже не могут быть максимумом ни в каком будущем окне, которое включает r)

добавляем r

если голова вышла из окна (индекс меньше левой границы), удаляем её слева

Нюансы, которые любят на интервью:

мы храним индексы, чтобы понимать, вышел ли элемент из окна

знак <= означает, что при равных значениях мы выбрасываем более старый индекс, чтобы голова была максимально “свежей” и не вылетела раньше времени

Как выбирать структуру на собеседовании

Короткая памятка выбора:

нужен “последний незакрытый контекст” → стек

нужно обрабатывать “в порядке прихода” → очередь

нужна очередь в Python → почти всегда deque

нужно “следующее большее/меньшее” или “границы влияния элемента” → монотонный стек

нужно максимум/минимум в скользящем окне → монотонный deque

Как это связывается с предыдущими темами курса

со скользящим окном монотонная очередь даёт усиление: вместо поддержки частот через dict (когда условие про символы) вы поддерживаете экстремум (когда условие про максимум/минимум)

с хеш-структурами стек/очередь часто комбинируются в задачах на строки: например, стек для структуры, dict для быстрых сопоставлений или позиций

В следующих темах эти структуры станут “строительными блоками” для графов (BFS/DFS), задач на интервалы и продвинутых паттернов оптимизации.

Деревья и графы: BFS, DFS, кратчайшие пути

Задачи на деревья и графы — один из самых частых «порогов» на алгоритмическом собеседовании в Яндекс: они проверяют умение построить модель, выбрать обход (BFS/DFS), аккуратно хранить состояние и писать код без ошибок в индексации и структурах данных.

Эта тема напрямую опирается на предыдущие статьи курса:

из статьи про хеш-структуры вам пригодятся dict и set для хранения графа и visited

из статьи про очереди и deque — реализация BFS

из статьи про стек — итеративный DFS и понимание стека вызовов при рекурсии

!Иллюстрация идеи BFS как обхода по слоям и почему расстояния в не взвешенном графе считаются корректно

Что такое граф и как он связан с деревом

Граф состоит из:

вершин (узлов)

рёбер (связей)

Часто в задачах встречаются варианты:

неориентированный граф: ребро соединяет две вершины в обе стороны

ориентированный граф: ребро идёт из u в v

взвешенный граф: у ребра есть стоимость (вес)

Дерево — частный случай графа:

связный

без циклов

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

Как хранить граф в Python

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

Список смежности (самый частый вариант)

Если у нас n вершин с номерами 0..n-1 (или 1..n), то обычно делают:

g[u] — список соседей u

Для неориентированного графа каждое ребро добавляется в обе стороны.

Сложность памяти для списка смежности обычно оценивают как , где:

— число вершин

— число рёбер

Смысл записи : память растёт пропорционально количеству вершин (храним контейнер для каждой) и количеству рёбер (храним всех соседей).

Пример построения для неориентированного графа:

Взвешенный граф

Тогда g[u] обычно хранит пары (v, w):

Почему обычно не используют матрицу смежности

Матрица смежности — это n x n таблица. По памяти это , что почти всегда слишком дорого при около .

BFS: обход в ширину и кратчайшие пути без весов

BFS (Breadth-First Search) обходит граф «по слоям» от стартовой вершины.

Главная ценность BFS на интервью:

в не взвешенном графе (или когда все веса равны) BFS находит кратчайшее расстояние по числу рёбер

Инвариант BFS

Удобная формулировка:

когда вершина извлекается из очереди, её расстояние уже минимально возможное

Это верно, потому что очередь FIFO гарантирует обработку вершин в порядке увеличения расстояния.

Реализация BFS на deque

Мы будем хранить:

dist[v] — расстояние от старта до v (или -1, если не достижима)

parent[v] — откуда пришли (полезно для восстановления пути)

Почему важно отметить deque:

popleft() у deque работает эффективно

если пытаться делать очередь через list.pop(0), то удаление из начала потребует сдвигать элементы, и это часто «убивает» время

Восстановление пути по parent

Если нужно вывести сам путь start -> ... -> target:

Сложность BFS

BFS обычно оценивают как по времени, где:

— число вершин

— число рёбер

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

DFS: обход в глубину, компоненты связности и циклы

DFS (Depth-First Search) «ныряет» в глубину, пока может, а затем откатывается назад.

Где DFS очень типичен:

посчитать компоненты связности в неориентированном графе

проверить достижимость

найти цикл (особенно в ориентированном графе)

топологическая сортировка (ориентированный ациклический граф)

!Иллюстрация связи рекурсивного DFS со стеком и того, что итеративная версия делает то же самое

Рекурсивный DFS: просто, но есть риск глубины

Рекурсивная версия часто самая читаемая, но на больших графах можно упереться в ограничение глубины рекурсии.

На интервью полезно проговорить:

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

Итеративный DFS через стек

Это прямое применение структуры из прошлой темы про стеки.

Нюанс: мы делаем проверку visited при извлечении из стека. Это упрощает код, потому что одна и та же вершина может быть добавлена несколько раз разными путями.

Компоненты связности (частая задача)

Если граф неориентированный, то компоненты связности считаются так:

идём по всем вершинам

если вершина ещё не посещена, запускаем DFS/BFS из неё и увеличиваем счётчик

Деревья на практике: корень, родитель, глубина

На собеседовании дерево часто дают как:

массив parent для вершин 1..n, где parent[v] — родитель

или как список рёбер

Типовые подзадачи:

найти глубины вершин от корня

посчитать размеры поддеревьев

проверить свойства (например, что это дерево)

Если дан список рёбер дерева, то вы строите список смежности как для графа, выбираете корень root и запускаете DFS/BFS, но добавляете параметр p (родитель), чтобы не «ходить назад».

Пример DFS по дереву с вычислением глубин:

Кратчайшие пути: какой алгоритм выбрать

Самый частый вопрос на интервью: по графу нужно найти минимальную стоимость пути. Дальше решает тип рёбер.

Невзвешенный граф

используем BFS

расстояние — число рёбер

Взвешенный граф с неотрицательными весами

чаще всего нужен алгоритм Дейкстры

Есть отрицательные веса

Дейкстра не подходит

в интервью обычно достаточно сказать это вслух и предложить другой класс алгоритмов (например, Беллмана–Форда), но код чаще всего не требуют, если задача не про это

Дейкстра на Python: heapq и релаксации

Алгоритм Дейкстры поддерживает текущие лучшие расстояния dist[v] и всегда выбирает следующую вершину с минимальным неизвестным расстоянием.

В Python это обычно делается кучей:

модуль heapq: heapq — Heap queue algorithm

Инвариант Дейкстры (важно проговорить)

когда вершина извлечена из кучи с расстоянием d, и d совпадает с текущим dist[v], это расстояние уже минимально и больше не улучшится (при неотрицательных весах)

Реализация

Что важно в этой реализации:

проверка if d != dist[v]: continue отсекает устаревшие записи в куче

веса w должны быть неотрицательными, иначе инвариант «достали минимум и зафиксировали» ломается

Сложность Дейкстры (как обычно говорят на интервью)

Часто достаточно формулировки:

по времени примерно

Здесь:

— вершины

— рёбра

появляется из-за операций с кучей (добавление и извлечение минимума)

Частный, но полезный случай: веса 0 и 1 (0-1 BFS)

Если веса рёбер только 0 или 1, можно сделать быстрее и проще, используя deque:

если вес 0, добавляем вершину влево (appendleft)

если вес 1, добавляем вправо (append)

Это хороший мостик к теме deque из предыдущих статей: структура данных помогает сохранить правильный порядок обработки.

На собеседовании обычно достаточно:

узнать этот приём

понимать, почему deque здесь работает

Типовые форматы ввода и каркас solve()

В графовых задачах чаще всего дают:

n m

дальше m рёбер

Взвешенный вариант:

u v w

Каркас для чтения и запуска алгоритма:

Важно: под конкретную задачу меняется только чтение (ориентированный/неориентированный, веса) и то, какой алгоритм вы вызываете.

Как это объяснять на собеседовании

Универсальная структура ответа (из первой статьи курса) здесь особенно хорошо работает:

Переформулировать задачу как графовую модель

1. что является вершинами 2. что является рёбрами 3. ориентированность, веса

Выбрать алгоритм

1. BFS, если рёбра равны по стоимости 2. Дейкстра, если веса неотрицательные 3. DFS, если нужна структура достижимости, компоненты, циклы

Назвать инвариант

1. BFS обрабатывает вершины по слоям 2. Дейкстра фиксирует вершину с минимальным расстоянием (при неотрицательных весах)

Оценить сложность

1. BFS/DFS: 2. Дейкстра: примерно

Частые ошибки

перепутали индексацию 1..n и 0..n-1

забыли добавить ребро в обе стороны для неориентированного графа

сделали очередь через list.pop(0) вместо deque.popleft()

в BFS отметили visited слишком поздно и получили много повторных добавлений (обычно ставят метку при добавлении в очередь)

применили Дейкстру при отрицательных весах

рекурсивный DFS на большой глубине без понимания риска переполнения стека

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

Динамическое программирование и жадные алгоритмы

После массивов/окон, хеш-структур, стеков/очередей и графовых обходов следующий большой пласт задач на алгоритмическом интервью в Яндекс — это динамическое программирование и жадные алгоритмы.

Эти темы часто путают, потому что обе «строят ответ постепенно». Разница в том, что:

жадный алгоритм делает локально лучшее решение прямо сейчас и больше к нему не возвращается

динамическое программирование перебирает варианты с запоминанием результатов подзадач, чтобы гарантировать оптимум

Обе техники обычно опираются на уже разобранные инструменты курса:

dict полезен для мемоизации и сопоставлений состояний

deque и heapq часто усиливают жадные решения (выбор лучшего кандидата)

анализ сложности из первой статьи нужен, чтобы объяснить, почему DP проходит по ограничениям, а перебор — нет

!Сравнение интуиции жадного выбора и DP через общие состояния

Как выбирать: жадность или DP

Практическая эвристика для интервью:

Если вы можете доказать, что локальный оптимальный выбор всегда ведёт к глобальному оптимуму, — берите жадный.

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

Признаки жадного алгоритма

решение строится из выбора элементов (интервалы, задачи, предметы)

после сортировки можно «идти слева направо», выбирая следующий допустимый элемент

есть естественный критерий выбора: самый ранний конец, самая маленькая цена, самый большой выигрыш

Признаки динамического программирования

нужно максимизировать/минимизировать значение при ограничениях

наивный рекурсивный перебор даёт много повторов

состояние можно выразить через пару параметров вроде «позиция + ресурс» или «позиция + предыдущий выбор»

Динамическое программирование: смысл и рецепт

Динамическое программирование — это техника, где мы:

разбиваем задачу на подзадачи

замечаем, что подзадачи повторяются

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

В интервью от вас обычно ждут не «магии DP», а чёткого рецепта.

Стандартный шаблон формулировки DP

Состояние: что означает .

Переход: как выразить состояние через более простые.

База: стартовые значения.

Порядок вычисления: чтобы нужные состояния были уже посчитаны.

Ответ: из какого состояния берём результат.

Важно объяснять обозначения. Например, если вы говорите :

— индекс позиции (например, в массиве или строке)

— значение оптимума/количества способов для префикса длины или для позиции (надо проговорить явно)

Два стиля реализации

сверху вниз: рекурсия + мемоизация

снизу вверх: итерация по таблице

В Python для мемоизации часто применяют lru_cache:

functools.lru_cache

Снизу вверх часто быстрее по константам и не зависит от глубины рекурсии.

DP на одном измерении: классический «шаги по лестнице»

Задача-архетип: есть лестница из ступеней, за шаг можно подняться на 1 или 2. Сколько способов добраться до ?

Состояние

Пусть — количество способов попасть на ступень .

— номер ступени (от 0 до )

— число способов оказаться на

Переход

На можно прийти:

с шагом 1

с шагом 2

Значит, .

База

(один способ «быть в начале»)

-

Итеративная реализация с памяти

Мы можем не хранить весь массив, а держать только два предыдущих значения.

Что проговорить на интервью:

Я храню смысл dp, переход и базу.

Каждый i считается один раз, время линейное.

Память O(1), потому что нужны только два предыдущих значения.

DP «позиция + выбор»: минимальная стоимость

Частая разновидность DP: нужно минимизировать стоимость, выбирая, как двигаться.

Пример: дан массив cost, где cost[i] — цена наступить на ступень i. Можно идти на 1 или 2. Найти минимальную стоимость добраться до конца.

Состояние

Пусть — минимальная стоимость оказаться на ступени .

Переход

Чтобы попасть на , мы приходим с или , и платим cost[i]:

-

Почему это DP, а не жадность

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

Двумерное DP: «позиция + ресурс» (мини-рюкзак)

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

Классический формат 0/1 рюкзака:

есть предметы с весами w[i] и ценностями v[i]

можно взять предмет или не взять

общий вес не должен превышать W

Состояние

Пусть — максимальная ценность, если мы рассмотрели первые предметов и имеем лимит веса .

— сколько предметов рассмотрели

— текущий допустимый вес (от 0 до )

— лучший результат

Переход

Для предмета есть два варианта:

не брать: остаётся

брать (если ): получаем

И берём максимум.

На интервью обычно важнее не писать огромную таблицу, а правильно объяснить идею и оценку сложности:

времени будет порядка

памяти тоже порядка , но часто оптимизируют до

Важное ограничение для интервью

DP вида проходит только если не очень большой (например, до иногда на грани, зависит от констант). Если до , значит нужен другой подход.

DP по строкам: идея без углубления в формулы

Строковые DP (например, расстояние редактирования, LCS) часто выглядят пугающе, но на уровне интервью важна модель:

состояние обычно — ответ для префиксов строк длины и

переход зависит от того, равны ли символы на позициях и

Если вы уверенно объясняете «что означает ячейка таблицы», это уже половина успеха.

Типовые ошибки в DP

неясное состояние: dp что именно хранит?

неправильная база: особенно для пустого префикса

перепутали «индекс в массиве» и «длину префикса»

сделали рекурсию без мемоизации и получили экспоненту

не оценили ограничения и применили там, где огромный

Жадные алгоритмы: идея и как их доказывают

Жадный алгоритм строит решение последовательно, каждый раз выбирая локально лучший вариант.

Самая важная часть на интервью — обоснование, почему локальный выбор корректен.

Два самых частых вида доказательства

Обменный аргумент: показываем, что любое оптимальное решение можно «превратить» в наше, не ухудшая ответ.

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

Классический жадный пример: максимум непересекающихся интервалов

Задача: дан набор отрезков . Выбрать максимальное число непересекающихся.

Правильная жадность:

отсортировать отрезки по правому концу

всегда брать отрезок с минимальным правым концом среди доступных

Почему именно правый конец:

чем раньше заканчиваем, тем больше места оставляем следующим

Скелет решения:

Что важно сказать на интервью:

Я сортирую по правым границам.

Локальный выбор: взять самый рано заканчивающийся интервал.

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

Жадность с структурами данных: куча и выбор лучшего

Иногда «локально лучший» означает «самый маленький/большой элемент среди текущих кандидатов». Тогда жадные решения комбинируются с кучей.

Инструмент Python:

heapq

Типовая схема:

сортируем события/задачи по времени начала

добавляем кандидатов в кучу по ключу (например, минимальный дедлайн или максимальная выгода)

на каждом шаге вытаскиваем лучший доступный

На интервью достаточно уверенно объяснить, почему куча нужна:

нам нужно много раз выбирать лучший элемент среди динамического набора, а куча даёт логарифмическое время на вставку и извлечение минимума

Где чаще ошибаются в жадных алгоритмах

выбирают «похожий» критерий (например, по длине интервала вместо правого конца)

не доказывают корректность, ограничиваются интуицией

забывают про сортировку и ошибаются в итоговой сложности

Мини-шпаргалка: что говорить про сложность

Для DP:

если состояний и каждый считается за , итог

память: сколько состояний храните (или сколько после оптимизации)

Для жадности:

почти всегда есть сортировка: это

плюс проход и, возможно, операции с кучей: ещё

Как это стыкуется с предыдущими темами курса

DP часто строится поверх массивов и строк: аккуратные индексы и отказ от лишних срезов критичны

мемоизация DP может использовать dict (или lru_cache) как хеш-структуру

жадные алгоритмы часто требуют heapq, а это «очередь с приоритетом», концептуально продолжение темы очередей

в графах вы уже видели «похожее на DP» поведение: Дейкстра выбирает локально минимальную дистанцию из кучи, но корректность там опирается на неотрицательные веса

Дальше (если расширять курс) эти две темы станут базой для комбинированных задач: DP с восстановлением ответа, жадность + бинарный поиск по ответу, DP на деревьях и графах.

Бинарный поиск, сортировки, кучи и продвинутая практика

Эта статья закрывает важный «инструментальный» блок для алгоритмического интервью в Яндекс: бинарный поиск, сортировки и кучи.

Связь с предыдущими темами курса:

после массивов/строк и двух указателей вы уже умеете делать линейные решения, а сортировка часто превращает «хаос» в структуру, где работают указатели и жадность

после хеш-структур вы умеете проверять принадлежность за среднее , а куча позволяет выбирать лучший элемент среди кандидатов быстрее, чем сортировать заново

после очередей/deque вы знаете BFS, а heapq — это очередь с приоритетом, которая нужна для Дейкстры и многих жадных задач

после DP/жадности вы увидите «бинарный поиск по ответу» как способ оптимизировать задачи, где проверка решения делается быстро, но сам ответ нужно найти

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

Бинарный поиск применим, когда у вас есть монотонность: если некоторое условие истинно для значения , то для всех значений левее/правее оно тоже истинно (в зависимости от постановки).

Чаще всего встречаются два режима:

поиск элемента в отсортированном массиве

поиск границы (первого подходящего значения) — это то, что реально чаще нужно на интервью

!Диаграмма, показывающая как бинарный поиск делит диапазон пополам и сужает границы

Поиск границы: «первый индекс, где значение >= x»

Это фундаментальная версия, потому что:

её можно адаптировать почти к любому поиску по монотонному условию

она безопаснее, чем «классический» бинарный поиск с множеством вариантов while l <= r

Инвариант удобного шаблона:

мы держим полуинтервал

ответ всегда лежит внутри этого диапазона

Код «нижней границы» для списка a:

Как это интерпретировать:

возвращаемое l — это индекс первого элемента, который не меньше x

если все элементы меньше x, вернётся len(a)

Сложность:

по времени сравнений

по памяти

Когда лучше использовать bisect

В Python есть стандартный модуль bisect, который реализует границы и обычно используется в интервью, если не запрещён.

bisect_left(a, x) — аналог lower_bound

bisect_right(a, x) — индекс первого элемента строго больше x

Ссылка: bisect — Array bisection algorithm

Почему иногда всё же пишут руками:

интервьюер может попросить явно проговорить инварианты

так проще встроить бинарный поиск в «поиск по ответу», где нет массива

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

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

Структура задачи обычно такая:

Нужно минимизировать или максимизировать некоторое значение ans.

Можно написать функцию ok(ans), которая проверяет условие за или .

Если ok(x) истинно, то для всех «больших» (или «меньших») значений тоже истинно.

!Схема монотонного предиката ok(x) и поиска первой точки True

Мини-шаблон: найти минимальное x, для которого ok(x) == True

Что важно на интервью проговорить:

какие границы l и r вы выбрали и почему в них точно лежит ответ

почему ok(x) монотонна

итоговую сложность: число итераций умножить на стоимость ok

Типовой пример: «разместить объекты с минимальной дистанцией»

Класс задач: есть отсортированные позиции, нужно поставить k объектов так, чтобы минимальное расстояние между ними было максимально.

Идея:

сортируем позиции

проверка ok(d): можно ли поставить k объектов, соблюдая дистанцию d

предикат монотонен: если можно для d, то можно для меньших дистанций

Проверка обычно делается жадно одним проходом:

Полное решение обычно:

сортировка:

бинарный поиск по d: итераций (где R — диапазон ответа)

каждая проверка:

Итого: .

Сортировка как способ «включить» паттерны

Сортировка — одна из самых частых «легальных» оптимизаций на интервью. Множество задач становятся проще после того, как вы упорядочили данные.

Что важно знать про sorted и list.sort

sorted(a) возвращает новый список

a.sort() сортирует список на месте и возвращает None

обе сортировки в Python стабильны (сохраняют порядок равных элементов)

Документация:

Sorting HOW TO

Ключ key=: главный инструмент

На интервью почти всегда ожидают, что вы уверенно применяете key=.

Примеры:

Практический совет:

если у вас сложный компаратор, чаще всего его можно переписать в key= через кортеж

После сортировки часто работают два указателя и жадность

Вспомните из прошлых статей:

два указателя для поиска пар в отсортированном массиве

жадность по правой границе для интервалов

Сортировка часто является «входным билетом» в такие решения.

Частые ошибки

Путают sorted и sort и пытаются писать a = a.sort().

Забывают, что сортировка добавляет .

Пишут key= как дорогую функцию, которая внутри делает сложные операции.

Куча (heapq) как очередь с приоритетом

Куча нужна, когда вы много раз выполняете операции:

добавить элемент

быстро достать минимальный (или максимальный)

В Python это модуль heapq, который реализует минимальную кучу.

Документация: heapq — Heap queue algorithm

!Иллюстрация свойства минимальной кучи и связи с хранением в массиве

Базовые операции

heapq.heappush(h, x)

heapq.heappop(h)

h[0] — текущий минимум (без извлечения)

Сложности (как обычно проговаривают на интервью):

вставка и извлечение:

просмотр минимума:

Как сделать максимальную кучу

Вариант по умолчанию:

хранить числа с минусом

На интервью важно сказать вслух:

В Python heapq — min-heap, поэтому для max-heap инвертируем знак.

Топ-k элементов потока

Если нужно поддерживать k самых больших элементов:

держим min-heap размера k

если пришёл элемент больше минимума, заменяем

Что проговорить:

Куча хранит текущие k лучших, минимальный среди них лежит в корне.

Каждый элемент обрабатывается за , итог .

Слияние k отсортированных списков

Типовой приём:

кладём в кучу первый элемент каждого списка вместе с указателями

каждый раз достаём минимум и добавляем следующий из того же списка

Сложность:

, где — общее число элементов, — число списков

Продвинутая практика: как узнавать эти паттерны в задачах

Ниже — компактные «сигналы», по которым на интервью быстро выбирают инструмент.

Когда почти наверняка нужна сортировка

нужно работать с интервалами или событиями на линии времени

нужно сгруппировать или упорядочить пары/тройки по одному полю

после сортировки становится возможен линейный проход (два указателя, жадность)

Когда почти наверняка нужна куча

«каждый раз взять лучший/минимальный/максимальный среди текущих кандидатов»

«обрабатывать задачи по времени, но выбирать по приоритету»

«поддерживать топ-k на лету»

Когда почти наверняка нужен бинарный поиск по ответу

ответ — число, и вы хотите минимальное возможное или максимальное возможное

вы можете быстро проверить кандидата x функцией ok(x)

ok(x) монотонно

Мини-каркас solve() с быстрым вводом

Частые ошибки на интервью и как их предотвратить

Бинарный поиск без монотонности

1. Если ok(x) не монотонна, бинарный поиск по ответу применять нельзя.

Ошибки границ в бинарном поиске

1. Предпочитайте шаблон с полуинтервалом или чётко фиксируйте, что именно означает l и r.

Использование list.pop(0) вместо deque.popleft() или heapq

1. Для очереди берите deque, для приоритетной очереди — heapq.

Слишком дорогой key=

1. key вызывается много раз; старайтесь, чтобы он был простым.

Неправильное ожидание от кучи

1. Куча не даёт «доступ к максимуму/минимуму среди всех» для произвольных удалений; она оптимальна именно для операций на вершине.

Что дальше

Эти инструменты постоянно комбинируются:

сортировка + два указателя

сортировка + жадность

куча + жадность (выбор лучшего кандидата)

бинарный поиск по ответу + линейная/логарифмическая проверка

Если вы уверенно видите монотонность, умеете сортировать «по правильному ключу» и используете кучу как приоритетную очередь, вы закрываете большой процент задач уровня алгоритмического интервью в Яндекс.