Longest Common Prefix in an array of Strings

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;
}

• Apr 11, 2014 at 21:19
• @palacsint... helpful. Even more helpful (for slow people like me): getCommonPrefix Apr 17, 2018 at 19:01

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.

• is my worst correct? Apr 11, 2014 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. Apr 11, 2014 at 21:41
• would you hire me with the code I wrote? (Fresh out of college)? Apr 11, 2014 at 22:33
• 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. Apr 11, 2014 at 23:06
• To avoid checking lengths throughout, do a one-time scan to find the shortest string. Apr 12, 2014 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.

• 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. Apr 12, 2014 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.

• 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!) Apr 13, 2014 at 18:28
• get* is for accessors. This is not an accessor. Dec 16, 2014 at 11:50