Design a Text Editor
Asked at Rippling
Problem
Design a text editor with cursor movement (left, right), text insertion, text deletion, and a print operation. The cursor starts at position 0. This problem tests your ability to model cursor-based editing with appropriate data structures.
Asked At
| Company | Difficulty | |
|---|---|---|
| Rippling | Hard | View all Rippling questions → |
How to Think About It
Brute force: use a string or array to store text. Each insert/delete shifts elements. That's O(n) per operation. The left/right moves are O(1) but text operations are slow.
Better approach: use a doubly linked list. Each character is a node. The cursor is a pointer. Insert adds a node after the cursor. Delete removes the node before the cursor. Left/right moves the pointer. All operations are O(1).
The doubly linked list approach: maintain a cursor pointer. Insert(x): add node with value x after cursor, move cursor forward. Delete(): remove node before cursor. MoveLeft(k): move cursor back k steps. MoveRight(k): move cursor forward k steps. Print(): collect all nodes and return as string.
For print, you need to traverse from the head to the end. The doubly linked list has O(n) print but O(1) for all other operations. Since print is called infrequently, this is acceptable.
Edge cases: cursor at beginning (can't move left), cursor at end (can't move right), deleting from empty text, inserting into empty text, moveLeft/moveRight with k larger than available positions.
Visual walkthrough:
init: head -> [dummy] -> [tail]. cursor at dummy.
addText("abc"): head -> [dummy] -> [a] -> [b] -> [c] -> [tail]. cursor at c.
cursorLeft(1): cursor moves to b.
deleteText(1): remove c. head -> [dummy] -> [a] -> [b] -> [tail]. cursor at b.
print(): traverse from head.next, return "ab".
addText("xyz"): head -> [dummy] -> [a] -> [b] -> [x] -> [y] -> [z] -> [tail]. cursor at z.
cursorRight(2): cursor stays at z (can't go past tail).
Optimal Approach
Data structure: doubly linked list with dummy head and tail nodes.
cursor: pointer to the current node (starts at dummy head)addText(text): for each character, insert a new node after cursor, advance cursordeleteText(k): delete up to k nodes before cursor, return count deletedcursorLeft(k): move cursor back k steps (min k, available steps)cursorRight(k): move cursor forward k steps (min k, available steps)textEditorText(): traverse from head to tail, collect characters, return string
The doubly linked list gives O(1) insert/delete/move and O(n) for printing.
Walkthrough:
addText("leetcode"): list = [dummy,l,e,e,t,c,o,d,e]. cursor at e.
cursorLeft(4): cursor moves to t.
deleteText(5): remove e,t,c,o,d. list = [dummy,l,e,e]. cursor at e (second).
addText("practice"): list = [dummy,l,e,e,p,r,a,c,t,i,c,e]. cursor at e.
textEditorText(): return "leetcodepractice" (traverse from first real node).
What Trips People Up in Real Interviews
Using a string or array. Insert and delete in the middle of a string are O(n) due to shifting. A doubly linked list gives O(1) for these operations.
Forgetting dummy head and tail nodes. Without them, you need null checks for insert at the beginning and delete at the beginning. Dummy nodes eliminate edge cases.
Confusing cursor position with array index. The cursor is a pointer to a node, not an integer index. Moving left means following prev pointers, not decrementing an index.
Not handling the case where cursorLeft or cursorRight tries to move past the boundaries. Clamp the movement: cursorLeft stops at head, cursorRight stops at tail.prev.
Deleting from the wrong side. Delete removes the character BEFORE the cursor (to the left of it), not after it. This matches most text editors' behavior.
Solution Code
class Node:
def __init__(self, val=''):
self.val = val
self.prev = None
self.next = None
class TextEditor:
def __init__(self):
self.head = Node()
self.tail = Node()
self.head.next = self.tail
self.tail.prev = self.head
self.cursor = self.head
def addText(self, text):
for ch in text:
node = Node(ch)
node.prev = self.cursor
node.next = self.cursor.next
self.cursor.next.prev = node
self.cursor.next = node
self.cursor = node
def deleteText(self, k):
deleted = 0
while k > 0 and self.cursor != self.head:
prev = self.cursor.prev
prev.next = self.cursor.next
self.cursor.next.prev = prev
self.cursor = prev
k -= 1
deleted += 1
return deleted
def cursorLeft(self, k):
while k > 0 and self.cursor != self.head:
self.cursor = self.cursor.prev
k -= 1
def cursorRight(self, k):
while k > 0 and self.cursor.next != self.tail:
self.cursor = self.cursor.next
k -= 1
def textEditorText(self):
result = []
node = self.head.next
while node != self.tail:
result.append(node.val)
node = node.next
return ''.join(result)Frequently Asked Questions
What is the Design a Text Editor problem?
Design a text editor with cursor movement (left, right), text insertion, text deletion, and a print operation. The cursor starts at position 0. This problem tests your ability to model cursor-based editing with appropriate data structures.
How do you solve Design a Text Editor?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Design a Text Editor?
Design a Text Editor is asked at Rippling. It is a hard difficulty problem.
What are common mistakes on Design a Text Editor?
- Using a string or array. Insert and delete in the middle of a string are `O(n)` due to shifting. A doubly linked list gives `O(1)` for these operations.
- Forgetting dummy head and tail nodes. Without them, you need null checks for insert at the beginning and delete at the beginning. Dummy nodes eliminate edge cases.
- Confusing cursor position with array index. The cursor is a pointer to a node, not an integer index. Moving left means following prev pointers, not decrementing an index.
- Not handling the case where cursorLeft or cursorRight tries to move past the boundaries. Clamp the movement: cursorLeft stops at head, cursorRight stops at tail.prev.
- Deleting from the wrong side. Delete removes the character BEFORE the cursor (to the left of it), not after it. This matches most text editors' behavior.