Notepad System

Text editor with undo and redo

Design a small text editor: notes with insert and delete, unlimited undo and redo, tags and search. The undo stack is the heart of the design.

Overview

A notepad keeps a set of notes. Each note has a title, a body of text and some tags. The user inserts text, deletes text, and can take any edit back with undo, then put it back with redo. There is also a search box.

Interviewers ask this problem because undo is a clean, everyday case for the Command pattern: every edit becomes a small object that knows how to do itself and how to reverse itself. Two stacks of those objects give unlimited undo and redo in a few lines. The rest of the problem, notes, tags and search, tests whether you can keep each class to one job.

A strong answer names the two stacks in the first minute, explains why a new edit must empty the redo stack, and writes commands that store only what they need to reverse themselves, not a copy of the whole note.

Scoping the problem

Ask these before you write code. Each answer changes the design.

Is undo per note or one history for the whole app? — Decides where the history object lives — Per note, like most editors
Is there a limit on undo depth? — A bounded history drops the oldest command — Unlimited in the interview; a cap is a one-line change
Which edits are undoable: text only, or title and tags too? — Every undoable change must become a command — Text in the core; the rest as a follow-up
One user or many at once? — Concurrent editing is a different problem (see the follow-ups) — One user; no locks needed
How large can a note be? — Decides whether a plain string is enough — Small; a string works
What does search match? — Title, body, tags; case sensitivity — Case-insensitive on title and body

Two stacks

The history keeps two stacks. A new command runs, then goes on the undo stack. Undo pops the newest command, calls its undo(), and pushes it on the redo stack. Redo does the reverse. Both are O(1) stack moves; the cost that remains is the command's own work on the string.

The trace runs the code below on one note. The stacks list commands newest first.

1 — insert(0, 'hello') — hello — insert(0)
2 — insert(5, ' world') — hello world — insert(5), insert(0)
3 — delete(0, 6) — world — delete(0,6), insert(5), insert(0)
4 — undo() — hello world — insert(5), insert(0) — delete(0,6)
5 — undo() — hello — insert(0) — insert(5), delete(0,6)
6 — redo() — hello world — insert(5), insert(0) — delete(0,6)
7 — insert(11, '!') — hello world! — insert(11), insert(5), insert(0) — empty

Step 7 is the rule interviewers check: a new edit empties the redo stack. The redo entry delete(0,6) was recorded against text that no longer exists; replaying it after the new insert would remove the wrong characters.

Why a new edit clears redo

Think of the history as a state machine. Redo is only valid while the note is exactly as it was when the undo happened.

Command versus snapshot

There are two ways to make an edit reversible: store the change (Command) or store a copy of the text before the change (Memento, the snapshot pattern). Both come from the 1994 Design Patterns book.

Command (this design) — Position and the inserted or removed text — About the size of the typed text, a few KB — One string splice
Snapshot of the whole note — A full copy of the content — Roughly 1,000 × 10 MB = 10 GB — Swap the string back
Snapshot with sharing — A copy of only the changed pieces — Small, but needs a tree-shaped text structure — Pointer swap

The command stores only its delta, so InsertCommand keeps the position and the text, and DeleteCommand keeps the range and the text it removed. The price is care: every command must reverse itself exactly, and a compound operation such as replace-all becomes a list of small commands undone together.

Search and tags

Search is a scan over every note, lowercasing the query and the text once. That is O(total text) per query and is fine for a personal notepad. If the interviewer pushes on scale, describe an inverted index: a dict from each word to the set of note ids that contain it, updated when a command runs.

Linear scan (the code below) — O(total text) — none — Hundreds of notes
Inverted index: word to set of note ids — O(words in query) plus a set intersection — Re-index the edited note — Many notes, frequent search
Tag index: tag to set of note ids — O(1) per tag — Update two sets on tag change — Always; tags are exact matches

What you will be able to do

Explain undo and redo with two stacks, and say why a new edit empties the redo stack.
Write insert and delete commands that store only what they need to reverse themselves.
Compare Command with snapshots and give the memory argument with numbers.
Keep Notepad, Note and CommandHistory to one job each and say which class owns what.
Answer the follow-ups: grouping edits, bounded history, large text, and many users at once.

Functional requirements

Create notes with a title; read, rename and delete them
Insert text at a position and delete a range of text in a note
Undo and redo any number of text edits, per note
A new edit after an undo discards the redo history
Add and remove tags on a note; list notes by tag
Search notes by a case-insensitive match on title or content

Non-functional requirements

Undo and redo are O(1) stack operations plus one string splice
A history entry holds the delta only, never a copy of the whole note
Invalid positions and unknown note ids raise errors instead of silently doing nothing
Single user; the classes are not shared between threads

Interview questions

Why store commands instead of a snapshot of the note before each edit?
Typing one character at a time would make undo remove one letter per step. How do you group edits?
What should happen to undo if the note is renamed or a tag is added?
Two users edit the same note at once. What changes?
A 100 MB log file is opened in the editor. What breaks?
What bugs do candidates write here, and how do you avoid them?