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.
