Merge Overlapping Chat Messages | Dataford Interview Questions

Your question is Merge Overlapping Chat Messages. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Reddit may receive multiple timestamped message fragments for the same chat stream. Given a list of message objects, merge fragments belonging to the same stream whenever their time intervals overlap or touch.

Formal Specification

Implement merge_chat_streams(messages), where messages is a list of dictionaries with the following fields:

stream_id: a string identifying the Reddit chat stream
start: an integer start timestamp
end: an integer end timestamp, with start <= end
text: the message fragment as a string

Return a list of dictionaries. Each result must contain stream_id, the earliest start, the latest end, and messages, an array of fragment texts ordered by increasing start. Return result streams ordered lexicographically by stream_id, then by start time. A fragment belongs to the same unified stream only when its stream_id matches and its start is less than or equal to the current merged interval's end. Do not mutate the input list.

Constraints

0 <= len(messages) <= 10^5
0 <= start <= end <= 10^9
stream_id and text are non-empty strings
Each message contains exactly stream_id, start, end, and text
The input list must not be mutated

Function Signature

def merge_chat_streams(messages):