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.
A slight variant of Radix Sort gives a simple O(n) time and O(k) additional space solution
ReplyDeleteStore the keys of the dictionary in a trie data structure. Now do an preorder traversal of the trie to get the sorted list.
ReplyDelete