Edit Distance (Levenshtein)
As a Fresher engineer, explain Edit Distance (Levenshtein). What problem does it solve and how would you describe it in an interview?
Answers use simple, clear English.
Audio N/AQuick interview answer
At Fresher depth: start with the problem, then mechanism, then a short example. Min insert/delete/replace ops to transform word1→word2.
Detailed answer
At Fresher depth: start with the problem, then mechanism, then a short example. Min insert/delete/replace ops to transform word1→word2. Recurrence: match → diagonal; else 1 + min(left, up, diag). Base: empty string costs. Core: Min insert/delete/replace ops to transform word1→word2. Recurrence: match → diagonal; else 1 + min(left, up, diag). Base: empty string costs. Real-time example: Autocomplete spell correction: rank 'sittng' → 'sitting' by minimum edits. Pros: Directly models typos; extends to weighted operations in NLP pipelines. Cons: O(mn) memory; use two-row rolling DP for interviews when m,n large. Common mistakes: Using LCS recurrence instead of min of three ops; wrong base cases for i=0 or j=0. Best practices: State three operations explicitly; mention Damerau-Levenshtein for transpositions. Audience level: Fresher.
Full explanation
Min insert/delete/replace ops to transform word1→word2. Recurrence: match → diagonal; else 1 + min(left, up, diag). Base: empty string costs.
Real example & use case
Autocomplete spell correction: rank 'sittng' → 'sitting' by minimum edits.
Pros & cons
Pros: Directly models typos; extends to weighted operations in NLP pipelines. Cons: O(mn) memory; use two-row rolling DP for interviews when m,n large.
Common mistakes
Using LCS recurrence instead of min of three ops; wrong base cases for i=0 or j=0.
Best practices
State three operations explicitly; mention Damerau-Levenshtein for transpositions.
Follow-up questions
- How would you test Edit Distance (Levenshtein)?
- What metrics prove Edit Distance (Levenshtein) is healthy in prod?
- How does Edit Distance (Levenshtein) change at 10× traffic?