Event Stream Count in Time Range

Stream of `(event_type, timestamp)` events with monotonically increasing timestamps. Implement `Receive(event_type, timestamp)` and `Count(event_type, start_time, end_time)` returning how many events of that type fell in the inclusive window. Requirements Receive(event_type, timestamp) -> void. Timestamps are guaranteed non-decreasing across calls. Count(event_type, start_time, end_time) -> int returns the number of events of event_type with start_time ≤ timestamp ≤ end_time. Multiple event types share the same stream; counts are per-type. Expected to handle a large number of events efficiently — naive linear scan per query is not the intended answer. Examples Receive("login", 100) Receive("click", 110) Receive("login", 120) Receive("login", 200) Count("login", 100, 150) # → 2 Count("login", 100, 250) # → 3 Count("click", 0, 1000) # → 1 Notes Keep one sorted (append-only) list of timestamps per event type. Because Receive is monotonic, appending preserves sort order at O(1) amortized. Count becomes two binary searches on the per-type list: bisect_left(start_time) and bisect_right(end_time), difference is the count. This is the canonical "Time Based Key-Value Store" data-structure pattern (LC 981), reduced to counting instead of value retrieval. Edge cases: empty stream, start > end, event type never seen, count over a window where all events are equal to the boundaries (inclusive vs exclusive matters — clarify with the interviewer). If the monotonic guarantee were dropped — a follow-up interviewers do ask explicitly — the per-type list needs a balanced BST / TreeMap (or order-statistics tree / segment tree) keyed by timestamp so inserts stay ordered and range counts stay logarithmic. Preparation Implement the per-type sorted-list + binary-search version from scratch. Drill the boundary semantics: inclusive on both ends is the most common ask, but write a small test to verify both bisect_left and bisect_right behave as expected at the boundary timestamps. Be ready to defend the choice of binary search over a more complex structure when the monotonic-timestamp guarantee is in place. Exact class shape class EventCounter: def receive(self, eventType: str, timestamp: int) -> None: ... def count(self, eventType: str, startTime: int, endTime: int) -> int: ... count is inclusive on both ends: [startTime, endTime]. Unknown event types return 0, and monotonic timestamps across receive calls are part of the intended binary-search solution.