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.

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.

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.

# document "cat", cursor at the end: "cat|"
e.move_cursor("left") # "ca|t"
e.type_in("r") # "car|t"
e.backspace() # "ca|t"

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.

# document "abc\nxyz", cursor after "x": "abc\nx|yz"
e.move_cursor("up") # "a|bc\nxyz"

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