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 <
radhakrishnance...@gmail.com> wrote:
> with BST we can query the occurence in lg (n)
>
> On Sun, Dec 26, 2010 at 5:19 PM, mohit ranjan <shoonya.mo...@gmail.com>
> 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
> > <radhakrishnance...@gmail.com> 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 <shashank7andr...@gmail.com>
> 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 algoge...@googlegroups.com.
> >> > To unsubscribe from this group, send email to
> >> > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> >> > 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 algoge...@googlegroups.com.
> >> To unsubscribe from this group, send email to
> >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> >> 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 algoge...@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> > 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 algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> 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 algoge...@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?hl=en.
