Detect Anomalies with Sliding Window | Dataford Interview Questions

Pearson MyLab records student interaction events in chronological order. Detect students whose activity exceeds an allowed interaction count within any fixed-size sliding time window.

An interaction log is represented as a list of two-item arrays: [timestamp, student_id]. Timestamps are integer seconds and the logs are sorted by nondecreasing timestamp. For each student, return the student ID if any window of window_size seconds contains more than max_events interactions.

Treat a window ending at timestamp t as the inclusive interval [t - window_size + 1, t]. Return the anomalous student IDs in lexicographic order. A student should appear at most once.

Formal Specification

Implement detect_anomalies(logs, window_size, max_events).

Input: logs, a list of [int, str] pairs; window_size and max_events, positive integers.
Output: a sorted list of student ID strings whose interaction count exceeds max_events in at least one window.

Constraints

0 <= len(logs) <= 10^5
Each log entry has the form [timestamp, student_id]
0 <= timestamp <= 10^9
1 <= window_size <= 10^9
1 <= max_events <= 10^5
Each student_id is a nonempty string
logs is sorted by nondecreasing timestamp

Function Signature

def detect_anomalies(logs, window_size, max_events):

Your question is Detect Anomalies with Sliding Window. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem