Java Interview questions: Write a String Reverser (and use Recursion!)
Interviewing developers for a programming job is hard and tedious. There are some excellent Guides, like the Joel Guerilla Guide to interviewing, but in the end you need to decide yourself to hire or not to hire. To get a quick idea about their programming abilities I have considered asking the String reverse question. Others have used this question with some success. There are lots of answers to this question which gives you room to explore the candidates skills. Thinking about this myself, I found some answers on how to reverse a String in Java. The answer the candidate gives is a good way to see how he thinks. You could combine this question with one about interfaces and ask for a reverser interface:
public interface Reverser {
public String reverse(String str);
}
The best implementation in Java is to use the reverse method of the StringBuffer class in the JDK. It’s fast, efficient and knows how to handle unicode surrogate pairs, something most other solutions ignore.
public class JdkReverser implements Reverser {
public String reverse(String str) {
if ((null == str) || (str.length() <= 1)) {
return str;
}
return new StringBuffer(str).reverse().toString();
}
}
Not only is the chosen implementation interesting as an answer, but also does the candidate reuse the JDK or not or does he tell you at least "there has to be something in the JDK". Which is quite as good, because googling in reality will help him find the JDK solution. You don't want developers to implement everything themselves.
Handling problems
Ask him where the bug is in this code, even if there is none. Or how his code can go wrong. His answers can lead into a discussion about how to handle a null value
- return null
- return ""
- throw NullPointerException
- throw IllegalArgumentException
and the merits of every solution. The second discussion point is how to optimize the solution, like returning the string itself for "" and every one length string (which is a reversal of itself already).
Recursion
Then ask the candidate to write a recursive solution of the reversal problem (which is the most beautiful but least usable one).
public String reverse(String str) {
if ((null == str) || (str.length() <= 1)) {
return str;
}
return reverse(str.substring(1)) + str.charAt(0);
}
Some developers can't handle recursion in their head. Most candidates will need some time and some help, but actually get to a solution. Those that can't handle several stages of recursion in their head probably can't handle complex problems or several layers in their head either.
You can ask them about the efficiency of the recursive solution, ask about Tail Recursion, ask about the ineffeciency of the "+" operation for Strings, how to handle that, about why Strings are immutable (most of the time at least) and ask the candidate how many String objects are created for reversing "Stephan" with his recursive solution. When discussing this one of my developers said "Easy", he was doing Lisp at the university the whole time, which I didn't know until then, excellent news!
Ask where the stop condition is in the above code to end the recursion.
More solutions
Some more solutions, one with swapping a StringBuffer in place:
public String reverse(String str) {
if ((null == str) || (str.length() <= 1 )) {
return str;
}
StringBuffer result = new StringBuffer(str);
for (int i = 0; i < (str.length() / 2); i++) {
int swapIndex = str.length() - 1 - i;
char swap = result.charAt(swapIndex);
result.setCharAt(swapIndex, result.charAt(i));
result.setCharAt(i, swap);
}
return result.toString();
}
One with swapping an array:
public String reverse(String str) {
if ((null == str) || (str.length() <= 1)) {
return str;
}
char[] chars = str.toCharArray();
int right = chars.length - 1;
for (int left = 0; left < right; left++) {
char swap = chars[left];
chars[left] = chars[right];
chars[right--] = swap;
}
return new String(chars);
}
and one with appending to a StringBuffer:
public String reverse(String str) {
if ((null == str) || (str.length() <= 1)) {
return str;
}
StringBuffer reverse = new StringBuffer(str.length());
for (int i = str.length() - 1; i >= 0; i--) {
reverse.append(str.charAt(i));
}
return reverse.toString();
}
}
Perhaps the candidate even knows about the tricky XOR swapping solution.
From there it's an open field. You could ask the candidate to write a JUnit test for his reverse method. Not only can he show how to write a unit test, but what he considers as test cases ("", null, "A", "Even", "Odd", ....).
I hope this helps you in your decision with hire or no hire. And I hope it helps me in the future to decide this question for myself. As Joel said: when in doubt, always no hire.
Thanks for listening.
See also:
You can leave a Reply here. Of course, you should follow me on twitter here.
since java 5 the -operator ist no longer inefficient:
“The Java language provides special support for the string concatenation operator ( ), and for conversion of other objects to strings. String concatenation is implemented through the StringBuilder(or StringBuffer) class and its append method”