Quickie: String Reversing

An oldie but a goodie (actually, not a goodie, but I'll talk about that at the end). This question is often phrased in two parts:


First: Write an algorithm to reverse a string.


This should be pretty boring to you. Just start at the ends of the array and swap each element until the ends touch. I find keeping a start and an end counter to be easier to code on a whiteboard. Some people like to just increment a single counter for the start and calculate the end pointer from the length of the array. Probably a slight performance hit that way, but I wouldn't no hire someone for it.

        int mStart = 0;
        int mEnd = mChars.length - 1;
        while(mStart < mEnd) {
            char mTemp = mChars[mStart];
            mChars[mStart] = mChars[mEnd];
            mChars[mEnd] = mTemp;
            mStart++;
            mEnd--;
        }

So the second part of the question is: now reverse the order of the words in the string without reversing the words themselves so that a string "this is a test" would convert to "test a is this".


I'm not a fan of this for two reasons: First, half the candidates have seen this an know the trick. Second, for those who haven't seen it, it requires a flash of insight. Anything that requires a flash of insight just tests whether the candidate is lucky enough to have insightful flashes durring interviews. I'd rather see something test coding skill, algorithmic reasoning, grasp of recursing, anything like that. Just not luck.


But whatever, someone is probably going to ask you this question someday so here is the answer: reverse the string once, then reverse each word again. So first you make "tset a si siht" then you reverse that to "test a is this".

         int mStart = 0;
        int mEnd = mChars.length - 1;
        while(mStart < mEnd) {
            char mTemp = mChars[mStart];
            mChars[mStart] = mChars[mEnd];
            mChars[mEnd] = mTemp;
            mStart++;
            mEnd--;
        }
        
        int mLastWordStart = 0;
        int mLastWordEnd = 0;
        int mCurrentLocation = 0;
        while(mCurrentLocation < mChars.length) {
            
            mLastWordStart = -1;
            mLastWordEnd = -1;
            while((mCurrentLocation < mChars.length) && 
                    (mChars[mCurrentLocation] == ' ')) {
                mCurrentLocation++;
            }
            
            mLastWordStart = mCurrentLocation;
            
            while((mCurrentLocation < mChars.length) &&
                    (mChars[mCurrentLocation] != ' ')) {
                mCurrentLocation++;
            }
            
            mLastWordEnd = mCurrentLocation - 1;
            
            while(mLastWordEnd > mLastWordStart) {
                char mTemp = mChars[mLastWordEnd];
                mChars[mLastWordEnd] = mChars[mLastWordStart];
                mChars[mLastWordStart] = mTemp;
                mLastWordEnd--;
                mLastWordStart++;
            }
            
        }

There it is! Variations of this that I've seen include a question about how to flip a bitmapped image which is represented as a two dimensional array of pixels. The solution (which I'll leave largely to the reader) is treat each line of the file as a string to reverse and reverse them once. You could also probably do some cool pattern based conditional flipping by combining the word-by-word string reversal with the bitmap question.