Katkat
Back

Maintain a Fixed-Window Rolling Mean in Constant Time

Jump TradingQuantitative Researcher · Onsite
MediumQuantitative ResearcherOnsiteCoding & Algorithms

Last updated

Implement an efficient sliding-window mean calculation over a stream or sequence of signed integers. Tests sliding window mechanics, constant-time updates, handling integer overflow, and edge cases.

Problem Statement

In quantitative trading pipelines, high-frequency tick and bar data require computing moving indicators with minimal latency.

Implement the function rolling_means(values: list[int], window: int) -> list[float] that takes a sequence of signed integers and an integer window size window, and returns a list of 64-bit floating-point means for each complete consecutive window of size window.

Your solution must update the window sum in O(1) time per element, achieving overall O(n) time complexity.

Function Signature

def rolling_means(values: list[int], window: int) -> list[float]:
    ...

Constraints

  • 0 <= len(values) <= 10^7
  • 1 <= window <= 10^7
  • Each element x in values satisfies -2^63 <= x <= 2^63 - 1 (standard 64-bit signed integer range).
  • If len(values) < window, return an empty list [].

Examples

Example 1:

Input: values = [1, 3, -1, -3, 5, 3, 6, 7], window = 3
Output: [1.0, -0.3333333333333333, 0.3333333333333333, 1.6666666666666667, 4.666666666666667, 5.333333333333333]

Explanation:
- Window [1, 3, -1] -> sum = 3, mean = 3 / 3 = 1.0
- Window [3, -1, -3] -> sum = -1, mean = -1 / 3 = -0.3333333333333333
- Window [-1, -3, 5] -> sum = 1, mean = 1 / 3 = 0.3333333333333333
- Window [-3, 5, 3] -> sum = 5, mean = 5 / 3 = 1.6666666666666667
- Window [5, 3, 6] -> sum = 14, mean = 14 / 3 = 4.666666666666667
- Window [3, 6, 7] -> sum = 16, mean = 16 / 3 = 5.333333333333333

Example 2:

Input: values = [10, 20], window = 3
Output: []

Explanation:
The array length is smaller than the window size, so no complete window exists.

Edge Cases to Consider

  1. window == 1: The result should equal each element converted to float.
  2. window == len(values): The result contains exactly one mean.
  3. Large integers: In statically typed environments (like C++ or Java), intermediate sums of 64-bit integers can overflow standard 64-bit integer registers (int64_t). Consider how you would guard against or handle intermediate sum overflow in production systems.

Hints

Hint 1

Compute the sum of the first `window` elements first, then update the running sum by adding the incoming element and subtracting the outgoing element at each step.

Hint 2

Make sure you handle edge cases where `len(values) < window` by returning an empty list early.

Hint 3

In lower-level languages like C++, accumulating multiple large 64-bit integers can overflow `int64_t`; consider computing the running sum using `double` or using incremental mean formulas like Welford's algorithm if overflow is possible.

Follow-up questions

  • If values arrive as a real-time infinite stream via an API instead of an in-memory list, how would you design an object-oriented class `RollingMean` with `add(val: int) -> float | None`?
  • When accumulating floating-point numbers over millions of updates, standard sliding window addition and subtraction accumulates catastrophic cancellation and drift. How would you prevent numerical drift?
  • How would you extend this approach to maintain the rolling variance or standard deviation in O(1) time per step?