Chat Message Merge with Windowed API

Given a provided chat API that returns a window of messages centered on a target message id, implement a class that merges the context windows of an input list of message ids into a single sorted, de-duplicated message list, beating the naive O(M log M) bound. A current phone-screen variant instead asks you to own the ordered message store: load batches, return a target's two-message context on either side, merge multiple neighborhoods, then extend the design with caching, edits, and retained version history. Requirements A chat application stores messages with strictly increasing integer ids and string content. Messages are immutable. The interviewer provides a read-only Message model and a Chat API: class Message { int id; String content; } class Chat { /** * Returns the message with the given id plus up to `windowSize` messages * immediately before and after it, sorted by id ascending. Empty list if * the id does not exist. */ List<Message> getChatMessages(int id, int windowSize); } Implement ChatMessageMerger: ChatMessageMerger(Chat chat, int windowSize) List<Message> mergeMessages(List<Integer> ids) For each id in the input list, fetch its context window via getChatMessages, then merge all windows into a single sorted, de-duplicated list of messages. The returned list contains each message at most once. The returned list is sorted by message id ascending. Complexity bar: the solution must run in better than O(M log M), where M is the total number of context messages returned across all API calls. A common concrete parametrization sets windowSize = 5: each call returns up to 5 messages before the target, the target itself, and up to 5 after — so at most 11 messages per window. Near the start or end of a conversation fewer than 11 come back. Follow-up — caching: a common extension asks what to do when getChatMessages is called too many times (it is an expensive backend call). Put a cache in front of the API and discuss key choice and invalidation. Minority variant: own a stateful Chatter store that accepts multiple ordered batches, returns the target plus up to two messages on either side, merges neighborhoods for multiple ids, and later supports edits and retained history. This is a separate contract: its examples use decimal-valued ids instead of the primary variant's integer ids. Clarify the id type, API shape, and window size before coding. Examples With windowSize = 5 and ids = [1, 3, 5], the three windows overlap heavily and collapse into one contiguous ordered run: mergeMessages([1, 3, 5]) → messages with ids [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] In the stateful Chatter variant, the supplied batches produce these exact boundary and overlap cases: get_messages(123.41) → ids [123.41, 123.43, 123.45] get_multi([128.61, 130.65]) → ids [126.56, 126.57, 128.61, 129.62, 130.65, 132.67, 134.68] Notes The complexity bar rules out the naïve "collect everything into a set, then sort" approach — that is exactly O(M log M). The trick is that each call to getChatMessages already returns a sorted window. The aggregate problem is therefore a K-way merge of K sorted lists where K is the number of input ids. K-way merge with a min-heap is O(M log K), which is strictly better than O(M log M) when K ≪ M. Sort the input ids first so windows arrive in roughly increasing order and overlap can be detected without extra structures. The cleanest formulation is a single last_id watermark — no heap needed. Once both the input ids AND each window are sorted, any overlap between a later window and everything already emitted can only appear as a prefix of that later window. So one "largest id already appended" watermark suffices: sort the ids, fetch each window in order, and while scanning a window skip every message whose id is <= last_id, otherwise append it and advance last_id. This merges and deduplicates in a single pass with O(1) extra state — no heap, no hash set. This prefix-only property is the key insight interviewers reward; the min-heap is a correct but heavier fallback. For deduplication, exploit the strictly increasing id invariant: when emitting from the merge, skip any message whose id is at or below the previously emitted id. No hash set needed. An even tighter formulation for API cost: sort the input ids, then sweep them with a pointer. For each id, fetch the window only if the previous window did not already cover this id (i.e. the previous window's max id < current id − windowSize). This collapses overlapping windows into a single call sequence and avoids redundant API calls — a follow-up the interviewer almost always asks about. The interviewer probes for the difference between message-count complexity (M, i.e. the total T of messages returned across all calls) and API-call complexity (K). The former is the stated bar; the latter is the natural follow-up — what is the minimum number of getChatMessages calls needed? Complexity of the pointer-sweep merge: O(k log k) to sort the k input ids, O(T) to scan all returned messages, O(R) extra space for the R-message output. With windowSize = 5 each window is ≤ 11 messages, so T ≤ 11k. Edge cases that trip candidates: input id list is unsorted, input id list contains duplicates, an id does not exist (getChatMessages returns empty), windows do not all overlap (input ids are spread far apart). The caching follow-up exploits message immutability: cached windows never go stale, so an id-keyed cache (memoizing whole windows) cuts repeated getChatMessages calls. Expect probing on the cache key choice (single message id vs window) and on memory bounds. Follow-up — editable messages with version history A second follow-up drops the immutability assumption: messages can now be edited, and you must preserve history rather than overwriting content in place. The design move is to separate two things: the stable logical message identity (id), constant for the life of the message, and the immutable versions of that message over time, appended in chronological order. Each edit appends a new version record; the message keeps its current version for O(1) latest reads, and a snapshot query binary-searches the version list. A representative shape: @dataclass(frozen=True) class MessageVersion: version: int content: str edited_at: int # timestamps must be non-decreasing across edits class VersionedMessage: id: int current_version: int versions: list[MessageVersion] # append-only, sorted by edited_at def edit(self, new_content, edited_at) -> None: ... # O(1) append; reject out-of-order edited_at def latest(self) -> MessageVersion: ... # O(1) def as_of(self, timestamp) -> MessageVersion | None: # O(log v) binary search # rightmost version with edited_at <= timestamp; None if all edits are later Then getChatMessages(id, as_of=t) returns, for each message, the version visible at snapshot time t (or latest() if as_of is omitted — e.g. as_of(130) on a message edited at 100/120/150 yields the version from time 120, not the latest). Key points the interviewer looks for: Deduplicate the Part-1 merge by message_id, not by version number — the stable id means the pointer-sweep merge is unchanged; versioning is orthogonal to it. as_of(t) finds the rightmost version whose edited_at <= t (returns None if the message did not yet exist at t); latest() is O(1); edit is an O(1) append and rejects out-of-order timestamps. Space is O(v) per message for v versions. Old content is never overwritten, so audit history and rollback stay possible. In a real system this maps to two tables: messages(message_id, current_version, author_id, created_at, …) and message_versions(message_id, version, content, edited_at, editor_id, …). Stateful Chatter phone-screen variant The alternate interface owns the message collection instead of reading through a provided Chat service: class Chatter: def load(self, messages): ... def save(self): ... def get_messages(self, message_id): ... def get_multi(self, ids): ... def edit(self, message_id, message): ... load may be called repeatedly. Message ids are unique, and all incoming messages arrive in global id order. save returns the stored messages. get_messages returns the target, up to two predecessors, and up to two successors; stop at either collection boundary. get_multi unions the neighborhoods for every requested id, then returns one id-sorted list without duplicates. Read-heavy use prompts caches for both single-id and multi-id lookups. Adding edit requires revisiting cached results and invalidation. The final design follow-up retains every old message version instead of overwriting content in place. Preparation Practice the single-last_id-pointer sweep first — it is the answer interviewers actually want here (overlap is prefix-only, so the min-heap is overkill). Still be able to write a K-way merge with a min-heap from scratch, untouched by library helpers, in under 10 minutes as the fallback. Drill the canonical "merge K sorted lists" LeetCode problem and the streaming dedup variant (skip when <= previous emitted). Practice articulating the API-call optimization out loud: "sort input ids, sweep, only call when the next id is more than windowSize past the previous window's max." Interviewers explicitly reward this follow-up answer. Pre-decide your Message identity check (id field, not object equality) and your heap comparator (sort by id, tie-break on insertion order). Rehearse the editable-messages follow-up: separate logical id from an append-only version list, as_of(t) via binary search on edited_at, and state up front that Part 1's merge still dedupes by message_id.