Sliding Window And Streaming Statistics
Asked of: Machine Learning Engineer
Last updated

What's being tested
Sliding-window streaming statistics test whether you can maintain aggregates over the last k items without recomputing from scratch. Expect efficient data-structure choices for moving average, minimum/maximum, median, and adjacent array/matrix basics like diagonal checks or BFS path reconstruction.
Patterns & templates
-
Fixed-size sliding window — use
dequeplus runningsum;next(x)isO(1)time,O(k)space. -
Moving average — add new value, evict oldest when size exceeds
k, returnsum / len(window); watch integer overflow. -
Sliding minimum/maximum — use monotonic deque storing indices; each element enters/exits once, so total
O(n)time. -
Sliding median — use two heaps: max-heap lower half, min-heap upper half; rebalance sizes after insert/delete.
-
Lazy deletion for heaps — maintain
delayed[value]counts because arbitrary heap removal is notO(log k)in Python. -
Matrix diagonal / Toeplitz check — verify
matrix[r][c] == matrix[r-1][c-1];O(mn)time,O(1)space. -
2D pathfinding — use BFS for shortest unweighted path; store
parent[(r,c)]to reconstruct path after reaching target.
Common pitfalls
Pitfall: Recomputing
sum(window)or sorting each window givesO(nk)orO(nk log k)and usually misses the intended solution.
Pitfall: Median implementations often fail on duplicates unless deletion is counted by value and heap sizes track only valid elements.
Pitfall: Returning average over
kbefore the stream haskelements; usually divide by current window length unless specified otherwise.
Practice these
The practice cards below cover the canonical variants — solve all of them and time yourself.
Featured in interview prep guides
Practice questions
- Implement bounds, minimum, pathfinding, and moving averageMeta · Machine Learning Engineer · Onsite · Medium
- Solve matrix components, median, and traversalsMeta · Machine Learning Engineer · Technical Screen · Medium
- Check diagonal and compute window statisticsMeta · Machine Learning Engineer · Technical Screen · Medium
- Compute sliding-window mediansMeta · Machine Learning Engineer · Technical Screen · Medium
- Implement sliding-window moving averageMeta · Machine Learning Engineer · Technical Screen · Medium
- Solve matrix diagonal and sliding-window statisticsMeta · Machine Learning Engineer · Technical Screen · Medium
Related concepts
- Intervals, Sliding Windows, And Time-Ordered StateCoding & Algorithms
- Streaming, Large Inputs, And External MemorySoftware Engineering Fundamentals
- Real-Time Top-K And Streaming AnalyticsSystem Design
- Sliding Window Counters And QPSCoding & Algorithms
- Stateful Stream Processing And Time SchedulingCoding & Algorithms
- Top-K Queries And Streaming AggregationCoding & Algorithms