Implement sliding-window device anomaly

Streaming detection algorithm: Implement a function process_logins(stream) that consumes a time-ordered stream of login events (user_id, ts, device_id, success) and emits an alert (user_id, window_start_ts, window_end_ts, distinct_devices) whenever a user accumulates ≥4 distinct device_ids with successful logins within any 10-minute sliding window. Constraints: (1) Memory must be O(U * K) where U is active users and K is the number of distinct devices within the last 10 minutes; (2) Support out-of-order events up to 30 seconds late; (3) Amortized time per event should be O(1)–O(log K). Tasks: A) Describe the data structures (e.g., per-user deque keyed by ts plus a hash map of device_id→count) and eviction strategy; B) Explain how you’d handle late events while avoiding duplicate alerts; C) Provide pseudocode (Python-like) and the exact alerting semantics when events arrive on the boundary (inclusive/exclusive).

Sliding-Window Device Anomaly Detection

You are building a fraud-detection signal for a payments platform. Implement process_logins(events) (named solution in the Python harness) that consumes a time-ordered list of login events and emits an alert whenever a user accumulates 4 or more distinct device IDs with successful logins inside any 10-minute (600-second) sliding window.

Input — a list of events, each a tuple (user_id, ts, device_id, success):

• user_id (str): the account.
• ts (int): event timestamp in seconds. Events are non-decreasing in ts.
• device_id (str): the device the login came from.
• success (bool): whether the login succeeded. Failed logins are ignored.

Window semantics (exact): for an incoming successful event at time ts, consider all successful events whose timestamps fall in the inclusive interval [ts - 599, ts] — a 600-second window ending at and including ts. Count the number of distinct device_ids among them. If that count is >= 4, emit an alert.

Alert format — a tuple (user_id, window_start_ts, window_end_ts, distinct_devices):

• window_end_ts is the current event's ts.
• window_start_ts is the timestamp of the oldest event still inside the window for that user.
• distinct_devices is the number of distinct devices in the window at that moment.

De-duplication: emit at most one alert per user per distinct window_end_ts. (A given event triggers at most one alert; a later event at a strictly larger ts that still satisfies the threshold fires its own alert.)

Return the alerts in the order they are emitted (i.e. in event order).

Performance targets (met by the reference solution): memory O(U * K) for U active users and K distinct devices in the trailing window; amortized O(1)–O(log K) work per event using a per-user deque + eviction.

Constraints

• Events are given in non-decreasing timestamp order.
• Window length is 600 seconds (10 minutes), inclusive: [ts - 599, ts].
• Only events with success == True count toward the distinct-device total.
• Alert threshold is >= 4 distinct device_ids.
• Emit at most one alert per user per distinct window_end_ts.
• 0 <= len(events); timestamps fit in a 64-bit integer.

Examples

Example 1

Input: ([],)
Output: []

Explanation: Empty stream produces no alerts.

Example 2

Input: ([('u1', 0, 'd1', True), ('u1', 100, 'd2', True), ('u1', 200, 'd3', True)],)
Output: []

Explanation: Only 3 distinct devices in the window — below the threshold of 4.

Hints

1. Keep one deque of (ts, device_id) per user. Append on each successful event, then pop from the front while the oldest timestamp is older than ts - 599.
2. The window must include the current event, so window_start = ts - 600 + 1; the oldest surviving deque entry's ts is window_start_ts in the alert.
3. To hit the amortized O(1)-O(log K) target, maintain a device_id -> count map alongside the deque: increment on append, decrement on eviction, and track distinct as the number of keys with count > 0 instead of rebuilding a set each time.
4. Failed logins (success == False) are skipped entirely — they neither count nor enter the deque.