A real-time SLA monitor ingests 500,000 latency samples/sec per shard and must emit the exact rolling maximum latency over the last `k = 10,000` samples (and in a variant, over a `W = 5,000 ms` time window). The current implementation uses a max-heap (`PriorityQueue` / `heapq`) with lazy deletion, which grows beyond `100k` stale nodes during bursts and triggers `p99` spikes and GC pauses. Design a strict `O(1)` amortized-per-event sliding window maximum engine.
From patterns to decisions.
A real-time SLA monitor ingests 500,000 latency samples/sec per shard and must emit the exact rolling maximum latency over the last `k = 10,000` samples (and in a variant, over a `W = 5,000 ms` time window). The current implementation uses a max-heap (`PriorityQueue` / `heapq`) with lazy deletion, which grows beyond `100k` stale nodes during bursts and triggers `p99` spikes and GC pauses. Design a strict `O(1)` amortized-per-event sliding window maximum engine.
A lazy-deletion heap never pops.
A lazy-deletion heap never pops expired smaller items until they reach the root, growing to O(N); storing indices lets the deque detect window expiry in O(1).
| Choice | What it buys | What it costs |
|---|---|---|
| Trade-off 1 | Deque achieves O(N) time and <= k space, whereas heap takes O(N log k) time and up to O(N) space. |
Step 1
Trace [100, 99, 98, ...] in a lazy-deletion heap: 100 stays at root for k steps while 99..1 accumulate below.
Step 2
Show that storing (index, value) allows dq[0][0] <= i - k.
Alternative 1
For arbitrary element deletion (non-sliding), a TreeMap or indexed heap is needed.
Failure Mode 1
Using Python list.pop(0) instead of deque.popleft() degrades to O(N*k).
# Monotonically decreasing input [1000, 999, 998, ..., 1] with k=10:
# Lazy heap holds all 1000 nodes until 1000 expires; deque holds at most 10.
Use collections.
Use collections.deque storing (index_or_ts, value) with popleft() for window expiry and pop() for monotonic dominance.
| Choice | What it buys | What it costs |
|---|---|---|
| Trade-off 1 | Strict O(N) total time across N events and <= k memory. |
Step 1
Evict expired front elements (while loop for time-based, if for count-based).
Step 2
Pop back elements <= val to preserve strict decreasing order.
Step 3
Append (key, val) and return dq[0][1].
Alternative 1
In Java, use a primitive long[] / double[] circular ring buffer to avoid GC allocation at 500k/s.
Failure Mode 1
Using if instead of while in push_time leaks expired elements when multiple events share a timestamp.
from collections import deque
class SlidingWindowMax:
def __init__(self, window_size: int) -> None:
self.k = window_size
self.dq: deque[tuple[int, float]] = deque()
self.idx = 0
def push_count(self, val: float) -> float:
if self.dq and self.dq[0][0] <= self.idx - self.k:
self.dq.popleft()
while self.dq and self.dq[-1][1] <= val:
self.dq.pop()
self.dq.append((self.idx, val))
self.idx += 1
return self.dq[0][1]
def push_time(self, ts_ms: int, val: float) -> float:
cutoff = ts_ms - self.k
while self.dq and self.dq[0][0] <= cutoff:
self.dq.popleft()
while self.dq and self.dq[-1][1] <= val:
self.dq.pop()
self.dq.append((ts_ms, val))
return self.dq[0][1]
Using <= evicts older equal.
Using <= evicts older equal maxima immediately because the newer identical value will stay in the window longer—keeping deque size smaller.
| Choice | What it buys | What it costs |
|---|---|---|
| Trade-off 1 | `<=` minimizes memory on flat plateaus; use `<` only if you specifically need the *oldest* index of a tied maximum. |
Compare `[5, 5, 5]` with `k=3`
< keeps all three (0,5),(1,5),(2,5), while <= keeps only (2,5).
Alternative 1
Two-stack queue max algorithm if you prefer a purely functional / immutable approach.
Failure Mode 1
None for max value; only affects index tie-breaking.
# With <= on [5, 5, 5]: deque holds [(2, 5)] (len=1)
# With < on [5, 5, 5]: deque holds [(0, 5), (1, 5), (2, 5)] (len=3)
Implementation & Guardrails (4).
Pre-aggregate incoming events into fixed-width time buckets (e.g., 10 ms tumbling buckets) and run the monotonic deque over those 500 buckets instead of raw events.
| Choice | What it buys | What it costs |
|---|---|---|
| Trade-off 1 | Caps memory at O(W / bucket_ms) with +-10 ms boundary granularity. |
Step 1
Bucket timestamps via bucket_ts = (ts_ms // 10) * 10 and track max per bucket.
Step 2
Feed completed/active buckets into the monotonic deque, capping memory at 5000 / 10 = 500 entries.
Alternative 1
Hard-cap deque length and shed oldest samples during extreme floods.
Failure Mode 1
Unbounded raw-event deque OOMing during DDoS or retry storms.
# 10 ms bucketing bounds 5,000 ms window to <= 500 deque entries regardless of QPS!
Run one local monotonic deque.
Run one local monotonic deque per partition, emit each partition's (bucket_ts, local_max) to an aggregator, and take max across the 16 partition maxima.
| Choice | What it buys | What it costs |
|---|---|---|
| Trade-off 1 | Reduces cross-network fan-in by 500,000x while preserving exactness per aligned time bucket. |
Step 1
Exploit associativity of max(A ∪ B) = max(max(A), max(B)).
Step 2
Aggregate 16 local bucket maxima in O(16) instead of centralizing 8M raw events/sec.
Alternative 1
Apache Flink sliding window with AggregateFunction.
Failure Mode 1
Clock skew across partitions causing misaligned bucket boundaries; use event-time watermarks.
global_max = max(partition_maxes.values()) # 16 values instead of 8M events/s
Theory & Tips and Tricks
Practical heuristics & interview traps
- 01Interview anchor: Store indices in a monotonic decreasing deque, evicting expired front indices and smaller back indices so every element is pushed and popped at most once.
- 02Trade-off tip:
<=minimizes memory on flat plateaus; use<only if you specifically need the oldest index of a tied maximum. - 03Watch out for: Unbounded raw-event deque OOMing during DDoS or retry storms.
Sliding Window Maximum Monotonic Deque — Normal → Load / Fault → Recovery
Store indices in a monotonic decreasing deque, evicting expired front indices and smaller back indices so every element is pushed and popped at most once.
Putting Sliding Window Maximum with a Monotonic Deque Together
Store indices in a monotonic decreasing deque, evicting expired front indices and smaller back indices so every element is pushed and popped at most once.
Putting Sliding Window Maximum with a Monotonic Deque Together
- Evict expired front elements (
whileloop for time-based,iffor count-based). - Pop back elements
<= valto preserve strict decreasing order. - Append
(key, val)and returndq[0][1].
Interview Readiness Check
Pre-aggregate incoming events into fixed-width time buckets (e.g., 10 ms tumbling buckets) and run the monotonic deque over those 500 buckets instead of raw events.
Walk through bottlenecks, back-of-the-envelope math, and failure recovery.
Make the trade-off yourself.
Practice Check
Test your understanding
When is ACID Transaction Fundamentals the right default for a production team?
Sliding Window Maximum with a Monotonic Deque
Store indices in a monotonic decreasing deque, evicting expired front indices and smaller back indices so every element is pushed and popped at most once.
