Efficient Event Stream Processing

Box receives a large chronological stream of file-access events. Detect users who access at least threshold distinct files within any rolling window of time, while processing events incrementally.

Emit an alert only when a user's distinct-file count crosses from below threshold to at least threshold. If the count later falls below the threshold because events expire, emit another alert when the user crosses the threshold again.

Formal Specification

Implement process_events(events, window, threshold).

• events is an iterable of events, where each event is [timestamp, user_id, file_id].
• timestamp is an integer, and events arrive in nondecreasing timestamp order.
• user_id and file_id are strings.
• window is a positive integer. At event time t, an event is active when timestamp > t - window.
• threshold is a positive integer.
• Return a list of alerts, each represented as [timestamp, user_id], in processing order.
• The function must not copy or sort the entire input stream.

Use data structures that support expiration of old events and duplicate file accesses efficiently. Aim for near-linear processing time and memory proportional to the active window.