PPractick

The problem

You're on the team building the "spell-check + auto-fix" backend for a code-editor plugin (think: quick-fix suggestions when a variable name is misspelled, or a git-diff-style similarity scorer). Given two strings word1 and word2, you need to compute the minimum number of operations required to convert word1 into word2. The three allowed operations are:

1. Insert a character
2. Delete a character
3. Replace a character

This exact metric (edit distance / Levenshtein distance) is also what powers DNA sequence alignment tools and "did you mean" search corrections.

Function signature

int minDistance(string word1, string word2);

Test cases

word1	word2	Output	Explanation
"horse"	"ros"	3	horse → rorse (replace h→r) → rose (remove r) → ros (remove e)
"intention"	"execution"	5	classic textbook example
""	"abc"	3	insert a, b, c
"abc"	""	3	delete a, b, c
"abc"	"abc"	0	already equal
"a"	"b"	1	replace a→b
""	""	0	trivial

(Always mention these edge cases — empty strings, identical strings, single-char strings — before coding.)

How interviewers phrase it

• "Given two words, find the minimum number of insertions, deletions, and substitutions to convert one into the other."
• "How similar are these two strings?" (disguised framing — they want edit distance)
• "Design a spell-checker's suggestion scorer" (system-design-flavored disguise of the same core DP)

Clarifying questions to ask

1. Are all three operations (insert/delete/replace) allowed, or only a subset? (Some variants only allow insert+delete — that changes the problem to LCS-based edit distance.)
2. Do all operations cost the same (unit cost), or are costs weighted differently (e.g., replace costs 2)? This changes the DP transition slightly.
3. Are the strings case-sensitive?
4. What's the expected length of the strings? (If very large, O(n·m) might still be fine since it's polynomial, but they may ask about space optimization.)
5. Do I need to just return the count, or also reconstruct the sequence of operations?

Follow-ups to expect

1. "Can you optimize space?"
2. "Can you print the actual sequence of operations, not just the count?"
3. "What if operations have different costs?" (e.g., insert=1, delete=1, replace=2)
4. "What if only insert and delete are allowed (no replace)?"
5. "Can you solve it recursively with memoization first before jumping to bottom-up?"
6. "What's the relation between this and LCS (Longest Common Subsequence)?"

Related questions

• Longest common subsequence Hard
• Print Longest Common Subsequence Hard
• Longest common substring Hard
• Longest palindromic subsequence Hard
• Minimum insertions to make string palindrome Hard
• Minimum insertions or deletions to convert string A to B Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in