How do you calculate the edit distance between two strings?
This problem measures the minimum number of operations to transform one string into another. It is a classic dynamic programming problem.
Why Interviewers Ask This
Edit distance is widely used in spell checkers and DNA sequencing. Interviewers ask this to test complex DP table construction and understanding of insertion, deletion, and substitution costs.
How to Answer This Question
Construct a 2D DP table where dp[i][j] represents the edit distance between the first i characters of string A and the first j characters of string B. Fill the table based on match/mismatch logic. Optimize space if possible by using two rows.
Key Points to Cover
- Build 2D DP table
- Handle insert, delete, substitute
- Base cases for empty strings
- Optimize space if needed
Sample Answer
I will create a DP table where rows represent characters of the first string and columns represent the second. If characters match, the cost is the same as the diagonal. If they differ, we take the minimum of insertion, deletion, or substitution plus one. The bottom-right cell gives the final edit distance.
Common Mistakes to Avoid
- Incorrect recurrence relation
- Off-by-one errors in indexing
- Not handling empty strings
Practice This Question with AI
Answer this question orally or via text and get instant AI-powered feedback on your response quality, structure, and delivery.
Related Interview Questions
How do you count ongoing events for multiple query times?
Hard
GoogleWhat is the optimal path to maximize collected rocks in a grid?
Hard
Goldman SachsHow do you find a triplet where a squared equals b squared plus c squared?
Medium
AmazonExplain the concept of graph components in computer science?
Medium
Microsoft CorporationWhy are you suitable for this specific role at Amazon?
Medium
AmazonDesign a 'Trusted Buyer' Reputation Score for E-commerce
Medium
Amazon