Окно переменного размера
на собеседованиях и в работе

Категория

Обзор темы

Уровень

Начальный

Опирается на

Модуль 9: окно [l, r) и состояние окна; модуль 8: указатели в одну сторону

Зачем это знать

Понимать, какие задачи модуля встретятся на интервью

§1Задачи с условием на подотрезок

В модуле 9 длина подотрезка была записана в условии числом: «отрезок длины k», «за любые 3 часа подряд». В задачах этого модуля длина в условии не названа. Вместо неё задано требование к подотрезку: сумма не меньше порога, все символы разные, нулей не больше двух. Нужно найти самый короткий или самый длинный подотрезок, который это требование выполняет. Обе типичные задачи алгоритмической секции из статьи журнала Яндекс Образования устроены так же.

В первой задаче требование к подотрезку — «каждое следующее число не меньше предыдущего», во второй — «все числа различны». Длина подходящего подотрезка зависит от данных: в одном месте списка он занимает два элемента, в другом — десять. Поэтому окно фиксированной длины здесь не подходит. Нужно окно, у которого границы двигаются по отдельности: правая берёт новые элементы, левая отбрасывает старые, когда требование перестаёт выполняться.

Там же сказано, что оценивают на секции. Каждому пункту этой оценки в модуле соответствует своя глава.

§2Окно переменного размера в программах подготовки

В двух программах подготовки на LeetCode скользящее окно выделено отдельным разделом. В первом разделе на окно переменного размера приходятся две задачи из четырёх, во втором — три. Состав разделов проверен по данным сайта.

Задачи 643 и 1456 из первой программы разобраны в модуле 9. Задачи 209 и 3 из второй программы — практика этого занятия по КТП: «Решить задачи на минимальный отрезок с суммой не меньше S и подстроку без повторов». Задача 209 разобрана в главе 10.4, задача 3 — в главе 10.5.

§3Задачи с собеседований

У всех задач в таблице на LeetCode стоит метка Sliding Window, это проверено по данным сайта. В каждой из них длина подотрезка определяется требованием из третьего столбца. По этому требованию задачу и узнают: если в условии просят самый длинный или самый короткий подотрезок и ставят ограничение на его содержимое, первым проверяют окно переменного размера.

В задачах 209, 713, 1004 и 1493 для проверки требования достаточно одного числа: суммы, произведения или счётчика нулей. В задачах 3, 904, 2958, 424 и 76 нужно знать, сколько раз каждое значение встречается в окне. Для этого в окне ведут словарь «значение → сколько раз встретилось», его называют частотной картой. Задачи модуля идут в этом порядке: сначала окно с суммой, затем окно с частотной картой. Задача 76 уровня Hard в модуль не входит, в таблице она показывает, до какой сложности доходит тот же приём.

§4Где приём работает в программах

Окно, у которого границы двигаются по отдельности, встречается там, где данные идут потоком, а участок, с которым работает программа, ограничен условием.

Дальше в главе используется один пример. В списке записано число заказов интернет-магазина по часам. Нужно найти самый короткий промежуток из часов подряд, за который набралось не меньше 30 заказов. Первый способ — перебрать все подотрезки и проверить сумму каждого.

>>> orders = [5, 8, 3, 12, 20, 6, 22, 9]
>>> segments = [(l, r) for l in range(8) for r in range(l + 1, 9)]
>>> len(segments)
36
>>> good = [(l, r) for l, r in segments if sum(orders[l:r]) >= 30]
>>> len(good)
20
>>> min(good, key=lambda p: p[1] - p[0])
(3, 5)
>>> orders[3:5]
[12, 20]

В списке из восьми элементов 36 подотрезков, у 20 из них сумма не меньше 30. Самый короткий — orders[3:5], два часа с 12 и 20 заказами. Ответ верный. Чтобы его получить, перебор проверил все 36 подотрезков и сумму каждого посчитал заново. У списка из n элементов подотрезков n·(n + 1)/2, поэтому перебор стоит не меньше O(n²). Окно переменного размера находит тот же ответ за один проход.

§5Расширение и сжатие окна

Перед определениями — сравнение из жизни, на котором видно, как двигаются границы окна.

Теперь то же самое точными словами. Окно записывается так же, как в модуле 9, полуинтервалом [l, r). В него входят элементы от a[l] до a[r − 1], длина равна r − l. Новых понятий три.

