Алгоритмы
Сложность, сортировка, поиск, строковые и графовые алгоритмы, алгоритмы STL и распространённые структуры данных.
101 вопросов
JuniorКодОчень частоПроверьте, является ли бинарное дерево сбалансированным
Проверьте, является ли бинарное дерево сбалансированным
В каждом узле высоты левого и правого поддеревьев отличаются не больше чем на 1. Оптимальный O(n) DFS возвращает высоту поддерева либо −1 как sentinel для «несбалансировано», совмещая вычисление высоты и проверку баланса в одном проходе.
Открыть задачу →Типичные ошибки
- ✗Использовать подход O(n²) с отдельной функцией высоты, вызываемой в каждом узле
- ✗Проверять только детей корня, не рекурсивно каждый узел
- ✗Не возвращать sentinel-значение — возврат просто bool теряет информацию о высоте, нужную родителю
Уточняющие вопросы
- →Что такое AVL-дерево и как оно поддерживает баланс при вставках?
- →В чём разница между деревьями, сбалансированными по высоте и по весу?
JuniorКодОчень частоРеализуйте бинарный поиск в массиве
Реализуйте бинарный поиск в массиве
Бинарный поиск работает на отсортированном диапазоне, последовательно уменьшая пространство поиска вдвое. Поддерживаются левая и правая границы; средний элемент сравнивается с целевым; граница сдвигается в сторону цели. Время O(log n), память O(1).
Открыть задачу →Типичные ошибки
- ✗Переполнение целого в
mid = (low + high) / 2при больших low и high — используйтеlow + (high - low) / 2 - ✗Ошибка на единицу в условии цикла:
while (low < high)vswhile (low <= high)меняет семантику - ✗Не проверять, что массив отсортирован — бинарный поиск на несортированных данных даёт неверный результат
Уточняющие вопросы
- →Чем
std::lower_boundотличается отstd::binary_search? - →Как расширить бинарный поиск для нахождения самого левого / самого правого вхождения значения?
JuniorКодОчень частоРекурсивный поиск значения в дереве бинарного поиска
Рекурсивный поиск значения в дереве бинарного поиска
В BST левое поддерево узла содержит меньшие значения, правое — большие. Рекурсивно: пусто → nullptr; равно → вернуть; меньше → влево; иначе вправо. Время O(h): O(log n) при балансе, O(n) в худшем случае.
Открыть задачу →Типичные ошибки
- ✗Не проверять nullptr перед обращением к node->val
- ✗Использовать полный обход дерева вместо свойства BST для отсечения ветвей
- ✗Забывать, что гарантии BST распространяются на значения, а не на структурный баланс
Уточняющие вопросы
- →Как вставить и удалить узел в BST?
- →Что такое AVL-дерево или красно-чёрное дерево и почему они гарантируют O(log n)?
JuniorТеорияОчень частоЧто такое сложность алгоритма (нотация O-большое)?
Что такое сложность алгоритма (нотация O-большое)?
Big-O описывает рост времени выполнения или памяти в худшем случае относительно размера входа n, игнорируя константы. Типовые классы: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ); та же нотация применяется к пространственной сложности.
Типичные ошибки
- ✗Путать худший случай (O), средний случай (Θ) и лучший случай (Ω) — на собеседованиях обычно ожидается худший случай
- ✗Игнорировать константные коэффициенты, которые важны на практике: O(n) с большой константой может быть медленнее O(n²) при малом n
- ✗Забывать про пространственную сложность — рекурсивные алгоритмы часто обменивают время на память стека
Уточняющие вопросы
- →Что такое амортизированная сложность? Приведите пример
std::vector::push_back. - →Почему O(n log n) считается оптимальным для сортировки, основанной на сравнениях?
JuniorКодОчень частоПосчитайте количество единиц (set bits) в числе
Посчитайте количество единиц (set bits) в числе
Трюк Кернигана: n &= n - 1 сбрасывает младший установленный бит, повторяем до n == 0 — O(k), где k — количество единиц. В C++20 лучше std::popcount, компилируется в одну инструкцию.
Типичные ошибки
- ✗Использовать наивный побитовый цикл O(32) вместо трюка Кернигана O(set bits)
- ✗Некорректно обрабатывать отрицательные числа при знаковом int — используйте unsigned
- ✗Забывать о
std::popcountв C++20, который делает задачу однострочной
Уточняющие вопросы
- →Как проверить, является ли число степенью двойки, используя побитовые операции?
- →Что делает
n & (n-1)в общем случае?
JuniorКодОчень частоРеализуйте подсчёт чисел Фибоначчи
Реализуйте подсчёт чисел Фибоначчи
Наивная рекурсия — O(2ⁿ), катастрофически медленно. Итеративный подход снизу вверх использует две переменные и работает за O(n) времени и O(1) памяти. Мемоизация сверху вниз — тоже O(n), но O(n) памяти. Возведение матрицы в степень даёт O(log n).
Открыть задачу →Типичные ошибки
- ✗Писать наивную рекурсию без мемоизации — fib(40) уже занимает секунды
- ✗Переполнение при больших n — явно используйте
uint64_tили__int128; fib(93) — последнее значение, умещающееся в uint64_t - ✗Ошибка на единицу в базовом случае: fib(0)=0, fib(1)=1, fib(2)=1
Уточняющие вопросы
- →Как возведение матрицы в степень вычисляет Фибоначчи за O(log n)?
- →Как вычислить fib(n) mod M для очень большого n?
JuniorКодОчень частоНайдите уникальный элемент в массиве, где все остальные встречаются дважды
Найдите уникальный элемент в массиве, где все остальные встречаются дважды
Применить XOR ко всем элементам. Пары взаимно уничтожаются (a XOR a = 0), в результате остаётся единственный непарный элемент. Время O(n), память O(1), один проход.
Открыть задачу →Типичные ошибки
- ✗Использовать хеш-таблицу — O(n) память излишня, когда XOR даёт O(1)
- ✗Сортировать массив — O(n log n) и изменяет входные данные
- ✗Не обобщать: это работает только когда ровно один элемент встречается нечётное число раз
Уточняющие вопросы
- →Как найти два уникальных элемента, когда все остальные встречаются дважды?
- →Как найти уникальный элемент, когда все остальные встречаются трижды?
JuniorКодОчень частоДля структуры типа односвязный список напишите функцию вставки элемента
Для структуры типа односвязный список напишите функцию вставки элемента
Вставка в голову — O(1): новый узел, его next → старая голова, обновить голову. На позицию k — O(k): дойти до предшественника. В хвост без tail-указателя — O(n).
Открыть задачу →Типичные ошибки
- ✗Забывать отдельно обрабатывать вставку на позицию 0 (голова)
- ✗Пройти на один узел дальше — нужен узел перед точкой вставки, а не на ней
- ✗Не обновлять указатель на голову при вставке на позицию 0
Уточняющие вопросы
- →Как вставить элемент в уже отсортированный список с сохранением порядка?
- →Какова сложность построения отсортированного списка последовательными вставками в порядке?
JuniorКодОчень частоДлина наибольшей подстроки без повторяющихся символов
Длина наибольшей подстроки без повторяющихся символов
Двигайте окно с указателем left и таблицей последнего индекса каждого символа. Для каждого right, если символ виден на позиции >= left, сдвиньте left на одну позицию после него. Текущая длина окна — right - left + 1; отслеживайте максимум. Один проход, O(n) время.
Типичные ошибки
- ✗Сдвигать
leftнаlastSeen+1, даже когдаlastSeenдо текущего окна, ошибочно его сужая - ✗Сбрасывать окно с нуля на повторе, вырождаясь в O(n²)
- ✗Путать число различных символов с наибольшей подстрокой без дубликатов
Уточняющие вопросы
- →Почему
leftдолжен двигаться только вперёд и никогда назад? - →Как вернуть саму подстроку, а не только её длину?
JuniorКодОчень частоНапишите функцию для определения, является ли слово палиндромом
Напишите функцию для определения, является ли слово палиндромом
Используйте два указателя с обоих концов, движущихся к центру. Сравниваем символы; если они различаются — строка не является палиндромом. Время O(n), память O(1).
Открыть задачу →Типичные ошибки
- ✗Разворачивать всю строку и сравнивать — излишне выделяет O(n) дополнительной памяти
- ✗Не учитывать регистр или неалфавитно-цифровые символы для реальных входных данных
- ✗Использовать знаковую арифметику индексов, которая может уйти в отрицательные значения при пустой строке
Уточняющие вопросы
- →Как проверить, является ли связный список палиндромом?
- →Что такое задача нахождения наидлиннейшей палиндромной подстроки и какой алгоритм эффективно её решает?
JuniorКодОчень частоНапишите функцию, которая разворачивает односвязный список
Напишите функцию, которая разворачивает односвязный список
Используйте три указателя: prev (изначально nullptr), curr и next. На каждом шаге: сохраните next, направьте curr->next на prev, продвиньте prev к curr, продвиньте curr к сохранённому next. Когда curr равен nullptr, prev — новая голова. Время O(n), память O(1).
Открыть задачу →Типичные ошибки
- ✗Потерять следующий узел до перезаписи curr->next — всегда сохраняйте
next = curr->nextпервым - ✗Возвращать curr вместо prev в конце — curr равен nullptr при выходе из цикла
- ✗Не обрабатывать крайние случаи: пустой список или список из одного элемента
Уточняющие вопросы
- →Как развернуть двусвязный список?
- →Как развернуть только подотрезок [m, n] связного списка?
JuniorКодОчень частоРеализуйте реверс строки
Реализуйте реверс строки
Используйте два индекса (или итератора) с обоих концов и меняйте символы местами к центру. O(n) времени, O(1) памяти in-place. std::reverse из <algorithm> делает то же в одну строку.
Типичные ошибки
- ✗Возвращать новую обращённую строку, когда требуется in-place (тратит O(n) памяти)
- ✗Не обрабатывать крайние случаи: пустая строка или строка из одного символа
- ✗Наивный реверс UTF-8 строк — нужно работать с codepoints, а не байтами
Уточняющие вопросы
- →Как перевернуть слова в предложении, не переворачивая символы внутри каждого слова?
- →Как правильно обратить строку в кодировке UTF-8?
JuniorКодОчень частоРеализуйте любую сортировку
Реализуйте любую сортировку
Quicksort: среднее O(n log n), in-place, нестабильная, деградирует до O(n²) при неудачном опорном — используйте медиану трёх или случайный пивот. Merge sort: гарантированное O(n log n), стабильная, требует O(n) доп. памяти.
Открыть задачу →Типичные ошибки
- ✗Всегда выбирать первый элемент как опорный — O(n²) на отсортированном входе
- ✗Не обрабатывать базовый случай (массив размера 0 или 1)
- ✗Путать стабильность merge sort со свойством in-place у quicksort
Уточняющие вопросы
- →Что такое introsort и почему
std::sortиспользует его вместо чистого quicksort? - →Когда следует предпочесть merge sort перед quicksort?
JuniorТеорияОчень частоЧто такое алгоритмы сортировки и какие вы знаете?
Что такое алгоритмы сортировки и какие вы знаете?
Алгоритмы сортировки упорядочивают коллекцию. Ключевые: пузырьковая, выбором и вставками — O(n²); слиянием — O(n log n) и стабильна; быстрая — O(n log n) в среднем / O(n²) в худшем; пирамидальная — O(n log n). std::sort использует introsort (гибрид быстрой, пирамидальной и вставками) ради гарантированного O(n log n).
Типичные ошибки
- ✗Выбирать пузырьковую сортировку для реальных задач — она полезна только в учебных целях
- ✗Не знать, что быстрая сортировка деградирует до O(n²) на уже отсортированных данных без хорошей стратегии выбора опорного элемента
- ✗Забывать, что стабильная сортировка сохраняет относительный порядок равных элементов — важно при сортировке по вторичному ключу
Уточняющие вопросы
- →В чём разница между
std::sortиstd::stable_sort? - →Когда стоит использовать поразрядную или сортировку подсчётом вместо сортировки на основе сравнений?
JuniorТеорияОчень частоОбъясните структуры данных стек и очередь.
Объясните структуры данных стек и очередь.
Стек — структура LIFO: push добавляет элемент на вершину, pop удаляет с вершины. Очередь — FIFO: enqueue добавляет в конец, dequeue удаляет из начала. В C++ std::stack и std::queue — адаптеры контейнеров, обычно реализованные поверх std::deque.
Типичные ошибки
- ✗Путать переполнение стека (stack overflow) со структурой данных стек — stack overflow — это ошибка времени выполнения стека вызовов
- ✗Использовать
std::stackилиstd::queue, когда нужна итерация — у них нет итераторов; используйтеstd::dequeилиstd::listнапрямую - ✗Забывать, что
std::queue::front()иback()— O(1), ноstd::stackпредоставляет толькоtop()
Уточняющие вопросы
- →Как реализовать стек, поддерживающий
min()за O(1)? - →Когда стоит использовать кольцевой буфер вместо очереди на основе deque?
JuniorКодОчень частоПроверка симметричности бинарного дерева
Проверка симметричности бинарного дерева
Симметрия — зеркальное свойство двух поддеревьев, а не одного узла. Рекурсивно сравнивайте left с right: два узла зеркальны тогда и только тогда, когда их значения равны и left.l зеркален right.r, а left.r зеркален right.l. Оба null — симметрично; один null — нет. Пустое дерево симметрично. O(n) время.
Типичные ошибки
- ✗Сравнивать двух детей одного узла вместо зеркалирования между двумя поддеревьями
- ✗Считать «один null, один есть» совпадением вместо отказа
- ✗Полагаться на палиндром обхода, который проходит и для несимметричных деревьев
Уточняющие вопросы
- →Почему сравнения собственных левого и правого детей узла недостаточно?
- →Как написать это итеративно с очередью?
JuniorТеорияОчень частоЧто такое pre-, in-, post-order и level-order обходы и когда их применять?
Что такое pre-, in-, post-order и level-order обходы и когда их применять?
Pre-order (root, left, right): копирование или сериализация дерева. In-order (left, root, right): на BST даёт отсортированный порядок. Post-order (left, right, root): удаление дерева или вычисление выражения. Level-order (BFS): через очередь, печать по уровням.
Типичные ошибки
- ✗Применять in-order к не-BST и ждать отсортированного вывода
- ✗Реализовать итеративный post-order без двух стеков (или флага visited)
- ✗Путать pre-order и DFS по глубине — pre-order это один из DFS
Уточняющие вопросы
- →Как сериализовать/десериализовать бинарное дерево?
- →Что такое Morris traversal и когда полезен?
MiddleТеорияОчень частоКогда использовать BFS, а когда DFS для обхода графа?
Когда использовать BFS, а когда DFS для обхода графа?
BFS (очередь) обходит по уровням — лучший для кратчайшего пути в невзвешенном графе. DFS (стек/рекурсия) идёт вглубь по веткам — естественен для топосортировки, поиска циклов и SCC. Оба O(V+E); BFS — O(V) памяти, DFS — O(h).
Типичные ошибки
- ✗Использовать DFS для кратчайшего невзвешенного пути — найдёт какой-то путь, не кратчайший
- ✗Забыть пометку visited и зациклиться в графе с циклами
- ✗Глубокая рекурсия DFS — stack overflow
Уточняющие вопросы
- →Как найти кратчайший путь во взвешенном графе (Dijkstra)?
- →Когда итеративный DFS лучше рекурсивного на практике?
MiddleТеорияОчень частоЧто такое нотация O-большое и как определить сложность алгоритма?
Что такое нотация O-большое и как определить сложность алгоритма?
O-большое — асимптотическая верхняя граница роста. Считают доминирующие операции от n, отбрасывают младшие члены и константы; вложенные циклы перемножают, независимые складывают; для рекурсии — Мастер-теорема.
Типичные ошибки
- ✗Забывать, что O-большое описывает только скорость роста, а не реальную скорость — O(n) может быть медленнее O(n²) при малом n
- ✗Не распознавать паттерны O(log n): бинарный поиск, операции с BST, высота сбалансированного дерева
- ✗Считать операции с хеш-таблицей всегда O(1) — в худшем случае они O(n) из-за коллизий
Уточняющие вопросы
- →Объясните Мастер-теорему и когда она применима к рекуррентным соотношениям.
- →В чём разница между нотациями O, Ω (Омега) и Θ (Тета)?
MiddleКодОчень частоНайдите зацикливание в односвязном списке
Найдите зацикливание в односвязном списке
Алгоритм Флойда (черепаха и заяц) использует два указателя от головы, движущихся с разной скоростью: медленный — на 1 шаг за итерацию, быстрый — на 2; если они встретились внутри списка, цикл есть, а если быстрый дошёл до nullptr — цикла нет. Время O(n), память O(1).
Открыть задачу →Типичные ошибки
- ✗Использовать хеш-множество для отслеживания посещённых узлов — O(n) память, не нужна с алгоритмом Флойда
- ✗Не проверять
fast && fast->nextперед продвижением — приводит к разыменованию nullptr - ✗Останавливаться на fast == nullptr, но не проверять fast->next == nullptr (нужно для списков чётной длины)
Уточняющие вопросы
- →Как найти начало цикла после его обнаружения?
- →Как найти длину цикла?
MiddleКодОчень частоTwo Sum: индексы двух чисел с суммой, равной цели
Two Sum: индексы двух чисел с суммой, равной цели
Используйте хеш-таблицу «значение → индекс». Для каждого элемента проверяйте, есть ли target - nums[i] уже в таблице; если да — верните оба индекса. Иначе вставьте nums[i] → i. Один проход, O(n) время и O(n) память — против перебора двойным циклом за O(n²).
Типичные ошибки
- ✗Возвращать сами значения вместо их индексов
- ✗Использовать один и тот же элемент дважды для пары
- ✗Соглашаться на двойной цикл за O(n²), когда ожидается O(n)
Уточняющие вопросы
- →Как бы вы изменили решение, если массив уже отсортирован?
- →Что меняется, если допустимых пар может быть несколько или ни одной?
JuniorКодЧастоРеализуйте функцию int atoi(const char* str)
Реализуйте функцию int atoi(const char* str)
Пропустить пробелы, обработать знак, накапливать цифры: result = result * 10 + digit. Учесть переполнение (clamp до INT_MIN/INT_MAX) и остановиться на первом нецифровом символе.
Типичные ошибки
- ✗Не пропускать ведущие пробелы (стандартный
atoiих игнорирует) - ✗Переполнение целого при накоплении — проверяйте до умножения
- ✗Некорректно обрабатывать знак минус: '-' перед цифрами устанавливает флаг
Уточняющие вопросы
- →В чём разница между
atoi,strtol,std::stoiиstd::from_chars? - →Чем
std::from_charsотличается отstd::stoiв плане обработки ошибок?
JuniorКодЧастоПодсчёт левых листьев бинарного дерева
Подсчёт левых листьев бинарного дерева
Свойство «левый лист» нельзя решить по одному узлу — оно зависит от родителя. Рекурсируйте, передавая флаг isLeft: узел считается, когда он лист (без детей) и isLeft истинно. Рекурсия в left с isLeft = true, в right с isLeft = false. Корню передаётся isLeft = false. O(n) время.
Типичные ошибки
- ✗Считать все листья независимо от того, левые ли они дети
- ✗Пытаться решить «левость» по самому узлу, а не по контексту родителя
- ✗Считать корень дерева из одного узла левым листом
Уточняющие вопросы
- →Почему узел не может сам решить, что он левый лист?
- →Как вместо этого просуммировать значения левых листьев?
JuniorКодЧастоИндекс равновесия, где сумма слева равна сумме справа
Индекс равновесия, где сумма слева равна сумме справа
Сначала посчитайте общую сумму. Затем за один проход ведите текущую левую сумму; на индексе i правая сумма равна total - left - a[i]. Когда left == total - left - a[i], верните i. Один проход после подсчёта суммы — O(n) время и O(1) дополнительной памяти. Верните -1, если совпадений нет.
Типичные ошибки
- ✗Пересчитывать правую сумму с нуля на каждом индексе, получая O(n²)
- ✗Забывать, что
a[i]не относится ни к одной стороне, и неверно выводить правую сумму - ✗Не обрабатывать пустой массив или возвращать неверное значение-маркер, когда баланса нет
Уточняющие вопросы
- →Почему вычитание
a[i]из общей суммы даёт ровно сумму правой стороны? - →Как найти все индексы равновесия, а не только первый?
JuniorКодЧастоИндекс первого неповторяющегося символа
Индекс первого неповторяющегося символа
Первый проход: посчитайте вхождения каждого символа в хеш-таблице (или массиве фиксированного размера для известного алфавита). Второй проход: идите по строке слева направо и верните индекс первого символа со счётчиком 1. Верните -1, если такого нет. O(n) время.
Типичные ошибки
- ✗Повторно сканировать строку на каждый символ, вырождаясь в O(n²)
- ✗Возвращать первую запись со счётчиком 1 из неупорядоченной таблицы, теряя исходный порядок
- ✗Путать «ещё не встречался» с «встречается ровно один раз»
Уточняющие вопросы
- →Почему второй проход должен идти по строке, а не по таблице?
- →Как сделать это за один проход, если хранить ещё и индекс каждого символа?
JuniorКодЧастоВариант FizzBuzz: Foo для /2, Bar для /3, Buzz для /6
Вариант FizzBuzz: Foo для /2, Bar для /3, Buzz для /6
Цикл i от 1 до n, заводим пустую строку, дописываем Foo при i % 2 == 0, Bar при i % 3 == 0, Buzz при i % 6 == 0. Если строка осталась пустой — печатаем i, иначе печатаем строку. Поскольку правила дописывают, число, кратное 6, даёт FooBarBuzz.
Типичные ошибки
- ✗Использовать else-if, из-за чего значение получает только одну метку вместо дописывания всех подходящих
- ✗Не уточнить, печатает ли кратное 6 «FooBarBuzz» или только «Buzz»
- ✗Забыть напечатать число, когда ни одно правило не подошло
Уточняющие вопросы
- →Как переписать без явного цикла, через функциональный map?
- →Почему правило
% 6избыточно, если% 2и% 3уже дописывают?
JuniorТеорияЧастоКакие алгоритмы на графах вы знаете?
Какие алгоритмы на графах вы знаете?
Основные алгоритмы на графах: BFS (кратчайший путь в невзвешенных графах, O(V+E)), DFS (поиск циклов, топосортировка, O(V+E)), Дейкстра (кратчайший путь с неотрицательными весами, O((V+E) log V)), Беллман–Форд (отрицательные рёбра, O(VE)), Флойд–Уоршелл (все пары, O(V³)), Краскал/Прим для MST.
Типичные ошибки
- ✗Применять Дейкстру на графах с отрицательными рёбрами — результат будет неверным; используйте Беллман–Форд
- ✗Забывать отмечать посещённые вершины в BFS/DFS, что приводит к бесконечным циклам на циклических графах
- ✗Путать топологическую сортировку с BFS — топологическая сортировка использует DFS или алгоритм Кана (на основе BFS) и применима только к DAG
Уточняющие вопросы
- →Как обнаружить цикл в ориентированном графе? В неориентированном?
- →В чём разница между деревом, DAG и общим графом?
JuniorКодЧастоОпределите, является ли год високосным
Определите, является ли год високосным
Год високосный, если делится на 4, кроме вековых (делится на 100), если только он не делится также на 400. 2000 — да, 1900 — нет, 2024 — да.
Открыть задачу →Типичные ошибки
- ✗Проверять только
year % 4 == 0, забывая исключение для вековых лет - ✗Писать вложенные if, делающие логику трудночитаемой, вместо одного булевого выражения
- ✗Не обрабатывать год 0 или отрицательные года, если API их принимает
Уточняющие вопросы
- →Каково правило Григорианского календаря и почему оно было введено?
- →Как работает
std::chrono::year::is_leap()в C++20?
JuniorКодЧастоУдалите из unordered_map элементы, которые делятся на 2, и выведите ключи этих элементов
Удалите из unordered_map элементы, которые делятся на 2, и выведите ключи этих элементов
Нельзя удалять элементы из контейнера, итерируя его с range-for — это инвалидирует итератор. Безопасные подходы: собрать ключи для удаления, затем удалить отдельным проходом; или использовать std::erase_if (C++20), который делает это аккуратно.
Типичные ошибки
- ✗Удалять элементы внутри range-for — неопределённое поведение из-за инвалидации итератора
- ✗Использовать
map.erase(it)без сохранения возвращённого итератора на следующий элемент в ручном цикле - ✗Не знать о
std::erase_if(C++20) — самое чистое решение
Уточняющие вопросы
- →Что такое инвалидация итератора и какие контейнеры наиболее/наименее подвержены ей?
- →Как
eraseвозвращает следующий допустимый итератор в большинстве контейнеров?
JuniorКодЧастоМаксимальное число подряд повторений для каждого символа
Максимальное число подряд повторений для каждого символа
Идите по строке, отслеживая текущий символ и длину его серии. Когда символ меняется, обновите записанный максимум этого символа в таблице, если только что завершённая серия длиннее, затем начните новую серию длины 1. После цикла выведите последнюю серию. Один проход, O(n) время.
Открыть задачу →Типичные ошибки
- ✗Выводить общую частоту вместо наибольшей непрерывной серии
- ✗Забывать вывести последнюю серию после окончания цикла
- ✗Сворачивать регистр, когда по условию надо учитывать его (или наоборот)
Уточняющие вопросы
- →Почему сортировка ломает ответ для чередующегося символа вроде
aba? - →Как сохранить ключи вывода в порядке первого появления, а не отсортированными?
JuniorДебаггингЧастоИсправьте счётчик длиннейшей серии единиц, теряющий последнюю серию
Исправьте счётчик длиннейшей серии единиц, теряющий последнюю серию
best обновляется только в ветке else (на нуле), поэтому хвостовая серия 1, не встретившая ноль, не сравнивается. Исправьте, обновляя best = max(best, cur) на каждой 1 (внутри if) или ещё раз после цикла. O(n).
Типичные ошибки
- ✗Считать счётчик верным, ведь он работает для массивов, кончающихся на 0
- ✗Обновлять максимум лишь на границах серий, отмеченных нулём
- ✗Добавить проверку после цикла, но забыть про пустой массив
Уточняющие вопросы
- →Как изменится исправление, если нужно вернуть и индекс начала серии?
- →Какой аналогичный баг для длиннейшей серии любого фиксированного значения?
JuniorКодЧастоМинимальное произведение любой пары элементов массива
Минимальное произведение любой пары элементов массива
Отслеживайте два наименьших и два наибольших значения за один проход. Кандидаты на минимум — min1*min2, max1*max2 (два больших отрицательных дают малое произведение) и min1*max1 при смешанных знаках; сравните их и возьмите наименьший. O(n) время, O(1) память; следите за переполнением, используя long long.
Типичные ошибки
- ✗Рассматривать только два наименьших, упуская случай двух больших отрицательных
- ✗Переполнять
intпри умножении двух значений большого модуля - ✗Сортировать (O(n log n)), когда ожидается проход за O(n)
Уточняющие вопросы
- →Почему два больших отрицательных числа никогда не дают минимальное произведение?
- →Как меняется ответ для максимального произведения?
JuniorКодЧастоНормализация Unix-пути (точки, .. и //)
Нормализация Unix-пути (точки, .. и //)
Разбейте путь по /. Кладите каждый компонент в стек; пропускайте пустые (из //) и .; на .. извлекайте из стека, если он непуст (подъём выше корня игнорируется). В конце соедините стек через / с ведущим /. Один проход, O(n) время.
Типичные ошибки
- ✗Извлекать из стека на
.., когда он уже пуст (подъём выше корня) - ✗Забывать, что подряд идущие слеши дают пустые компоненты, которые надо пропустить
- ✗Посимвольные правки, неверно обрабатывающие
.., чей родитель из многих символов
Уточняющие вопросы
- →Почему разбивать на компоненты, а не править сырую строку символов?
- →Как относительные пути (без ведущего слеша) изменят правило
..выше корня?
JuniorКодЧастоСхлопывание серий пробелов в один пробел на месте
Схлопывание серий пробелов в один пробел на месте
Используйте индексы чтения и записи. Копируйте каждый символ в позицию записи, но пишите пробел, только если предыдущий записанный символ не был пробелом. После прохода усеките строку до индекса записи. Один проход, O(n) время, O(1) дополнительной памяти; одиночные пробелы в начале и в конце сохраняются.
Открыть задачу →Типичные ошибки
- ✗Обрезать пробелы в начале или конце, когда по условию надо только схлопывать серии
- ✗Забывать усечь строку, оставляя устаревшие символы в хвосте
- ✗Вызывать
eraseна каждый лишний пробел, превращая O(n) в O(n²)
Уточняющие вопросы
- →Как одиночный конечный пробел сохраняется, если вход заканчивается несколькими?
- →Что меняется, если нужно ещё и обрезать концы?
JuniorКодЧастоПроверка строк на расстояние в одно редактирование
Проверка строк на расстояние в одно редактирование
Если длины различаются больше чем на 1, верните false. Если равны, посчитайте несовпадения символов и допустите не более одного. Если различаются на 1, идите двумя указателями, разрешив ровно один пропуск в длинной строке; любое второе несовпадение — отказ. Один проход, O(n) время, O(1) память.
Типичные ошибки
- ✗Обрабатывать случаи равной длины и разницы в один одинаково, ошибаясь с пропуском при вставке/удалении
- ✗Забывать сразу отвергнуть, когда длины различаются больше чем на один
- ✗Допускать второе несовпадение после единственного разрешённого редактирования
Уточняющие вопросы
- →Почему разница длин больше одного позволяет вернуть результат сразу?
- →Как пропуск двух указателей моделирует вставку против удаления?
JuniorКодЧастоУдаление нулей из вектора с сохранением порядка за O(n)
Удаление нулей из вектора с сохранением порядка за O(n)
Используйте индекс записи. Идите по вектору индексом чтения; для каждого ненулевого элемента копируйте его в позицию записи и продвигайте индекс записи. После прохода усеките вектор до индекса записи. Один проход, O(n) время, O(1) дополнительной памяти. Идиоматичная форма — erase-remove: v.erase(std::remove(v.begin(), v.end(), 0), v.end()).
Типичные ошибки
- ✗Вызывать
eraseна каждый ноль, сдвигая хвост каждый раз и вырождаясь в O(n²) - ✗Обмен с концом, который удаляет нули, но ломает порядок оставшихся элементов
- ✗Забывать усечь/erase оставшийся хвост после уплотнения
Уточняющие вопросы
- →Что
std::removeна самом деле делает с хвостом и почемуeraseвсё ещё нужен? - →Как вместо этого перенести все нули в конец, сохранив порядок ненулевых?
JuniorКодЧастоРазворот символов каждого слова с сохранением порядка слов
Разворот символов каждого слова с сохранением порядка слов
Идите по строке; в начале каждой максимальной непробельной серии найдите её конец, затем разверните эту серию на месте двумя указателями, меняя символы навстречу. Пробелы пропускаются и не трогаются, поэтому все пробелы сохраняются. Один проход, O(n) время, O(1) дополнительной памяти.
Открыть задачу →Типичные ошибки
- ✗Нормализовать или схлопывать пробелы, когда по условию их надо сохранить точно
- ✗Разворачивать через пробелы, сливая соседние слова
- ✗Выделять новый буфер, когда ожидается решение на месте с O(1) памяти
Уточняющие вопросы
- →Как сохранить двойные пробелы, разворачивая только символы слов?
- →Как ещё и развернуть порядок самих слов?
JuniorКодЧастоРазвернуть порядок слов, не меняя положения пробелов
Развернуть порядок слов, не меняя положения пробелов
Соберите слова по порядку. Затем идите по исходной строке: пробелы копируйте без изменений, а в каждую максимальную непробельную серию вставляйте следующее слово, взятое с КОНЦА списка слов. Пробелы остаются на местах; разворачиваются только слова. O(n).
Открыть задачу →Типичные ошибки
- ✗Нормализовать пробелы (классический разворот слов) вместо сохранения точного шаблона
- ✗Неверно обработать пробелы в начале или конце
- ✗Ломаться на строке только из пробелов или вовсе без пробелов
Уточняющие вопросы
- →Почему классический split-и-join не подходит для этого варианта?
- →Как сделать это на месте, без лишней аллокации?
JuniorКодЧастоRLE-сжатие строки A-Z без счётчика для одиночных символов
RLE-сжатие строки A-Z без счётчика для одиночных символов
Пройдите строку один раз, отслеживая текущий символ и длину его серии. Когда следующий символ отличается, выведите символ, добавьте счётчик только если серия больше одного, затем сбросьте. После цикла выведите последнюю группу. Проверяйте, что каждый символ — A-Z, иначе бросайте ошибку. O(n) время.
Типичные ошибки
- ✗Забывать вывести последнюю серию после окончания цикла
- ✗Добавлять
1для одиночных символов вместо того, чтобы оставлять их без счётчика - ✗Выводить лишь одну цифру многозначного счётчика или пропускать проверку входа
Уточняющие вопросы
- →Как декодер отличает цифры счётчика от букв при распаковке?
- →Что изменится, если одиночный символ мог бы законно быть цифрой?
JuniorКодЧастоНайдите элементы двух массивов, которые попадаются только в каждом из них. Используйте STL.
Найдите элементы двух массивов, которые попадаются только в каждом из них. Используйте STL.
Отсортируйте оба массива, затем используйте std::set_symmetric_difference для получения элементов, присутствующих ровно в одном из двух массивов. Альтернатива — вставить один массив в unordered_set и проверять второй — O(n+m) в среднем при O(n) дополнительной памяти.
Типичные ошибки
- ✗Забывать, что
std::set_symmetric_differenceтребует отсортированного входа - ✗Не использовать
std::back_inserterкак выходной итератор - ✗Путать симметрическую разность (ровно в одном) с разностью (в первом, но не во втором)
Уточняющие вопросы
- →Какова временная сложность
std::set_symmetric_difference? - →Как найти пересечение двух массивов с помощью STL?
JuniorКодЧастоКратчайшее расстояние между X и Y в строке
Кратчайшее расстояние между X и Y в строке
Пройдите один раз, храня последний виденный индекс X и Y. На X, если Y уже встречался, обновляйте минимум через i - lastY; на Y симметрично через i - lastX. Если одна из букв не встретилась, верните 0. Один проход, O(n) время, O(1) память.
Типичные ошибки
- ✗Обновлять только
lastXи неlastY(или наоборот), пропуская пары в одну сторону - ✗Возвращать устаревшее большое значение-маркер, когда одна из букв не встретилась, вместо 0
- ✗Считать расстояние только от первого вхождения, а не от ближайшего
Уточняющие вопросы
- →Почему достаточно хранить только последний виденный индекс каждой буквы?
- →Как расширить это до кратчайшего расстояния между любыми двумя из K букв?
JuniorКодЧастоОтсортированные квадраты отсортированного массива за O(n)
Отсортированные квадраты отсортированного массива за O(n)
Два указателя по обоим концам: наибольший квадрат — на одном из концов, так как вход отсортирован. Сравнивайте abs(nums[left]) и abs(nums[right]), записывайте больший квадрат в результат с конца и двигайте этот указатель внутрь. Один проход, O(n) время и O(n) память.
Типичные ошибки
- ✗Возводить в квадрат и сортировать, теряя оценку O(n), которую даёт метод двух указателей
- ✗Считать квадраты уже отсортированными, раз вход был отсортирован, — неверно при наличии отрицательных
- ✗Заполнять результат с начала, а не с конца, из-за чего большие квадраты попадают не в те ячейки
Уточняющие вопросы
- →Где именно находится наибольший квадрат до начала прохода и почему?
- →Как изменился бы подход, если бы вход вообще не был отсортирован?
JuniorТеорияЧастоКакие алгоритмы STL вы применяли? В чём преимущество перед собственноручно написанными функциями?
Какие алгоритмы STL вы применяли? В чём преимущество перед собственноручно написанными функциями?
Частые: std::sort, find/find_if, transform, for_each, accumulate, copy, remove_if, unique, lower_bound/upper_bound, count_if. Плюсы перед ручными циклами: намерение выражено именем, реализация протестирована и оптимизирована, а с C++17 многие поддерживают политики параллельного исполнения.
Типичные ошибки
- ✗Использовать
std::remove/std::remove_ifбез последующего вызоваerase— идиома erase-remove необходима для фактического уменьшения контейнера - ✗Передавать несортированные диапазоны в
std::binary_search,std::lower_boundилиstd::upper_bound - ✗Вызывать
std::sortдляstd::list— у списков нет итераторов произвольного доступа; используйте методlist::sort()
Уточняющие вопросы
- →Как
std::transform_reduceэффективно сочетает преобразование и свёртку? - →Что такое алгоритмы диапазонов C++20 и чем они отличаются от классических алгоритмов STL?
JuniorТеорияЧастоИз чего состоит STL?
Из чего состоит STL?
STL состоит из четырёх компонентов: контейнеры (последовательные, ассоциативные, неупорядоченные, адаптеры), итераторы (связующее звено между контейнерами и алгоритмами), алгоритмы (sort, find, transform, accumulate и др.) и объекты-функции/лямбды для настройки поведения алгоритмов.
Типичные ошибки
- ✗Считать STL и стандартную библиотеку C++ одним и тем же — стандартная библиотека является расширенным набором, включающим
<iostream>,<thread>и т.д. - ✗Использовать сырые циклы там, где алгоритм STL был бы понятнее и потенциально оптимальнее
- ✗Забывать, что аллокаторы — это пятый компонент, важный для пользовательских стратегий управления памятью
Уточняющие вопросы
- →Что такое адаптеры диапазонов в C++20 (
std::ranges)? - →Почему следует предпочитать
std::begin()/std::end()вместо.begin()/.end()?
JuniorТеорияЧастоКакие алгоритмы работы со строками вы знаете?
Какие алгоритмы работы со строками вы знаете?
Ключевые алгоритмы строк: наивный поиск подстроки O(n·m), КМП (Кнута–Морриса–Пратта) O(n+m), Бойера–Мура O(n/m) в среднем, Рабина–Карпа (скользящий хеш) для поиска нескольких паттернов, Z-функция для совпадений с префиксом. Для расстояния редактирования: Левенштейн (динамическое программирование O(n·m)).
Типичные ошибки
- ✗Использовать
std::string::findв цикле с результатом O(n²), тогда как KMP дал бы O(n) - ✗Забывать, что сравнение строк в C++ — O(n), а не O(1) как сравнение указателей
- ✗Игнорировать проблемы локали/кодировки при обработке не-ASCII строк
Уточняющие вопросы
- →Чем Z-функция отличается от КМП? Когда предпочтительнее использовать каждый из них?
- →Какие улучшения стратегии поиска добавил C++17 в
std::search?
JuniorКодЧастоДва наибольших числа в массиве за один проход
Два наибольших числа в массиве за один проход
Держите две переменные max1 и max2, обе инициализированы наименьшим возможным значением (не 0). Для каждого элемента: если он больше max1, перенесите max1 в max2 и обновите max1; иначе если он больше max2, обновите max2. Ключевое else if не даёт потерять старый максимум. Один проход, O(n).
Типичные ошибки
- ✗Опускать ветку
else if (x > max2), из-за чего второй максимум затирается первым - ✗Инициализировать максимумы нулём, что ломается на полностью отрицательных массивах
- ✗Не обрабатывать массив менее чем из двух элементов
Уточняющие вопросы
- →Почему инициализация нулём не работает для полностью отрицательного массива?
- →Как обобщить это до K наибольших элементов?
JuniorКодЧастоURLify: замена пробелов на %20 на месте
URLify: замена пробелов на %20 на месте
Два прохода. Сначала посчитайте пробелы, чтобы вычислить итоговую длину. Затем пишите с конца: копируйте каждый символ в его финальную ячейку, а для каждого пробела пишите '0', '2', '%' (в обратном порядке). Запись справа налево гарантирует, что вы не затрёте необработанный вход. O(n) время, O(1) дополнительной памяти.
Типичные ошибки
- ✗Писать с начала и затирать ещё не обработанные символы
- ✗Не использовать предусмотренную ёмкость и писать за исходной длиной
- ✗Выводить символы
%20в неверном порядке при обратном проходе
Уточняющие вопросы
- →Почему запись с конца избегает затирания непрочитанных символов?
- →Как изменилось бы решение, если буфер нельзя менять на месте?
JuniorКодЧастоРеализуйте класс vector с операциями: push_back, push_front, pop_back, pop_front, size, clear
Реализуйте класс vector с операциями: push_back, push_front, pop_back, pop_front, size, clear
Вектор владеет массивом, выделенным на куче, размером (использованные элементы) и вместимостью (выделенные слоты). push_back амортизированно O(1) — вместимость удваивается при заполнении. push_front — O(n), так как все элементы нужно сдвинуть. Для корректности необходимы конструктор копирования, оператор присваивания и деструктор (Правило пяти).
Типичные ошибки
- ✗Использовать
new T[n], который инициализирует все элементы по умолчанию — предпочтительнее сырая память + placement new - ✗Забывать вызывать деструкторы существующих элементов перед
clear()для нетривиального T - ✗Увеличивать на 1 вместо удвоения — приводит к суммарной стоимости push_back O(n²)
Уточняющие вопросы
- →Почему
std::vectorиспользует удвоение вместимости, а не утроение или фиксированный инкремент? - →Как эффективно реализовать
insertв произвольную позицию?
JuniorКодЧастоРеализуйте подсчёт слов в предложении
Реализуйте подсчёт слов в предложении
Сканируйте строку, отслеживая, был ли предыдущий символ пробелом. Каждый переход от пробела к непробелу увеличивает счётчик слов. Корректно обрабатывайте множественные пробелы и ведущие/завершающие пробелы.
Открыть задачу →Типичные ошибки
- ✗Считать пробелы вместо переходов от пробела к непробелу — даёт неверный результат при нескольких пробелах подряд
- ✗Ошибка на единицу: не считать последнее слово, если строка не заканчивается пробелом
- ✗Не обрабатывать случай пустой строки
Уточняющие вопросы
- →Как подсчитать уникальные слова в предложении?
- →Как разбить строку по произвольному разделителю?
MiddleКодЧастоВыдать сумму банкомата минимумом купюр; когда жадность ломается?
Выдать сумму банкомата минимумом купюр; когда жадность ломается?
Идём по номиналам от крупных к мелким, беря min(amount / denom, stock[denom]) каждого. Жадность оптимальна лишь потому, что номиналы взаимно делятся. Считаем план во временный буфер и применяем, только если остаток нулевой — так неудача оставляет запас нетронутым.
Типичные ошибки
- ✗Менять реальный запас до того, как сумма полностью собрана
- ✗Считать жадность оптимальной для произвольных номиналов, а не только делящихся
- ✗Оставлять номиналы с нулевым количеством в результате выдачи
Уточняющие вопросы
- →Приведите набор номиналов, где жадность ломается, но решение есть.
- →Как перейти к решению через динамику для произвольных номиналов?
MiddleКодЧастоПодсчёт островов суши в сетке 0/1 заливкой
Подсчёт островов суши в сетке 0/1 заливкой
Сканируем каждую клетку. На непосещённой клетке суши увеличиваем счётчик островов и заливаем всю её связную компоненту через DFS или BFS, помечая каждую достигнутую клетку посещённой (например, обнуляя её). Заливка стоит на воде и границах, каждая клетка посещается константно.
Открыть задачу →Типичные ошибки
- ✗Считать каждую клетку суши островом вместо каждой связной компоненты
- ✗Не помечать посещённые клетки, из-за чего один остров считается повторно
- ✗Путать 4- и 8-направленную смежность, меняя ответ
Уточняющие вопросы
- →Как 8-направленная связность изменит подсчёт?
- →Как избежать переполнения стека на огромной сетке при рекурсивном DFS?
MiddleКодЧастоПодсчёт подстрок без повторяющихся символов за O(n)
Подсчёт подстрок без повторяющихся символов за O(n)
Скользящее окно: держите left — начало окна без повторов, lastSeen[c] — последний индекс символа. Для каждого правого конца j поставьте left = max(left, lastSeen[c]+1) и прибавьте j - left + 1 (число допустимых левых концов). Один проход, O(n).
Типичные ошибки
- ✗Сдвигать
leftнаlastSeen[c]вместоlastSeen[c]+1, оставляя повтор внутри окна - ✗Не ограничивать через
max(left, ...), из-за чегоleftпрыгает назад на старом повторе - ✗Использовать
intдля итога, когда n достаточно велико для переполнения
Уточняющие вопросы
- →Чем это отличается от поиска длины самой длинной такой подстроки?
- →Почему
leftдолжен двигаться только вперёд?
MiddleТеорияЧастоКак работает алгоритм Дейкстры и какая структура данных делает его эффективным?
Как работает алгоритм Дейкстры и какая структура данных делает его эффективным?
Дейкстра находит кратчайшие пути от источника в графе с неотрицательными весами. Извлечь вершину с минимальной dist из приоритетной очереди, релаксировать соседей, push обновлений. Бинарная куча — O((V+E) log V); для отрицательных весов нужен Bellman-Ford.
Типичные ошибки
- ✗Применять Дейкстру с отрицательными рёбрами — неверный результат
- ✗Не обрабатывать «устаревшие» записи в приоритетной очереди (вершина со старой dist)
- ✗Не помечать вершину завершённой после pop минимальной dist
Уточняющие вопросы
- →Когда A* быстрее Дейкстры?
- →Какая сложность Дейкстры на Fibonacci heap и практичен ли он?
MiddleТеорияЧастоЧто такое динамическое программирование и чем мемоизация отличается от табуляции?
Что такое динамическое программирование и чем мемоизация отличается от табуляции?
DP использует перекрывающиеся подзадачи и оптимальную подструктуру, кешируя их решения. Мемоизация (top-down) — рекурсия с кешированием по требованию; табуляция (bottom-up) итеративно заполняет таблицу от base case и часто допускает сжатие памяти.
Типичные ошибки
- ✗Делать мемоизацию через
std::map, когда хватит массива — O(log n) vs O(1) - ✗Не обработать base case в табуляции
- ✗Не сжать память, когда recurrence требует только последнюю строку/столбец
Уточняющие вопросы
- →Как восстановить оптимальное решение после построения DP-таблицы?
- →Сравните top-down и bottom-up для задачи о рюкзаке.
MiddleКодЧастоСгруппировать массив строк в наборы анаграмм
Сгруппировать массив строк в наборы анаграмм
Дайте каждому слову канонический ключ, общий для всех его анаграмм, затем раскладывайте слова по ключу в хеш-таблицу. Ключ — это либо отсортированные символы слова, либо сигнатура из 26 счётчиков символов. Слова с одним ключом — анаграммы. Собираем значения таблицы как группы.
Открыть задачу →Типичные ошибки
- ✗Сортировать массив в надежде, что анаграммы станут соседними, чего не происходит
- ✗Группировать по длине или первой букве, что сталкивает неанаграммы
- ✗Сваливаться к O(n^2) попарным проверкам перестановок
Уточняющие вопросы
- →Почему сигнатура из 26 счётчиков — более быстрый ключ, чем сортировка слова?
- →Как обработать Unicode-слова, где 26 корзин недостаточно?
MiddleКодЧастоНапишите реализацию очереди (кольцевой буфер)
Напишите реализацию очереди (кольцевой буфер)
Очередь на кольцевом буфере использует массив фиксированного размера с индексами head и tail, оборачивающимися по модулю вместимости. enqueue записывает в tail и продвигает его; dequeue читает из head и продвигает его. Условие заполненности: (tail + 1) % cap == head. Это даёт O(1) для enqueue/dequeue без динамических выделений.
Типичные ошибки
- ✗Путать условия заполненности и пустоты — (tail + 1) % cap == head для полной, head == tail для пустой
- ✗Тратить один слот для различения полной и пустой очереди — альтернатива: отдельный счётчик размера
- ✗Ошибка на единицу в арифметике по модулю
Уточняющие вопросы
- →Как сделать эту очередь потокобезопасной для одного производителя и одного потребителя?
- →В чём преимущество кольцевого буфера перед очередью на связном списке?
MiddleТеорияЧастоСравните quicksort и merge sort по сложности, стабильности и памяти.
Сравните quicksort и merge sort по сложности, стабильности и памяти.
Quicksort: средняя O(n log n), худшая O(n²) на плохих pivot, in-place (O(log n) стек), нестабилен; обычно быстрее на практике. Merge sort: гарантированная O(n log n), O(n) доп. памяти, стабилен. По умолчанию — quicksort (introsort); merge sort — когда нужна стабильность или внешняя сортировка.
Типичные ошибки
- ✗Quicksort с pivot=first/last — O(n²) на отсортированном входе
- ✗Брать merge sort ради «гарантии» — обычно медленнее introsort в памяти
- ✗Чисто рекурсивный quicksort — глубокий стек
Уточняющие вопросы
- →Что такое introsort и как избегает худшего случая quicksort?
- →Как external merge sort обрабатывает данные больше RAM?
MiddleКодЧастоЭлементы одного сортированного списка, которых нет в другом
Элементы одного сортированного списка, которых нет в другом
Merge двумя указателями: при a[i] < b[j] элемент a[i] отсутствует в b, выводим его и двигаем i. При a[i] == b[j] пропускаем a[i] (он есть). При a[i] > b[j] двигаем j. После исчерпания b выводим остаток a. O(n + m), O(1).
Типичные ошибки
- ✗Неверная обработка дублей, напр. удаление обеих копий значения, которое в b лишь раз
- ✗Забыть вывести хвост a после исчерпания b
- ✗Не сдвигать указатель при равенстве, вызывая бесконечный цикл
Уточняющие вопросы
- →Как меняется обработка дублей, если в b могут быть повторы?
- →Почему merge двумя указателями предпочтительнее хеш-множества, когда оба входа уже отсортированы?
MiddleКодЧастоНайти подотрезок с суммой X (с отрицательными числами)
Найти подотрезок с суммой X (с отрицательными числами)
Идите по массиву, накапливая префиксную сумму P, с хеш-таблицей «префикс → ранний индекс», засеянной 0 → -1. На каждом j, если P - X есть в таблице, подотрезок после того индекса до j даёт сумму X. Отрицательные числа исключают окно, поэтому таблица даёт O(n).
Типичные ошибки
- ✗Использовать скользящее окно при отрицательных числах, что ломает монотонность суммы
- ✗Забыть засеять
0 → -1, из-за чего подотрезок с начала пропускается - ✗Допустить переполнение префиксной суммы в
intна больших входах
Уточняющие вопросы
- →Как упростился бы подход, если бы все числа гарантированно были неотрицательными?
- →Почему запись-затравка
0 → -1необходима?
MiddleКодЧастоНайти путь от корня к листу в бинарном дереве с заданной суммой
Найти путь от корня к листу в бинарном дереве с заданной суммой
Запускаем поиск в глубину, несущий остаток суммы и текущий путь. В каждом узле вычитаем его значение; в листе принимаем путь тогда и только тогда, когда остаток стал нулём. Рекурсируем в детей, добавляя узел перед и снимая после (бэктрекинг). Возвращаем первый принятый путь. O(n).
Открыть задачу →Типичные ошибки
- ✗Принимать во внутреннем узле вместо требования конца в листе
- ✗Считать все значения положительными и отсекать отрицательные ветви
- ✗Забыть снять узел при бэктрекинге, протащив его в чужой путь
Уточняющие вопросы
- →Как разрешение отрицательных значений исключает раннюю отсечку?
- →Как вернуть все такие пути вместо первого?
JuniorКодИногдаДлина наибольшей серии одинаковых символов
Длина наибольшей серии одинаковых символов
Пройдите один раз с текущей длиной серии. Пока следующий символ равен текущему, продлевайте серию; при смене сбрасывайте до 1. Отслеживайте максимальную длину серии за проход. Один проход, O(n) время, O(1) память; пустая строка даёт 0.
Открыть задачу →Типичные ошибки
- ✗Сбрасывать длину серии в 0 вместо 1 при смене символа
- ✗Забывать сравнить последнюю серию с максимумом после цикла
- ✗Путать общую частоту символа с наибольшей непрерывной серией
Уточняющие вопросы
- →Как расширить это до наибольшей подстроки с не более чем K различными символами?
- →Почему общая частота — не то же самое, что наибольшая серия?
MiddleКодИногдаПроверить, лежат ли все целочисленные точки на одной прямой
Проверить, лежат ли все целочисленные точки на одной прямой
Зафиксируйте первые две точки как опорное направление (dx, dy). Точка p на прямой тогда и только тогда, когда кросс-произведение dx*(p.y-y0) - dy*(p.x-x0) равно нулю. Проверьте для каждой точки. Берите long long против переполнения; без деления вертикали тоже работают. O(n).
Типичные ошибки
- ✗Использовать дробный наклон, теряя точность или деля на ноль на вертикали
- ✗Считать кросс-произведение в
int, переполняясь на больших координатах - ✗Проверять лишь часть точек вместо каждой против опорной прямой
Уточняющие вопросы
- →Почему кросс-произведение предпочтительнее сравнения наклонов?
- →Какие краевые случаи возникают при менее чем трёх точках?
MiddleКодИногдаПодсчёт пар индексов с разностью значений не меньше K
Подсчёт пар индексов с разностью значений не меньше K
Отсортируйте массив. Для каждого i бинпоиском найдите первый индекс со значением не меньше a[i]+K; каждый элемент оттуда до конца образует валидную пару, прибавьте их число. При K = 0 так считаются все пары i <= j. Итого O(n log n) — намного лучше цикла за O(n²).
Типичные ошибки
- ✗Забыть, что при K=0 в подсчёт входит самопара (i, i)
- ✗Считать упорядоченные пары, когда спецификация просит i <= j (или наоборот)
- ✗Использовать исходные индексы и не заметить, что сортировка допустима, ведь важны лишь значения
Уточняющие вопросы
- →Как изменился бы подход для пар с разностью не больше K (вместо не меньше)?
- →Почему сортировка безопасна, хотя в вопросе упомянуты индексы?
MiddleКодИногдаВернуть все встречи, пересекающиеся хотя бы с одной другой
Вернуть все встречи, пересекающиеся хотя бы с одной другой
Сортируем по from, затем проходим, отслеживая текущий максимум to среди ранее начавшихся встреч. Встреча пересекает более раннюю, когда её from < maxEnd; тогда помечаем и её, и встречу, задавшую maxEnd. Флаг на встречу гарантирует один отчёт на каждую. O(n log n).
Типичные ошибки
- ✗Сравнивать только соседние отсортированные интервалы, пропуская встречу, пересечённую более ранней несоседней
- ✗Смешивать проверки замкнутых и полуоткрытых границ, из-за чего касающиеся интервалы ошибочно считаются пересекающимися
- ✗Сообщать встречу дважды, когда она пересекает несколько других
Уточняющие вопросы
- →Как полуоткрытое правило
[from, to)меняет сравнение границ? - →Чем это отличается от поиска максимального числа одновременных встреч?
MiddleКодИногдаНайдите уникальный элемент в контейнере за один проход
Найдите уникальный элемент в контейнере за один проход
Если все элементы — целые и каждый повторяющийся встречается ровно дважды, XOR всех значений: a^a=0, остаётся уникальный — O(n) времени, O(1) памяти. В общем случае: за один проход построить unordered_map<T,int> счётчиков, затем вернуть запись с count==1.
Типичные ошибки
- ✗Называть решение 'однопроходным', когда второй просмотр карты/множества — это второй проход
- ✗Использовать сортировку — требует двух проходов или O(n log n)
- ✗Не уточнять ограничения задачи перед выбором алгоритма
Уточняющие вопросы
- →Как найти первый неповторяющийся символ в строке за один проход?
- →Что делать, если элементы могут встречаться любое число раз и нужен тот, у которого нечётное количество?
MiddleКодИногдаРеализуйте fuzzysearch: является ли needle подпоследовательностью haystack?
Реализуйте fuzzysearch: является ли needle подпоследовательностью haystack?
Два указателя. Идите по haystack; когда символ haystack равен текущему символу needle, двигайте указатель needle. Needle — подпоследовательность тогда и только тогда, когда его указатель дошёл до конца. Один линейный проход, O(|haystack|), константа памяти.
Типичные ошибки
- ✗Путать подпоследовательность (порядок сохранён, пропуски можно) с подстрокой (подряд)
- ✗Проверять лишь наличие символов и игнорировать относительный порядок
- ✗Двигать указатель needle на каждом символе haystack, а не только при совпадении
Уточняющие вопросы
- →Какие уточняющие вопросы важны (пустой needle, регистр)?
- →Почему жадный однопроходный матч никогда не пропускает валидную подпоследовательность?
MiddleКодИногдаНайдите циклы и недоступные вершины в ориентированном графе
Найдите циклы и недоступные вершины в ориентированном графе
Используйте DFS с трёхцветной пометкой: белый (непосещённый), серый (в текущем пути), чёрный (полностью обработан). Обратное ребро (серый→серый) указывает на цикл. Недоступные узлы остаются белыми после полного DFS от всех исходных вершин. Deadlock-состояние — это цикл в графе зависимостей/ожидания.
Открыть задачу →Типичные ошибки
- ✗Использовать только множество посещённых — оно обнаруживает посещённые, но не обратные рёбра (в пути vs полностью обработан)
- ✗Не выполнять DFS от всех непосещённых вершин — пропускает несвязные компоненты
- ✗Путать обнаружение цикла в неориентированном графе (union-find) с ориентированным (цвета DFS)
Уточняющие вопросы
- →Как топологическая сортировка связана с обнаружением циклов в DAG?
- →Что такое алгоритм Тарьяна для нахождения сильно связных компонент?
MiddleКодИногдаСложить два шестнадцатеричных числа, заданных строками
Сложить два шестнадцатеричных числа, заданных строками
Идите по обеим строкам от последнего символа к первому, переводя hex-цифру в 0–15 и складывая с переносом. Запишите sum % 16 как следующую цифру, держите sum / 16 как перенос. После концов выведите остаток переноса и разверните строку. O(макс. длины).
Типичные ошибки
- ✗Забыть вывести финальный перенос, теряя старшую цифру
ff + ff - ✗Дополнять не с той стороны и сбивать разрядность
- ✗Ошибиться в переводе цифр a–f в значение (сдвиг на 10)
Уточняющие вопросы
- →Как обобщить это на произвольное основание?
- →Почему обработка с младшего конца нужна для переноса?
MiddleКодИногдаK ближайших по значению к a[index] в отсортированном массиве
K ближайших по значению к a[index] в отсортированном массиве
Поставьте два указателя на index-1 и index+1, сначала взяв сам a[index]. На каждом шаге сравнивайте расстояния левого и правого кандидатов до a[index] и берите ближнюю сторону, пока не наберёте k. Защитите оба края. O(k), ведь массив отсортирован.
Типичные ошибки
- ✗Выход за левый или правый край без проверки границ
- ✗Неверная обработка массива из одного элемента, где ни один указатель не валиден
- ✗Выбор дальнего из двух равноудалённых кандидатов при заданном правиле разрешения ничьей
Уточняющие вопросы
- →Чем это отличается от поиска k ближайших к произвольному значению x, а не a[index]?
- →Как сделать разрешение ничьей детерминированным в пользу меньших значений?
MiddleКодИногдаK элементов, ближайших к значению x, в отсортированном массиве
K элементов, ближайших к значению x, в отсортированном массиве
Бинпоиском найдите позицию x, затем растите окно размера k. На каждом шаге сравнивайте расстояния границ до x; если x - arr[left-1] <= arr[right] - x, двигайте левую, иначе правую. Знак <= отдаёт ничью меньшему значению. Окно остаётся отсортированным. O(log n + k).
Типичные ошибки
- ✗Возвращать
kэлементов лишь справа от x вместо ближайших с обеих сторон - ✗Использовать
<вместо<=и ломать правило ничьей в пользу меньшего - ✗Допускать выход указателей left/right за границы массива
Уточняющие вопросы
- →Чем это отличается от поиска k ближайших к a[index], а не к свободному значению x?
- →Почему окно остаётся непрерывным на всём протяжении?
MiddleКодИногдаУмножение длинного десятичного числа (строки цифр) на одну цифру
Умножение длинного десятичного числа (строки цифр) на одну цифру
Идём с младшего разряда. На каждой позиции считаем product = digit * n + carry, записываем обратно product % 10, кладём carry = product / 10. После цикла, пока carry > 0, дописываем carry % 10 как новые старшие разряды. Хранение от младшего разряда даёт переносу течь вперёд.
Типичные ошибки
- ✗Забыть дописать остаточный перенос после последнего разряда
- ✗Сваливаться к целому фиксированной ширины, переполняющемуся на длинных числах
- ✗Идти от старшего разряда, из-за чего переносу некуда течь
Уточняющие вопросы
- →Как изменится алгоритм, если разряды — 32-битные лимбы вместо основания 10?
- →Почему хранение младшим разрядом вперёд упрощает перенос?
MiddleКодИногдаСамый длинный строго монотонный подотрезок за O(n)
Самый длинный строго монотонный подотрезок за O(n)
Один проход с отслеживанием начала и направления текущей серии. Если следующая пара меняет направление — начните серию с предыдущего индекса; если равна — с текущего. Храните самую длинную серию. Равенство всегда обрывает строгую серию. O(n) время, O(1) память.
Открыть задачу →Типичные ошибки
- ✗Считать равные соседние значения продолжением строго монотонной серии
- ✗Сбрасывать начало серии на текущий индекс вместо предыдущего при смене направления
- ✗Ошибка на единицу, когда самая длинная серия кончается последним элементом
Уточняющие вопросы
- →Почему новая серия начинается с предыдущего индекса, а не с текущего?
- →Как изменится логика для нестрогой (с равенством) монотонности?
MiddleКодИногдаМинимальная абсолютная разность элементов двух массивов
Минимальная абсолютная разность элементов двух массивов
Сортируем оба массива, затем идём по ним двумя указателями. На каждом шаге фиксируем abs(a[i] - b[j]) и продвигаем указатель на меньшем значении — сдвиг большего лишь расширил бы разрыв. Минимум на этом слиянии и есть глобальный минимум. Вычитаем в 64 битах, избегая переполнения. O(n log n).
Типичные ошибки
- ✗Продвигать не тот указатель, из-за чего ближайшие пары пропускаются
- ✗Вычитать в 32-битных int и переполняться на крайних значениях
- ✗Не обрабатывать пустой массив, у которого нет допустимой пары
Уточняющие вопросы
- →Почему продвижение меньшего значения никогда не пропускает оптимум?
- →Как
lower_boundдаст альтернативу O(n log n) без слияния?
MiddleКодИногдаРазбить массив на 3 части с минимальной суммой стоимостей первых элементов
Разбить массив на 3 части с минимальной суммой стоимостей первых элементов
Первая часть всегда начинается с индекса 0, поэтому её стоимость фиксирована как nums[0]. Две другие части начинаются с любых двух индексов > 0, поэтому их стоимости — два наименьших среди nums[1..]. Ответ — nums[0] плюс эти два минимума, за один O(n) проход.
Типичные ошибки
- ✗Сортировать и не заметить, что стоимость первой части вынужденно равна nums[0]
- ✗Включать nums[0] при поиске двух минимумов остальных частей
- ✗Использовать двойной цикл за O(n²), когда достаточно одного прохода
Уточняющие вопросы
- →Почему стоимость первой части вынуждена, а остальные свободны быть любыми двумя поздними индексами?
- →Как изменится ответ при разбиении на k частей?
MiddleКодИногдаКратчайшая подстрока, содержащая все буквы заданного алфавита
Кратчайшая подстрока, содержащая все буквы заданного алфавита
Используем скользящее окно со счётчиком ещё недостающих символов в хеш-таблице. Расширяем right, уменьшая счётчик, когда нужный символ впервые покрыт. Пока окно покрывает все требуемые символы, фиксируем его, если короче, и сжимаем слева. Идём до конца, чтобы окно с концом на последнем символе тоже учлось.
Типичные ошибки
- ✗Расширять окно, но не сжимать слева для его минимизации
- ✗Останавливаться рано и пропускать окно, кончающееся на последнем символе
- ✗Не сообщать неудачу, когда алфавит так и не покрыт полностью
Уточняющие вопросы
- →Как счётчик нехватки позволяет проверять покрытие за O(1) на шаг?
- →Как меняется ответ, если лишние символы не допускаются?
MiddleКодИногдаСкалярное произведение двух RLE-сжатых векторов
Скалярное произведение двух RLE-сжатых векторов
Идите по обоим спискам двумя указателями, отслеживая остаток текущей серии с каждой стороны. На каждом шаге берите min(остатков) позиций, добавляя value_l * value_r * min к аккумулятору, затем двигайте исчерпанную серию. O(|l|+|r|), без разворота, 64-битная сумма.
Типичные ошибки
- ✗Считать, что границы серий двух RLE совпадают, вместо потребления минимума остатков
- ✗Разворачивать векторы и терять преимущество O(|l|+|r|)
- ✗Переполнять 32-битный аккумулятор при больших произведениях value*count
Уточняющие вопросы
- →Чем это отличается от сложения разреженных векторов, где сливают, а не умножают?
- →Почему потребление минимума двух остатков — ключевой шаг?
MiddleКодИногдаОбщие элементы в каждом K-префиксе двух массивов за O(N)
Общие элементы в каждом K-префиксе двух массивов за O(N)
Идите по обоим префиксам синхронно с двумя хеш-множествами seenA, seenB и счётчиком common. Новое значение из a уже есть в seenB — увеличьте common; так же для нового b в seenA. Записывайте common после каждого шага. Один проход, O(N).
Типичные ошибки
- ✗Перестраивать префиксные множества на каждом K вместо инкрементального расширения
- ✗Считать дублирующееся значение новым совпадением более одного раза
- ✗Забыть, что новый элемент проверяется против множества ДРУГОГО массива
Уточняющие вопросы
- →Как меняется ответ, если пересечение учитывает кратность (минимум частот)?
- →Почему счётчик остаётся верным, когда оба префикса растут вместе?
MiddleКодИногдаСократить путь L/R/U/D, вырезая замкнутые подмаршруты
Сократить путь L/R/U/D, вырезая замкнутые подмаршруты
Идём по шагам, отслеживая текущую координату (x, y) и хеш-таблицу каждой посещённой координаты к её позиции в выходе. Когда координата повторяется, шаги с её первого посещения образуют замкнутую петлю: усекаем выход до той позиции и убираем координаты, добавленные между.
Типичные ошибки
- ✗Сводить к итоговому смещению, что теряет форму реального маршрута
- ✗Гасить только соседние развороты, пропуская крупные петли вроде R,D,L,U
- ✗Забыть засеять стартовую координату на индексе 0 выхода
Уточняющие вопросы
- →Почему итоговое смещение даёт неверный ответ для
[D,R,U]? - →Как стирать промежуточные координаты из таблицы при усечении?
MiddleКодИногдаПоток чисел по связанным файлам с бегущим средним и без зацикливания
Поток чисел по связанным файлам с бегущим средним и без зацикливания
Считаем файлы узлами графа, а ссылки — рёбрами; обходим через DFS, держа множество посещённых путей, чтобы цикл не переоткрыл файл. Держим бегущие sum и count; для каждой числовой строки прибавляем её и печатаем sum / count. Ссылка ведёт к названному файлу, только если он не посещён.
Типичные ошибки
- ✗Пересуммировать все числа на каждую строку вместо бегущих суммы и счётчика
- ✗Опускать множество посещённых, из-за чего цикл ссылок зациклится навсегда
- ✗Отслеживать посещения по метке времени или размеру, а не по пути файла
Уточняющие вопросы
- →Почему множество посещённых превращает это в обычный обход графа?
- →Как держать бегущее среднее численно устойчивым для множества значений?
MiddleКодИногдаОбернуть почти отсортированный поток чисел в отсортированный
Обернуть почти отсортированный поток чисел в отсортированный
Держим min-кучу размером не более k + 1. На каждом get дозаполняем её из источника, пока не станет k + 1 элементов или источник не кончится, затем извлекаем наименьший. Значение в пределах k от места, поэтому минимум окна k + 1 — следующий по порядку. Возвращаем -1 при опустошении.
Типичные ошибки
- ✗Буферизовать весь поток, теряя смысл ограниченной памяти
- ✗Брать окно размера
kвместоk + 1, из-за чего следующий элемент может оказаться меньше - ✗Не дренировать буфер после конца источника, теряя хвост
Уточняющие вопросы
- →Почему буфер должен держать
k + 1, а неkэлементов? - →Какая структура данных даёт здесь O(log k) на извлечение минимума и вставку?
MiddleКодИногдаНапишите код для решения судоку
Напишите код для решения судоку
Используйте поиск с возвратом: найдите первую пустую клетку, попробуйте цифры 1–9, проверьте ограничения строки/столбца/блока, рекурсируйте. Если ни одна цифра не подходит — откат. Теоретически O(9^m), где m — количество пустых клеток, но отсечение ограничений делает алгоритм быстрым на практике.
Открыть задачу →Типичные ошибки
- ✗Проверять всю доску на каждом шаге вместо только затронутых строки, столбца и блока
- ✗Не возвращать
trueпри нахождении решения — рекурсия должна передавать успех наверх - ✗Использовать 1-индексированные координаты, вызывающие ошибки на единицу в вычислении блока
Уточняющие вопросы
- →Как распространение ограничений (дуговая согласованность) улучшает производительность поиска с возвратом?
- →Что такое эвристика 'наиболее ограниченная переменная' при выборе следующей клетки?
MiddleКодИногдаСвернуть список целых в строку диапазонов
Свернуть список целых в строку диапазонов
Отсортируйте массив. Идите по нему, отслеживая начало текущей серии подряд идущих чисел; когда следующее значение не prev + 1, выведите серию как start или start-end и начните новую. Выведите последнюю серию после цикла. O(n log n) на сортировку, O(n) на сборку.
Типичные ошибки
- ✗Забыть отсортировать, из-за чего несоседние подряд идущие значения пропускаются
- ✗Печатать одиночку как
k-kвместо простоk - ✗Терять последний диапазон, потому что он выводится лишь внутри цикла
Уточняющие вопросы
- →Как изменилась бы логика, если бы дубли были разрешены?
- →Почему вывод после цикла необходим?
MiddleКодИногдаМожно ли сделать строку палиндромом, удалив ровно один символ?
Можно ли сделать строку палиндромом, удалив ровно один символ?
Два указателя с обоих концов. На первом несовпадении попробуйте пропустить левый или правый символ и проверьте, палиндром ли оставшийся участок. Если строка уже палиндром, удаление центрального символа сохранит его, так что верните true. O(n), O(1).
Открыть задачу →Типичные ошибки
- ✗Трактовать спецификацию как «не более одного» удаления, тогда как сказано «ровно одно»
- ✗Проверять лишь одну сторону на несовпадении вместо обоих удалений
- ✗Перепросматривать всю строку для каждого кандидата на удаление, делая O(n²)
Уточняющие вопросы
- →Чем «ровно одно» тонко отличается от «не более одного» для уже-палиндромной строки?
- →Почему достаточно попробовать обе стороны на первом несовпадении?
MiddleКодИногдаНайти вертикальную ось симметрии множества 2D-точек за O(n)
Найти вертикальную ось симметрии множества 2D-точек за O(n)
Единственный кандидат на ось — (minX + maxX) / 2, поэтому удвоенная ось это minX + maxX. Кладём каждую точку в хеш-множество; для (x, y) зеркало — (minX + maxX - x, y). Если каждое зеркало есть, ось верна. Берём удвоенное значение, чтобы избежать дробей. O(n).
Типичные ошибки
- ✗Сравнивать вещественные оси через float вместо удвоения для целочисленности
- ✗Считать осью центроид при неравномерном распределении
- ✗Переполнять
minX + maxXдля больших координат
Уточняющие вопросы
- →Почему
minX + maxX— единственная возможная удвоенная ось? - →Как дублирующиеся точки влияют на проверку зеркал?
MiddleКодИногдаСлучайный выбор сервера пропорционально весам нагрузки
Случайный выбор сервера пропорционально весам нагрузки
Строим кумулятивное распределение: идём по весам, накапливая сумму, и возвращаем первый индекс, где сумма превысила r. Это отображает равномерный отсчёт на корзины, размером с вес, так что шанс каждого сервера равен его весу. O(k), или O(log k) с массивом префиксных сумм и бинпоиском.
Типичные ошибки
- ✗Сравнивать
rс каждым сырым весом вместо кумулятивной суммы - ✗Ошибка на единицу на границе, например
<=, из-за чего последняя корзина недостижима - ✗Считать, что равномерный выбор уже учитывает веса
Уточняющие вопросы
- →Как ускорить повторные отсчёты массивом префиксных сумм и бинпоиском?
- →Что меняется, если веса не суммируются ровно в 1?
SeniorКодИногдаНайти подстроку — перестановку S за O(|T|)
Найти подстроку — перестановку S за O(|T|)
Двигайте окно длины |S| по T и держите один счётчик того, сколько частот символов ещё не совпадают с образцом. На каждом сдвиге добавляйте входящий символ и убирайте выходящий, обновляя счётчик за O(1). Когда он равен нулю — окно анаграмма. O(|T|), независимо от алфавита.
Типичные ошибки
- ✗Перепросматривать весь массив частот на окно, ставя константу в зависимость от размера алфавита
- ✗Забыть и добавить входящий, и убрать выходящий символ на каждом сдвиге
- ✗Путать анаграмму (то же мультимножество) с равенством (тот же порядок)
Уточняющие вопросы
- →Как вернуть все начальные индексы анаграмм вместо первого?
- →Почему ведение единственного счётчика несовпадений делает работу на сдвиг O(1)?
SeniorКодИногдаРазвернуть скобочную грамматику (term)[N] в строку
Развернуть скобочную грамматику (term)[N] в строку
Держим стек частичных строк. На ( кладём текущую строку и начинаем новую; на ) разбираем N в скобках, снимаем сохранённую строку и дописываем собранную, повторённую N раз; иначе дописываем букву. Многозначное N разбирается поразрядно, N == 0 ничего не дописывает.
Типичные ошибки
- ✗Разбирать только первую цифру многозначного счётчика вроде
[28] - ✗Неверно обрабатывать
N == 0, оставляя лишние символы вместо пустого терма - ✗Пытаться обойтись одним накопителем, что ломается на вложенных скобках
Уточняющие вопросы
- →Чем это отличается от синтаксиса
N[term]в decode-string на LeetCode? - →Можно ли разворачивать лениво, чтобы не материализовать огромную строку вывода?
SeniorКодИногдаНаименьший общий предок в дереве с parent-указателями, O(1) памяти
Наименьший общий предок в дереве с parent-указателями, O(1) памяти
Вычислите глубину каждой вершины подъёмом по parent к корню. Поднимите более глубокую вершину на разность глубин, чтобы обе были на одном уровне, затем двигайте обе вверх синхронно до встречи указателей — эта вершина и есть LCA. O(h) время, O(1) память.
Типичные ошибки
- ✗Использовать хеш-множество предков, нарушая требование O(1) памяти
- ✗Предполагать дерево поиска и сравнивать значения, что не работает на общем дереве
- ✗Забыть выровнять глубины перед синхронным подъёмом
Уточняющие вопросы
- →Как вычислить глубины без дополнительного хранилища?
- →Каков вариант за O(d) с экспоненциальными шагами вверх?
SeniorКодИногдаУдалить смайлики :-))) и :-((( из сообщения за один проход
Удалить смайлики :-))) и :-((( из сообщения за один проход
Один проход как небольшой автомат. На каждой позиции проверяйте :, затем -, затем серию ) или (; если найдено, пропустите весь токен и продолжите за ним, иначе скопируйте символ в вывод. Без отката в выведенный текст, поэтому вложенность не схлопывается. O(n).
Типичные ошибки
- ✗Откатываться и схлопывать вложенные смайлики, которые спецификация велит не трогать
- ✗Забыть, что смайлику нужны двоеточие, дефис И непустая серия скобок
- ✗Делать повторные проходы стирания, превращая задачу одного прохода в O(n²)
Уточняющие вопросы
- →Почему отказ от отката даёт поведение без вложенности, как требует спецификация?
- →Как сделать это по-настоящему на месте с индексом записи?
SeniorКодИногдаСложить два разреженных вектора из сортированных пар (индекс, значение)
Сложить два разреженных вектора из сортированных пар (индекс, значение)
Merge двумя указателями по отсортированным спискам: при равных индексах складываем значения, иначе выводим меньший индекс и двигаем тот указатель. Пропускаем записи с нулевой суммой (они уже не ненулевые). Линейно по суммарной длине, O(|l|+|r|).
Открыть задачу →Типичные ошибки
- ✗Забыть выбросить записи с нулевой суммой значений
- ✗Двигать оба указателя, когда совпал лишь один индекс
- ✗Накапливать в узком типе и переполняться при сложении двух больших значений
Уточняющие вопросы
- →Чем это отличается от скалярного произведения разреженных векторов, где умножают?
- →Почему нулевую сумму нужно удалять, чтобы остаться по-настоящему разреженным?
JuniorТеорияРедкоЧто значит, что сортировка стабильна, и какие STL-сортировки стабильны?
Что значит, что сортировка стабильна, и какие STL-сортировки стабильны?
Стабильная сортировка сохраняет относительный порядок элементов с равными ключами. std::stable_sort стабильна (merge-sort, O(n log n), доп. память O(n)); std::sort нестабильна (introsort, O(n log n) в среднем, in-place). Для нескольких ключей применяйте stable_sort от менее значимого к более значимому.
Типичные ошибки
- ✗Использовать
std::sortи удивляться перемешанному порядку равных ключей - ✗Сортировать по всем критериям сразу сложным компаратором вместо каскада stable_sort
- ✗Забывать, что stable_sort требует O(n) доп. памяти
Уточняющие вопросы
- →Как отсортировать по (department asc, salary desc) каскадом stable?
- →Что такое timsort и где он используется (Python, Java)?
MiddleТеорияРедкоЧто добавляют C++20 ranges и views по сравнению с классическими STL-алгоритмами?
Что добавляют C++20 ranges и views по сравнению с классическими STL-алгоритмами?
Ranges принимают range вместо пары итераторов (std::ranges::sort(v)), уменьшая ошибки итераторов. Views (v | filter | transform) лениво компонуют преобразования; время компиляции растёт.
Типичные ошибки
- ✗Хранить view от временного контейнера — dangling
- ✗Ждать переиспользования views без сброса — большинство single-pass
- ✗Недооценивать рост времени компиляции в template-heavy проектах
Уточняющие вопросы
- →Как
std::ranges::to(C++23) превращает view обратно в контейнер? - →Что такое sentinel и как он обобщает итераторы?
SeniorДизайнРедкоЗапросы приходят по времени. Чередуются две операции: пользователь генерирует событие и запрос «сколько пользователей сгенерировали не менее 1000 событий за последние 5 минут». Спроектируйте структуру данных, обрабатывающую обе за амортизированное O(1) на запрос, с константой, не зависящей от порога 1000 и ширины окна в 5 минут. Опишите структуры, почему каждая операция амортизированно O(1) и ловушки с памятью (опустошение окна и не очищаемые устаревшие записи по пользователям).
Запросы приходят по времени. Чередуются две операции: пользователь генерирует событие и запрос «сколько пользователей сгенерировали не менее 1000 событий за последние 5 минут». Спроектируйте структуру данных, обрабатывающую обе за амортизированное O(1) на запрос, с константой, не зависящей от порога 1000 и ширины окна в 5 минут. Опишите структуры, почему каждая операция амортизированно O(1) и ловушки с памятью (опустошение окна и не очищаемые устаревшие записи по пользователям).
Держите очередь событий окна, таблицу userId → count и текущий robotCount пользователей на пороге или выше. На операции выкидывайте события старше окна, добавляйте новое и правьте robotCount при пересечении порога. Каждое событие ставится и снимается с очереди раз, поэтому амортизированно O(1).
Типичные ошибки
- ✗Не обрабатывать момент, когда окно становится пустым
- ✗Никогда не удалять пользователей со счётчиком, упавшим до нуля, утекая памятью на длинном потоке
- ✗Позволять константе зависеть от порога 1000 или ширины окна в 5 минут
Уточняющие вопросы
- →Как удержать память ограниченной, когда долго идут только события (без запросов)?
- →Почему текущий robotCount избавляет от перепросмотра всех пользователей на запрос?
SeniorКодРедкоНайти два поддерева с одинаковым множеством букв за O(N)
Найти два поддерева с одинаковым множеством букв за O(N)
Рекурсия в post-order: множество букв вершины — это (1 << (Value-'A')) в OR с масками детей. Каждую вычисленную маску кладём в хеш-таблицу «маска → вершина»; при первом повторе маски найдены две эквивалентные вершины. Один обход, O(N) время и O(N) память.
Типичные ошибки
- ✗Считать частоты букв вместо трактовки поддерева как множества (спецификация игнорирует частоты)
- ✗Пересчитывать маску поддерева с нуля в каждой вершине вместо OR масок детей
- ✗Забыть добавить букву самой вершины в её маску
Уточняющие вопросы
- →Как вместо этого вернуть эквивалентную пару с наибольшим суммарным размером поддеревьев?
- →Почему 32-битного целого достаточно и когда понадобился бы другой дескриптор?
SeniorТеорияРедкоЧто такое политика исполнения для параллельных алгоритмов STL?
Что такое политика исполнения для параллельных алгоритмов STL?
C++17 добавил политики исполнения ко многим STL-алгоритмам: std::execution::seq (последовательно), par (параллельно), par_unseq (параллельно и векторизованно). Политика — подсказка, реализация сама решает, как её использовать.
Типичные ошибки
- ✗Полагать, что
parавтоматически делает код потокобезопасным — вы всё равно обязаны защищать общее состояние - ✗Использовать лямбды, захватывающие по ссылке, с
par— конкурентный доступ к одной переменной — это гонка данных - ✗Ожидать, что
parвсегда быстрее — для малого входа накладные расходы создания потоков доминируют
Уточняющие вопросы
- →Какую библиотеку используют libstdc++ / MSVC для реализации параллельных политик исполнения?
- →Как алгоритмы диапазонов C++20 взаимодействуют с политиками исполнения?
SeniorКодРедкоРеализуйте алгоритм хеширования с обработкой коллизий
Реализуйте алгоритм хеширования с обработкой коллизий
Хорошая хеш-функция равномерно распределяет ключи и быстро вычисляется (FNV-1a, djb2). Разрешение коллизий: метод цепочек или открытая адресация (линейное/квадратичное зондирование, двойное хеширование). std::unordered_map обычно использует цепочки.
Типичные ошибки
- ✗Использовать плохую хеш-функцию, кластеризующую значения — приводит к O(n) поиску в худшем случае
- ✗Не обрабатывать рост таблицы (рехеширование) при превышении порогового коэффициента нагрузки
- ✗Использовать криптографический хеш (SHA, MD5) для хеш-таблицы — слишком медленно
Уточняющие вопросы
- →Что такое коэффициент нагрузки и как он влияет на производительность?
- →Сравните открытую адресацию и метод цепочек с точки зрения кэш-производительности.
SeniorДизайнРедкоДаны даты заезда и отъезда каждого гостя (заезд строго раньше отъезда, поэтому каждый гость проводит хотя бы одну ночь). Спроектируйте алгоритм, находящий максимальное число гостей, одновременно проживающих в гостинице. В общий день уезжающий гость выезжает раньше, чем заезжает новый. Опишите структуры данных, сложность по времени и как вы разрешаете ничью, когда интервалы соприкасаются в одной точке.
Даны даты заезда и отъезда каждого гостя (заезд строго раньше отъезда, поэтому каждый гость проводит хотя бы одну ночь). Спроектируйте алгоритм, находящий максимальное число гостей, одновременно проживающих в гостинице. В общий день уезжающий гость выезжает раньше, чем заезжает новый. Опишите структуры данных, сложность по времени и как вы разрешаете ничью, когда интервалы соприкасаются в одной точке.
Используйте sweep line: разбейте каждое проживание на событие заезда +1 и отъезда −1, отсортируйте по времени и пройдите, ведя текущий счётчик, чей максимум и есть ответ. В общий момент обрабатывайте отъезды раньше заездов. O(N log N) на сортировку.
Типичные ошибки
- ✗Ошибиться в разрешении ничьей в общий день, считая отъезд и заезд одновременными
- ✗Использовать массив по дням, который раздувается при огромном диапазоне дат
- ✗Забыть, что отъезд освобождает место, поэтому
−1применяется в нужный момент
Уточняющие вопросы
- →Как ещё и сообщить, в какой день (или дни) был пик загрузки?
- →Что меняется, если нужно поддержать поток проживаний, добавляемых по одному?
SeniorКодРедкоДлиннейшая серия из 1 после удаления ровно одного элемента
Длиннейшая серия из 1 после удаления ровно одного элемента
Скользящее окно, допускающее не более одного нуля внутри; ответ — максимальный размер окна минус один (один элемент всегда удаляется). Когда нулей нет, это «минус один» всё равно применяется, давая L-1 для массива из одних единиц. Один проход, O(n), O(1).
Открыть задачу →Типичные ошибки
- ✗Возвращать размер окна без вычитания единицы за обязательное удаление
- ✗Провалить случай всех единиц, где элемент всё равно удаляется (ответ L-1)
- ✗Допускать более одного нуля в окне
Уточняющие вопросы
- →Чем «ровно одно» удаление отличается от «не более одного» для массива всех единиц?
- →Как обобщить окно на удаление до k элементов?
SeniorКодРедкоВосстановить все валидные IPv4-адреса из строки цифр
Восстановить все валидные IPv4-адреса из строки цифр
Бэктрекинг: расставьте три точки, разбивая строку на четыре октета. На шаге пробуйте октет из 1, 2 или 3 цифр, принимая его лишь если значение 0–255 без ведущего нуля (кроме ровно "0"). Когда все четыре октета покрывают всю строку, запишите адрес.
Типичные ошибки
- ✗Разрешать ведущие нули вроде
01или00в октете - ✗Принимать значения октетов больше 255
- ✗Не требовать, чтобы все четыре октета покрывали всю строку
Уточняющие вопросы
- →Какие входы дают ноль валидных адресов?
- →Как расширить это на группировку IPv6?
SeniorТеорияРедкоКакие улучшения получил std::search в C++17?
Какие улучшения получил std::search в C++17?
C++17 добавил перегрузку с searcher: std::search(first, last, searcher) и три типа — default_searcher, boyer_moore_searcher, boyer_moore_horspool_searcher. Searcher предобрабатывает паттерн один раз в конструкторе.
Типичные ошибки
- ✗Создавать новый объект searcher внутри цикла — преимущество предобработки теряется; создавайте его один раз
- ✗Использовать Boyer-Moore для очень коротких паттернов — накладные расходы предобработки не амортизируются
- ✗Ожидать, что
boyer_moore_searcherработает с итераторами без произвольного доступа — он требует их
Уточняющие вопросы
- →Какова временная сложность поиска Boyer-Moore в лучшем и худшем случаях?
- →Как написать пользовательский searcher, соответствующий интерфейсу C++17?
SeniorКодРедкоРеализуйте алгоритм сортировки (уровень Senior): merge sort или introsort с обоснованием
Реализуйте алгоритм сортировки (уровень Senior): merge sort или introsort с обоснованием
Merge sort гарантирует O(n log n) и является стабильной — подходит для связных списков и внешней сортировки. Introsort (quicksort + fallback на heapsort + сортировка вставками для малых диапазонов) используется в std::sort: гарантированное O(n log n), in-place, но нестабильная.
Типичные ошибки
- ✗Не знать, почему
std::sortиспользует introsort вместо чистого quicksort - ✗Реализовывать merge sort с O(n log n) дополнительной памятью, когда просят in-place
- ✗Игнорировать оптимизацию сортировкой вставками для малых подмассивов (< 16 элементов)
Уточняющие вопросы
- →При каком пороге глубины introsort переключается с quicksort на heapsort?
- →Чем
std::stable_sortотличается отstd::sortс точки зрения алгоритма и сложности?
