Алгоритмы на массивах · модуль 9 · скользящее окно
Глава 9.9
Ошибки
и объяснение решения
В этой главе собраны ошибки модуля 9 и то, как решение объясняют интервьюеру. Ошибки разобраны в главах 9.3–9.6, каждая с прогоном ошибочной и исправленной версии. Здесь они сведены в таблицу по симптомам: что видно в ответе, где искать в коде, на каком входе ошибка проявляется и где её прогон. Затем — четыре новые ошибочные версии для самостоятельного поиска, функция с двумя ошибками сразу и фразы, которыми объясняют три вида задач на окно.
- Категория
- Отладка и объяснение
- Уровень
- Средний
- Опирается на
- Главы 9.3–9.8; глава 8.9: ошибки модуля 8
- Зачем это знать
- Находить ошибку окна по симптому и объяснять решение на секции
§1Сводка ошибок по симптомам
Когда тест падает, сначала видно не строку с ошибкой, а неверный ответ. В таблице ошибки модуля сгруппированы по тому, как они выглядят в ответе. По симптому находят строку кода, которую нужно проверить, и вход, на котором ошибку видно. В последнем столбце — где эта ошибка запущена по шагам вместе с исправленной версией.
| Симптом в ответе | Где искать | Вход, который её показывает | Прогон |
|---|---|---|---|
| Первая сумма верная, дальше все неверные | Индекс ушедшего элемента: nums[r − k + 1] вместо nums[r − k] | Любой список длиннее k; при k = 1 все суммы равны первой | 9.3, §8 |
| Сумм на одну меньше, первой нет | Начало ответа: sums = [] вместо sums = [total] | k = n: ответ пустой | 9.3, §8 |
| Все суммы смещены на одно и то же число | Первое окно: sum(nums[:k − 1]) | Любой вход; смещение равно nums[k − 1] | 9.6, §1 |
| Суммы не совпадают ни с одним окном, кроме первого | Начало цикла: range(k + 1, …) | Любой список длиннее k | 9.6, §2 |
| При равных суммах возвращено окно правее | Знак сравнения: >= вместо > | Все окна с одной суммой: [5, 1, 5, 1], k = 2 | 9.4, §5 |
| Лучшая сумма 0, хотя такого окна нет | Начальное значение: best = 0 | Все суммы отрицательные | 9.4, §6 |
| Начало лучшего окна на единицу левее | start = r − k вместо r − k + 1 | Лучшее окно не первое | 9.6, §7, review 2 |
| Первое окно в ответе дважды, последнего нет | Порядок строк: запись до сдвига | Любой список длиннее k | 9.6, §7, review 1 |
| Ответ на неверный k вместо исключения | Нет проверки k < 1 or k > len(nums) | k = 0, k > n, пустой список | 9.6, §2 |
ValueError при допустимом k = n | Проверка k >= len(nums) | k = n | 9.6, §2 |
| В окне по времени на одно событие больше | Условие сдвига: > w вместо >= w | Событие ровно на правой границе: [0, 5], w = 5 | 9.5, §7 |
| В окне по времени на одно событие меньше | Подсчёт: r − l вместо r − l + 1 | Любой непустой список | 9.5, §7 |
Большая часть ошибок связана с одним из двух мест: границей — индексом, знаком сравнения, началом цикла — или начальным значением. Поэтому крайние входы k = 1, k = n, равные суммы, отрицательные числа и событие на границе ловят почти все ошибки таблицы, а обычный пример — только часть.
§2Найдите ошибку
Четыре версии ниже в главах не разбирались. В первых трёх вопросах выберите вход, на котором функция ошибается; на остальных вариантах её ответ верный. Четвёртая функция отвечает верно на любом входе — найдите, что с ней не так. Все ответы проверены запуском.
def window_sums(nums, k):
total = sum(nums[:k])
sums = [total]
for r in range(k, len(nums) - 1):
total += nums[r] - nums[r - k]
sums.append(total)
return sumsПри k = n цикл и так пуст, ответ
[6]верный.Верно. Цикл идёт до
len(nums) − 2, последний элемент в окно не входит. Ответ[3]вместо[3, 5].Одно окно, цикл пуст, ответ
[5]верный.
def best_window(nums, k):
total = sum(nums[:k])
best, start = total, 0
for r in range(k, len(nums)):
if total > best:
best, start = total, r - k
total += nums[r] - nums[r - k]
return (start, best)Лучшее окно
[1, 9]— первое, оно учтено до цикла. Ответ(0, 10)верный.Верно. Сравнение стоит до сдвига, поэтому каждое окно сравнивается на шаг позже, а последнее не сравнивается вовсе. Лучшее окно
[4]последнее, и функция возвращает(0, 3)вместо(2, 4).Лучшее окно первое, ответ
(0, 10)верный. Ошибку видно, только когда лучшее окно последнее.
def max_vowels(s, k):
vowels = set("aeiou")
count = sum(1 for ch in s[:k] if ch in vowels)
best = count
for r in range(k, len(s)):
count += (s[r] in vowels)
best = max(best, count)
return bestОкно одно, цикл пуст, ответ 5 верный.
Гласных нет, счётчику нечего прибавлять, ответ 0 верный.
Верно. Ушедшая гласная не вычитается, и счётчик только растёт: уже на втором окне
"ba"он равен 2, хотя гласная в нём одна.
def max_events(times, w):
best = 0
for r in range(len(times)):
l = 0
while times[r] - times[l] >= w:
l += 1
best = max(best, r - l + 1)
return bestНа пустом списке цикл не выполняется, функция возвращает 0 — это верный ответ.
Верно. Левая граница не монотонна: на каждом шаге она заново проходит все старые события. На замере 4000 событий через секунду эта версия обработала за 186 мс, а верная версия 40 000 событий — за 3,8 мс.
Условие
>= wверное, правая граница открыта. На 5000 случайных входах ответы совпали с верной версией.
Код 4 проходит все тесты max_events, потому что тесты проверяют только ответ. Время работы они не измеряют. Такую ошибку находят review и замер: монотонность указателя — первое, что проверяют в коде окна, глава 9.6, §7.
§3Две ошибки в одной функции
В окне ниже max_events с двумя ошибками из сводки: условие сдвига > w и подсчёт r − l. Исправьте обе. Сначала запустите тесты и посмотрите, какие проходят.
На заготовке тест test_right_edge проходит, хотя в функции обе ошибки. На входе [0, 5], w = 5 строгое сравнение оставляет в окне лишнее событие, а r − l одно событие теряет, и ошибки гасят друг друга. Если исправить только подсчёт, этот тест начинает падать: остаётся ошибка границы. Поэтому после каждой правки тесты запускают заново, и падение нового теста после исправления не значит, что исправление неверное.
§4Как объяснить решение на интервью
Кроме кода интервьюер ждёт рассуждение, по которому видно, что решение верное и почему оно O(n). Для трёх видов задач модуля это укладывается в несколько фраз. Каждая фраза под собой подписана: что она показывает интервьюеру.
Окно фиксированной длины: лучший отрезок
«Сумму первого окна считаю целиком. Дальше окно сдвигаю на одну позицию: прибавляю пришедший элемент и вычитаю ушедший».
Что показываетСостояние окна и его пересчёт за O(1).
«Лучшую сумму начинаю с первого окна: числа бывают отрицательными, и ноль может оказаться больше любого окна. Сравниваю строго, чтобы при равных суммах осталось самое левое окно».
Что показываетНачальное значение и знак сравнения выведены из условия.
«Окон n − k + 1, каждое после первого — две операции. Время O(n), память O(1). Неверный k проверяю в начале».
Что показываетОценка сложности и граничные входы.
Окно по времени: события
«r идёт по событиям. Пока самое старое событие окна дальше чем на w от нового, сдвигаю l. Окно полуоткрытое, поэтому сравниваю через «больше или равно»».
Что показываетПравило сдвига и граница окна.
«While внутри for, но l только растёт и не обгоняет r. Всего сдвигов не больше 2n — это O(n)».
Что показываетМонотонность указателя и верная оценка вложенного цикла.
Окно, которого нет в условии: карты с краёв
«Взятые карты по краям, значит, оставшиеся — отрезок подряд длины n − k. Сумма взятых — общая сумма минус оставшиеся».
Что показываетСведение задачи к известной технике.
«Ищу окно длины n − k с наименьшей суммой обычным сдвигом. При k = n окно пустое, ответ — сумма всех карт».
Что показываетГотовое решение применено к новой задаче, крайний случай назван.
Во всех трёх случаях порядок одинаковый: что хранится в состоянии окна, как оно меняется при сдвиге, почему указатели не возвращаются и что происходит на границах. Этот порядок совпадает с чек-листом review из главы 9.6, §7.
§5Проверьте себя
Вопрос 1Тест best_window([-5, -2, -8, -1], 2) вернул (0, 0). Какую строку проверить первой?
Верно. Сумма 0 не принадлежит ни одному окну: так бывает, когда
bestначинается с 0, а все суммы отрицательные.Знак сравнения меняет выбор между равными окнами, но не создаёт сумму, которой нет.
Неверный индекс даёт неверные суммы окон, но не ноль на месте отрицательной суммы при верном начале.
Вопрос 2Что интервьюер ждёт услышать о вложенном while в задаче о событиях?
Это неверная оценка. При монотонной левой границе вложенный цикл даёт O(n).
Верно. Это обоснование оценки O(n) через монотонность указателя.
В задаче о событиях нет k: длина окна задана временем, и за один шаг while может выполниться много раз.