Subj : Re: Reverse words in a string (Another Interview question)
To   : comp.programming
From : Roger Willcocks
Date : Tue Oct 04 2005 01:53 pm


"Randy" <joe@burgershack.com> wrote in message 
news:dhsgsb$dot$1@joe.rice.edu...
> Gerry Quinn wrote:
>> In article <dhk1fe$akt$1@joe.rice.edu>, joe@burgershack.com says...
> ...
>>>A linked list will certainly do the job, but unlike a stack, it will
>>>also do other jobs than simple sequence reversal.  As such, linked list
>>>code is not ideally minimalist or idiomatic -- an obvious natural
>>>mapping of problem space to solution space.
>>
>>
>> For me it's an obvious mapping, and perfectly idiomatic.  It's not
>> minimalist, but I do not accept minimalism as a valid criterion in
>> general.
>
> Perhaps you appreciate people who talk a lot yet say little.  I don't.
> I respect elegance in thought and conversation, especially when the
> speaker makes the intended point clearly and simply.  It shows that a
> clear incisive mind is in evidence, accompanied by ears that listen well
> and a mouth that doesn't waste my time.  I'd hire someone like that in
> an instant, rather than someone else who takes the scenic route to get
> to the point.
>
> BTW, Gerry, the phrase "for me" doesn't convey much gravitas.  Imagine a
> judge delivering a ruling and basing his/her judgment on "For me, ...".
> You might want to reconsider relying on that phrase as a basis for your
> conclusions in future.
>
> ...
>>>I'm proposing a solution that I think is better, not the only correct 
>>>one.
>>
>>
>> I'm using a linked list to contain words that will be output in reverse
>> order (or any other order I choose) after processing, which can be in
>> any order I choose.  (There is no reason why processing should be in
>> reverse order just because that is the desired output.)
>>
>> Using the minimal algorithm is like carefully choosing a shopping bag
>> no larger than will be needed for the goods you intend to buy.  It is a
>> waste of time that yields no significant benefits and reduces
>> flexibility.
>
> This was an interview question intended to show your understanding of a
> problem, its possible solutions, and whether you can devise an efficient
> route between them.  "How would you do X?"  The best answer is short,
> sweet, and to the point.  A stack is exactly that.  A solution motivated
> by software engineering principles, for example: a C++ container that
> provides a reverse iterator, might be the second half of a very good
> answer.  It's effective, thoroughly debugged, maximally reusable, and it
> minimizes the amount of code you write.  But it's inefficient and
> possibly unavailable (unless you'll be coding in C++).  By itself, that
> answer is not enough.
>
> A recursive (stack-based) design to solve this problem is an elegant and
> sound basis for further discussion of alternative solutions.  By way of
> illustration, here's an  implementation in C:
>
> (Interestingly, in programming this, I've changed my mind about the
> suitability of using C in doing this.  C's string handling sucks.  The
> elegance of this solution would be more apparent in a language with with
> proper string handling support and automatic garbage collection, like
> Java.  Oh well.  Damage done.)
>
> "
> #include <stdlib.h>
> #include <stdio.h>
> #include <string.h>
>
> char * string;  // the string to be reversed
>
>
> char * next_word( int * off, char * str)
> // Return 1st word in string, and offset to next.
> // When last word reached, return word with next = 0.
> {
> char * strp, * buf;
>
>  // Find next space or EOL
>  strp = str;
>  while (*strp && *strp != ' ')
>    strp++;
>  *off = strp - str;
>
>  // This should never happen
>  if (*off == 0) {
>    return NULL;
>  }
>
>  // Make dupe of word
>  buf = (char*) malloc( *off + 1);
>  strncpy( buf, str, *off);
>  buf[*off] = 0;
>  (*off)++;
>
>  // If end of string reached, return word and offset=0
>  if (*strp == '\0')
>    *off = 0;
>
>  return buf;
> }
>
>
> void reverse_string( char * ostr)
> // Reverse a string's tokens in place recursively.
> {
> char * word;  // a word
> int offset;   // offset to next word in string
>
>  // Get next word from old string
>  word = next_word( &offset, ostr);
>
>  // Push each word from old string onto stack recursively
>  if (offset) {
>    reverse_string( ostr + offset);
>
>    // Pop off stack's most recent word onto new string
>    strcat( string, " ");
>    strcat( string, word);
>    free( word);
>
>  } else {  // Copy last word to head of new string
>    strcpy( string, word);
>    free( word);
>  }
> }
>
>
> int main( void)
> {
>  string = strdup( "when in the course of human events");
>
>  reverse_string( string);
>
>  printf( "%s\n", string);
>  free( string);
> }


That seems like a lot of work... it's hard to beat the canonical solution:

#include <stdio.h>

void revtok(char* str, char sep)
{
    char *tmp, *end;
    do {
        while (*str && *str == sep) str++;
        end = str;
        while (*end && *end != sep) end++;
        tmp = str; str = end;
        while (--end > tmp) { char t = *tmp; *tmp++ = *end; *end = t; }
    } while (*str);
}

void main(int argc, char* argv[])
{
    char str[] = "when in the course of human events";
    revtok(str, '\0');
    revtok(str, ' ');
    printf("%s\n", str);
}

--
Roger

.