Merge Message Context Windows
Company: Reddit
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given a chat history in which each message has a unique integer `id` and a string `content`. Message IDs are strictly increasing, and the full history is ordered by `id` in ascending order.
A message is represented by this read-only model:
```java
class Message {
int id;
String content;
}
```
You are also given a provided API:
```java
class Chat {
/**
* Returns the message with the given id, along with up to `windowSize`
* messages before it and up to `windowSize` messages after it.
*
* The returned list is sorted by message id in ascending order.
* If the given id does not exist, an empty list is returned.
*/
public List<Message> getChatMessages(int id, int windowSize);
}
```
Implement the following class:
```java
class ChatMessageMerger {
ChatMessageMerger(Chat chat, int windowSize)
List<Message> mergeMessages(List<Integer> ids)
}
```
Requirements for `mergeMessages(ids)`:
- For each input message ID, query its context window using `getChatMessages(id, windowSize)`.
- Merge all returned messages into a single result.
- Remove duplicates, since different context windows may overlap.
- Return the final list sorted by message `id` in ascending order.
- If an input ID does not exist, its query contributes nothing.
Performance requirement:
- Let `M` be the total number of messages returned across all API calls before deduplication.
- Your algorithm must run in strictly better time than `O(M log M)`.
Design and implement an efficient solution.
Quick Answer: This question evaluates a candidate's skill in designing efficient algorithms and appropriate data-structure use for merging overlapping message context windows and eliminating duplicates under strict time-complexity constraints.