Re: [algogeeks] Facebook Online Question India

[Ashish Goel]

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  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.

Re: [algogeeks] Facebook Online Question India

[Ashish Goel]

KMP is exact substring match, so this is tricky..

Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652


On Thu, Nov 10, 2011 at 6:05 PM, Amol Sharma  wrote:

> this can be done by simple string matching...KMP algo.
> correct me if i am wrong !!
> --
>
>
> Amol Sharma
> Third Year Student
> Computer Science and Engineering
> MNNIT Allahabad
>   
> 
>
>
>
>
>
> On Thu, Nov 10, 2011 at 8:03 AM, rahul sharma wrote:
>
>> facebook visit DCE???wats package???
>>
>>
>> On Wed, Nov 9, 2011 at 9:22 PM, Decipher  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.
>>
>
>  --
> 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.
>

-- 
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.

Re: [algogeeks] Facebook Online Question India

[Jagannath Prasad Das]

How many students they took and whats the offer?

On Thu, Nov 10, 2011 at 8:03 AM, rahul sharma wrote:

> facebook visit DCE???wats package???
>
>
> On Wed, Nov 9, 2011 at 9:22 PM, Decipher  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.
>

-- 
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.

Re: [algogeeks] Facebook Online Question India

[Amol Sharma]

this can be done by simple string matching...KMP algo.
correct me if i am wrong !!
--


Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
 






On Thu, Nov 10, 2011 at 8:03 AM, rahul sharma wrote:

> facebook visit DCE???wats package???
>
>
> On Wed, Nov 9, 2011 at 9:22 PM, Decipher  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.
>

-- 
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.

Re: [algogeeks] Facebook Online Question India

[rahul sharma]

facebook visit DCE???wats package???

On Wed, Nov 9, 2011 at 9:22 PM, Decipher  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.

[algogeeks] Facebook Online Question India

[Decipher]

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.