How do you write streaming computations in code?

In this article

1. Before you start
2. Why interviewers ask this
3. Streaming computations in code from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page is one step of the coding interview questions learning path.

Why interviewers ask this

A solution that stores every event and recomputes from scratch works on a ten-line example and fails on a real feed, so streaming questions separate candidates who think about state from those who think about arrays. Candidates report questions of this kind: a rolling 7-day transaction count per user, a sliding-window anomaly detector in Python, the k largest elements of a running list, and a running recommendation list with recency weighting.

A weak answer re-sums the window on every event, or keeps a list that grows forever. A strong answer names the state it keeps per key, says what each event costs, and says what breaks, such as evicting a maximum or an event arriving late. A Staff-level answer also checks the numbers: the variance formula is numerically safe, the window boundary is half-open, and a spike does not hide the next spike.

Streaming computations in code from first principles

Streaming computation

A streaming computation is an algorithm that reads each event of a stream once, updates a small fixed state, and reports a result after every event, so its memory does not grow with the length of the stream, as with a rolling count per user.

Welford's update

Welford's update is a single-pass rule that keeps a count, a running mean and a running sum of squared distances from that mean, giving the variance after every event with constant memory and without subtracting two huge numbers; a matching removal step lets it cover a sliding window too.

Exponentially weighted moving average

An exponentially weighted moving average (EWMA) is a running score, s_t = λ·x_t + (1−λ)·s_(t−1), that blends each new value with the previous score, so the weight of an old value shrinks by the same factor at every step, and a larger λ forgets faster.

In plain words

Think of a shop assistant who tracks today's takings with a tally on a notepad. At each sale they update the tally. They never copy out every receipt and add them all up again. A streaming computation is that tally: the notepad is the state, and each sale is an event.

The analogy breaks in one place. A tally only grows, but many questions ask about the last seven days, so the assistant must also cross out old sales. Crossing out is easy for a sum and hard for a maximum.

In one precise sentence: a streaming computation keeps a state S and a rule that turns (S, new event) into (S', result), where the size of S stays fixed or is bounded by the window.

Step 1: Welford's update keeps a running mean and variance

Welford's update keeps three numbers: the count n, the mean, and a running total called M2 of squared distances from the mean. For each value x, set delta = x − mean, add delta / n to the mean, then add delta · (x − new mean) to M2. The variance is M2 / n for a population or M2 / (n − 1) for a sample. The method comes from Welford (1962).

The tempting alternative stores the sum and the sum of squares, then computes the mean of squares minus the square of the mean. With values near one billion, that subtraction cancels away every useful digit. For the four values 1,000,000,004, 1,000,000,007, 1,000,000,013 and 1,000,000,016, the true population variance is 22.5; the naive formula in 64-bit floating point returns −128.0, a negative variance, and Welford's update returns 22.5.¹ You now know how to keep statistics over the whole stream; the next step limits them to a recent window.

Step 2: A deque holds a sliding window of counts and sums

A deque (double-ended queue) is a sequence that adds and removes items at either end in constant time, as the Python documentation for undefined describes. A deque created with maxlen also drops items from the opposite end when it is full, so a count-based window of the last w values maintains itself. This is the sliding window idea applied to a feed.

For a running sum, subtract the value that is about to fall out, then add the new one. For a time-based window, such as rolling 7-day velocity, append the timestamp and pop from the left while the oldest is no longer inside the window:

from collections import deque, defaultdict

SPAN = 7 * 24 * 3600  # seven days in seconds

class Velocity:
    def __init__(self, span):
        self.span = span
        self.stamps = deque()

    def add(self, t):               # t must not go backwards
        self.stamps.append(t)
        while self.stamps[0] <= t - self.span:
            self.stamps.popleft()   # evict the old
        return len(self.stamps)     # events in (t - span, t]

users = defaultdict(lambda: Velocity(SPAN))   # one deque per user

Each event is appended once and popped at most once, so the cost per event is constant on average. Recomputing a 1,000-event window for 1,000,000 events costs 1,000,000,000 additions; the incremental update costs 2,000,000 operations, 500 times fewer.¹ A undefined creates each user's deque on first sight.

Step 3: An exponentially weighted average adds recency

An EWMA keeps one recency-weighted number per key instead of a window. With λ = 0.3, the newest event has weight 0.3, the one before it 0.21, then 0.147, 0.1029 and 0.072; the weight k steps back is λ(1−λ)^k, and the first ten weights sum to 0.9718.¹ The National Institute of Standards and Technology (NIST) handbook describes the same recursion for control charts.

For the series 10, 12, 11, 20, 12 the score runs 10, 10.6, 10.72, 13.504 and 13.0528: the spike of 20 lifts the score by about 2.8 and then fades.¹ A larger λ reacts faster and forgets faster.

For a running recommendation list, keep a score per item that decays with time, not with the event count, because recency is usually a rate per hour, while the λ above is a rate per event. Store (score, last_time) per item in a dictionary. When an event for an item arrives at time now, set the score to score · exp(−r · (now − last_time)) + weight, where r is the decay rate you choose, and set last_time to now. Other items are untouched until they are read, so the decay is lazy. A variant called forward decay instead adds weight · exp(r · t), so no stored score is ever rewritten and the order stays comparable.

With four illustrative events and r = 0.2 per hour, the scores decayed to hour 10 are 0.6703 for item c, 0.5847 for item a and 0.2019 for item b.¹ Read the top k with heapq.nlargest(k, scores.items(), key=...) at query time, which costs about n log k for n items. A plain size-k heap, as in K closest points to origin, does not fit here, because an item's score changes after it was pushed. If the list is read on every event, use a heap with lazy deletion that skips stale entries. The trade-off: the query-time scan is simple and exact, and an always-fresh top-k costs extra memory and bookkeeping.

Step 4: A rolling z-score turns the window into an anomaly detector

A z-score is the distance of a value from the window mean, measured in standard deviations. A sliding-window anomaly detector keeps the last w values in a deque, computes the mean and standard deviation of those values, and flags a new value when its absolute z-score passes a threshold such as 3. Check the value before you append it, so the point being tested does not help judge itself, and guard against a standard deviation of zero.

Recomputing the mean and standard deviation over the window at every event costs time that grows with the window size w. Welford's update does it in constant time if it can also remove a value. When the oldest value old leaves a window, subtract one from n, set delta = old − mean, subtract delta / n from the mean, then subtract delta · (old − mean) from M2, using the new mean in the last step. On the series below, this add-and-remove state matches the standard deviation recomputed with statistics.pstdev at every check, to within float rounding.¹

from collections import deque
from math import sqrt

class Detector:
    def __init__(self, w, limit=3.0):          # w must be at least 2
        self.w, self.limit, self.win = w, limit, deque()
        self.n, self.mean, self.m2 = 0, 0.0, 0.0

    def push(self, x):
        sd = sqrt(max(self.m2, 0) / self.n) if self.n else 0.0
        flag = self.n == self.w and sd > 0 and abs(x - self.mean) / sd > self.limit
        if self.n == self.w:                    # remove the oldest value
            old = self.win.popleft(); self.n -= 1
            d = old - self.mean
            self.mean -= d / self.n; self.m2 -= d * (old - self.mean)
        self.win.append(x); self.n += 1         # add the new value
        d = x - self.mean
        self.mean += d / self.n; self.m2 += d * (x - self.mean)
        return flag

On the illustrative series 10, 11, 9, 10, 12, 10, 11, 30, 10, 11 with a window of 6, the value 30 meets a mean of 10.5 and a standard deviation of 0.9574, a z-score of 20.37, and is flagged; the detector above flags the same single point.¹ The catch is masking. The 30 stays in the window for the next six checks. The next window contains it, with mean 13.6667 and standard deviation 7.3636, so a following 10 scores −0.5.¹

A second spike of 20 at that point would score a z-score of 0.86 and pass, against 11.75 if the 30 had been left out of the window.¹ There are two fixes. Keep flagged points out of the window state, at the price that a real, lasting level shift is then never learned. Or use the median and the median absolute deviation (MAD), which one outlier barely moves.

1 · Running variance2 · Window deque3 · EWMA score4 · z-score checkReplay

Step-by-step description

1. Welford's update keeps count, mean and M2.
2. Old events are popped from the left.
3. One number weights recent events more.
4. The window state flags an outlier.

• Welford's update keeps a count, a mean and a running sum of squared distances.
• A deque holds the window of recent events.
• An EWMA keeps one recency-weighted number per key instead of a window.
• A z-score check flags a value that is far from the window mean.

Worked example

Every number below comes from one script run on illustrative inputs. The event times for one user are, in hours: 0, 5, 30, 50, 100, 150, 170, 180, 200, 340 and 350, and the window is 168 hours (seven days). After each event the deque holds the events newer than the window start, so the counts are 1, 2, 3, 4, 5, 6, 6, 6, 6, 3 and 3.¹ At hour 170 the event at hour 0 is evicted; at hour 340 the cutoff is hour 172, so only the events at 180, 200 and 340 remain.¹

Across the 11 events the deque did 11 appends and 8 evictions, 19 operations in total, about two per event.¹

The recompute cost is n times w, the event count times the window size; the incremental cost is a constant per event, so n times two.¹ A top-3 over the stream 5, 1, 9, 3, 7, 8, 2, 10 keeps 10, 9 and 8, which matches heapq.nlargest.¹

Text description of the diagram

• The EWMA weight of the newest event is 0.3.
• The weight four steps back is 0.072.

Trade-offs and edge cases

The question decides the structure. A deque handles window sums by adding and subtracting what enters and leaves. A maximum cannot: when the current maximum is evicted, the next largest value is unknown unless you kept it. The answer is a monotonic deque. A monotonic deque is a deque of indexes whose values decrease from front to back, which handles window maxima and is the idea of a monotonic stack with a second open end. On the array 1, 3, 2, 5, 4, 2, 1, 6 with a window of 3 it returns 3, 5, 5, 5, 4, 6, equal to the brute-force answer.¹

A top-k of everything seen so far uses a min-heap, a heap whose root is the smallest item. Keep k items; a new value larger than the root replaces it with heappushpop, as the undefined documentation describes. A max-heap would put the wrong item at the top.

Text description of the diagram

• A deque handles window sums by adding and subtracting.
• A monotonic deque handles window maxima.
• A min-heap of size k handles the top-k of a stream.

Edge cases: a sliding window can count items or measure time, so ask which. A tumbling window is a fixed block that does not overlap the next, and a sliding window moves with every event. Make the boundary half-open and state it. Late or out-of-order events break the pop-from-the-left rule, so buffer and sort them first, or say what lateness you tolerate. A running float sum slowly drifts when you add and subtract, so recompute it now and then or use integers. See also subarray sum equals k for prefix sums, an alternative when the whole array is available.

How to answer it in an interview

The spoken structure: name the state, give the cost per event, then say what breaks and the fix.

Common mistakes

• "I re-sum the window on every event." (wrong) The cost grows with the window size. (right) "I add the new value and subtract the evicted one, so each event is constant time."
• "I compute variance as the mean of squares minus the square of the mean." (wrong) It can go negative on large values. (right) "I use Welford's update with a count, a mean and a running sum of squared distances."
• "I subtract the evicted value to keep a rolling maximum." (wrong) The next maximum is unknown. (right) "I keep a monotonic deque of candidates."
• "I use a max-heap for the k largest." (wrong) The smallest of the kept items is the one to replace. (right) "I keep a min-heap of size k and replace its root."
• "A window means a fixed number of items." (wrong) Many features are time-based. (right) "I ask whether the window is by count or by time, then evict by that rule."

Follow-up questions

How would you implement a sliding window feature like rolling 7-day transaction velocity per user?

Keep one deque of timestamps per user, append each event, and pop from the left while the oldest is no longer inside the seven days. The count is the length of the deque, and the cost per event is constant on average.¹

How do you keep track of the k largest elements of a running list?

Keep a min-heap of size k. Push until it holds k items, then replace the root whenever a new value is larger. Each event costs a heap operation that grows with the logarithm of k, and memory stays at k items. The pattern also appears in K closest points to origin.

How would you maintain a running recommendation list with recency weighting?

Keep a dictionary of (score, last_time) per item. When an event arrives, decay the stored score by exp(−r · elapsed time) and add the event's weight, so recency is measured in time and not in event counts. Read the top k with heapq.nlargest at query time, which scales with n log k for n items. If the list is read on every event, use a heap with lazy deletion, because a plain size-k heap cannot handle a score that changes after it was pushed. A larger r forgets faster.

How do you find the maximum of a sliding window in a stream?

Use a monotonic deque of indexes whose values decrease from front to back. Pop smaller values from the back when a new one arrives, and pop the front when it leaves the window. Each index enters and leaves once.

What changes when events arrive out of order?

The pop-from-the-left rule assumes timestamps never go backwards. Either buffer events briefly and sort them, or decide how late an event may be and drop or separately handle anything later. Say which choice you made.

How would you build histogram bins from a time series of user activities?

Use tumbling windows: the bin index is the timestamp divided by the bin width, rounded down, and a dictionary holds one count per bin, so each event costs constant time. On the illustrative event times, 11 events fall into 8 non-empty one-day bins.¹ Choose the width from the question, and decide which bin an event on the edge belongs to. More patterns of this kind are in the coding interview questions path and the Python interview questions.

Sources

1. collections: Container datatypes (deque and maxlen) — Python Software Foundation, 26 Oct 2026
2. heapq: Heap queue algorithm — Python Software Foundation, 26 Oct 2026
3. Note on a Method for Calculating Corrected Sums of Squares and Products (Technometrics 4(3)) — Technometrics (B. P. Welford), 1 Aug 1962
4. NIST/SEMATECH e-Handbook of Statistical Methods: EWMA control charts — NIST, 26 Oct 2026