Saturday, May 22, 2010

Sort a dictionary of variable lenght words

Assume you have a dictionary of k words. They have variable lengths, but the total number of symbols counted if we juxtapose all the words is n. Give an optimal sorting algorithm.

PS: this is a tricky question, with practical implication in information retrieval.


  1. A slight variant of Radix Sort gives a simple O(n) time and O(k) additional space solution

  2. Store the keys of the dictionary in a trie data structure. Now do an preorder traversal of the trie to get the sorted list.