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.
Posts
Another Anti-Gay Attack Reported in New York City
-
For the third time since Mark Carson was shot and killed by a homophobe on
Saturday, a gay man was attacked in Manhattan because of his sexual
orientatio...
38 minutes ago
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