Subj : Re: Reverse words in a string (Another Interview question)
To   : comp.programming
From : Willem
Date : Thu Sep 29 2005 06:11 pm

Jaspreet wrote:
) 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:
)
) ...
)
) 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 linked list solution is cleaner and more understandable, and it is
the same big-oh complexity, so the question if it's more efficient by some
constant factor or not is, to me, a moot point.  Especially if the language
supports linked lists and strig operations, natively or by functions.


Anyway, the simplest way, and probably the most efficient, would be to
allocate room for a new string, and then just copy the string word by
word, in reverse order.  This should take the same amount of time as
the linked-list solution, except that you don't have to do any operations
on the linked list structure itself.  Two reads and one write per
character.

The only way the inline method could be more efficient would be if the
extra malloc, combined with the small extra overhead of more cache misses,
outweighs having to walk the string twice.


SaSW, Willem
-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

.