Time-Series Anomaly Detection

HardPython

Problem

Zoox autonomy telemetry arrives as a stream of numeric samples. Implement a robust online detector that identifies samples whose value is anomalous relative to the immediately preceding rolling window.

For each sample after the first complete window, calculate the window's median and median absolute deviation (MAD). Define the modified z-score as 0.6745 * abs(value - median) / MAD. Mark the sample anomalous when this score is greater than threshold. The current sample must not be included in its own baseline window.

If MAD == 0, mark the sample anomalous exactly when it differs from the window median. Return the zero-based indices of anomalous samples in ascending order.

Formal Specification

detect_anomalies(values, window_size, threshold) receives a list of numeric values, a positive integer window size, and a positive numeric threshold. It returns a list of integer indices. Samples before the first complete prior window are never anomalous.

Constraints

1 <= len(values) <= 10^5
1 <= window_size <= len(values)
0 < threshold <= 100
Values are finite integers or floating-point numbers

Function Signature

def detect_anomalies(values, window_size, threshold):

If MAD == 0, mark the sample anomalous exactly when it differs from the window median. Return the zero-based indices of anomalous samples in ascending order.