Subj : Re: Reverse words in a string (Another Interview question)
To   : comp.programming
From : Gerry Quinn
Date : Tue Oct 04 2005 12:04 pm

In article <dhsgsb$dot$1@joe.rice.edu>, joe@burgershack.com says...
> 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.

It was not intended to bestow gravitas, but to point out that your 
personal observations on what is an obvious mapping are not of 
universal applicability.

What seems an obvious mapping may depend in part on the tools one's 
favoured language supplies.  I would expect a powerful set of safe 
tools for string manipulation to be available for use in such a 
problem. 

Actually, I probably wouldn't choose a stack or linked list, but build 
up a result iteratively, as in the following.  But if I were using the 
MFC CString which has handy functions such as MakeReverse() rather than 
the somewhat ugly STL string class, I would comsider it.

#include <string>
using namespace std;

string ReverseString( const string & str )
{
	const string WHITESPACE( " \r\n" );
	string result;
	int stPos = 0;
	while( true )
	{
		stPos = str.find_first_not_of( WHITESPACE, stPos );
		if ( stPos < 0 )
		{
			break;
		}
		if ( result.size() > 0 )
		{
			result += ' ';
		}
		int endPos = str.find_first_of( WHITESPACE, stPos );
		if ( endPos < 0 )
		{
			endPos = str.size();
		}
		for ( int iChar = endPos - 1; iChar >= stPos; iChar-- )
		{
			result += str[ iChar ];
		}
		stPos = endPos + 1;
	}
	return result;
}

(Why yes, I *do* use int instead of size_type.)

- Gerry Quinn

.