Алгоритмы с нуля
Списки, стеки, очереди: тест с выбором
Суть Синтез по юниту в формате выбора: cost model linked list, манипуляция pointer, дисциплина LIFO/FIFO, реализация deque и амортизационный аргумент monotonic stack.
Высота — путь к senior
НольJuniorMiddleSenior
Ты на middle-высоте — в небеШесть вопросов через весь юнит. Каждый — это решение, на которое давит интервьюер: не определение для пересказа, а cost model, которую надо защитить, и выбор реализации, который надо обосновать.
Цель
Убедись, что умеешь связать раскладку linked list в памяти с его cost model, рассуждать о манипуляции pointer не теряя узлов, выбирать правильную дисциплину LIFO/FIFO под задачу и объяснять, почему monotonic stack линеен несмотря на внутренний цикл.
Викторина
Completed
Нагрузка делает push в голову 10 000 раз, а затем 100 раз читает по индексу в случайных позициях. Надо выбрать array vs singly linked list. Что быстрее в сумме и почему?
Heads-up Массивы выигрывают только на индексации и локальности кэша. Здесь нагрузка — это вставки в голову, а это ровно сила linked list O(1) против O(n)-сдвига массива.
Heads-up Оба поддерживают операции, но стоимости различаются на порядок: массив платит O(n) за вставку в голову, linked list — O(1). Доминирует именно 10k вставок в голову.
Heads-up Вывод верный, но причина неверна. Доступ по индексу у linked list — O(n): нет формулы адреса, надо перепрыгивать по pointer. Linked list выигрывает на вставках в голову, а не на индексации.
Викторина
Completed
Ты пишешь in-place разворот singly linked list. Коллега пишет внутри цикла current.next = prev; current = current.next;. Что ломается?
Heads-up Стандартный цикл сначала сохраняет преемника: const next = current.next; current.next = prev; prev = current; current = next;. Пропуск сохранения портит обход, потому что ты перезаписал нужный pointer.
Heads-up Утечки нет — GC соберёт недостижимые узлы. Баг логический: обход идёт в неправильную сторону, потому что pointer на преемника уничтожен до сохранения.
Heads-up Падает на любом нетривиальном списке. Как только ты перезаписал current.next и затем читаешь его, ты идёшь по развёрнутому pointer назад в prev вместо продвижения вперёд.
Викторина
Completed
Ты постоянно вставляешь и удаляешь в голове singly linked list и всё время натыкаешься на null-pointer спецслучаи для пустого списка и позиции головы. Какой самый чистый структурный фикс?
Heads-up Back pointer помогает с O(1)-доступом к предшественнику, но не убирает спецслучаи головы/пустоты — ты всё равно ветвишься по тому, null ли head. Sentinel убирает ветку, гарантируя предшественника.
Heads-up Глушение ошибки прячет баг, а не чинит логику. Структурный фикс — sentinel-узел, чтобы ссылка на предыдущий узел всегда была валидна.
Heads-up Счётчик не объединяет пути кода для операций над головой и серединой. Именно sentinel делает 'вставку в голову' идентичной 'вставке в середину'.
Викторина
Completed
Ты валидируешь вложенные скобки в парсере конфигов и отдельно делаешь обход дерева в порядке уровней (в ширину). Какие структуры подходят и почему?
Heads-up Stack на дереве даёт обход в глубину, а не по уровням. Обход по уровням требует FIFO, чтобы дети узла ждали позади всех уже добавленных узлов текущего уровня — это queue.
Heads-up Queue на скобках вытолкнула бы самую старую открытую скобку первой — это обратно вложенности. Сопоставлению скобок нужна дисциплина 'последний-первым' у stack.
Heads-up Ровно наоборот. Вложенность — это последний-открыт-первым-закрыт (stack); обход в ширину — порядок прибытия (queue). Перестановка даёт неправильный обход и неправильную валидацию.
Викторина
Completed
Ты реализуешь FIFO queue на массиве JavaScript: push для enqueue и shift для dequeue. Под устойчивым потоком из N пар enqueue+dequeue какова суммарная стоимость и фикс?
Heads-up push амортизированно O(1), но shift — O(n): удаление индекса 0 сдвигает каждый последующий элемент на слот вниз. N dequeue над растущим массивом суммируются в O(N^2).
Heads-up Здесь нет ничего логарифмического. shift линеен по длине массива, а сумма линейных стоимостей по N операциям даёт квадрат, а не N log N.
Heads-up Правильный deque (doubly linked list или circular buffer) — O(1) с обоих концов, но массив с shift — это не он: shift всё равно переиндексирует. Смысл в том, чтобы перестать использовать shift.
Викторина
Completed
Решение next-greater-element на monotonic stack имеет цикл while внутри for, но это O(n), а не O(n^2). В чём точный аргумент?
Heads-up Внутренний цикл может попнуть много элементов за один внешний шаг (высокий элемент чистит длинную серию). Это не константа на шаг — граница глобальна: каждый элемент попается максимум один раз за весь прогон.
Heads-up Ничего не сортируется; stack поддерживает монотонное подмножество внутри. Линейная граница идёт от того, что каждый элемент входит и выходит из stack один раз, а не от сортировки.
Heads-up Никакого деления пополам нет. Посещается каждый элемент; эффективность идёт от инварианта push-once/pop-once, который ограничивает суммарные операции stack величиной 2n.
Итог
Сквозная линия юнита — одна cost model и три дисциплины. Раскладка в памяти задаёт стоимость: непрерывность покупает O(1)-индексацию, разбросанность — O(1)-вставку в голову; выбираешь по доминирующей операции. Манипуляция pointer — это сохранять связи до перезаписи и использовать sentinel, чтобы стереть спецслучаи головы. Stack (LIFO) и queue (FIFO) — это дисциплины, а не структуры данных: выбирай по тому, нужен ли тебе последний-первым или порядок прибытия, и никогда не делай dequeue через shift. Monotonic stack — это выигрыш: stack плюс инвариант порядка превращают O(n^2)-скан в O(n) по аргументу push-once/pop-once.