Count Events in a Time Range
Events arrive as (type, timestamp) with timestamps that never decrease. Design EventCounter:
receive(type, timestamp) count(type, start, end) // events of that type with start <= timestamp <= end
receive("view", 1) · receive("click", 2) · receive("view", 5) · receive("view", 9)
count("view", 2, 9) -> 2
count("click", 3, 9) -> 0Many count calls follow the receives, over arbitrary windows, so make them fast.
Hints
Hint 1
Keep one list of timestamps per type. Because arrivals are in order, appending keeps each list sorted for free.
Hint 2
count is upperBound(end) − lowerBound(start) on that type's list: the first index with timestamp > end minus the first index with timestamp >= start.