Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
Autocomplete can be achieved many different ways. Most common is Ajax on the client side, and an NLP search engine application like Apache Lucene or Solr that does a reverse lookup and returns the matches based on the typed characters. These search engines can be very finely tuned. The rest of the question is not clear.
Lets take example of Google page - auto suggestion. This is what I believe should be happening.
- AlgoAlgae April 24, 20141. When user enters into search box, the view module (ex jsp) makes a call the google webapp servlet with user inputs as parameter string using ofcourse AJAX.
2. Based on the inputs / paramter string the server looks up the possible suggestion by looking up the data structure that stores all the previous searched strings. Data structure here would best be Trie. search is a DFS
3. after completing all strings search, the servlet sends back the collection to view module.
4. view on reciept of response, sets the respective DOM object to display the suggestion.
This happens as you type :).