interested ppl can read ths link for stream algorithms... http://www.americanscientist.org/issues/pub/the-britney-spears-problem/1
Mohit On Sun, Dec 26, 2010 at 7:49 PM, Ankur Khurana <[email protected]>wrote: > may be we can assume that k>log(n) > else i dont see a way out than hashing , because that is the only > thing less that log(n). > > On Sun, Dec 26, 2010 at 6:37 PM, mohit ranjan <[email protected]> > wrote: > > 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]<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.
