Subj : Re: Reverse words in a string (Another Interview question)
To   : comp.programming
From : David Tiktin
Date : Thu Sep 29 2005 01:42 pm

On 29 Sep 2005, "Jaspreet" <jsingh.oberoi@gmail.com> wrote:

> I was asked to reverse the words in a string. Say if we have
> "Welcome to google groups", I need to have it reversed to "groups
> google to Welcome".
> 
> I told the interviewer that we could keep each word in a node in a
> linked list and then try to reverse the linked list. That is:
> 
> --Original linked list
> Welcome -> to -> google -> groups
> --After reversing
> groups -> google -> to -> Welcome
> 
> I guess the interviewer had learnt/used something else. He wanted
> me to try reversing it inline that is without the option of using
> another linked list. He probably wanted me to do something similar
> to - First reverse the whole string and then individually reverse
> the words 
> 
> a) Reverse the string to get:
> spuorg elgoog ot emocleW
> 
> b) then reverse the individual words to get:
> groups google to Welcome.
> 
> Now agreed my solution would take up extra memory but am not sure
> which one is a faster and more efficient solution. I did the
> mistake of telling the interviewer that the solution he thinks of
> is slightly slower and in-efficient to code or go through by
> future programmers which I am sure he did not like.
> 
> I would like an opinion on this from you. Which one is a better
> and a more efficient solution ?

The 2nd version is the cannonical "cute" solution for interviews, but 
I guess it depends on what primitives you have available.  In Perl, 
you're solution would be:

    	$string = join(' ', reverse(split(/ /, $string)));

I can't think of a way to do the cannonical solution in Perl that's 
as clear and simple.  (Maybe someone else can.)  In C, maybe the 2nd 
would be easier, unless, of course, you have libraries to do 
essentially what split(), join() and reverse() do (which, as it 
happens, I do ;-).

Dave

-- 
D.a.v.i.d  T.i.k.t.i.n
t.i.k.t.i.n [at] a.d.v.a.n.c.e.d.r.e.l.a.y [dot] c.o.m

.