Microsoft Interview Question Software Engineer / Developers
0of 0 votesDesign the autocomplete feature (ex:Google Suggest)
Team: Bing
Country: United States
Interview Type: Phone Interview
this is more complicated then this... you need to get profiling to the user. you can guess to complete the search sentence using trie and profile + use the type of keyword you were guessing like if software then add download or something like that, which has maximum search with that keyword... many thing also need to be consider like location and more..
true as word completion algorithm, and profiling as a sentence completion rules,which is more complicated.
true as word completion algorithm, and profiling as a sentence completion rules,which is more complicated.
true as word completion algorithm, and profiling as a sentence completion rules,which is more complicated.
true as word completion algorithm, and profiling as a sentence completion rules,which is more complicated.
you can use the "Levenshtein distance" or "fuzzy string searching" or "Knuth–Morris–Pratt algorithm" to do that. Designing such system is complex task.
below is simple algo that I thought it will work.
1> capture a string while user is typing
2> for each such a string apply above algorithm
3> show the results to user and goto step 1
This is a useless and wrong answer. Let me breakdown the stupidity at display here:
1. "For each string, apply above algorithm" - Let's try applying the algorithms you have proposed:
1. KMP: For you to be able to apply this algorithm, you will need a large string that contains all possible words and the search will take O(n) time in the worst case.
Furthermore, you might be able to hit upon a word, but how do you get to other words that show up as part of auto-complete. Do you pick the next word, the previous word? How do you remember the user's last choice (do you use a different data structure for that?)
2. Use Levenshtein distance: And how exactly do you think we should use this? You are not trying to fix a spelling error, you are trying to find a partial match. Just putting down a fancy term, doesn't mean that it is actually usable. Try to think before you start posting random nonsense.
3. Fuzzy string searching: Oh boy! Here we go again. What exactly is "fuzzy string searching"? A Google link would be helpful or maybe you could codify the fuzziness in your head to enlighten us all?
To clarify, that all I am adding is not just criticism, the first post about Trie is absolutely correct and with a bit of modification, can be used to store frequency etc. Do not try to post answers without thinking about them first.
Use a TRIE to do that...!
- Arghyadip January 14, 2012