Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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;
}
share|improve this question

3 Answers 3

up vote 10 down vote accepted

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.

share|improve this answer
    
is my worst correct? –  bazang Apr 11 at 21:37
    
O(n m) is optimal, due to the nature of the problem. Your original solution may or may not be O(n m), depending on how String.substring() works. Since Java 7, it's worse. –  200_success Apr 11 at 21:41
    
would you hire me with the code I wrote? (Fresh out of college)? –  bazang Apr 11 at 22:33
2  
Well, it wouldn't immediately disqualify you. An interview is not an exam where you get one chance to write something and hand it in. A good interviewer would challenge you to improve on it and gauge your reaction. –  200_success Apr 11 at 23:06
    
To avoid checking lengths throughout, do a one-time scan to find the shortest string. –  David Harkness Apr 12 at 1:18

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.

share|improve this answer
1  
I would never penalize a candidate--especially one fresh out of college--for "failing" to point out that there's probably a well-rested library to solve any problem. I would make a positive note if they mentioned likely candidates, but this is something I can easily teach to a new hire so it's minor. I'm happy to assume that most candidates would assume that when I ask them to write code in an interview...I'm asking them to write code. Much of my work involves writing reusable code, and this is a common interview technique. –  David Harkness Apr 12 at 1:26

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.

share|improve this answer
1  
wow, you taught me something new; had no clue that var args even existed(although I'd seen them before, I just thought it was some hack!) –  bazang Apr 13 at 18:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.