CareerCup

trie can be used

en.wikipedia.org/wiki/Trie

Yes Its Trie

if we have a lot of space at out disposal we can use Hashtable.
for each prefix of a word in the dictionary, we must hash that prefix and value should be a set of all the words which has that prefix...look up will be constant time

We should definitely use a trie but also we should provide suggestions of word that are minimal in length from the current internal node.

Ternary search tree is good solution

Hashtables are most efficient if we have a lot of space
for examples if the words are :
accomplish, accomplishment, account
then hash['a'] = {accomplish, accomplishment, account}
hash['ac] = {accomplish, accomplishment, account}
hash['acc'] = {accomplish, accomplishment, account}
hash['accom'] = {accomplish, accomplishment}
hash['accomp'] = {accomplish, accomplishment}
hash['accompl'] = {accomplish, accomplishment}
hash['accompli'] = {accomplish, accomplishment}
hash['accomplis'] = {accomplish, accomplishment}
and so on...

although a lot of extra space is used but search suggestion is always O(number of words mactching the prefix}...thus it is better than trie if space is sufficient.

Other than that trie is always used