On campus interview: 1) How would you implement a Naive String matching program? 2) How do you know when if a binary tree is a BST?

On site interview: 1) Given 2 strings that you are reading from 2 streams (so you don't know the length of any of the strings and the only method you have is getNextChar() for each string), implement a program that tells you when 2 of these strings are 1 edit away from being the same. 1- edit is defined as a single insert char, single remove char or single modify/change char in only 1 of the strings.

Question

On campus interview: 1) How would you implement a Naive String matching program? 2) How do you know when if a binary tree is a BST?

On site interview: 1) Given 2 strings that you are reading from 2 streams (so you don't know the length of any of the strings and the only method you have is getNextChar() for each string), implement a program that tells you when 2 of these strings are 1 edit away from being the same. 1- edit is defined as a single insert char, single remove char or single modify/change char in only 1 of the strings.

Ramon · Accepted Answer

The purest solution is probably the following, but it doesn't provie the chars that are different:
The more math approach would be;
public class LevenshteinDistance {                                               
    private static int minimum(int a, int b, int c) {                            
        return Math.min(Math.min(a, b), c);                                      
    }                                                                            
                                                                                 
    public static int computeLevenshteinDistance(CharSequence lhs, CharSequence rhs) {      
        int[][] distance = new int[lhs.length() + 1][rhs.length() + 1];        
                                                                                 
        for (int i = 0; i <= lhs.length(); i++)                                 
            distance[i][0] = i;                                                  
        for (int j = 1; j <= rhs.length(); j++)                                 
            distance[0][j] = j;                                                  
                                                                                 
        for (int i = 1; i <= lhs.length(); i++)                                 
            for (int j = 1; j <= rhs.length(); j++)                             
                distance[i][j] = minimum(                                        
                        distance[i - 1][j] + 1,                                  
                        distance[i][j - 1] + 1,                                  
                        distance[i - 1][j - 1] + ((lhs.charAt(i - 1) == rhs.charAt(j - 1)) ? 0 : 1));
                                                                                 
        return distance[lhs.length()][rhs.length()];                           
    }                                                                            
}

I assume the characters could be out of order and are not always in the same sequence? In Java or where it is permitted, you can possibly convert the string to an array list and do the removeAll or retainAll() for the bigger collection. You would need to sort the elements beforehand. You can also possibly use binary trees to keep the elements as well if you don't want to sort. You can use a simple size() to check if they are 1 edit away. You can also keep on adding to the arrays to see if the new chars preserve the 1 editor broke. Another idea I had is to use regex and count how many times you have a match. If a character is not found more then twice, you know you are not 1 edit. You only iterate through the shorter string. That way you might not need to loop through both of the arrays but doesn't really change much. This same idea could be applied in Java for count() for the array, that way you just need to iterate through the possible characters in use by each string. Which makes me think that the simplest approach is just to count the characters as they arrive and then compare the numbers.

J · Answer

For the onsite question, you can simplify the concept of an "edit" by collapsing the add/delete definitions into one definition, since deleting a character from one string is the same as adding one to the other. 

From there, you can create a boolean flag `edited` to indicate if an edit has been performed (since only one is allowed), read both strings character by character in parallel, and where a discrepancy is detected, identify if both characters one ahead match (meaning one character was edited) or if a character one ahead in one string matches the current character in the other string (meaning one character was added/deleted). If there is no such match, or if the `edited` flag is already set to true, then more than one edit is required to match the strings.

Meta

Meta Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches