We’re hiring, so interviews have been on my mind.
I’m cross-posting what was mostly a response to reading Stephans Blog [sic], which was itself a riff on Joel on Software’s Guerilla Guide to Interviewing. Both ask us to look at the string reverse problem.
All of the answers I’ve seen are pure junior varsity when it comes to string processing.
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.StringBuffer use the implementation of
reverse() from their common superclass,
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
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
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?