Алгоритмы с нуля
Массивы и строки: тест с выбором ответа
Суть Синтез юнита «Массивы и строки» в формате выбора: цена непрерывности, two pointers, sliding window, prefix sum, запись in-place и ловушка конкатенации строк.
Высота — путь к senior
НольJuniorMiddleSenior
Ты на middle-высоте — в небеШесть вопросов через весь юнит. Каждый — это выбор, который ты делаешь у доски или на код-ревью: не определение для зубрёжки, а правильный приём и то условие, на которое он молча опирается.
Цель
Убедись, что связываешь модель стоимости непрерывного массива с приёмами поверх неё — two pointers, sliding window, prefix sum, запись in-place и строки-как-массивы — и узнаёшь предусловие, которое каждый из них тихо предполагает.
Викторина
Completed
Профайлер показывает горячий цикл, который на каждый запрос вставляет по индексу 0 в массив из 1M элементов. Почему это узкое место и какой правильный фикс?
Heads-up Индексация — O(1) независимо от размера: address = base + i × element_size, без сканирования. Здесь цена — это сдвиг, который навязывает вставка в начало, а не сам доступ.
Heads-up Сортировка не меняет цену вставки — вставка в середину или начало отсортированного массива всё равно сдвигает O(n) элементов. Сортировка помогает поиску, а не вставке.
Heads-up O(1) амортизированно — только у append. Вставка в начало или середину — O(n) из-за сдвига, как бы массив ни рос.
Викторина
Completed
Ты применяешь two pointers с концов (two-sum) для поиска пары с заданной суммой, но он пропускает пары, которые ты видишь глазами. Самая вероятная причина?
Heads-up Сходящийся проход рассматривает все жизнеспособные пары за один проход и не останавливается после первой. Дефект — запуск на неотсортированном входе, где правило движения больше не отслеживает направление суммы.
Heads-up Оба с индекса 0 — это форма same-direction (fast/slow) для уплотнения in-place. Two-sum требует схождения с концов; баг — отсутствие предусловия сортировки, а не стартовые позиции.
Heads-up Two pointers — O(n): каждый указатель сдвигается не более n раз. Тут он не «зависает» — он возвращает неверные ответы, потому что нарушено предусловие сортировки.
Викторина
Completed
Для «наименьший подмассив с суммой ≥ target» на положительных целых вариативное окно (sliding window) работает за O(n), хотя внутри есть вложенный while. Почему это не O(n²)?
Heads-up Внутренний цикл может прокрутиться много раз на одном шаге и ноль раз на другом. Оценка O(n) идёт из того, что суммарное движение left вперёд ≤ n за весь прогон, а не из ограничения на итерацию.
Heads-up Это вариативное окно — его длина меняется. Окно фиксированного размера — другая форма; здесь оценка O(n) держится на том, что left и right каждый сдвигаются вперёд не более n раз суммарно.
Heads-up Sliding window работает на неотсортированных массивах и сохраняет внутренний цикл сжатия. Оценка амортизирована по монотонному движению указателей только вперёд, а не из-за сортировки.
Викторина
Completed
Сервис отвечает на тысячи запросов суммы на диапазоне по логу фиксированной длины. Сейчас каждый запрос проходит диапазон. Когда предвычисление prefix sum — правильный выбор и чего оно стоит?
Heads-up Prefix sum ускоряет только запросы вида «сумма на диапазоне» на статичном массиве. Он ничего не даёт для вставки, поиска или поэлементного обновления, а любое изменение элемента вынуждает O(n)-перестройку.
Heads-up Построение — O(n) однократно, но амортизируется по тысячам O(1)-запросов. При большом q предвычисление многократно окупается.
Heads-up Prefix sum не требует сортировки — он работает на любых значениях, включая отрицательные. Единственное реальное требование — массив остаётся статичным между запросами.
Викторина
Completed
Ревьюер отмечает, что твой in-place «удалить все нули» через write-указатель мутирует массив вызывающего, ломая последующее чтение оригинала. Как правильно сформулировать компромисс?
Heads-up Построение нового массива — это альтернатива с O(n) памяти, а не починка бага. Подход с write-указателем корректен; вопрос — в контракте, может ли вызывающий сохранять оригинал.
Heads-up Преимущество — память (O(1) вспомогательной), а не гарантированная скорость. Реальный компромисс — сэкономленная память против перезаписи исходного входа.
Heads-up Направление не отменяет мутацию — любое уплотнение in-place перезаписывает ячейки. Чтобы сохранить оригинал, копируй его заранее, а не меняй направление прохода.
Викторина
Completed
Функция собирает большой CSV через result += line внутри цикла по n строкам и неожиданно медленна на масштабе. Что происходит и какой фикс?
Heads-up Сама конкатенация — O(n²): каждый += копирует всю строку целиком. Даже без ввода-вывода квадратичное копирование доминирует на масштабе.
Heads-up Индексация и length — O(1). Цена — повторные полные копии, которые навязывает неизменяемость на каждом +=, а не доступ к индексу или длине.
Heads-up + и += делают одно и то же выделение-и-копирование на неизменяемых строках — оба O(n²) в цикле. Фикс — push в массив плюс один join, а не другой оператор.
Итог
Сквозная линия юнита — одна модель стоимости и приёмы, что её используют. Непрерывность даёт O(1) индексацию, но O(n) сдвиги, поэтому вставка в начало/середину — ловушка, а append дёшев. Two pointers превращают вложенный перебор пар в один проход — но two-sum с концов требует отсортированного входа. Sliding window — O(n), потому что указатели идут только вперёд. Prefix sum меняет O(n) памяти на O(1) запросы по диапазону на статичных данных. Запись in-place покупает O(1) памяти ценой оригинала. А строки — это массивы с одним укусом: неизменяемость делает конкатенацию в цикле O(n²) — складывай в массив и join.