Katkat
Back

Detect k events in a sliding window

GeminiData Scientist · Onsite
MediumData ScientistOnsiteCoding & Algorithms

Last updated

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.

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
  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.