CareerCup

I think either option is fine, but given that you're going to do a lot more inserts / lookups than index generation (which only happens once) it might be more efficient to use a hashmap for the O(1) lookup and insertion per word, and then to spend the time sorting all indices with O(N*logN) rather than having to navigate the trie each time when adding a word to the index.

A TreeMap of word and linked list of page number (TreeMap<String, LinkedList<String>>)will be better solution. Since all entry in TreeMap is stored in key order.

I think you can use a hashmap: <String, ArrayList<Integer>> and a trie. The hashmap is used to store the word and the page numbers in increasing order. The trie is used for storing all words in alphabetical order.

Whenever you find a new word or an existing word in the hashmap, insert or put the word in the hashmap and append the page number arraylist. Meanwhile, insert the word in the trie if it's not there.

Since we just need to a book index, all we need is to print it out once; performance is most likely irrelevant. map<string, set<int> > should be the most convenient dataset for this purpose, since it autoimatically sorts the words and the page numbers.