Re: Reverse words in a string (Another Interview question)


"Randy" <joe@xxxxxxxxxxxxxxx> wrote in message
news:dhsgsb$dot$1@xxxxxxxxxxxxxxx
> Gerry Quinn wrote:
>> In article <dhk1fe$akt$1@xxxxxxxxxxxx>, joe@xxxxxxxxxxxxxxx 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


.

Relevant Pages

  • Re: alloca / _alloca / dynamic stack memory
    ... that will be copied and set to the internal char*. ... So, String looks like this: ... If a heap has been allocated on a per-thread basis, ... approach actually uses more of the stack than using a plain old local ...
    (microsoft.public.vc.language)
  • Re: Stack Corruption and app disappearing issue-- seh --
    ... I suspect the stack has plenty enough room to hold your string without ... but it's corrupting it something awful. ... > {char e; ...
    (microsoft.public.vc.language)
  • Re: Reverse words in a string (Another Interview question)
    ... > I'm using a linked list to contain words that will be output in reverse ... A stack is exactly that. ... C's string handling sucks. ... // Return 1st word in string, and offset to next. ...
    (comp.programming)
  • Re: To reverse a string
    ... can create the string in the first place it should reverse it. ... char *str_rev ... char *t, swap; ...
    (comp.lang.c)
  • Re: To reverse a string
    ... can create the string in the first place it should reverse it. ... char *last, temp; ... size_t lgh; ...
    (comp.lang.c)