Detect k events in a sliding window

Q: Detect k events in a sliding window

This question evaluates a candidate's ability to design efficient sliding-window and streaming algorithms for time-series event data, encompassing deduplication, handling bounded out-of-order arrivals and clock skew, distinct-device counting, and meeting specified time and space complexity constraints.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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 ≥ X. If so, output the earliest such window [start_ts, end_ts] and the k device_ids; otherwise output none. Input

events: iterable of (user_id INT, device_id TEXT, ts ISO-8601 string, amount_cents INT), up to n=1e6 total events across users, potentially out of order by ≤5 minutes. Parameters
k ∈ {3,4,5}; t up to 1440; X ≥ 0. Requirements
Time: O(n log n) overall; Space: O(m) where m is max events per user within t-minute horizon.
Handle out-of-order events (≤5 minutes skew) and deduplicate exact duplicates.
Timestamps are UTC; beware DST transitions and clock skew.
Return all qualifying users with their earliest window and devices. Follow-ups

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

Detect k events in a sliding window

Overview

Comments (0)