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 <ankur.kkhur...@gmail.com>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 <shoonya.mo...@gmail.com>
> 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
> > <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<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.
