Longest Common Prefix in an array of Strings

Question

Please be brutal, and treat this as if I was at an interview at a top 5 tech firm.

Question: Write a function to find the longest common prefix string amongst an array of strings.

Time it took: 17 minutes

Worst case complexity analysis: n possible array elements, each can have length m that we are traversing, hence O(n*m); m could be a constant, since it's rare to find a string with length, so in a sense, I imagine this could be treated as O(n *constant length(m)) = O(n)?

Space complexity analysis: O(n)

public String longestCommonPrefix(String[] strs) {
    String longestPrefix = "";
    if(strs.length>0){
        longestPrefix = strs[0];
    }
    for(int i=1; i<strs.length; i++){
        String analyzing = strs[i];
        int j=0;
        for(; j<Math.min(longestPrefix.length(), strs[i].length()); j++){
            if(longestPrefix.charAt(j) != analyzing.charAt(j)){
                break;
            }
        }
        longestPrefix = strs[i].substring(0, j);
    }
    return longestPrefix;
}

Answer 1

Pure functions should generally be declared static.

You shouldn't need to take substrings in a loop — that's inefficient. Think of scanning a two-dimensional ragged array of characters. Check that all of the first characters match, then that all of the second characters match, and so on until you find a mismatch, or one of the strings is too short.

public static String longestCommonPrefix(String[] strings) {
    if (strings.length == 0) {
        return "";   // Or maybe return null?
    }

    for (int prefixLen = 0; prefixLen < strings[0].length(); prefixLen++) {
        char c = strings[0].charAt(prefixLen);
        for (int i = 1; i < strings.length; i++) {
            if ( prefixLen >= strings[i].length() ||
                 strings[i].charAt(prefixLen) != c ) {
                // Mismatch found
                return strings[i].substring(0, prefixLen);
            }
        }
    }
    return strings[0];
}

Space complexity: O(1).

Worst-case time complexity: O(n m) to scan every character in every string.

Answer 2

As mentioned in the comments of another answer, no one would decide to hire you after writing a few lines of code. I basically can't really tell if you are competent or not from those few lines.

Personally, if I were asked to do something like this in an interview, I would start by saying that I would first look in Apache Commons and Google Guava since they probably already have some functions to do such a task and it would be a waste of developer time ($) to rewrite something like this. Then I would do the exercise. Maybe others could comment here, because that might get you in trouble more than anything else.

There is a very tiny detail which I noticed: you are not consistent about having spaces or not around =, < or >. It's a very small detail, but, to me, it means that you don't code that much and you have never figured out which to pick.

Answer 3

A few notes about the original code which was not mentioned earlier:

1. From Clean Code, Chapter 2: Meaningful Names:

   Method Names

   Methods should have verb or verb phrase names like postPayment, deletePage, or save. Accessors, mutators, and predicates should be named for their value and prefixed with get, set, and is according to the javabean standard.

   So, I'd rename the method to getLongestCommonPrefix.

2. For the method declaration:

   public String longestCommonPrefix(String[] strs) {
   

   You could use varargs here:

   public static String getLongestCommonPrefix(String... strs) {
   

   So the method could be called without creating arrays:

   getLongestCommonPrefix("aaa", "aab");
   

3. The method currently throws a NullPointerException when one of the parameters is null. It would be more friendly to the users to simply return an empty string.

4. You have a variable for strs[i]:

   String analyzing = strs[i];
   

   You could use that here too:

   for(; j<Math.min(longestPrefix.length(), strs[i].length()); j++){
   

Don't do premature optimization but it's interesting to see what other experts used to optimize StringUtils.getCommonPrefix in Apache Commons Lang. (javadoc, source)

1. You can have a short-circuit path to avoid calling Math.min on every iteration. (Applies to 200_success's solution and the one in Apache Commons):

   // find the min and max string lengths; this avoids checking to make
   // sure we are not exceeding the length of the string each time through
   // the bottom loop.
   

2. They have a guard clause for nulls and empty strings:

   // handle lists containing some nulls or some empty strings
   

   For cases when it gets an array where the first elements are long strings but last one is an empty one.