Алгоритмы
64 задач, из них 24 на код с автопроверкой. Условие и варианты ответа открыты всем; проверка, подсказка и разбор — в клубе.
Сложность и стоимость структур данных
- Вставка в начало списка Python внутри цикла: во что превращается сложность
- Проверка вхождения: list против set на большом наборе
- Вложенный цикл с ранним возвратом: лучший и худший случай
- Почему n вызовов append дают линейное, а не квадратичное время
- K наименьших элементов: вернуть их по возрастанию, не сортируя весь список
- Скользящее максимальное окно суммы: посчитать максимум суммы k подряд идущих элементов за один проход
- Стоимость операций: свести журнал команд стека к его финальному состоянию
- Конкатенация строк в цикле: почему профайлер показывает квадратичный рост
Массивы, строки и два указателя
- Два указателя на отсортированном массиве: куда двигать при слишком маленькой сумме
- Что вернёт срез с отрицательным шагом и границами
- Удаление элементов из списка во время итерации по нему
- Проверка палиндрома с пропуском лишних символов: где ломается инвариант цикла
- Подпоследовательность строки: проверить вхождение символов по порядку
- Сжатие отсортированного массива: убрать дубликаты на месте и вернуть длину значимой части
- Самая длинная подстрока без повторов: найти её длину за один проход
- Одновременный перебор пар: как выбрать между сортировкой и хешом на почти отсортированных данных
Хеш-таблицы, словари и множества
- Стоимость подсчёта частот: dict.get против сортировки списка
- Что вернёт словарь при ключах True, 1 и 1.0
- Изменяемый объект как ключ словаря: что произойдёт при попытке
- defaultdict внутри проверки: почему словарь растёт от одних только чтений
- Группировка анаграмм: собрать слова с одинаковым набором букв
- Первое неповторяющееся: найти первый элемент, встречающийся ровно один раз
- Самая длинная последовательность подряд идущих чисел через множество
- Хеш-коллизии и пользовательский класс: почему объекты пропали из множества
Сортировка и бинарный поиск
- sorted с key: как отсортировать словари по двум полям в разных направлениях
- Что вернёт bisect_left на массиве с повторами
- Устойчивость сортировки: что она гарантирует на практике
- Бинарный поиск с рекурсивным вызовом и срезами: где спрятана линейная стоимость
- Бинарный поиск по ответу: минимальная грузоподъёмность, чтобы уложиться в k рейсов
- Вставить значение в отсортированный список, сохранив порядок и вернув позицию
- Слияние отсортированных интервалов после сортировки по левой границе
- Сортировка по ключу против cmp_to_key: где решение проседает по времени
Стек, очередь и куча
- Очередь на обычном list: во что превращается pop(0) на 200 тысячах элементов
- Что напечатает h[0] и h[-1] после серии heappush
- Обратная польская запись: что посчитает стек на выражении 5 1 2 + 4 * + 3 -
- Десять максимумов из двух миллионов чисел: чем nlargest отличается от sorted
- is_balanced: проверка правильной вложенности скобок трёх видов
- k_smallest: k наименьших элементов без порчи исходного списка
- Очередь на двух стеках: почему дорогой pop не делает алгоритм квадратичным
- next_greater: ближайший справа строго больший элемент за один проход
Рекурсия и динамическое программирование
- Наивная рекурсия Фибоначчи: откуда берётся экспонента
- lru_cache над функцией, которой передают список
- Рекурсивная сумма работает на 500 элементах и падает на 5000
- Размен монетами: почему порядок вложенных циклов меняет ответ
- climb_stairs: число способов подняться шагами 1 и 2
- max_subarray_sum: максимальная сумма непустого подотрезка
- Рюкзак 0/1 на одномерном массиве: почему предмет берётся дважды
- min_coins: минимальное число монет на сумму, -1 если размен невозможен
Графы и обходы
- DFS вместо BFS: почему путь получается длиннее минимального
- BFS с пометкой посещения при извлечении: что именно ломается
- В каком порядке BFS обойдёт вершины этого графа
- Дейкстра на графе с одним отрицательным ребром
- count_components: число компонент связности неориентированного графа
- shortest_path_len: кратчайшее расстояние в рёбрах обходом в ширину
- Кратчайший путь в графе с весами 0 и 1: чем обычный BFS здесь плох
- has_cycle: есть ли ориентированный цикл в графе зависимостей
Жадные алгоритмы и интервалы
- Максимум непересекающихся встреч: по какому полю сортировать
- Жадность по удельной ценности: где она оптимальна, а где нет
- Как одним условием проверить, что два интервала пересекаются
- Достижим ли конец списка прыжками: что даёт жадность
- merge_intervals: слияние пересекающихся и касающихся отрезков
- min_rooms: сколько переговорок нужно, чтобы развести все встречи
- Заметание прямой: почему можно разрывать пары «начало-конец»
- erase_overlap_count: минимум удалений, чтобы интервалы перестали пересекаться