[algogeeks] Re: Amazon intern Question
bump!! On Sep 5, 8:42 pm, Arun yourarunb...@gmail.com wrote: Hi friends, Sorry that I am so late to reply. Thanks much responses have come regarding finding the similarity between words. Now what about the searching algorithm from the 'millions of words'. I think they expected an answer like hashing or more multi-level hashing. But I cant figureout an idea regarding the hash function and also about multi-level hashing, Regards -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Re: Amazon intern Question
Does similarity here refer to similarity in strings or similar to items in same category ? If its similarity to strings then edit distance can be used here. But if its the latter, then how will edit distance help ? It would probably be only looking for items in the same category. On Thu, Sep 2, 2010 at 7:10 AM, Gene gene.ress...@gmail.com wrote: Even if you're only matching words, there are different kinds of similarity. Check out the soundex algorithm, for example. Levenshtein distance. The Hungarian algorithm. What does 50% similarity mean anyway? I know of no accepted meaning. My point is that if you're in an interview situation and you ask intelligent questions about the question you're asked, you are more likely to get the job. At least I would be more likely to give it to you. I've been responsible for hiring quite a few people. On Sep 1, 11:52 am, Chakravarthi Muppalla chakri...@gmail.com wrote: @Gene, it isn't about related words, its abt matching words! On Wed, Sep 1, 2010 at 8:26 PM, saurabh singh saurabh.n...@gmail.com wrote: I think DS will be somewhere between suffix and trie DS On Wed, Sep 1, 2010 at 9:35 AM, jaladhi dave jaladhi.k.d...@gmail.com wrote: trie On Wed, Sep 1, 2010 at 5:45 PM, Arun yourarunb...@gmail.com wrote: You are given the amazon.com database which consists of names of millions of products. When a user enters a search query for particular object with the keyword say foo , output all the products which have names having 50% or more similarity with the given keyword ie foo Write the most efficient algorithm for the same. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards, Saurabh -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards, Chakravarthi. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Re: Amazon intern Question
I think Gene is right. they are asking more than search here. Thanks to Gene for suggesting this idea :) now the how part, we can have a level of abstraction: no of products matching to name --- use trie, suffix tree, some genetic algo, string matching, ms tree.. based on products get first abstraction like: category --- like video, audio, and display most preferred products also from that category in sub format . On Sep 2, 6:40 am, Gene gene.ress...@gmail.com wrote: Even if you're only matching words, there are different kinds of similarity. Check out the soundex algorithm, for example. Levenshtein distance. The Hungarian algorithm. What does 50% similarity mean anyway? I know of no accepted meaning. My point is that if you're in an interview situation and you ask intelligent questions about the question you're asked, you are more likely to get the job. At least I would be more likely to give it to you. I've been responsible for hiring quite a few people. On Sep 1, 11:52 am, Chakravarthi Muppalla chakri...@gmail.com wrote: @Gene, it isn't about related words, its abt matching words! On Wed, Sep 1, 2010 at 8:26 PM, saurabh singh saurabh.n...@gmail.comwrote: I think DS will be somewhere between suffix and trie DS On Wed, Sep 1, 2010 at 9:35 AM, jaladhi dave jaladhi.k.d...@gmail.comwrote: trie On Wed, Sep 1, 2010 at 5:45 PM, Arun yourarunb...@gmail.com wrote: You are given the amazon.com database which consists of names of millions of products. When a user enters a search query for particular object with the keyword say foo , output all the products which have names having 50% or more similarity with the given keyword ie foo Write the most efficient algorithm for the same. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards, Saurabh -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards, Chakravarthi.- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Re: Amazon intern Question
Trie-traverse search will be best.. On Thu, Sep 2, 2010 at 8:10 PM, Manjunath Manohar manjunath.n...@gmail.comwrote: trie will be the best choice for this.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Dhruvesh Kumar Mobile No.: +919911314113 M.C.A., Department of Computer Science, Delhi University, INDIA -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Re: Amazon intern Question
trie will be the best choice for this.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Re: Amazon intern Question
HI Arun, This is the edit distance problem which can be solved using DP. Calculate the cost for each product on the fly and return the top products with the least edit cost! On Sep 1, 5:15 pm, Arun yourarunb...@gmail.com wrote: You are given the amazon.com database which consists of names of millions of products. When a user enters a search query for particular object with the keyword say foo , output all the products which have names having 50% or more similarity with the given keyword ie foo Write the most efficient algorithm for the same. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Re: Amazon intern Question
Edit distance is one way to determine similarity. It assumes all differences are typographic. Amazon is probably interested in many other forms of similarity. When someone types audio system in the Amazon search, you want them to see receivers, speakers, tuners, etc. It's very possible this question is designed to see how well you think, not how well you can cite the standard computer science answer. On Sep 1, 9:36 am, jagadish jagadish1...@gmail.com wrote: HI Arun, This is the edit distance problem which can be solved using DP. Calculate the cost for each product on the fly and return the top products with the least edit cost! -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Re: Amazon intern Question
Even if you're only matching words, there are different kinds of similarity. Check out the soundex algorithm, for example. Levenshtein distance. The Hungarian algorithm. What does 50% similarity mean anyway? I know of no accepted meaning. My point is that if you're in an interview situation and you ask intelligent questions about the question you're asked, you are more likely to get the job. At least I would be more likely to give it to you. I've been responsible for hiring quite a few people. On Sep 1, 11:52 am, Chakravarthi Muppalla chakri...@gmail.com wrote: @Gene, it isn't about related words, its abt matching words! On Wed, Sep 1, 2010 at 8:26 PM, saurabh singh saurabh.n...@gmail.comwrote: I think DS will be somewhere between suffix and trie DS On Wed, Sep 1, 2010 at 9:35 AM, jaladhi dave jaladhi.k.d...@gmail.comwrote: trie On Wed, Sep 1, 2010 at 5:45 PM, Arun yourarunb...@gmail.com wrote: You are given the amazon.com database which consists of names of millions of products. When a user enters a search query for particular object with the keyword say foo , output all the products which have names having 50% or more similarity with the given keyword ie foo Write the most efficient algorithm for the same. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards, Saurabh -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards, Chakravarthi. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
