# Out of Nowhere > Every stream has a rhythm. Find the readings that break it. Canonical URL: 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. ## 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** ```python 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. > **Two failures the happy path hides** > > Two ways to fail this on the whiteboard: pulling the current reading into its own window (look-ahead bias that mutes the very spike you want), and dividing by a std of 0 on a constant run, which throws ZeroDivisionError mid-stream. Both are invisible on the happy-path test and both show up the instant the input has a flat segment. > **Time and space** > > Time is O(n * window): each eligible index recomputes its mean and variance from scratch. Space is O(a) for the anomalies returned. Fine for a one-shot batch scan; a problem above a few hundred thousand points wants the streaming form. > **The O(n) path worth naming** > > Carry running sums of the values and their squares (Welford's online variance) and slide them as the window advances. That turns the per-point recompute into O(1) updates and the whole scan into O(n). Implement the readable O(n*window) version, then say out loud that you'd switch to incremental sums for a live stream. > **The guard and the O(n) path are the tells** > > Whether you name the incremental sliding-sum optimization even after writing the recompute version, and whether you reach for the zero-std guard unprompted. Both are the tells that you've shipped a real monitoring pipeline, not just solved a textbook exercise. --- ## Common follow-up questions - How would you run this over an unbounded live stream instead of a batch list? _(Tests maintaining a fixed-size deque with incrementally updated running sums.)_ - What if the series has daily or weekly seasonality the rolling mean ignores? _(Tests seasonal decomposition or comparing each point against the same phase in prior cycles.)_ - How would you make the baseline adapt when the normal level slowly trends up? _(Tests exponentially weighted moving averages so the baseline adapts to drift.)_ - A single huge spike poisons the next few windows. How would you make detection robust to that? _(Tests robustness of mean/std to outliers and a switch to median plus MAD.)_ ## Related - [All practice problems](https://datadriven.io/problems) - [Mock interview mode](https://datadriven.io/interview/out_of_nowhere) - [Python Interview Questions](https://datadriven.io/python-interview-questions) - [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep) - [Daily Challenge](https://datadriven.io/daily) --- Source: DataDriven (https://datadriven.io). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.