Stupid Interview Questions Everyone Still Asks: Reverse the Words in a String

Stupid Interview Questions is a recurring series about frequently asked interview questions that are, regardless of the self satisfied smirk that accompanies them, just not a good idea. This series looks to help engineers know more than just the answer, but also why the question was asked in the first place.
 
Click here to see them all
 
Click here to request that your question be covered

EDIT – Called out on my sample implementation not handling whitespace well so I updated the example. Well played Internet, well played.

The Question:

Can you write a function that reverses the words in a string? In this case “the quick brown fox” becomes “fox brown quick the”. Demonstrate on the whiteboard. Bonus points for not using any external memory.

The Answer:

This one is actually a fun little teaser, and I won’t judge you if you take off for a moment to try and puzzle it out. Go ahead, do it now: I’ve got an answer posted below so now’s your chance. Back yet? Now that we’ve all gotten that out of our systems I’m going to tell you the many, many, many things that make this a flat out bad interview question. First though I need to pause to talk about the infamous, frequently dreaded whiteboard.

In most cases this little fella is your friend and ally. Its shiny surface is a tactile and intuitive place to map your ideas in brainstorming sessions, and if you inhale the fumes from its markers you can travel to worlds beyond your wildest dreams. But in an interview it can become your worst enemy, mocking you as you try to piece together how to write an ampersand (&) by hand.


Kind of a dick

But I wouldn’t blame our smudgy, oft maligned friend. The fault here actually lies with interviewers that ask programmers to write code by hand under continual review, a process that is totally foreign to the methods they’ll employ in their day to day job. It forces engineers to write code linearly, makes improvisation difficult, removes all the tools they’re normally supplied with, and adds a specific kind of stress and scrutiny to their problem solving process that they will never encounter again.

Now don’t get me wrong: there are appropriate times to ask for whiteboard code. Typically I’ll use it for no-brainer, due diligence type testing. In other words, I ask for snippets of low complexity that any programmer should be able to write in their sleep. Acceptable questions to me are “reverse a string” (not the words in the string), “swap two items in a linked list”, and other dirt simple examples that most programmers have actually used. Another way to phrase those questions could be “show me you know how to use pointers in 10 lines or less”.

But complex problem solving that requires writing actual code, especially when you plan that the candidate has never heard the question before, is a bad, bad idea. Rely on code on the whiteboard and you run the risk of passing on qualified candidates and accepting those that simply have been asked the question in a previous interview.



A swimsuit competition is a similar dead end.

Now you may have noticed that I just pointed out “reverse a string” as acceptable whiteboard code. What makes that problem different than “reverse the words in a string”? A whole hell of a lot it turns out.

First is that just about all forms of this question add a whole order of complexity to the simple “reverse a string” problem. Where once you had to worry about making your function safe against a few cases, adding the “words” requirement adds a bunch of tokenization issues you have to at least consider. Not tough for a good engineer, but enormously painful when wrangling the nightmare of suck that is the whiteboard. So there’s that.

But it gets worse. As you may have intuited from the “bonus points” addendum that absolutely always accompanies this question, there are two approaches to the problem, and in an interview only one is really considered correct. The fact is there is a “trick” to this problem, and if you answer it in a straight forward manner prepare to be prodded in a follow up. “OK fine, now how about the bonus?”

In that manner it’s a layered, muddled question. Can you figure out the trick, and then can you you solve the moderately involved code structure up on the whiteboard? Neither point really tests engineering skill well, and the “brain teaser” aspect of it is only amusing outside of a high pressure situation that may cost you a job you really want.



There’s no trick to it. It’s just a simple trick!

Now having said all that, and since you will absolutely be asked this question in a high pressure interview situation, you can trust in the benevolent State of Houston to give you the answer they’re looking for.

Reverse the string in-place and then reverse each of the words in place. TA DA! You might even do something like this:

#include <stdio.h>
#include <string.h>

//================================================================

bool IsWhitespace(  char    _cChar  )
{
    return ((_cChar == ' ') || (_cChar == '\n') || (_cChar == ' '));
}

//================================================================

// Reverses up a string, optional breaking on whitespace.
// Returns just past the found token or the location of the null
// terminator if no token is found.
char* ReverseTheWords_Helper(   char*       _pString,
                                const bool  _bBreakOnWhitespace )
{
    // First find the end (the token location)
    char*   pToken = _pString;

    while ( (!_bBreakOnWhitespace || !IsWhitespace( *pToken )) && (*pToken != '\0') )
    {
        ++pToken;
    }

    // Reverse!
    char*   pCur    = _pString;
    char*   pEnd    = (pToken - 1);

    while ( pCur < pEnd )
    {
        char        cTemp = *pCur;

        *pCur   = *pEnd;
        *pEnd   = cTemp;

        --pEnd;
        ++pCur;
    }

    // Return the token location.
    if ( *pToken != '\0' )
    {
        ++pToken;
    }

    return pToken;
}

// Reverse the words in a string in place
// e.g. "the quick brown fox" becomes "fox brown quick the"
void ReverseTheWords(   char*   _pString    )
{
    if ( _pString )
    {
        // First reverse the whole string
        ReverseTheWords_Helper( _pString, false );

        // Now reverse each of the words separately
        do
        {
            _pString = ReverseTheWords_Helper( _pString, true );
        } while( *_pString != '\0' );
    }
}

//================================================================

int main(   int     _argv,
            char**  _argc       )
{
    // Run the function through the wringer
    const int   NumExamples = 6;
    char*       Examples[6] = {     "the quick brown    fox",
                                    "hamburger",
                                    "hamster   pockets!",
                                    "",
                                    " ",
                                    "New lines\nAs well."
                                };

    printf( "Reversing the words..." );

    char        Buffer[256];

    for ( int i = 0; i < NumExamples; i++ )
    {
        strcpy( Buffer, Examples[i] );
        ReverseTheWords( Buffer );
        printf( "   Example%d: %s\n", i, Buffer );
    }

    printf( "...Done" );

    return 0;
}

//================================================================

 

The Take Away

So is this really that bad of a question?

Yes. Yes it is.

Does everybody ask it anyway?

Yes. Yes they do.

So as always memorize it, try it out on your friends, and answer correctly when asked. But when it’s your turn to make an interviewee squirm, leave this particular pain with the last generation of engineers. It’s for your own good.