Skip to content

Counting Rate of Events

Level: L4-L5 Topics: Sliding Window, System Design, Data Structures

Problem Statement

Design a solution to monitor events in a system. You need to detect if the number of events exceeds a threshold within a rolling time window.

Specifically, implement the following API:

bool event(int64 time_s)
  • time_s is the timestamp (in seconds) of the event.
  • The function returns true if the number of events in the last period_s seconds (inclusive of the current event) exceeds max_count.
  • period_s and max_count are configured at initialization.

Background & Constraints

  • Events arrive with monotonically increasing timestamps (in the basic version).
  • period_s can range from seconds to days.
  • max_count can range from 1 to millions.
  • The solution should be efficient in both time and space.
  • You may assume the system processes a high volume of events.

Examples

Configuration: max_count = 3, period_s = 10

The window for an event at time t is [t - period_s, t] (inclusive of t itself).

event(1)   → false   (1 event  in [-9, 1]:  {1})
event(3)   → false   (2 events in [-7, 3]:  {1, 3})
event(7)   → false   (3 events in [-3, 7]:  {1, 3, 7};  3 does not exceed 3)
event(8)   → true    (4 events in [-2, 8]:  {1, 3, 7, 8})
event(15)  → false   (3 events in [5, 15]:  {7, 8, 15};  event 1 and 3 fell out)
event(16)  → true    (4 events in [6, 16]:  {7, 8, 15, 16})

The event(15) step shows the count dropping back below the threshold once older events fall out of the rolling window. The next event then pushes it over again.

Hints & Common Pitfalls

  • Basic approach: Maintain a queue (or deque) of event timestamps. On each call, remove timestamps older than time_s - period_s, add the new timestamp, and check if the queue size exceeds max_count.

  • Space concern: If the event rate is very high, the queue could hold millions of entries. Consider whether you can use a more compact representation.

  • Histogram buckets: For approximate counting, you can divide the time window into fixed-size buckets and count events per bucket. This trades exactness for space efficiency. But be careful with boundary effects.

  • Common mistake: Off-by-one errors on the window boundary. Clarify whether "last period_s seconds" means (time_s - period_s, time_s] or [time_s - period_s, time_s].

Follow-Up Questions

  1. 100% correctness: The basic queue approach gives exact results. What is its time and space complexity? Can you guarantee O(1) amortized time per call?

  2. Improve efficiency: If you used a histogram-bucket approach, how do you handle the tradeoff between accuracy and memory? What bucket size gives acceptable error bounds?

  3. Very long durations: If period_s is extremely large (e.g., one year) and events are frequent, a flat histogram won't fit in memory. How would you handle this? Consider multi-resolution histograms or logarithmic bucketing.

  4. Out-of-order events: What if events can arrive with timestamps that are not monotonically increasing? How does this change your data structure and algorithm? What if events can arrive arbitrarily late?

  5. Distributed version: If events arrive at multiple servers, how would you implement a global rate limiter with this API?