If the input stream does not allows random access(and we cant store the elements in auxillary memory) then there is no way to find in O(1)(Can be done non-deterministically though in O(1)) . If the above two constraints are not present then the problem is trivial enough to be discussed.
On Fri, Dec 16, 2011 at 2:15 PM, hardbug <[email protected]> wrote: > > I guess median would be the middle element of the array(A[n/2]) where > n is odd, and if the array size is even then you might return the mean > of two middle values. > > On Dec 16, 12:26 pm, Sangeeta <[email protected]> wrote: > > You are given a stream of numbers which can be positive or negative. > > You are > > required to provide an operation FIND MEDIAN..which when invoked > > should be > > able return the median of the numbers in stream (in sorted order) in > > O(1) > > time. > > -- > 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. > > -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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.
