Katkat
Back

Design a rolling event tracker with ranges

DatabricksSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates understanding of time-series data structures and streaming counters, testing algorithm design, space/time complexity analysis, correctness across edge cases, and handling of large-scale event tracking.

Design a rolling event tracker that supports time-based queries. Implement a data structure with: (

  1. record(timestamp): record one event at integer timestamp (seconds since epoch). Assume timestamps for record are non-decreasing. (
  2. count(windowSeconds, currentTimestamp): return the number of events in the inclusive interval [currentTimestamp - windowSeconds + 1, currentTimestamp]. (
  3. countRange(startTimestamp, endTimestamp): return the number of events in the inclusive interval [startTimestamp, endTimestamp]. Follow-ups: (a) Prevent counter overflow under very high traffic; discuss data types, rollover/saturation strategies, and how to keep correctness across boundaries. (b) Propose a bucketing/chunking scheme (e.g., per-second or per-minute circular buffer) to bound memory; analyze time/space complexity and, if you compress buckets, quantify any accuracy trade-offs. (c) Support efficient queries for long ranges (hours to days); compare designs (queues, circular buffers, prefix sums, Fenwick/segment trees) and explain update/query costs. (d) Explain eviction/expiry of old buckets and how sliding windows are maintained when the requested window exceeds the in-memory buffer. (e) Provide complexity analysis and key test cases covering edge conditions (empty ranges, single-point ranges, large windows, and near-integer-limit counts).