Google Interview Question
Web:
www.google.com
|
HQ:
Mountain View, CA
Overview |
| |
Salaries |
| |
Reviews |
| |
Interviews |
| |
Photos |
| |
Jobs |
| |
|
1,069 Interview Reviews |
Back to all Google Interview Questions & Reviews
Interview questions and reviews posted anonymously by interview candidates
Interview Question for Software Engineer at Google:
Aug 12, 2009
Most phones now have full keyboards. Before there there three letters mapped to a number button. Describe how you would go about implementing spelling and word suggestions as people type.
Add Tags
[?]
Helpful Question?
Yes |
No
Inappropriate?
Answers & Comments (3)
Aug 29, 2009
Each key will represent 3 possibilities (letters). If N keys are pressed, it will create 3^N possibilities. The Dictionary of known words is organized as a Radix Tree on the Alphabet. Then just lookup the tree for the 3^N possibilities. Display the possible completions (spelling check) as well as longest matches.
Helpful Answer?
Yes |
No
Inappropriate?
1 of 1 people found this helpful
Dec 26, 2010
Take every word in the dictionary, and convert it to a sequence of digits.
Form a trie where the keys are the digit sequences, and values are the words.
With every key press, the possible completions will be a smaller sub-tree of the previous trie.
Possible improvements, if data and computation power are available:
-Display words in decreasing order of frequency in English language.
-Display words in decreasing order of probability based on some Markov model.
-Find possible typos by looking at keys with a short Hamming distance away from the typed sequence.
Form a trie where the keys are the digit sequences, and values are the words.
With every key press, the possible completions will be a smaller sub-tree of the previous trie.
Possible improvements, if data and computation power are available:
-Display words in decreasing order of frequency in English language.
-Display words in decreasing order of probability based on some Markov model.
-Find possible typos by looking at keys with a short Hamming distance away from the typed sequence.
Helpful Answer?
Yes |
No
Inappropriate?
Members can
answer or comment on this question
–
Join Now (It's Free) or
Sign In
You might also be interested in: Interview Questions, Software Engineer Interview Questions, Google Interview
0 of 2 people found this helpful
by Interview Candidate: