Edit Distance
Given two strings str1 and str2 and below operations that can performed on str1. Find minimum number of edits (operations) required to convert ‘str1’ into ‘str2’.

Insert
Remove
Replace
All of the above operations are of equal cost.
Input: str1 = "geek", str2 = "gesek"
Output: 1
We can convert str1 into str2 by inserting a 's'.

Input: str1 = "cat", str2 = "cut"
Output: 1
We can convert str1 into str2 by replacing 'a' with 'u'.

Input: str1 = "sunday", str2 = "saturday"
Output: 3
Last three and first characters are same. We basically
need to convert "un" to "atur". This can be done using
below three operations.
Replace 'n' with 'r', insert t, insert a.

Question

Edit Distance

Given two strings str1 and str2 and below operations that can performed on str1. Find minimum number of edits (operations) required to convert ‘str1’ into ‘str2’.

Insert

Remove

Replace

All of the above operations are of equal cost.

Input: str1 = "geek", str2 = "gesek"

Output: 1

We can convert str1 into str2 by inserting a 's'.

Input: str1 = "cat", str2 = "cut"

Output: 1

We can convert str1 into str2 by replacing 'a' with 'u'.

Input: str1 = "sunday", str2 = "saturday"

Output: 3

Last three and first characters are same. We basically

need to convert "un" to "atur". This can be done using

below three operations.

Replace 'n' with 'r', insert t, insert a.

Accepted Answer

Firstly I gave the interviewer, a recursive solution then he asked me to reduce complexity as it was exponential of recursive solution so I gave him a top-down DP solution.

Accepted Answer

Recursive Approach

We will write a recursive approach.
The base case would be if the length of the first string is 0 then we need to add all the characters of the second string to the first string hence return the length of the second string. Similarly, if the length of the second string is 0 return length of the first string.
Now the recurrence relation is as follows:
- If the last characters of two strings are not the same, try all operations and it will cost 1. Here i is initially the last index of s1 and j is initially the last index of s2 and f(i, j) is the edit distance of str1(0, i) to str2(0, j). str(i, j) denotes the substring formed by taking the characters at index i through index j.
- f(i, j) = 1 + min(f(i - 1, j), f(i, j - 1), f(i - 1, j - 1))
- Here the three recursive calls are for the insert, remove and replace respectively and s1, s2 will be parameters of all function calls. If the last characters of two strings are the same (s1[i] == s2[j]) then the relationship would be:
  - f(i, j) = f(i - 1, j - 1)

Space Complexity: OtherExplanation:

O(N + M), Where N is the size of the first string and M is the size of the second string.

Since we are making recursive calls that require the recursion stack. Therefore the space complexity is O(N + M).

Time Complexity: OtherExplanation:

O(3 ^ (N * M)), Where N is the size of the first string and M is the size of the second string.

Since we are making 3 recursive calls each time, therefore the time complexity is O(3 ^ (N * M)).

Accepted Answer

Memoization

We will write a recursive approach and memoize it. So first make a 2D array of size (N + 1) x (M + 1) where N and M are lengths of the two strings and fill it with -1. -1 means that we don’t know the answer for that state.
The base case would be if the length of the first string is 0 then we need to add all the characters of the second string to the first string hence return the length of the second string. Similarly, if the length of the second string is 0 return the length of the first string. Else check the value of the dp array at index i, j. If it's not equal to -1, simply return its value. Otherwise, go the following step
The recurrence relation is as follows:
- If the last characters of two strings are not the same, try all operations and it will cost 1. Here i is initially the last index of s1 and j is initially the last index of s2. f(i, j) is the edit distance of str1(0, i) and str2(0, j).
- str(i, j) denotes the substring formed by taking the characters at index i through index j.
- f(i, j) = 1 + min(f(i - 1, j), f(i, j - 1), f(i - 1, j - 1))
- Here the three recursive calls are for the insert, remove and replace respectively and s1, s2 will be parameters of all function calls. If the last characters of two strings are the same (s1[i] == s2[j]) then the relationship would be:
  - f(i, j) = f(i - 1, j - 1)
Before returning the result, store it in the array at index i, j. This will save the overlapping subproblems.

Space Complexity: O(m*n) - For 2d arraysExplanation:

O(N * M), where N is the length of the first string and M is the length of the second string

Since we are making a 2-dimensional array of size N * M. Therefore the space complexity is O(N * M).

Time Complexity: O(m*n) - For 2d arraysExplanation:

O(N * M), where N is the length of the first string and M is the length of the second string.

Since we fill the entire memoization array and we visit each cell just once via recursion. Therefore the time complexity is O(N * M).

Accepted Answer

Iterative DP

We will use the dynamic programming approach here and will have a 2-dimensional array, dp where

dp[i][j] stores the edit distance of the (i+1)th length substring of str1 and (j+1)th length substring of str2 starting from index 0

The base case would be when the size of first-string is 0 then edit distance will be equal to the size of other string i.e when i = 0 then dp[i][j] = j and similarly vice versa, so if j = 0 then dp[i][j] = i.

Now we will use our recurrence relation

// If str1[i - 1] == str2[j - 1]
dp[i][j] = dp[i-1][j-1]
// Otherwise
dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1])

Space Complexity: O(m*n) - For 2d arraysExplanation:

O(N * M), where N is the length of the first string and M is the length of the second string.

Since we are making a 2-dimensional array of size N * M. Therefore the space complexity is O(N * M).

Time Complexity: O(m*n) - For 2d arraysExplanation:

O(N * M), where N is the length of the first string and M is the length of the second string.

Since we are running two nested loops of sizes N and M. Therefore the time complexity is O(N * M).

Top Goldman Sachs Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Goldman Sachs Software Developer