Design a rolling event tracker with ranges
Company: Databricks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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).
Quick Answer: 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.
Implement the coding portion of a rolling event tracker. You are given a sequence of operations that must be processed in order. Support:
1) ("record", timestamp): record one event at the given integer timestamp.
2) ("count", windowSeconds, currentTimestamp): return the number of recorded events in the inclusive interval [currentTimestamp - windowSeconds + 1, currentTimestamp].
3) ("countRange", startTimestamp, endTimestamp): return the number of recorded events in the inclusive interval [startTimestamp, endTimestamp].
Timestamps used in record operations are guaranteed to be non-decreasing. Query timestamps may be large, so building a dense array over time is not allowed. If startTimestamp > endTimestamp, treat the range as empty and return 0.
For the coding part, return the answers for all query operations in order. In a real interview follow-up, you should also be ready to discuss overflow handling, bounded-memory bucketing, and trade-offs for very long-range queries.
Constraints
- 1 <= len(operations) <= 200000
- 0 <= timestamp, currentTimestamp, startTimestamp, endTimestamp <= 10^18
- Timestamps in record operations are non-decreasing
- 1 <= windowSeconds <= 10^18 for count operations
- Multiple events may occur at the same timestamp
Examples
Input: ([("record", 10), ("record", 10), ("record", 12), ("count", 1, 10), ("count", 3, 12), ("countRange", 11, 12)],)
Expected Output: [2, 3, 1]
Explanation: There are two events at 10 and one at 12. [10,10] has 2 events, [10,12] has 3 events, and [11,12] has only the event at 12.
Input: ([("count", 5, 100), ("countRange", 7, 7), ("record", 8), ("countRange", 9, 8), ("count", 1, 8)],)
Expected Output: [0, 0, 0, 1]
Explanation: Queries before any record return 0. The range [9,8] is empty because start > end. After recording one event at 8, the 1-second window ending at 8 contains 1 event.
Hints
- Because record timestamps never decrease, you can keep timestamps in sorted order without inserting in the middle. If the same timestamp repeats, merge it into the last bucket.
- To answer an inclusive range query quickly, find the first recorded timestamp >= start and the last recorded timestamp <= end, then use cumulative totals.