Message Event Aggregation in a 5-Minute Sliding Window

Problem: Message Event Aggregation Implement a message event aggregator. The system receives a batch of chat-related events. Each event contains: timestamp: an integer in seconds user_id: a string chat_id: a string event_type: one of: message: a normal message event react: the user reacted in a chat end_chat: the user ended a chat The window size is fixed to the last 5 minutes, i.e. 300 seconds. For an event at time t, the sliding window is the inclusive interval [t - 300, t]. For every input event, output two values in the original input order: message_count: the number of message events in the same chat_id within the last 5 minutes, up to the current event. active_chat_count: the number of active chats for the current user_id within the last 5 minutes, up to the current event. A (user_id, chat_id) pair is considered active at time t if and only if: There is at least one react or end_chat event for this pair inside [t - 300, t]; and The latest state event of this pair inside the window is react. In other words, if a chat has a react event and no later end_chat, it is active for that user. If the latest state event is end_chat, it is not active. Important Requirements Input timestamps are not guaranteed to be increasing. If multiple events have the same timestamp, their original input order defines their order. The output must be in the original input order. In the online version, memory should not grow unbounded with historical chats: expired states outside the sliding window should be cleaned up. Input Format n timestamp user_id chat_id event_type ... 1 <= n <= 200000 0 <= timestamp <= 10^9 user_id and chat_id are strings without spaces event_type ∈ {message, react, end_chat} Output Format Print n lines. The i-th line corresponds to the i-th input event: message_count active_chat_count Example Input: 5 100 u1 c1 message 0 u1 c1 message 50 u1 c1 react 400 u1 c1 message 200 u1 c1 end_chat Output: 2 1 1 0 1 1 2 0 2 0 Example Input 3 0 u1 c1 message 100 u1 c1 message 301 u1 c1 message Output 1 0 2 0 2 0