В блоке ниже решается задача о заказах из §4. Условие допустимости — «сумма окна не меньше S». Кнопка «шаг» сдвигает одну границу: правую, пока сумма меньше порога, и левую, когда сумма порога достигла. Перед каждым сжатием длина окна сравнивается с самым коротким из найденных. Под лентой показано, сколько раз сдвинута каждая граница.

При пороге 30 окно сначала расширяется пять раз подряд, до суммы 48. После этого оно четыре раза подряд сжимается. Перед каждым сжатием окно подходит, и его длина записывается: 5, 4, 3, 2. Окно a[3:5] длины 2 — то же, что нашёл перебор. Правая граница за весь проход сдвинута 8 раз, левая — 7 раз: 15 сдвигов вместо 36 проверок с суммой каждого подотрезка. Порог можно менять кнопками. При пороге 90 подходящего окна нет, потому что сумма всех элементов равна 85.

С ростом списка разница увеличивается: число подотрезков растёт как n², число сдвигов границ — как n.

Способ работает при одном ограничении на данные: числа в списке неотрицательные. Тогда расширение не уменьшает сумму, а сжатие не увеличивает, и по сумме понятно, какую границу сдвигать. С отрицательными числами это правило нарушается. Вопрос о знаке чисел задают интервьюеру до решения, он разобран в главе 10.2, а причина ограничения — в главе 10.3.

§6Сравнение с окном фиксированной длины

Окно переменного размера собрано из уже известных частей. Запись окна полуинтервалом и состояние окна взяты из модуля 9. Два указателя, которые идут в одну сторону с разной скоростью, — из модуля 8. Новое здесь одно: сдвигом левой границы управляет условие допустимости.

Из таблицы следует, что код окна переменного размера отличается от кода модуля 9 одним местом. В главах 9.3 и 9.4 левая граница сдвигалась на каждом шаге без проверки. Здесь на её месте стоит цикл while с условием допустимости. Поэтому в контроле занятия по КТП записано: «Кандидат объясняет условие while и состояние окна».

§7Две постановки задачи

Задачи из таблицы §3 делятся на две группы по тому, что нужно найти: самый короткий допустимый отрезок или самый длинный. От этого зависит, когда окно сжимается и в какой момент записывается ответ.

В первой постановке допустимое окно сжимают, чтобы проверить, останется ли оно допустимым при меньшей длине. Во второй недопустимое окно сжимают, чтобы оно снова стало допустимым, и после этого сравнивают его длину с лучшей. Задача о заказах из §5 относится к первой группе. Две задачи КТП взяты по одной из каждой группы, поэтому после модуля обе постановки разобраны на коде.

§8Карта модуля

Модуль построен так же, как модули 8 и 9: от того, как задачу формулируют и уточняют, к решению, крайним случаям и замеру. Главы 10.1 и 10.2 — про условие, 10.3–10.5 — про сами алгоритмы, 10.6 и 10.7 — про проверку. Глава 10.8 проводит новую задачу через все этапы собеседования, 10.9 собирает ошибки модуля и объяснение решения, 10.10 — практика и домашнее задание, 10.11 — тренажёр в формате собеседования.

1. 10.2 Формулировки и вопросы до решения. Как звучат задачи на окно переменного размера и что уточнить до кода: знак чисел, пустой вход, что вернуть, если ответа нет.
2. 10.3 Условие допустимости, расширение и сжатие. Общая схема прохода, цикл while, почему левая граница не возвращается назад и откуда O(n).
3. 10.4 Минимальный отрезок с суммой не меньше S. Задача КТП, LeetCode 209: перебор, окно, пошаговый прогон.
4. 10.5 Подстрока без повторов и частотная карта. Задача КТП, LeetCode 3: словарь в роли состояния окна.
5. 10.6 Границы. Пустая строка, повторы, один элемент, ответа нет — тесты из контроля КТП.
6. 10.7 Замер. Окно против перебора всех подотрезков на списках разной длины.
7. 10.8 Задача целиком. Новая задача от условия до проверки в порядке interview canvas, с ориентиром по минутам.
8. 10.9 Ошибки и объяснение решения. Сводка ошибок модуля по симптомам и что говорить интервьюеру об условии while.
9. 10.10 Практика и ДЗ. Стартовый набор, тесты, шпаргалка, домашнее задание.
10. 10.11 Мок-интервью. Задачи на окно переменного размера по этапам секции с секундомером.

§9Проверьте себя