Top-K Anomaly Detection

HardPython

Problem

A Gulfstream aircraft health monitoring stream contains an unsorted array of integer sensor readings. Define each reading's anomaly score as its absolute difference from the median of all readings. Return the original indices of the k readings with the largest anomaly scores.

If multiple readings have the same score, prefer the smaller original index. Return indices ordered by decreasing anomaly score, then increasing index.

Formal Specification

Implement top_k_anomalies(readings, k). The input readings is a non-empty list of integers, and k is an integer from 1 through len(readings). Return a list of exactly k integer indices.

For an even number of readings, calculate the median as the arithmetic mean of the two middle values after sorting. A reading equal to the median has an anomaly score of zero.

Constraints

1 <= len(readings) <= 10^5
1 <= k <= len(readings)
-10^9 <= readings[i] <= 10^9
Duplicate readings are allowed

Function Signature

def top_k_anomalies(readings, k):

If multiple readings have the same score, prefer the smaller original index. Return indices ordered by decreasing anomaly score, then increasing index.

Formal Specification

Implement top_k_anomalies(readings, k). The input readings is a non-empty list of integers, and k is an integer from 1 through len(readings). Return a list of exactly k integer indices.

For an even number of readings, calculate the median as the arithmetic mean of the two middle values after sorting. A reading equal to the median has an anomaly score of zero.