Code Puzzle: String Reversal

Here is a question: Given an input String, how do you reverse it? I have seen this used as an interview question during technical interviews. There are myriad ways to implement this, so asking someone to solve this problem gives you some insight into the kinds of solutions they would look to first. Hopefully this can then be used as a proxy to see whether someone fits in with your technical culture or not, but the consensus lately seems to be that technical interviews are not really that useful.

But just for fun, let’s go ahead and play that game. An interface would look something like this:

public interface StringReverser {
   String reverse(String input);
}

What could you tell about someone based on their solution?

Those who like to rely on the standard libraries and have a head for concise solutions might first think of using StringBuffer.

public class SimpleStringReverser implements StringReverser {
    @Override
    public String reverse(String input) {
        return input == null ? input : new StringBuffer(input).reverse().toString();
    }
}

Those who like to bring in functionality from external libraries might first think of Apache Commons.

import org.apache.commons.lang.ArrayUtils;

public class StringReverserArrays implements StringReverser {
    @Override
    public String reverse(String input) {
        if (input == null) {
            return null;
        }
        char[] chars = input.toCharArray();
        ArrayUtils.reverse(chars);
        return new String(chars);
    }
}

Those who eschew primitives out of some idea of object purity might hide the use of primitives altogether.

import org.apache.commons.lang.ArrayUtils;

public class HeavyStringReverser implements StringReverser {
   @Override
    public String reverse(String input) {
        if (input == null) {
            return null;
        }
        Character[] characters = ArrayUtils.toObject(input.toCharArray());
        List<Character> characterList = Arrays.asList(characters);
        Collections.reverse(characterList);
        return new String(ArrayUtils.toPrimitive((Character[]) characterList.toArray()));
    }
}

Finally, those who like to have a little fun with it and are comfortable with recursion might bring up a recursive solution. There are performance issues here of course, the same performance issues that we saw with the recursive solution for detecting palindromes.

public class RecursiveStringReverser implements StringReverser {
    @Override
    public String reverse(String input) {
        if (input == null) {
            return null;
        }
        if (input.length() <= 1) {
            return input;
        }
        StringBuffer buffer = new StringBuffer();
        buffer.append(input.substring(input.length() - 1, input.length()));
        String substring = input.substring(0, input.length() - 1);
        buffer.append(reverse(substring));
        return buffer.toString();
    }
}

Finally, of course all this should be unit tested, and a parameterized test is a great tool for this.

The fun doesn’t stop there. We can take it a little further and look for more creative solutions with questions like “What if the string was in a 3GB file and we couldn’t load the whole thing into memory?” Again, this question is left as an exercise for the reader or for a future blog post 🙂

What other variations on the string reversal problem can we ask? Can you think of other solutions?

Advertisements

Leave a comment

Filed under Software Engineering

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s