Java Interview questions: Write a String Reverser (and use Recursion!)
Published November 9th, 2007 in Interview, Java, RecursionInterviewing 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.
25 Responses to “Java Interview questions: Write a String Reverser (and use Recursion!)”
- 1 Pingback on Nov 11th, 2007 at 10:00 am
- 2 Pingback on Dec 5th, 2007 at 9:29 pm
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”
Hello fw,
this depends. I don’t think the java compiler can use StringBuffer for the given recursion, it’s only possible to detect easy cases of String usage currently. So
will be converted to a StringBuffer by the javac compiler,
probably not, unless the compiler or the JIT VM have some very, very smart escape analysis.
Great post! It gave me some fun minutes to code some methods myself. I have to check which solutions I did. The recursive one was really fun, but I had to think about it for a minute before starting to code it. Actually what first comes to my mind was the good old self-swapping in a char[]. :-) I put that as a remaining of my electrotechnical background.
Actually, I prefer the JDK provided methods and I definitly would have taken a look into the API before starting to code that in a real project. Relying on the JDK is one of my most-liked parts of Java.
Hi Carsten, thanks :-) The first one that came to my mind was appending to a StringBuffer. I have an aversion agains arrays somehow. But perhaps in the end I would choose the swap solution with an array, it should be the fastest. When looking at the StringBuffer.reverse() function in the JDK, it’s not easy to implement though to work correctly with surrogate pairs.
I thought there was such a function in String and was searching for it, there I found StringBuffer.reverse.
Actually i came up with this version.Hope i am not in the list of dummy’s.
Thanks
Prashant
http://prashantjalasutram.blogspot.com/
public class StringReverser {
static String orgStr = "prasanth";
static char[] orgCharArr = orgStr.toCharArray();
static char[] distCharArr = new char[orgStr.length()];
static int endCounter = orgCharArr.length - 1;
static int startCounter = 0;
static StringBuffer output = new StringBuffer();
public static void main(String[] args) {
String orginalString = "pras";
char[] reverseStr=reverse(orgCharArr);
System.out.println(reverseStr);
}
static char[] reverse(char[] org) {
distCharArr[endCounter]=orgCharArr[startCounter];
if(endCounter<=0 || startCounter>=orgStr.length()) {
return distCharArr;
}else {
startCounter ;
endCounter–;
return reverse(orgCharArr);
}
}}
prashant: Hehe. Was that a joke?
Wintermut.
It might be a bit out of topic but, what about asking for any participation in open source projects? Or isn’t that very relevant?
You should use tail recurions.
Example in Erlang:
reverse(X) ->
reverse(X, []).
reverse([A|Rest], Acc) ->
reverse(Rest, A Acc);
reverse([], Acc) ->
Acc.
This should take constant stack space.
@Witek: My example uses tail recursion.
@Paulo: Yes, off topic for this post, not off topic for interviewing. Asking about Open Source projects is a good idea. I would prefer a candidate who is participating in Open Source projects, good idea.
No, your example isn’t tail recursive. Your recursive call is
return reverse(str.substring(1)) + str.charAt(0);
So the stack frame has to stay around to do the append on the recursive result. To make this tail recursive you need to pass in an accumulator like Witek’s solution.
@PXM: Ah thanks. Every new day something new to learn.
@Witek: Sorry for my ill informed reply.
“text”.reverse in Ruby LOL
@Leo: “text”.reverse in Groovy
This does not help, as the main reason for the question is the discussion on why the developer has chosen the particular solution.
So obviously I would ask a different question when interviewing Ruby developers.
Or Javascript developers.
Or Lisp developers.
Or did I missunderstand your comment and it was another “Ruby rulez Java” comment?
it was a joke… and yes i do like ruby and no there is no one solves all Rulez anywhere really so not about to start another flame war.
On the programmers interviews though, I like to ask about their experiences in a practical sense and have them explain to me parts of projects they have worked on. Not puzzles like this one you are outlining here.
Greetz
Leo
I don’t consider writing a reverse String function a puzzler. Man hole covers are. Writing code is not. “This does not help, as the main reason for the question is the discussion on why the developer has chosen the particular solution.” No puzzler there.
Obviously one would ask the candidate about past projects, his roles in these projects, his view on technologies, testing, quality assurance, requirement engineering, his social skills and much more. Asking one programming question is only a small part of an interview process.
Gr33tZ
-stephan
Hmm.. Your stupid recursion solution only handles strings less than 65536 chars in length due to the call stack depth limit.
@Unimpressed: I’m not impressed by your comment either. As written before the recursive solution isn’t very good for Java and Unicode reversal because Java has immutable Strings which will make you run out of memory faster than the call stack and Unicode has surrogate pairs which will make your reversed string unreadable.
But go ahead, write a tail recursive version. Which will not help, because Java does not optimize tail recursion.
“Java does not optimize tail recursion”. Too broad statement. Sun’s VM does not.
IBM’s VM optimizes tail recursion into iteration.
I’ve been googling around, found some mentions of tail recursion and tail call elimination in IBM VMs but no official description. The most I found from IBM were some academic papers on the topic. So I didn’t mention IBMs VM. Have you found a description of tail recursion/call elimination in IBMs VM? I would be highly interested.
Ask the candidate to implement String reversal using recursion . Now that would boil down to some sort of tail recursion . If the aim is to test the candidate’s Recursion capabilities , then i think tail recursion and such a question is a bad choice .
Tail recursion should be best avoided , in such cases an iterative solution is much much better . Fibonacci series ( iterative vs recursion ) has been discussed a zillion times .
I feel its best to ask recursive problems that truly are recursive without being tail recursive .
Before reversing a “string”, we need to get clear on what we want. At one level, a Java String object is just an array of chars. At another level, it represents a sequence of unicode code points. The tension arises from the fact that String(char[]) lets you construct a string with a sequence of chars that don’t correspond to valid unicode code points. This tension was ratcheted up in the 1.5 JDK when they moved to Unicode 4.0.
In the 1.5 JDK, Sun changed the behavior of the StringBuffer.reverse() method in a way that was not backward compatible with 1.4. That is, there are StringBuffer instances for which reverse() in 1.4 returns a different value than in 1.5.
The 1.5 version of reverse() is sensitive to surrogate pairs (unicode code points requiring more than 16 bits, and hence more than one char, in UTF-16). In 1.5, both java.lang.StringBuilder and java.lang.StringBuffer use the implementation of reverse() from their common superclass, java.lang.AbstractStringBuilder.
Here’s the first paragraph of doc for java.lang.StringBuffer.reverse() from JDK 1.5:
“Causes this character sequence to be replaced by the reverse of the sequence. If there are any surrogate pairs included in the sequence, these are treated as single characters for the reverse operation. Thus, the order of the high-low surrogates is never reversed.”
And here’s the first paragraph of doc from java.lang.StringBuffer.reverse() from JDK 1.4:
“The character sequence contained in this string buffer is replaced by the reverse of the sequence.”
Following Stephan’s suggestion to use the built-in has either a good or bad side effect. Moving from 1.4 to 1.5 either breaks backward compatibility for the string as char sequence representation, or appropriately handles unicode 5.0 in the string as sequence of code points representation.
Extra credit 1: Recursion won’t work because it’ll blow out the stack if we’re using Sun’s JDKs, which (at least so far) don’t perform tail recursion optimization (a kind of last call optimization).
Extra credit 2: The exception thrown when trying to reverse a null string should be a null pointer exception. That’s how Sun codes the JDK itself (see, e.g., the java.lang.String.String(String) constructor). It’s a runtime exception because it’s a coding error to send reverse(String) a null string (assuming you want behavior like your call to StringBuffer.reverse()). It should be a null pointer exception, as that’ll lead you right to the problem while debugging.
Do I get a callback for a second interview?
“Do I get a callback for a second interview?” Sure ;-) Thanks for the long comment. We usually do a face to face as a second one.
“The exception thrown when trying to reverse a null string should be a null pointer exception.”
I’m not certain on this one. Developers search for the cause of NPEs by looking for dots which dereference references. So throwing a NPE when there is no null pointer access doesn’t help. I also think that throwing an NPE for
int i = (Integer) null;
was a wrong decision on Suns side. A AutoUnboxingException would have been more helpful and make this error much easier to detect.
I’ve added a tail recursive version here
http://stephan.reposita.org/archives/2007/11/12/string-reversing-part-ii-tail-recursion/