Katkat
Back

Design an Editable Text Buffer

OpenAIMachine Learning Engineer · Technical Screen
MediumMachine Learning EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to design an efficient data structure for text manipulation while implementing undo/redo history and a dynamic prefix-based autocomplete feature.

Problem Statement

Design a class TextEditor that supports efficient text operations and provides a way to suggest completions based on current word frequencies. The editor should support the following operations:

  • insert(char): Inserts a character at the current cursor position and moves the cursor forward.
  • delete(): Deletes the character to the left of the cursor.
  • move_cursor(position): Moves the cursor to a specific index.
  • undo(): Reverts the last modification (insertion or deletion).
  • redo(): Re-applies the last undone modification.
  • suggest(prefix): Returns the top 3 most frequently typed words that start with the given prefix. A word is defined as a sequence of alphanumeric characters separated by spaces.

Constraints

  • insert and delete should perform better than O(N) where N is the total text length.
  • Assume total characters do not exceed 10^5.
  • suggest should prioritize words based on how often they have been 'committed' (i.e., typing a space or newline).

Example

# Initialize
editor = TextEditor()
editor.insert('h')
editor.insert('i')
# Text: "hi", Cursor at 2

editor.undo()
# Text: "h", Cursor at 1

editor.redo()
# Text: "hi", Cursor at 2

Edge Cases

  • Deleting at the beginning of the buffer.
  • Undo/Redo operations when the history stack is empty.
  • Handling empty suggestions when no words match the prefix.

Hints

Hint 1

Consider using a Gap Buffer or a Doubly Linked List of characters to make insertions and deletions near the cursor O(1) or O(log N).

Hint 2

To manage undo/redo, use two separate stacks to store the state of the buffer or the command objects representing the operations.

Hint 3

For the autocomplete feature, maintain a Trie where each node stores the frequency of words passing through it, and update the frequency only when a word is completed.

Follow-up questions

  • How would you modify your design to support concurrent editing by multiple users in real-time?
  • If the text grows to several gigabytes, what changes would you make to the storage strategy to handle memory constraints?
  • How does your implementation handle complex character encodings (e.g., emojis or multi-byte Unicode characters)?