Subj : Re: Reverse words in a string (Another Interview question) To : comp.programming From : William Date : Thu Sep 29 2005 01:34 pm "Jaspreet" wrote in message news:1128011781.932340.25490@o13g2000cwo.googlegroups.com... > Hi All > > Just had another interview with those same questions which hardly make > a sense except this one probably. > > 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 Well, the requirement was to reverse the words IN the string. Not create a linked list allowing the words to be processed in reverse order, or even create a second string. [...] > Now agreed my solution would take up extra memory That could easily be a consideration depending on the application. > but am not sure which one is a faster and more efficient solution. For reasonable length strings, his is fast and efficient enough. > 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. Probably because it may not be true. Depending on the language, it could be a trivial piece of code which future programmers will never need to touch. > I would like an opinion on this from you. Which one is a better and > a more efficient solution ? Can't say without more details. I can give you an example of making a simple task harder than it needs to be from my own experience. Once, while working on a game project, there was a need to store sprites in a particular order (which represented the "level" at which they would appear relative to other sprites). Someone came up with a nice ordered storage system using linked nodes that was pretty nifty. We didn't use it, though. There were only 32 sprites and 8 possible drawing levels. We just created a 32-entry array and gave each sprite a level #. When it came time to draw, we would just scan the array once for each level, drawing sprites that matched that level. Easy to code, easy to maintain, no overhead if you wanted to draw one arbitrary level. And far faster than we needed. -Wm .