Problem 96 · Data Engineering & Streaming

Tumbling and Sliding Window Aggregation

MediumClassic DSA & systems

01Problem

Given (timestamp, value) events, compute per-window sums for tumbling windows of a given size and for sliding (hopping) windows of a given size and slide.

02Key insight

Tumbling: window start = floor(ts/size)*size, each event in exactly one window. Sliding: each event belongs to size/slide windows whose starts are multiples of slide in (ts-size, ts]; compute that range arithmetically instead of scanning windows. Use event time, not arrival order.

03Solution

solution.pypython21 lines

from collections import defaultdict
from typing import Iterable


def tumbling_sum(events: Iterable[tuple[int, float]], size: int) -> dict[int, float]:
    out: dict[int, float] = defaultdict(float)
    for ts, value in events:
        out[(ts // size) * size] += value
    return dict(sorted(out.items()))


def sliding_sum(events: Iterable[tuple[int, float]], size: int, slide: int) -> dict[int, float]:
    if size % slide:
        raise ValueError("size must be a multiple of slide")
    out: dict[int, float] = defaultdict(float)
    for ts, value in events:
        # window [s, s+size) contains ts  <=>  ts - size < s <= ts, s multiple of slide
        first = ((ts - size) // slide + 1) * slide
        for start in range(first, (ts // slide) * slide + 1, slide):
            out[start] += value
    return dict(sorted(out.items()))

Try it first.

TimeO(n * size/slide)

SpaceO(#windows)

tests.py · 4 passing

tests.pypython5 lines

events = [(1, 1), (2, 2), (5, 3), (11, 4)]
assert tumbling_sum(events, 5) == {0: 3, 5: 3, 10: 4}
assert sliding_sum(events, 10, 5) == {-5: 3, 0: 6, 5: 7, 10: 4}
assert sliding_sum(events, 5, 5) == tumbling_sum(events, 5)  # slide == size is tumbling
assert tumbling_sum([(9, 1), (0, 1)], 10) == {0: 2}          # out-of-order is fine

04Staff-level follow-up

In a real stream when do you emit a window and drop its state? When the watermark (max event time minus allowed lateness) passes window end; late events after that go to a side output. For huge size/slide ratios, aggregate per slide 'pane' once and combine panes to avoid O(size/slide) updates per event.