Level 1 Per-user counts over a sliding window, with bounded memory
A chat backend wants live counters of how many messages each user sent recently. The service runs for months, so it must forget old events. Build ChatEventAggregator:
ChatEventAggregator(m: int): the window length in seconds,m >= 1.record(user_id: str, chat_id: str, timestamp: int) -> None: one message fromuser_idinchat_idattimestamp(whole seconds).count(user_id: str, timestamp: int) -> int: how many messagesuser_idsent in the window[timestamp - m + 1, timestamp](both ends included).stored_events() -> int: how many events the aggregator is currently keeping.
Guarantees about the calls:
- The
timestamparguments of allrecordandcountcalls, taken together in call order, never decrease (it is a live clock). - A single user never records twice in the same second (different users can).
Memory rule. After any call with timestamp T, the aggregator must have dropped every event with timestamp <= T - m, for all users, including users who are never mentioned again. stored_events() therefore equals the number of recorded events with timestamp in [T - m + 1, T], where T is the latest timestamp seen (0 before any call). Don't keep empty per-user entries around either.
agg = ChatEventAggregator(10)
agg.record("u1", "c1", 1)
agg.record("u2", "c1", 3)
agg.record("u1", "c2", 5)
agg.count("u1", 5) # 2
agg.count("u1", 10) # 2 window [1, 10]
agg.count("u1", 11) # 1 window [2, 11]: the event at 1 is gone
agg.stored_events() # 2 (u2@3 and u1@5)
agg.count("u3", 13) # 0
agg.stored_events() # 1 (u2@3 expired at T = 13 even though nobody asked about u2)
agg.count("u1", 15) # 0
agg.stored_events() # 0
count must be O(1) amortised: don't scan a user's events on every call.
Show hint
Keep one queue of all events in time order, plus a dict user -> number of events in the window. Every call first pops expired events off the front of the queue (decrementing, and deleting at zero, their user's counter). Each event is pushed and popped once, so the cost is O(1) amortised.