Как реализовать алгоритм скользящего среднего с окном k без полного пересчёта массива?

Что проверяют

Понимаете ли вы приём «скользящее окно»: сумма окна обновляется за O(1) при каждом сдвиге, а не пересчитывается заново. Следом обычно спрашивают про потоковый вариант, когда значения приходят по одному, например FPS или задержка запросов на графике, и всего массива нет.

Как отвечать

• бегущая сумма: к сумме прибавляете входящий элемент a[i] и вычитаете выходящий a[i - k]. Среднее записываете, только когда окно заполнено, то есть при i >= k - 1. Итог: O(n) по времени вместо O(n·k) и O(1) дополнительной памяти, не считая результата;
• краевые случаи: k <= 0 или дробное k отвергаете сразу, k > n даёт пустой результат, k === 1 возвращает копию массива;
• потоковый вариант: кольцевой буфер длины k с индексом i % k. При записи из суммы вычитается значение, которое сейчас затирается. В JavaScript под буфер удобно брать Float64Array(k);
• точность: все числа в JS это double, и на длинном потоке бегущая сумма накапливает ошибку округления. Помогает периодический полный пересчёт окна или суммирование Кэхэна. Для целых значений проблемы нет, пока сумма не выходит за Number.MAX_SAFE_INTEGER.

Код на TypeScript укладывается в несколько строк: sum += a[i]; if (i >= k) sum -= a[i - k]; if (i >= k - 1) out.push(sum / k);. Хорошо добавить, чем это отличается от экспоненциального сглаживания: там окно не хранится вовсе, но старые значения влияют на результат с убывающим весом бесконечно долго.

Где спотыкаются

Пишут «оптимизированный» вариант через a.slice(i - k + 1, i + 1).reduce(...) на каждой итерации. Это тот же полный пересчёт окна, только спрятанный за методами массива.

В потоковой версии держат окно в обычном массиве и выкидывают старое значение через shift(). В общем случае это линейная операция, и на большом окне весь выигрыш бегущей суммы съедается сдвигом элементов.

Делят на k, пока окно ещё не набралось, и получают заниженные первые значения. Если по условию нужно среднее и для неполного окна, делить надо на фактическое число элементов, и об этом лучше договориться с интервьюером до того, как писать код.