CareerCup

trie

trie would be the best data structure for the real world dictionary as if hash table is used the worst case running time would be O(n) where n would be the total number of elements in dictionary but worst case time taken in case of trie is O(m) where m is the length of string
For more information please refer the following link

wikipedia.org/wiki/Trie

It should be hashtable right?

This question is ambiguous... I would ask the interviewer what does he mean by real world dictionary... A real world dictionary may need O(1) access, in which case it will need HashMap for implementation (I would not go for hashtable, because atleast in java.. hashtable do not allow concurrent access, not even for read, and in dictionary we do not need to modify it that often, so we should use hashmap, such that concurrent read access are allowed, and when we need to modify it, we can use synchronized methods to achieve that).

Or if my real world is fine with o(log n) access time, then we can use trie. Also to keep in mind tries are used for substring search rather then dictionary, though it could be extended to the dictionary concept.

Use hashset with chain in the buckets.Keep N buckets where N is less than total words in dictonary.For each bucket use a list (appearing as chain ).For insertion of key 1) get hash of the key.2)Apply compression to hash as hash mod N to keep hashcode under N.3)traverse the chain in the bucket nth .4) then add entry(key,value) to the chain.

Try Skip list. Its better then any Data Structure that uses Tree like structure

Trie DS is the answer.
this question is asked to my friend and he answered this and got selected.

I would have asked interviewer.

1. what do he intend to store in the dictionary? (English words, Names, Phone Numbers etc)
2. How many elements will be there in dictionary?
3. What all operations he want to perform with the dictionary? (Search by complete element, search words with prefix and so on.)
4. For which device he want to use this dictionary? (cell phone, PC etc).

1. Lets suppose dictionary is for words in english language.
2. There are over 10 lacs of words making a hashmap will lead to collision and cost of resolving collision will be greater as compare to cost of searching which will be O(1) for hashmap and O(k) for TRIE (k = 6-12) hashmap -1 TRIE +1.
3. We want our search to display all words with mentioned prefix. hashmap again -1 TRIE +1.
4. Lets say we want to store the dictionary on cell phone , then memory available is limited and storing 10 lacs of word in hashmap and keeping them all in memory is not a feasible soultion. hashmap -1 TRIE+1.

Trie plus Hash table,
Trie to organize words in sorted manner, and once get word, use that as key into hash table