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