## Implement a Stateful Chatter Message Store Design a `Chatter` class that can load multiple ordered batches of messages, save its current messages, return a five-message neighborhood around one ID, combine neighborhoods for several IDs without duplicates, edit messages, and optionally retain every historical version. Each message has an immutable unique ID and text. Messages arrive in increasing ID order across repeated `load` calls. The source uses decimal-looking IDs but does not specify their storage type; choose an exact totally ordered representation and do not rely on binary floating-point equality. ### Part 1 — Define `load` and `save` Specify the internal state and the behavior of repeated loads and saves, including validation of ordering and duplicate IDs. #### What This Part Should Cover - One ordered current-message sequence and stable message identity. - Appending later batches without discarding earlier messages. - A decision for invalid order or duplicate input even though valid calls exclude both. - Returning a copy or immutable view from `save` so callers cannot mutate internal state. ```hint Preserve one global order The first ID in a later batch must be compared with the last ID already loaded, not only with its neighbors inside that batch. ``` ### Part 2 — Implement Neighborhood Reads `getMessages(id)` returns up to two messages before the matching message, the message itself, and up to two after it. At either boundary it returns only the available messages. `getMulti(ids)` returns the union of those neighborhoods, sorted by message ID with no duplicate message. #### What This Part Should Cover - A documented result for an unknown ID. - Exact start and end indexes for the five-message window. - Deduplication when requested neighborhoods overlap. - Output order by message ID rather than request order. ```hint Think in index intervals Once an ID resolves to its ordered position, its neighborhood is one bounded interval; overlapping intervals can be merged before materializing results. ``` ### Part 3 — Optimize Repeated Reads The workload performs many calls to both read methods. Add indexes or caches and explain how `load` and `edit` keep them correct. #### What This Part Should Cover - A hash map from message ID to ordered index. - Cache keys for a single neighborhood and for a canonicalized set of requested IDs. - Invalidation or versioning when appends change windows near the old tail. - Avoiding mutable cached objects that callers can alter. ```hint Cache against a dataset version An appended message can change a previously short window near the end even though none of its existing messages were edited. ``` ### Part 4 — Support Editing and Version History Define `edit(id, message)` for current state, then redesign the message record so all older text versions remain queryable. #### What This Part Should Cover - Immutable IDs and ordering when text changes. - Cache invalidation for edited payloads without rebuilding the ID index. - Append-only versions with version number or update time and a current-version pointer. - Clear `save` and neighborhood semantics for current versus historical views. ```hint Separate position from content version Editing text need not move the message, but any cached window containing that message must stop serving the old payload. ``` ### What a Strong Answer Covers - Maintains one exact ordered sequence across repeated loads. - Uses ID-to-index lookup and interval union for fast, deterministic reads. - Keeps caches correct after both append and edit operations. - Adds history through immutable versions rather than copying or overwriting the whole store. ### Follow-up Questions 1. Which cached single-ID windows can change after one message is appended? 2. How would you process `getMulti` when thousands of requested windows overlap heavily? 3. What should `save` return after several edits when history is enabled? 4. How would you migrate decimal-looking IDs that were previously stored as floating-point values?