Subj : Re: Reverse words in a string (Another Interview question)
To   : comp.programming
From : Randy
Date : Mon Oct 03 2005 08:03 pm

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);
}
"

    Randy

.