CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

Microsoft Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person



Comment hidden because of low score. Click to expand.
2
of 2 vote

This is the minimum edit distance algorithm. You can look it up at various sources, some of them listed below (AKA "Levenshtein distance"):
w_ww.stanford.edu/class/cs124/lec/med.pdf
w_ww.csse.monash.edu.au/~lloyd/tildeAlgDS/Dynamic/Edit/
e_n.wikipedia.org/wiki/Levenshtein_distance

- ashot madatyan April 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

find longest common subseuqence, and use the avail operations on the rest of the characters.

- gen-y-s April 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I would think it should use the A* search algorithm.

- chenlc626 April 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In python strings are immutable . I tried similar kind of string manipulation problem but it didn't work out . Use C/C++ or StringBuffer in Java

- Aditya Pn April 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Using Edit distance algorithm:
Code:

public final int I = 8;
	public final int D = 6;
	public final int R = 8;
	public int minEdits(char s1[], char s2[]) {
		int m = s1.length, n = s2.length;
		int d[][] = new int[m + 1][n + 1];
		for (int i = 0; i <= m; i++) {
			for (int j = 0; j <= n; j++) {
				if (i == 0)
					d[i][j] = j * I;
				else if (j == 0)
					d[i][j] = i * D;
				else {
					if (j < i)
						d[i][j] = minimum(d[i - 1][j - 1]
								+ ((s1[i - 1] == s2[j - 1]) ? 0 : R),
								d[i - 1][j] + R, d[i][j - 1] + I);
					else
						d[i][j] = minimum(d[i - 1][j - 1]
								+ ((s1[i - 1] == s2[j - 1]) ? 0 : R),
								d[i - 1][j] + R, d[i][j - 1] + D);
				}

			}
		}
		return d[m][n];
	}

	public int minimum(int a, int b, int c) {
		return Math.min(a, Math.min(b, c));
	}

- Dhass April 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Using Edit distance algo.
Code:

public final int I = 8;
	public final int D = 6;
	public final int R = 8;
	public int minEdits(char s1[], char s2[]) {
		int m = s1.length, n = s2.length;
		int d[][] = new int[m + 1][n + 1];
		for (int i = 0; i <= m; i++) {
			for (int j = 0; j <= n; j++) {
				if (i == 0)
					d[i][j] = j * I;
				else if (j == 0)
					d[i][j] = i * D;
				else {
					if (j < i)
						d[i][j] = minimum(d[i - 1][j - 1]
								+ ((s1[i - 1] == s2[j - 1]) ? 0 : R),
								d[i - 1][j] + R, d[i][j - 1] + I);
					else
						d[i][j] = minimum(d[i - 1][j - 1]
								+ ((s1[i - 1] == s2[j - 1]) ? 0 : R),
								d[i - 1][j] + R, d[i][j - 1] + D);
				}

			}
		}
		return d[m][n];
	}

	public int minimum(int a, int b, int c) {
		return Math.min(a, Math.min(b, c));
	}

- Dhass April 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Using Edit distance algo
Code:

public final int I = 8;
	public final int D = 6;
	public final int R = 8;
	public int minEdits(char s1[], char s2[]) {
		int m = s1.length, n = s2.length;
		int d[][] = new int[m + 1][n + 1];
		for (int i = 0; i <= m; i++) {
			for (int j = 0; j <= n; j++) {
				if (i == 0)
					d[i][j] = j * I;
				else if (j == 0)
					d[i][j] = i * D;
				else {
					if (j < i)
						d[i][j] = minimum(d[i - 1][j - 1]
								+ ((s1[i - 1] == s2[j - 1]) ? 0 : R),
								d[i - 1][j] + R, d[i][j - 1] + I);
					else
						d[i][j] = minimum(d[i - 1][j - 1]
								+ ((s1[i - 1] == s2[j - 1]) ? 0 : R),
								d[i - 1][j] + R, d[i][j - 1] + D);
				}

			}
		}
		return d[m][n];
	}

