Скользящее окно
на собеседованиях и в работе

Категория

Обзор темы

Уровень

Начальный

Опирается на

Модуль 8: указатели в одну сторону; занятие 7: срезы и полуинтервалы

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

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

§1Задачи на подотрезок на секции

Подотрезок массива — несколько элементов, которые стоят подряд: a[2], a[3], a[4]. В Python это срез a[2:5] из занятия 7. Задачи на подотрезки встречаются на алгоритмической секции с первого этапа. В журнале Яндекс Образования, в статье об алгоритмических собеседованиях, обе типичные задачи секции — про подотрезки.

У массива из n элементов около n²/2 подотрезков, поэтому перебрать их все и для каждого посчитать ответ заново — это O(n²) или дольше. Скользящее окно проходит подотрезки по порядку и пересчитывает ответ по изменению: что вошло в подотрезок и что из него вышло. Первую задачу из цитаты решают одним проходом с текущей длиной подотрезка. Вторую — окном переменной длины со словарём, это тема занятия 10. Окно фиксированной длины, тема этого модуля, — самая простая форма приёма: длина подотрезка задана, и при каждом сдвиге в окно входит ровно один элемент и ровно один выходит.

§2Где окно стоит отдельной темой

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

Раздел LeetCode 75 начинается с окна фиксированной длины: на нём проще всего увидеть, как сумма окна пересчитывается при сдвиге. Задачи на окно переменной длины используют тот же сдвиг, но длина окна в них меняется по условию.

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

У всех задач ниже на LeetCode стоит метка Sliding Window, это проверено по данным сайта. Первые шесть — окно фиксированной длины, остальные используют окно вместе с техниками из следующих занятий.

Задачи 209 и 3 — практика занятия 10, в КТП она записана так: «Решить задачи на минимальный отрезок с суммой не меньше S и подстроку без повторов». Для занятия 9 КТП ставит другие две задачи: «Найти лучший отрезок длины k и максимальное число событий в фиксированном временном окне».

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

Окно фиксированной длины встречается везде, где по ряду значений считают показатель за последние k значений или за последние N секунд.

Число посетителей сайта по часам, сумма за каждые три часа подряд. Первые два значения — nan: для них трёх значений ещё нет.

>>> import pandas as pd
>>> visits = pd.Series([12, 15, 9, 20, 18, 7, 25])
>>> visits.rolling(3).sum().tolist()
[nan, nan, 36.0, 44.0, 47.0, 45.0, 50.0]

>>> from collections import deque
>>> last = deque(maxlen=3)
>>> for x in [5, 1, 4, 2, 8]:
...     last.append(x)
...     print(list(last))
...
[5]
[5, 1]
[5, 1, 4]
[1, 4, 2]
[4, 2, 8]

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

§5Окно и его сдвиг

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

Теперь то же самое точными словами.

Блок ниже показывает окно над списком посещений из §4. Кнопка «сдвинуть окно» делает один сдвиг и показывает, как пересчитывается сумма. Длину окна можно менять. Под лентой два счётчика обращений к элементам списка: сколько их было бы, если считать сумму каждого окна заново, и сколько нужно при сдвиге.

На семи значениях с k = 3 разница небольшая: 15 обращений против 11. Она растёт с длиной окна. Пересчёт с нуля читает k элементов для каждого из n − k + 1 окон, сдвиг — k элементов для первого окна и по два для каждого следующего.

Пересчёт с нуля стоит O(n·k): при k, сравнимом с n, это O(n²). Сдвиг окна стоит O(n) при любом k. Подробно оба способа и замер разобраны в главах 9.3 и 9.7.

§6Окно и два указателя

Границы окна l и r — это два указателя из модуля 8. Оба идут слева направо и назад не возвращаются, как указатели чтения и записи. Отличие в том, что расстояние между ними постоянно: r − l = k на каждом шаге. Поэтому оба указателя сдвигаются вместе, и в коде часто хранят только один из них.

§7Две формы окна

Задачи на окно делятся на две формы по тому, как задаётся длина окна. Форму узнают по условию задачи.

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

Модуль построен так же, как модуль 8: от того, как задачу формулируют и уточняют, к решению, крайним случаям и замеру. Главы 9.1 и 9.2 — про условие, 9.3–9.5 — про сами алгоритмы, 9.6 и 9.7 — про проверку. Глава 9.8 проводит новую задачу через все этапы собеседования, 9.9 собирает ошибки модуля и объяснение решения, 9.10 — практика и домашнее задание, 9.11 — тренажёр в формате собеседования.

1. 9.2 Формулировки и вопросы до решения. Как звучат задачи на окно фиксированной длины и что уточнить до кода.
2. 9.3 Окно и пересчёт за O(1). Сумма каждого среза против сдвига окна, состояние окна, пошаговый прогон.
3. 9.4 Лучший отрезок длины k. Задача КТП: наибольшая сумма и среднее, LeetCode 643, счётчик в окне.
4. 9.5 События во временном окне. Задача КТП: наибольшее число событий за любые N секунд.
5. 9.6 Границы. k = 0, k = 1, k = n, k больше n и неверный k — тесты из контроля КТП.
6. 9.7 Замер. Пересчёт окна против суммы каждого среза на списках разной длины.
7. 9.8 Задача целиком. LeetCode 1423 от условия до проверки в порядке interview canvas, с ориентиром по минутам.
8. 9.9 Ошибки и объяснение решения. Сводка ошибок модуля по симптомам и что говорить интервьюеру.
9. 9.10 Практика и ДЗ. Стартовый набор, тесты, домашнее задание.
10. 9.11 Мок-интервью. Восемь задач на окно по этапам секции: вопросы, примеры, выбор техники, код с тестами, прогон, секундомер.

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