First of all GoogleGroups suxs, its takes sooooo.. long for the new post/reply to appear.
Secondly I think we can improve the algorithm by having a hash table auxillary to the max heap we have constructed. Here the size of the hashtable is the size of the alphabet set (a constant). In that case we can search for the existence or non-existence of a new character in O(1) time. Hence the only bottle neck would be heapify operation O(log N) time (instead of O(N) time). _dufus On Aug 17, 12:15 am, richa gupta <richa.cs...@gmail.com> wrote: > @dufus : > > suppose the words occurs like ( at the last of the document or u can say > that in the window of size N , the scenario is ) > l, b,b,b, c , d,d, e a > so ur max heap will make it > b(3) > d(2) c(1) > e(1) a (1) l(1) > > now explain me what happens when b or d or some new word "m" > > 2009/8/16 Miroslav Balaz <gpsla...@googlemail.com> > > > > > I think the teoreticaly easiest solution is to have two balanced binary > > search trees interlinked. on for finding by string, second for keeping count > > second can keep subtree sizes, and every time you check the position and if > > it changes then you can update list, you do not have to make more > > computation than is needed to redraw screen and to maintain balanced tree. > > > 2009/8/14 richa gupta <richa.cs...@gmail.com> > > >> You have to develop a piece of code that can be attached to a program > >> like Microsoft Word, which would list the last "N" words of the > >> document in descending order of their occurence, and update the list > >> as the user types. What code would you write? Using pseudo code is > >> fine, just list the basic things you would consider > > >> -- > >> Richa Gupta > >> (IT-BHU,India) > > -- > Richa Gupta > (IT-BHU,India) --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
