This can be done in O(n ) with O(1) space compexity . This problem can be reduced to finding the kth smallest number in an unordered collection . There exists an O(n) algo for this . For finding the 10th most frequent number we should find (n-10)th smallest number . Once found by doing an linear scan we can finf max 10 elements . If we want to preserve the order of 10 max elements we can sort it constant time .
-Thanks & Regards K.Abhinav Raghunandan Department of Computer Science Engg, IIT Madras On Mon, Dec 27, 2010 at 10:01 PM, DIPANKAR DUTTA <[email protected] > wrote: > hey... > what's about the storage managment ? > the search text may not be a fixed length string.. > is implementation of a node is fessible? > > one alternative solution may be associate a hash table along with this. but > again the problem with collision ,, to avoid collision u can use perfect > hashing with universal hash function. > > you can also use an alternative solution hash function and priority queue > using MAX heap... > > > On Mon, Dec 27, 2010 at 2:20 AM, Chi <[email protected]> wrote: > >> A trie is a binary tree with it nodes has as many leafs as is suitable. >> A binary tree has only 2 leafs per nodes. In a trie it happens that a node >> doesn't contain any leafs. This happens over many nodes. This is >> considerable a waste of space. A radix-trie tries to eliminate this empty >> nodes by compressing them into 1 node. The difference between a radix-trie >> and suffix-trie is that a suffix-trie can solve text-based problems. A >> radix-trie is good to store a dictionnary and search for words. Or >> associative arrays. Or ip addresses. >> >> Unlike balanced trees, radix trees permit lookup, insertion, and deletion >> in O(k) time rather than O(log n). This doesn't seem like an advantage, >> since normally k ≥ log n, but in a balanced tree every comparison is a >> string comparison requiring O(k) worst-case time, many of which are slow in >> practice due to long common prefixes. In a trie, all comparisons require >> constant time, but it takes m comparisons to look up a string of length m. >> Radix trees can perform these operations with fewer comparisons and require >> many fewer nodes. >> K=key >> n=string >> >> I have a written a kart-trie in php: >> https://sourceforge.net/projects/kart-trie >> >> The only difference to a radix-trie is that the decision to branch either >> left or right is used with a key of 32-bit. >> >> ----- Ursprüngliche Mitteilung ----- >> > @Chi: Would you please explain the process in a little bit more >> > details? It will be helpful. >> > Is Trie and Radix-Trie same? >> > >> > -- >> > You received this message because you are subscribed to the Google >> > Groups "Algorithm Geeks" group. To post to this group, send email to >> > [email protected]. To unsubscribe from this group, send email >> > to [email protected]. For more options, visit this >> >> > group at http://groups.google.com/group/algogeeks?hl=en. >> > >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]<algogeeks%[email protected]> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > DIPANKAR DUTTA > M-TECH,Computer Science & Engg. > E&C Dept,IIT ROORKEE > Uttarakhand , India – 247667 > ------------------------------------------- > website:http://people.iitr.ernet.in/shp/09535009/Website/index.html > ph no-09045809987 > Lab: 286454 > email:[email protected] <email%[email protected]> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
