StrStr happens to be the favorite question for some interviewers. I have a senior colleague who is especially fond of this question. He had a hard time getting people from X country answer that correctly. So he decided, to gauge the difficulty of the strstr question by using my answer as a benchmark (Don’t know how wise this decision was?).
He started out by explaining the question to me. And then i started thinking about this. I knew about this question but never had the patience to find an answer. So i decided to think :), n2 algorithms are BAD so I did not even discuss the search the needle in the haystack solution.
Eventually after he putting almost all the words into my mouth I/we got the variant of the KMP strstr algorithm. And then to test if I really understood the solution (this is imp now because I did not design it :)) he just asked me to build another failure table as used in the KMP algorithm which takes the number of matches before a character failure and gives the skip count. And then I got that while waiting for my bus.
Conclusions are.
1. "Efficient" StrStr is not a simple algo to design.
2. There is much to think about it.
3. Once you get it, it easy. BUT... it can always be further optimized.
4. Its not a good interview question for a telephonic interviews. The reason being on the extremely smarts can do w/o hints, i think the person being interviewed should be given hints. Hints are not conveyed effectively over the phone. :)
5. It will fairly gauge the thinking abilities of the person being interviewed.
Tips for the "being interviewed".
1. If you know the answer be honest say that u already know the answer.
2. Don’t get overwhelmed, the direction to start working is not that intuitive. The starting is important.
3. As for all thinking questions you have to convey to the interviewer the fact that u r actually thinking. So think aloud getting the answer doesn't matter as long as you are able to think.