- Dhass April 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int minEdits(char s1[], char s2[]) {
		int m = s1.length, n = s2.length;
		int d[][] = new int[m + 1][n + 1];
		for (int i = 0; i <= m; i++) {
			for (int j = 0; j <= n; j++) {
				if (i == 0)
					d[i][j] = j * I;
				else if (j == 0)
					d[i][j] = i * D;
				else {
					if (j < i)
						d[i][j] = minimum(d[i - 1][j - 1]
								+ ((s1[i - 1] == s2[j - 1]) ? 0 : R),
								d[i - 1][j] + R, d[i][j - 1] + I);
					else
						d[i][j] = minimum(d[i - 1][j - 1]
								+ ((s1[i - 1] == s2[j - 1]) ? 0 : R),
								d[i - 1][j] + R, d[i][j - 1] + D);
				}

			}
		}
		return d[m][n];
	}

- Dhass April 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can solve this by Edit distance algo. Just by adding Insert,Delete,Replace costs.

- Dhass April 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

a typical dynamic problem called Edit Distance.

pasted my solution here:
public static int minDistance(String word1, String word2) {
// Start typing your Java solution below
// DO NOT write main() function
int[][] ans = new int[word1.length() + 1][word2.length() + 1];
for(int i = 0; i < word1.length() + 1; i++) {
ans[i][0] = i;
}
for(int i = 0; i < word2.length() + 1; i++) {
ans[0][i] = i;
}

for(int i = 1; i < word1.length() + 1; i++) {
for(int j = 1; j < word2.length() + 1; j ++) {
if(word1.charAt(i -1) == word2.charAt(j - 1)) {
ans[i][j] = getMin(ans[i-1][j-1], ans[i-1][j] + 1, ans[i][j-1] + 1);
} else {
ans[i][j] = getMin(ans[i-1][j-1] + 1, ans[i-1][j] + 1, ans[i][j-1] + 1);
}
}
}

return ans[word1.length()][word2.length()];
}

public static int getMin(int a, int b, int c) {
if(a < b && a < c) return a;
if(b < c) return b;
return c;
}

public static void main(String[] args) {
System.out.println(minDistance("algorithm", "altruistic"));
}

- chiou April 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

a typical dynamic problem called Edit Distance.

pasted my solution here:
public static int minDistance(String word1, String word2) {
// Start typing your Java solution below
// DO NOT write main() function
int[][] ans = new int[word1.length() + 1][word2.length() + 1];
for(int i = 0; i < word1.length() + 1; i++) {
ans[i][0] = i;
}
for(int i = 0; i < word2.length() + 1; i++) {
ans[0][i] = i;
}

for(int i = 1; i < word1.length() + 1; i++) {
for(int j = 1; j < word2.length() + 1; j ++) {
if(word1.charAt(i -1) == word2.charAt(j - 1)) {
ans[i][j] = getMin(ans[i-1][j-1], ans[i-1][j] + 1, ans[i][j-1] + 1);
} else {
ans[i][j] = getMin(ans[i-1][j-1] + 1, ans[i-1][j] + 1, ans[i][j-1] + 1);
}
}
}

return ans[word1.length()][word2.length()];
}

public static int getMin(int a, int b, int c) {
if(a < b && a < c) return a;
if(b < c) return b;
return c;
}

public static void main(String[] args) {
System.out.println(minDistance("algorithm", "altruistic"));
}

- chiou April 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

a typical dynamic problem called Edit Distance.

pasted my solution here:
public static int minDistance(String word1, String word2) {
// Start typing your Java solution below
// DO NOT write main() function
int[][] ans = new int[word1.length() + 1][word2.length() + 1];
for(int i = 0; i < word1.length() + 1; i++) {
ans[i][0] = i;
}
for(int i = 0; i < word2.length() + 1; i++) {
ans[0][i] = i;
}

for(int i = 1; i < word1.length() + 1; i++) {
for(int j = 1; j < word2.length() + 1; j ++) {
if(word1.charAt(i -1) == word2.charAt(j - 1)) {
ans[i][j] = getMin(ans[i-1][j-1], ans[i-1][j] + 1, ans[i][j-1] + 1);
} else {
ans[i][j] = getMin(ans[i-1][j-1] + 1, ans[i-1][j] + 1, ans[i][j-1] + 1);
}
}
}

return ans[word1.length()][word2.length()];
}

public static int getMin(int a, int b, int c) {
if(a < b && a < c) return a;
if(b < c) return b;
return c;
}

public static void main(String[] args) {
System.out.println(minDistance("algorithm", "altruistic"));
}

- chiou April 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

