Sliding-Window Chat Analytics: Recent Counts, Live Sessions, Out-of-Order Events

Build an in-memory, single-threaded analytics service for chat sessions. It consumes a real-time stream of interaction log records, and each record has three fields:

• user: str, the user;
• chat: int, a chat id that is unique only within its user, so a chat is identified by the pair (user, chat);
• ts: int, the time of the interaction in whole minutes.

Let T be the largest timestamp that has appeared anywhere in the stream so far. "The past 15 minutes" means the closed interval [T - 14, T]. For example, when T = 20 the window is [6, 20], and an event at minute 6 still counts.

The problem has three parts, and each part extends or relaxes the one before it. Write working code for each part, and state the time and memory cost of every operation.

Constraints and Clarifications

• T is global: it is the maximum over every user's events, not a per-user value. An event from another user can move the window forward and expire your chat's events.
• Ingestion and queries both arrive at high volume, so both must be efficient.
• Memory must stay bounded: proportional to the number of chats with activity in the past 15 minutes, not to the total history of the stream.
• Everything runs in one process on one thread; nothing needs to be persisted.

Clarifying Questions

• Can one chat have several distinct events in the same minute, and does each of them count?
• Is amortized constant time per operation acceptable, or must every individual call be constant time?
• What should a query return before any event has arrived, or for a chat or user that has never appeared?

Part 1 — Recent interaction count

Implement:

• ingest(user: str, chat: int, ts: int) -> None, which records one interaction;
• count_recent(user: str, chat: int) -> int, which returns the number of interactions of chat (user, chat) within [T - 14, T].

In this part, timestamps arrive in non-decreasing order across the whole stream, and the stream contains no duplicate records. Ingests and queries interleave arbitrarily.

What This Part Should Cover

• The closed window boundary and the global definition of T
• The cost of ingest and count_recent, amortized or worst case
• What triggers eviction, and why memory is bounded by the chats active in the window
• Behavior when one chat receives many events in the same minute

Part 2 — Live sessions per user

Each event now carries a fourth field, kind:

• "touch": the user sent a message in the chat and received a reply;
• "close": the user explicitly ended the session. A close may arrive arbitrarily long after the session's last touch, or never.

A chat session is live if and only if both of the following hold:

1. it has at least one touch within [T - 14, T];
2. no close has been received whose timestamp is strictly greater than the chat's latest touch.

So a new touch reactivates a closed session, and a close with the same timestamp as the latest touch does not end it. For example, a touch at minute 2 makes the user's live count 1, and a close for the same chat at minute 8 brings it back to 0.

Implement:

• ingest(user: str, chat: int, ts: int, kind: str = "touch") -> None;
• count_live(user: str) -> int, the number of the user's sessions that are live at the current T.

Timestamps are still non-decreasing in this part.

Clarifying Questions for this Part

• Should count_recent still be supported, and if so, does a close count as an interaction?
• Must count_live take constant time, or is a cost proportional to the user's recently active chats acceptable?

What This Part Should Cover

• The minimal per-chat state that decides liveness, including the strict tie rule between a close and the latest touch
• Reactivation by a new touch, and closes for chats with no touch in the window
• How live sessions expire as T advances, and the resulting cost of count_live
• A memory bound that still follows the recently active chats

Part 3 — Out-of-order arrival

Relax one assumption: events may now arrive out of order, so an event's ts can be smaller than timestamps that were already processed. T is still the largest timestamp seen so far, so it never decreases from one query to the next, and you may defer cleanup to query time.

Both count_recent(user, chat) and count_live(user) must stay correct under the definitions above, with "after the latest touch" decided by timestamps rather than by arrival order. For example, a close that arrives late but carries a timestamp greater than the chat's latest touch ends the session, and a late touch whose timestamp is greater than every close of that chat reactivates it.

Clarifying Questions for this Part

• Is there a bound on how late an event can arrive?
• Is cleanup at query time enough even for users who are never queried again, or must memory stay bounded whatever the query pattern?

What This Part Should Cover

• Why discarding already-expired arrivals and deferring eviction to queries are safe
• Per-chat state that accepts late events and applies the timestamp-based close rule
• The cost of ingest, count_recent and count_live, and when memory is bounded
• How correctness is verified against the definitions