Problem Description

Implement an algorithm that, for each user, determines whether there exists a set of at least k ACH credit events from distinct device_ids within any sliding window of t minutes, where each amount_cents is greater than or equal to X. If such a window is found, output the earliest [start_ts, end_ts] window and the k associated device_ids; otherwise, output none.

Input

• events: An iterable of tuples, each containing (user_id INT, device_id TEXT, ts ISO-8601 string, amount_cents INT). The total number of events n can be up to 1e6 across all users. Events may arrive out of order by up to 5 minutes.

Parameters

• k: An integer representing the minimum number of distinct device_ids required, k ∈ {3, 4, 5}.
• t: An integer representing the duration of the sliding window in minutes, t up to 1440.
• X: An integer representing the minimum amount_cents for an event to be considered, X ≥ 0.

Requirements

• Time Complexity: O(n log n) overall.
• Space Complexity: O(m) where m is the maximum number of events for a single user within a t-minute horizon.
• Handle out-of-order events with a skew of up to 5 minutes.
• Deduplicate exact duplicate events.
• Timestamps are UTC; be aware of DST transitions and clock skew.
• Return all qualifying users with their earliest window and corresponding k device IDs.

Follow-ups

1. Describe a streaming approach (bounded memory) if events arrive per user partition.
2. Prove correctness of your window advancement and distinct-device counting.
3. Discuss worst-case behavior on highly bursty users and how to mitigate.