Interview Questions And Answers 
-
What method would you use to look up a name in a dictionary?
19,567 Views |
(46 votes, avg: 3.22)
Loading ...
Answers »
Our Sponsors
Our Sponsors
What method would you use to look up a name in a dictionary?
19,567 Views | (46 votes, avg: 3.22)
Loading ...
This is the classic example of Divide and Conquer.
According to folklore, Professor Skiena would demonstrate binary search by asking for a name, and then looking it up in the phonebook by checking the middle of the book, does a comparison, and literally tear out half the book and throw it in the trash.
Remember that game 20 questions? You have to ask 20 questions to guess a word. Well, the way to cheat is to narrow it down half way every time. The English Dictionary has about 500,000 words, meaning you would still have queries to spare.
Yes, it would be boring, but it would go something like this:
Does your word come before the word “marry”? Yes
Does your word come before the word “gerrymander”?
You get the point.
Assuming you already know you have to sort, you can binary search at O(log_2 N). Which for say, a trillion, is less than 50.
But its application doesn’t stop there, as it (as well as its cousin ternary search) can help you solve numerical equations (this is actually call bisection, but same paradigm). For example, you want to find the cube root of N (N^(1/3)), but don’t have some sort of library ready. Easy solution? Binary search! You know x=y^3, so “guess” a value for x, and go from there!
Dictionary’s doesn’t contain names.
Well this was asked in one of my technical interviews. Thankfully i knew the answer. Anyone who has ever gone through “Introduction to Algos” would know that B-trees are used for this purpose. A B-tree has a single root node and can store a definite number of values. The concept of B-tree is difficult to explain through text only so heres an example.
Suppose there we are considering only two values of a root node say Ab and Ad, then a child will lie between the two values and will contain all the entries such that
(entry > Ab) and (entry
I would use trie - although the search is o(n) but you have other dictunary actions that is done efficiently in such data structure
I agree with sasha.. Trie should be the answer. When looking for a word in dictionary, what we do practically is nothing but using trie.
@Sasha: search is O(1) and not O(n) in case of trie
using binary search is fine, but we do something smarter when using a dictionary: we know that A is at the very beginning of the dictionary and L is somewhere in the middle and do the binary search accordingly. No one would open the middle of the dictionary to look up “abuse”. It is obviously at the very first pages of the dict. So a “smart” binary search algorithm is used, I can say.
For lookup name in a dictionary,
everyone following one method but without knowing name that is called “Binary Search-Indexing”.
For Example, if we want search name “INDIA”
First we will go to the “I” Index.
Then for Sorted names in I Index
Technically, all of those answers are right. However, major companies are looking for the most efficient way. By saying you use a trie, you search basically the way most people do. Slightly brighter people use binary searches, because it is much quicker. Even brighter people use B-Trees. A binary search is basically a B-tree search where the B-tree node has only 1 key and 2 pointers. There is an optimum B-tree that will have a search that is log_n().
O(log_n) 2.
ignore the last line, i was trying to say O(log_n x) is quicker than O(log_2 x) which is quicker than O(x).
If I were only going to be looking up words that were names of either a person, place or thing, I would first eliminate all other non-name words from the dictionary.
(Oh, this solution assumes that there will be millions of like requests.)
Put the names in an electronic dictionary and simply type the name into some standard word-search engine.
Since the (search) time differential between excluding or including non-names (e.g., verbs and adjectives) is pretty small, you could just include the non-names if your search count is in the thousands or hundreds of thousands or if the output is to go directly to a human instead of another machine.
Using a trie is better than binary search or a B-tree. Let us say that the input word to look for is of length w. In order to compare the input word with some word in the dictionary in binary search it takes O(w) time. So if there are n words in the dictionary, it takes O(w*log(n)) time. A similar argument applies for a B-tree also. But with a trie, it only takes O(w) time to search. Morover, the space overhead for a trie is less because most nodes are reused. If we have a sparse dictionary then Patricia trees could be used to eliminate even more space overhead. So I would say that a trie is a better solution.
Basically a bubble search.
We can use hashing method for implementing dictionary.
For each word in a dictionary we will generate the unique no. This all no. are sorted. When a user have to search for a word..he will use the same formula for number generation . THen that no. will be searched in given list of unique no. If no. found then it will display the details of the word in a dictonary .
I guess, we follow the multi-level hashing method in practical.
i guess i read something known as tries in my college days and thats how dictionaries work, so use tries(WIKI will tell you) and you are done in O(1) time
cheers
Leave an Answer/Comment