build a multimap and a map multimap to contain occurances of words of pattern substring in bigger substring
and map is to keep track of words covered in second parse the pattern substring is say "abc def geh ijk" and the given string is "abc ijk lmn geh ijk def def abc lmn" the multimap will have (a simple map would also do here) abc->0, 29 def->26 geh->12 ijk->4,16 map will have(bit map will suffice) abc ->false def->false geh->false ijk->false walk over the given big string word by word record start as 0 abc, present in multimap, so update the bitmap with true for abc(check if bitmap is all 1s) then return ijk, present in mmap, again update with true for ijk(check if bitmap is all 1s) lmn not present, reset record to 12, reset bitmap geh, found update bitmap ijk.. def.. def.. abc...now after setting the bitmap, it is all 1s so return start as the position. A lot many questions can be asked to interviewer before attempting the answer to get the requirements clear. Best Regards Ashish Goel "Think positive and find fuel in failure" +919985813081 +919966006652 On Wed, Nov 9, 2011 at 9:22 PM, Decipher <ankurseth...@gmail.com> wrote: > This question was asked by Facebook during their 2 hour online exam (Only > 1 question in 2 hour as per my junior) in DCE. > > Given a list of words wordlist on 1st line (no of words <= 100) and a > string qstr of len <= 1 million on 2nd line, print the index at qstr where > a continuous substring exists that contains all the given words in wordlist. > > Don't ask any further questions as I got this information from some junior > in my college. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To view this discussion on the web visit > https://groups.google.com/d/msg/algogeeks/-/JwSnPn-5WRUJ. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
