Katkat

Implement a Cursor-Based Text Editor

HarveySoftware Engineer · Onsite

Last updated

Design an in-memory cursor-based text editor supporting character insertion, deletion, and cursor navigation with efficient time complexity.

Problem Statement

Design a text editor that maintains a text string and a cursor position. The editor starts empty with the cursor at position 0 (the very beginning of the document).

Implement the TextEditor class:

  • TextEditor(): Initializes the text editor with an empty text.
  • insert(text: str) -> None: Inserts text at the current cursor position. The cursor moves to the right of the newly inserted characters.
  • delete(k: int) -> int: Deletes up to k characters immediately to the left of the cursor. The cursor shifts left by the number of deleted characters. Returns the actual number of characters deleted.
  • cursor_left(k: int) -> str: Moves the cursor k positions to the left (stopping at index 0 if it reaches the start of the text). Returns the last min(10, len) characters immediately to the left of the cursor (where len is the number of characters to the left of the cursor).
  • cursor_right(k: int) -> str: Moves the cursor k positions to the right (stopping at the end of the text if it reaches the end). Returns the last min(10, len) characters immediately to the left of the cursor.

Example

editor = TextEditor()
editor.insert("hello")        # Text: "hello|", cursor is after 'o'
editor.delete(2)              # Deletes 'l' and 'o', returns 2. Text: "hel|"
editor.insert("p")          # Text: "help|"
editor.cursor_left(2)         # Moves cursor 2 left: "he|lp", returns "he"
editor.cursor_right(1)        # Moves cursor 1 right: "hel|p", returns "hel"
editor.delete(10)             # Attempts to delete 10 left of cursor, deletes 3 ('h', 'e', 'l'), returns 3. Text: "|p"

Constraints

  • 1 <= len(text) <= 40 per insert call
  • 1 <= k <= 40 per delete, cursor_left, and cursor_right call
  • text consists only of lowercase English letters.
  • At most 2 * 10^5 calls will be made in total across all methods.
  • Operations must run efficiently enough to handle heavy sequences of insertions, moves, and deletions without quadratic time degradation.

Hints

Hint 1

Notice that the cursor naturally splits the document into two halves: text before the cursor and text after the cursor.

Hint 2

Using a single dynamic array or string requires O(n) shifts for each insertion or deletion in the middle of the text.

Hint 3

Consider maintaining two separate stacks or deques (one for characters to the left of the cursor and one for characters to the right) to make cursor moves and edits O(1) per character.

Follow-up questions

  • How would you support an Undo and Redo mechanism without snapshotting the entire state on every keystroke?
  • If the document grows to gigabytes in size and requires random-access jumps (e.g., jump to line 50,000), how would you replace the two-stack approach with data structures like a Rope or Piece Table?
  • How would you adapt this data model to support collaborative editing where multiple cursors concurrently edit the document?