Amazon Interview Question: How would you implement auto-... | Glassdoor

Interview Question

Senior Technical Program Manager Interview Seattle, WA

How would you implement auto-complete on the Kindle

 ? Answered that you first get the use cases: quick searching, better user experience, research. Keywords from the given text could be loaded with the book itself or generated using a scanning process. Put into a datastore in memory cache (quick access), ignoring basic words such as “the”, “and”, “or”, etc. Each letter typed in would reduce the result set. Sort the results user a weighting system, such as number of occurrences, uniqueness, etc. You would know if your algorithm is working by the number of characters entered vs. the word chosen and it’s place in the sorted result set.
Answer

Interview Answer

2 Answers

0

not sure what correct approach is

Interview Candidate on Jan 9, 2013
0

You need to implement a form of Trie algorithm and if memory is a constraint then use Ternary search tree.

A nice example is here
http://igoro.com/archive/efficient-auto-complete-with-a-ternary-search-tree/

John Chooracken on Oct 2, 2015

Add Answers or Comments

To comment on this, Sign In or Sign Up.