hmm.. ok let me try to explain my point... suppose in stream, the rate is 1 integer/k time, so within k time we need to process that number and be ready for next number.
Now when stream has just started, n is small so log(n) is OK, but a time will come when log(n)>k and then numbers will start accumulating.... Mohit On Sun, Dec 26, 2010 at 6:25 PM, radha krishnan < [email protected]> wrote: > with BST we can query the occurence in lg (n) > > On Sun, Dec 26, 2010 at 5:19 PM, mohit ranjan <[email protected]> > wrote: > > @Radha > > > > With BST, the time taken to search a node depends on size (n), which will > > keep on increasing as stream grows long, whereas we need to calculate > freq > > within the fixed time interval for all numbers... > > > > > > any better solution ? > > > > Mohit > > > > > > On Sun, Dec 26, 2010 at 4:48 PM, radha krishnan > > <[email protected]> wrote: > >> > >> An Augmented and self Balancin Binary Search Tree Will suffice > >> Tree { > >> int element; > >> int occurence; > >> } > >> when u have the element in the BST increment the occurence > >> Else create a New node > >> Total Complexity is O(n lgn ) > >> Correct me if am wrong > >> lg n -- for finding the previous occurence of the number > >> > >> On Sun, Dec 26, 2010 at 4:39 PM, bittu <[email protected]> > wrote: > >> > You are provided with a stream of numbers, design a data structure to > >> > store the numbers in the stream along with their no. of occurrences. > >> > > >> > > >> > > >> > Regards > >> > Shashank Mani > >> > > >> > -- > >> > 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]<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]<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]<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.
