Design an Editable Text Buffer

The interview question was asked in three progressive stages. Design an in-memory text editor. 1. **Basic text buffer** Implement a data structure that efficiently supports: - `insert(position: int, text: str)` - `delete(start: int, end: int)` where `end` is exclusive - `get_text() -> str` 2. **Undo / redo** Extend the editor with: - `undo()` - `redo()` Requirements: - Every `insert` and `delete` operation must be undoable. - After any new edit, the redo history must be cleared. - Discuss how to make the operations efficient. 3. **Prefix-based autocomplete** Add: - `suggest(prefix: str, k: int) -> List[str]` Requirements: - Words contain only lowercase letters. - Return the top `k` words that start with `prefix`, ranked by current frequency. - Frequencies must increase when words are added and decrease when words are removed. - You may assume the autocomplete index receives whole-word additions and removals derived from editor updates.