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.
>> >> > 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.
>> >>
>> >
>> > --
>> > 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.
>> >
>>
>> --
>> 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.
>>
>
> --
> 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.
>
--
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.
