Implement User Sessionization From Event Stream
Company: Discord
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
You are building a backend data-processing component that consumes a stream of newline-delimited JSON events. Each event represents a user sending a message to a channel and has the following shape:
```json
{"event_name":"send_message","timestamp":"2016-11-08T14:09:57Z","user_id":"1","channel_id":"1"}
```
The input events are guaranteed to arrive in chronological order. There are no missing, duplicated, or corrupt events. However, you must not assume the stream is finite, so your solution cannot depend on logic that runs only after reaching the end of input.
Define a **user session** as a sequence of events for the same `user_id` where each event occurs within **30 minutes, inclusive**, of that user's previous event. If the gap between two consecutive events for the same user is greater than 30 minutes, the previous session ends and a new session begins.
Implement a program or component that parses the event stream and emits a session record whenever a user session can be finalized. Each emitted session must contain:
- `user_id`
- `session_start_ts`: timestamp of the first event in the session
- `session_end_ts`: timestamp of the last event in the session
- `messages_sent`: total number of messages in the session
- `top_channel_id`: the channel that received the most messages during the session
- `top_channel_messages_sent`: number of messages sent to `top_channel_id`
The exact output format is flexible as long as all required fields are present. If multiple channels tie for the most messages, document and consistently apply a tie-breaking rule.
Example input lines:
```json
{"event_name":"send_message","timestamp":"2016-11-08T14:09:57Z","user_id":"1","channel_id":"1"}
{"event_name":"send_message","timestamp":"2016-11-08T14:10:01Z","user_id":"1","channel_id":"1"}
{"event_name":"send_message","timestamp":"2016-11-08T14:10:07Z","user_id":"2","channel_id":"1"}
```
Example output record:
```json
{
"user_id": "1",
"session_start_ts": "2016-11-08T14:09:57Z",
"session_end_ts": "2016-11-08T14:39:57Z",
"messages_sent": 15,
"top_channel_id": "3",
"top_channel_messages_sent": 12
}
```
Quick Answer: This question evaluates proficiency in stream processing, stateful sessionization, time-based aggregation, and per-user metric computation, focusing on competencies such as tracking user activity across unbounded ordered event streams and computing top-channel aggregates.
You are given `event_lines`, a list of newline-delimited JSON strings representing a chronological prefix of a potentially infinite event stream. Each event has the shape `{\"event_name\":\"send_message\",\"timestamp\":\"...\",\"user_id\":\"...\",\"channel_id\":\"...\"}`. Build a streaming sessionizer.
A user session is a maximal sequence of events for the same `user_id` such that the gap between consecutive events for that user is at most 30 minutes, inclusive. If the gap is greater than 30 minutes, the old session ends and a new one begins.
Because the stream may continue forever, you must not emit sessions just because the provided list ends. A session can be emitted only when it is provably closed while processing the stream. Concretely, before processing an event at time `T`, any active session whose last event time `L` satisfies `L + 30 minutes < T` must be emitted.
Return the emitted session records in the exact order they would be produced by the streaming processor. If multiple sessions become emit-ready at the same moment, emit them in lexicographically increasing `user_id` order. Each emitted record must contain:
- `user_id`
- `session_start_ts` (timestamp of the first event in the session)
- `session_end_ts` (timestamp of the last event in the session)
- `messages_sent`
- `top_channel_id`
- `top_channel_messages_sent`
If multiple channels tie for most messages inside a session, choose the lexicographically smallest `channel_id`.
Constraints
- 0 <= len(event_lines) <= 200000
- Each event line is valid JSON and `event_name` is always `send_message`
- Timestamps use UTC ISO-8601 format: `YYYY-MM-DDTHH:MM:SSZ`
- Input events are sorted by non-decreasing timestamp
- Do not emit sessions that are still active after the last provided event
Examples
Input: []
Expected Output: []
Explanation: No events means no emitted sessions.
Input: ['{"event_name":"send_message","timestamp":"2016-11-08T10:00:00Z","user_id":"1","channel_id":"7"}']
Expected Output: []
Explanation: A single event starts a session, but there is no later timestamp proving that session has ended.
Hints
- A session is only guaranteed to be closed when you see a later timestamp strictly greater than `last_event_time + 30 minutes`. Equality is not enough, because an event exactly 30 minutes later still belongs to the same session.
- Use a hash map to store each user's active session, and a min-heap of candidate expiry times so you can emit old sessions without scanning every active user on each event.