Splay Trees are self modifying trees. Upon the frequency of an element it's not is brought up closer to the root.
So in a continuous stream of words, every word is inserted as a node, if it is already present the score of that node is increased and the tree is modified, over a period of time, the more frequent words will be nearer to the root, the root being the most frequent word. For the top M elements, do a level order search and traverse only ' m ' elements. Total Complexity would be O(n logn) ( for insertions of n elements) On Wed, Nov 30, 2011 at 12:46 AM, kumar raja <[email protected]>wrote: > @Anup: > > How splay trees come into picture here?? I think TRIE or Hashtable will > work out. > > But it is difficult to conceive the TRIE solutions and explain it to the > Interviewer .so i am looking for something else better and concrete one. > > > On 29 November 2011 08:50, Anup Ghatage <[email protected]> wrote: > >> Splay trees >> >> On Tue, Nov 29, 2011 at 10:07 PM, kumar raja <[email protected]>wrote: >> >>> You get a stream of words, find top m frequent words. >>> >>> What are all the possible approaches for this problem ?? >>> >>> -- >>> Regards >>> Kumar Raja >>> M.Tech(SIT) >>> IIT Kharagpur, >>> [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]. >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> >> >> -- >> Anup Ghatage >> >> -- >> 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. >> > > > > -- > Regards > Kumar Raja > M.Tech(SIT) > IIT Kharagpur, > [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]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Anup Ghatage -- 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.
