|
What data structure would you use to implement spell correction in a document .....
Microsoft Interview Questions and Answers
(Continued from previous question...)
97. What data structure would you use to implement spell correction in a document .....
Question:
What data structure would you use to implement spell correction in a document. The goal is to find if a given word typed by the user is in the dictionary or not (no need to correct it).
What is the complexity? What if you have to support multiple languages/dictionaries?
maybe an answer:
Considering a word dictionary - the database is huge, and not efficient enough to load everything in the memory. Hence, an approach would help where-in we store the key indices to find the words in the dictionary - similar to B trees which are hash based dictionary tree that would give search performance of O(1) for best hash property or worst performance of O(log n) with different block sizes.
Suggest using B Trees with hash based index that gives the following
1) Search performance O(1) - worst O(log N) depending upon the hash property and block size selected.
2) Insert / delete for best hash property with zero collisions or at the worst O(log n). In this case insertion and deletions in a word dictionary is rare
3) Memory requirements are O(n) - as only hash indices are stored
(Continued on next question...)
Other Interview Questions
| 