Out of Nowhere

A hard Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
hard
Seniority
L6
Asked in
Meta

Problem

Flag every reading that sits more than threshold population standard deviations from the mean of the window readings just before it, reporting its baseline mean, standard deviation and z-score accurate to two decimal places. Our monitoring service sends data as (timestamp, value) pairs in time order, and a reading without a full window of history, or whose prior window is perfectly flat, is never flagged.

Every stream has a rhythm. Find the readings that break it.

Example 1

Input:

data = [[0,10],[1,11],[2,10],[3,12],[4,11],[5,10],[6,50],[7,11]], window = 5, threshold = 2

Output:

[{"value":50,"z_score":52.38,"timestamp":6,"rolling_std":0.75,"rolling_mean":10.8}]

Example 2

Input:

data = [[0,20],[1,20],[2,20],[3,80]], window = 3, threshold = 2

Output:

[]

Worked solution and explanation

What this really is

This is a rolling z-score wearing an anomaly-detection costume, and the whole problem turns on one boundary: which readings go into the baseline. Anyone can compute a mean and a standard deviation. What separates candidates is whether the current reading sneaks into its own window (it must not) and whether a flat stretch of identical readings detonates a divide-by-zero. Get the window boundary wrong and every spike quietly shrinks, because the spike is sitting inside the baseline it's supposed to stand out from.

How to get there

Step 1: Build the baseline from the PREVIOUS window only

For each index i at or beyond window, take the window readings ending just before i (values[i-window:i], current point excluded) and compute their mean and population standard deviation. The exclusion is the part interviewers actually check.

Step 2: Guard the divide, then apply the threshold

Before dividing, look at rolling_std. On a constant segment it is exactly 0 and the z-score is undefined, so skip the point rather than crash. Otherwise z = (value - mean) / std, and the reading is an anomaly when abs(z) > threshold (strict, not >=).

Step 3: Collect the stats in scan order

Emit one dict per flagged reading with timestamp, value, rolling_mean, rolling_std and z_score, in the order you scanned. The report only needs two-decimal accuracy, so the raw floats are already good enough; spend your attention on the window boundary instead. The first window readings never produce output.

The solution

Rolling z-score with a previous-window baseline and a zero-std guard
def detect_anomalies(data, window, threshold):
    import math
    times = [t for t, _ in data]
    values = [v for _, v in data]
    anomalies = []
    for i in range(len(values)):
        if i < window:
            continue
        win = values[i - window:i]
        rolling_mean = sum(win) / len(win)
        variance = sum((x - rolling_mean) ** 2 for x in win) / len(win)
        rolling_std = math.sqrt(variance)
        if rolling_std == 0:
            continue
        z_score = (values[i] - rolling_mean) / rolling_std
        if abs(z_score) > threshold:
            anomalies.append({
                "value": values[i],
                "z_score": z_score,
                "timestamp": times[i],
                "rolling_std": rolling_std,
                "rolling_mean": rolling_mean,
            })
    return anomalies

Population variance divides by len(win); the rolling_std == 0 guard runs before any division.

Window includes the current point
values[i-window:i+1] folds the spike into its own baseline. A 50 sitting among readings near 10 drags the mean up and inflates the std, so its z-score collapses toward the threshold and the alert never fires.
Window excludes the current point
values[i-window:i] measures the reading against history alone. The baseline stays small and tight, the 50 lands dozens of std away, and the anomaly is unmistakable.

Common follow-up questions