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

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
.

Relevant Pages

  • Re: Mergesort algorithm for linked lists
    ... That's completely wrong for stable mergesorting of linked lists ... Mergesorting a reverse ordered list requires the minimum ... For a stable mergesorting of an array, ...
    (comp.programming)
  • Re: Reverse words in a string (Another Interview question)
    ... > I was asked to reverse the words in a string. ... > linked list and then try to reverse the linked list. ... > I guess the interviewer had learnt/used something else. ... which they would appear relative to other sprites). ...
    (comp.programming)
  • Multiple Double Linked Lists
    ... Create 4 double linked lists as follows: ... string is a string of characters representing the identifier itself. ... typdef struct Names DLList; ...
    (comp.lang.c)
  • Re: problem with fwrite/fread and writing a struct
    ... > written out to the file the program first reads on startup. ... Obviously you more or less know how to deal with linked lists (just ... For each string you could write the length of the string first, ...
    (comp.unix.programmer)
  • Re: Reverse words in a string (Another Interview question)
    ... >> I was asked to reverse the words in a string. ... >> linked list and then try to reverse the linked list. ... >> I guess the interviewer had learnt/used something else. ... >> groups google to Welcome. ...
    (comp.programming)