CareerCup

I think trie

My Solution:

Prefix Tree, Hashing can be used for this solution.

trie..

Trie is generally used to represent a dictionary of words or dictionary of contacts in a cell phone but in our case we need to predict the next word which he is going to type based on the previous word . Based on the language/Grammar used and the usage pattern of the usage we build a graph with conneactions between the Nodes(Each word represented as word ) Edges (would reprenset a most proable word after this word comes) we can keep incrementing the value of the edge based on the usage of the next word . The next word that is being predicted can be done using by finding the next node with max value .

Hope it might help.