Хеш-таблицы, массивы и два указателя
Массивы и хеш-таблицы - примерно восемьдесят процентов лайвкодинга. Проверяют не память на конкретные задачи, а владение четырьмя паттернами: размен памяти на скорость, два указателя, скользящее окно, префиксные суммы. Узнал паттерн - решил за десять минут; не узнал - изобретаешь велосипед на глазах у интервьюера.
Типовые формулировки: «найди два числа с заданной суммой», «самая длинная подстрока без повторов», «сколько подмассивов с суммой k».
// Четыре паттерна с этих карточек закрывают большинство задач уровня easy и medium. Их стоит узнавать в лицо, а не выводить каждый раз заново.
Размен: память в обмен на скорость
Главный размен всего лайвкодинга. Вопрос «а видел ли я это раньше?» можно решать перебором за O(n) на каждую проверку, а можно хранить увиденное в множестве и отвечать за O(1). Записи читаются так: O(1) - время не зависит от объёма данных, O(n) - растёт пропорционально их количеству.
Разберём на классике - найти два числа с суммой 9 в массиве [2, 7, 11, 15]. Идём слева направо и держим множество увиденного. Взяли 2, ищем 7 среди увиденного - пусто, кладём 2. Взяли 7, ищем 9 − 7 = 2 - оно есть, ответ найден на втором шаге. Один проход, ни одного вложенного цикла.
Тот же приём в виде счётчика частот - типовой первый ход в куче задач: анаграммы, топ-k частых, «встречается ровно k раз». Всё начинается с одного прохода, собирающего словарь «значение - сколько раз».
// Ключ хеш-таблицы обязан быть неизменяемым: в Python это str, число, tuple, но не list и не dict. Причина механическая: место ключа определяется его хешем, и если ключ изменить после вставки, хеш поменяется, а лежать он останется на старом месте - и потеряется навсегда.
- коллизия
- два разных ключа попали в одну ячейку таблицы. Разруливается цепочкой элементов в ячейке или сдвигом в соседнюю свободную
Два указателя и скользящее окно
Два указателя работают на отсортированном массиве и опираются на его порядок. Ставим один в начало, другой в конец, смотрим сумму: мала - двигаем левый вправо, там числа больше; велика - двигаем правый влево. Каждый шаг убирает из рассмотрения целый пласт вариантов, поэтому весь проход стоит O(n) и не требует дополнительной памяти.
Скользящее окно - для задач вида «самый длинный отрезок, удовлетворяющий условию». Правый край едет вперёд и расширяет окно, а как только условие нарушилось, левый край подтягивается, пока условие не восстановится. Каждый элемент попадает в окно один раз и выходит один раз, значит суммарно не больше 2n действий - снова O(n).
Одна деталь решает всё: сжимать окно надо циклом while, а не одним if. Один if снимает одно нарушение, а после добавления элемента их может накопиться несколько подряд - и инвариант окна сломается тихо.
// Окно по суммам работает, только пока числа неотрицательны: тогда расширение окна сумму увеличивает, а сжатие уменьшает, и это даёт монотонность, на которой всё держится. Появились отрицательные - монотонность исчезает, и нужен другой инструмент.
Префиксные суммы
Идея в одну строчку: посчитать заранее массив накопленных сумм, где prefix[i] - сумма первых i элементов. Строится он за один проход, O(n). Зато после этого сумма любого отрезка от l до r считается как prefix[r+1] − prefix[l], то есть за O(1) вместо прохода по отрезку.
Признак задачи на префиксы: много запросов «сумма на отрезке» по одному и тому же массиву. Один раз потратились на подготовку, дальше отвечаем мгновенно.
Связка с хешом закрывает задачу «сколько подмассивов имеют сумму k», в том числе с отрицательными числами, где скользящее окно бессильно. Идём слева направо, считаем текущий префикс и ищем в хеше, сколько раз раньше встречался префикс со значением текущий − k: каждое такое совпадение и есть подмассив с нужной суммой.
// Та же идея живёт в двух измерениях - префиксные суммы по прямоугольнику дают сумму любого подпрямоугольника за константу. И она же встречается в аналитике под именем нарастающего итога.
- инвариант
- условие, которое остаётся верным на каждом шаге цикла. У окна это «внутри окна условие задачи выполнено», и именно его восстанавливает сжатие
Как отвечать: «Найди в массиве два числа с суммой target»
Один проход с хеш-множеством: для каждого x проверяю, встречалось ли раньше число target − x, и если нет, кладу x в множество. O(n) по времени, O(n) по памяти. Альтернатива без дополнительной памяти - два указателя с концов отсортированного массива: сумма мала, двигаю левый, велика - правый. Но сортировка стоит O(n log n) и разрушает исходные индексы. Поэтому сначала уточню два момента: возвращаем сами значения или их индексы, и отсортирован ли массив на входе. От ответов зависит, какое из двух решений правильное.
Два решения с явным разменом времени и памяти плюс уточняющий вопрос до начала кодинга. Именно так ведёт себя сильный кандидат: сужает задачу, а не угадывает, чего от него хотят.
На чём валят
- −Отсортировать массив и потерять индексы, когда в ответе нужны именно они: сортируй пары «значение и индекс» или решай хешом.
- −Сжимать окно через if вместо while: серия нарушений подряд не снимается, инвариант ломается молча.
- −Применять скользящее окно к суммам с отрицательными числами - монотонности нет, нужны префиксные суммы с хешом.
- −Использовать изменяемый объект как ключ словаря: после изменения ключ теряется в таблице.
- −Менять коллекцию прямо во время итерации по ней: часть элементов пропускается либо интерпретатор падает.
Проверьте себя
Пять вопросов из банка по этой подтеме. Всего их 24, остальные разбираются в тренажёре.
- Приём «два указателя» (two pointers) на отсортированном массиве чаще всего помогает...A)Случайно перемешать массив за O(1)B)Превратить O(n) в O(log n)C)Хранить данные компактнее в памятиD)заменить вложенный цикл O(n²) линейным проходом O(n), двигая указатели с концов к центру
показать ответ и разбор
+D)заменить вложенный цикл O(n²) линейным проходом O(n), двигая указатели с концов к центру// разбор: Классика two pointers: «найти пару с суммой X в отсортированном массиве». Указатели с краёв движутся навстречу: сумма больше X — правый влево, меньше — левый вправо. Один проход O(n) вместо перебора всех пар O(n²). Требует отсортированности или иной монотонности.
- Префиксные суммы (prefix sums) предподсчитывают массив P, чтобы потом...A)Устойчиво сортировать исходный массив за линейное время без сравненийB)Сжимать данные без потерьC)считать сумму любого подотрезка [l,r] за O(1): P[r+1] − P[l]D)Находить медиану за O(1)
показать ответ и разбор
+C)считать сумму любого подотрезка [l,r] за O(1): P[r+1] − P[l]// разбор: P[i] = сумма первых i элементов, строится за O(n). Тогда сумма на [l,r] = P[r+1] − P[l] за O(1). Окупается, когда запросов сумм много: предподсчёт O(n) + m запросов O(1) вместо m·O(n). Для обновлений элементов между запросами нужен уже дерево Фенвика/отрезков.
- Когда set/dict для дедупликации — плохой выбор, и лучше отсортировать и идти two pointers?A)Хеш-множество строго лучше по всем параметрамB)Когда элементов меньше десятиC)Когда важно сохранить именно исходный порядок вставки элементовD)Когда критична память или нужен детерминированный отсортированный вывод: set даёт O(n) доп. памяти и не гарантирует порядок
показать ответ и разбор
+D)Когда критична память или нужен детерминированный отсортированный вывод: set даёт O(n) доп. памяти и не гарантирует порядок// разбор: Хеш-множество тратит O(n) дополнительной памяти и не даёт упорядоченного результата. Если вход уже почти отсортирован, память в дефиците или нужен отсортированный уникальный вывод — сортировка O(n log n) + линейный проход указателями дедуплицирует на месте (O(1) доп. памяти) и сразу отсортированно. Классический трейдоф время↔память.
- Чем массив принципиально отличается от связного списка?A)массив хранит числа, список — произвольные объектыB)массив держит элементы отсортированными, список — как попалоC)доступ по индексу: у массива O(1), у списка O(n) по ссылкамD)массив живёт на стеке, а связный список — в куче
показать ответ и разбор
+C)доступ по индексу: у массива O(1), у списка O(n) по ссылкам// разбор: Массив — непрерывный кусок памяти: мгновенный доступ по индексу, но вставка в середину сдвигает хвост. Связный список — узлы со ссылками: вставка у известного узла O(1), но до k-го элемента идти по цепочке. Выбор: частый доступ по индексу — массив; частые вставки при известной позиции — список.
- Почему вставка элемента в начало динамического массива (list, ArrayList) стоит O(n)?A)массиву нужно пересчитать хеши всех элементовB)перед каждой вставкой массив удваивает свою ёмкостьC)элементы после вставки приходится пересортироватьD)все элементы сдвигаются на одну позицию вправо
показать ответ и разбор
+D)все элементы сдвигаются на одну позицию вправо// разбор: Динамический массив хранит элементы подряд, и чтобы освободить нулевую ячейку, все n элементов сдвигаются. Поэтому «очередь» на списке с pop(0)/insert(0) в цикле — классическая скрытая квадратичность. Для быстрых операций с обоих концов берут deque — кольцевой буфер с O(1) на концах.
дальше
Теорию прочитали. Навык ставится повторением
В Сеньорчике эта подтема идёт в ежедневных сессиях: движок возвращает её, пока ответы не станут уверенными, и ведёт прогресс отдельно по каждой подтеме. Теория внутри тоже бесплатна, лимит только на количество вопросов в день.