Subj : Re: Reverse words in a string (Another Interview question)
To   : comp.programming
From : Randy
Date : Mon Oct 03 2005 06:07 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.

Then you appreciate people who talk a lot and say very little?  I don't.
 I respect elegance in conversation, especially when the speaker makes
the intended point clearly and with minimal fanfare.  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 an indirect route
to get to the point.

BTW, Gerry, the phrase "for me" doesn't convey much weight in a
discussion.  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 future conclusions.

....
>>
>>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 solution, and whether you can compose an efficient route
between them.  "How to do X?"  The best answer is short, sweet, and to
the point.  A stack is exactly that.  A solution based in software
engineering, e.g. 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, it's inefficient and possibly unavailable (unless you're
coding in C++).

A recursive (stack-based) solution to this problem is elegant and a
sound basis for further discussion of alternative solutions.  Here's an
example in C.

(Interestingly, in writing this, I've changed my mind about the
suitability of using C to do a task like this.  C's string handling
sucks.  The elegance of this solution would be much more apparent in a
language with with better string handling support and automatic garbage
collection.  Like Java.  Oh well.)

"
#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

.