a typical dynamic problem called Edit Distance.

pasted my solution here:
<pre> public static int minDistance(String word1, String word2) {
// Start typing your Java solution below
// DO NOT write main() function
int[][] ans = new int[word1.length() + 1][word2.length() + 1];
for(int i = 0; i < word1.length() + 1; i++) {
ans[i][0] = i;
}
for(int i = 0; i < word2.length() + 1; i++) {
ans[0][i] = i;
}

for(int i = 1; i < word1.length() + 1; i++) {
for(int j = 1; j < word2.length() + 1; j ++) {
if(word1.charAt(i -1) == word2.charAt(j - 1)) {
ans[i][j] = getMin(ans[i-1][j-1], ans[i-1][j] + 1, ans[i][j-1] + 1);
} else {
ans[i][j] = getMin(ans[i-1][j-1] + 1, ans[i-1][j] + 1, ans[i][j-1] + 1);
}
}
}

return ans[word1.length()][word2.length()];
}

public static int getMin(int a, int b, int c) {
if(a < b && a < c) return a;
if(b < c) return b;
return c;
}

public static void main(String[] args) {
System.out.println(minDistance("algorithm", "altruistic"));
}</pre>

- chiou April 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

there is another thing that can be kept in mind while solving: there is a fixed cost of either deletion or insertion if the lengths of the input strings are different. and the additional cost can be thought of as the minimum hemming distance (multiplied by appropriate cost).

tried some code, there could be some bugs (and scope for improving efficiency) ..
have a slightly modified hemming distance calculator (adjusts length) and there is some redundancy in code .. but you know what to do about that :)

int LevenshteinDist(String a, String b) {
        int mincost = Integer.MAX_VALUE;
        
        int RCost = 8;
        int DCost = 6;
        int ICost = 8;
        
        if(a.equals(b)) return 0;
        int aLength = a.length();
        int bLength = b.length();
        
        String bigger = aLength > bLength ? a:b;
        String smaller = aLength <= bLength ? a:b;
        
        
        int fixedCost = 0;
        if(bLength > aLength) {
            fixedCost = ICost * (bLength - aLength);
        }else if (bLength < aLength) {
            fixedCost = DCost * (bLength - aLength);
        }
        fixedCost *= (fixedCost < 0 ? -1:1);    
        for(int i = 0; i <= bigger.length() -smaller.length();i++) {
            int cost = FindHemmingDist(bigger.substring(i, i+ smaller.length()),smaller);
            mincost = cost < mincost ? cost : mincost;
        }
        
        return mincost*RCost + fixedCost;
    }
    
    int FindHemmingDist(String src, String dst) {
        int dist = 0;
        int sLength = src == null ? 0:src.length();
        int dLength = dst == null ? 0:dst.length();
        
        String bigger = sLength > dLength ? src:dst;
        String smaller = sLength <= dLength ? src : dst;
        
        for(int i = 0; i < smaller.length(); i++) {
            //for (int j = 0; j < smaller.length(); j++) {
                if(bigger.charAt(i) != smaller.charAt(i)) dist++;
            //}
        }
        return dist;
    }

- VJ April 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is the trivial algorithm that is optimal once memoized or done in a dynamic programming fashion

def lev(word1, word2, costs, i=0, j=0):
	if i >= len(word1) or j >= len(word2):
		return float('inf')

	if i == len(word1) - 1 and j == len(word2) - 1:
		return 0

	return min(
		lev(word1, word2, costs, i, j + 1) + costs[0],
		lev(word1, word2, costs, i + 1, j) + costs[1],
		lev(word1, word2, costs, i + 1, j + 1) + (costs[2] if word1[i] != word2[j] else 0)
	)

Here costs is a tuple if (Insert, Delete, Replace) costs

- Lite April 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Dynamic programming approach:

Let S[I][J] denote the min valued operation required to convert the 1st I chars of A into first J chars of B.

Let Cd Ci Cr denote the cost pf deletion, insertion and replacement respectively.

S[0][J] = 0;S[I][0]=0;
S[I][J] = MIN ( S[I-1][J] + Cd , S[I][J-1] + Ci , (A[I] == B[J])? S[I-1][J-1], S[I-1][J-1] + Cr )

S[A.size()][B.size()] gives the optimal solution.

- sd September 14, 2013 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More