Text Editor with a Cursor: Typing, Backspace, and Four-Way Cursor Movement

Implement a `TextEditor` class that holds one document and a cursor. The cursor sits between two characters, or at the start or end of the text, and every edit happens at the cursor. Start with three operations: - `type_in(char)`: insert one character at the cursor. The cursor ends up just after the inserted character. - `backspace()`: delete the character immediately before the cursor. - `__str__()`: return the text with a `|` inserted at the cursor position. ```python e = TextEditor() e.type_in("h") e.type_in("i") str(e) # "hi|" e.backspace() str(e) # "h|" ``` The interviewer then adds cursor movement in two follow-ups: first left and right, then up and down. ### Constraints and Clarifications - A new editor is empty, with the cursor at the start, so `str(TextEditor())` is `"|"`. - `type_in` receives exactly one character per call. - Strings in the examples are shown as Python literals, so `\n` stands for a newline character. ### Clarifying Questions - What should `backspace()` do when the cursor is at the start of the document? - Can the document itself contain `|`, and if so, how should `__str__` keep the cursor position unambiguous? - What should a move do when it would leave the document, such as left at the start or right at the end? - For vertical movement, what defines a line: a typed newline character, or a fixed display width with wrapping? ### Part 1 — Typing, backspace and rendering Implement `type_in`, `backspace` and `__str__`, and state the time complexity of each operation. ```hint Edits happen in one place Every operation touches the text only at the cursor. Look for a representation in which the cost of an edit does not depend on how much text sits after the cursor. ``` #### What This Part Should Cover - A representation chosen for cheap edits at the cursor, and why it beats a plain string or a list with a cursor index - Correct behavior of backspace at the start of the document - Per-operation complexity, including the cost of building the string in `__str__` ### Part 2 — Moving the cursor left and right Add `move_cursor(direction)`, where `direction` is `"left"` or `"right"`, moving the cursor by one character. Typing and backspace must keep working at the new cursor position. ```python # document "cat", cursor at the end: "cat|" e.move_cursor("left") # "ca|t" e.type_in("r") # "car|t" e.backspace() # "ca|t" ``` ```hint One character changes sides A one-step move changes which side of the cursor exactly one character is on. Check that your representation can do that without touching the rest of the text. ``` #### What This Part Should Cover - Constant-time left and right moves that keep later edits at the cursor correct - Behavior at both ends of the document - How typing and backspace interact with a cursor in the middle of the text ### Part 3 — Moving the cursor up and down Extend `move_cursor` to accept `"up"` and `"down"`, moving the cursor to the previous or next line. ```python # document "abc\nxyz", cursor after "x": "abc\nx|yz" e.move_cursor("up") # "a|bc\nxyz" ``` ```hint Column and line length A vertical move needs two numbers: the cursor's column in its current line and the length of the line it moves to. Think about how you find each one in your representation, and whether storing something extra avoids rescanning. ``` #### Clarifying Questions for this Part - When the target line is shorter than the cursor's current column, where should the cursor land? - Should a run of vertical moves remember the column the user started from, as most editors do, or should each move use the current column? - What happens on `"up"` from the first line or `"down"` from the last line? #### What This Part Should Cover - How lines are defined and how the cursor's column is computed - The landing position when the target line is shorter, and behavior on the first and last lines - The cost of a vertical move, and whether a line-oriented structure would be a better trade ### What a Strong Answer Covers - Settles boundary behavior (backspace at the start, moves past either end, vertical moves on the first and last lines) before coding - Picks a representation in which typing, backspace and horizontal moves are O(1), and justifies it against simpler alternatives - Renders `__str__` correctly with the cursor at the start, in the middle and at the end - Extends the design to vertical movement without rewriting the earlier operations - Tests each operation with short call sequences, including the edge cases ### Follow-up Questions - How would you add `undo()` and `redo()` for typing and backspace? - If documents are many megabytes and `__str__` is called after every keystroke, what would you change? - How do a gap buffer, a rope and a list of lines compare for this editor, and when would you pick each?