This is a great solution. On Jul 28, 3:09 am, janak <chandar...@gmail.com> wrote: > How about keeping heap? > Have two heaps 1. max heap and 2. min heap > keep them equal size all the time and shift top element from one to > other when required... > > > > On Wed, Jul 28, 2010 at 7:46 AM, Gene <gene.ress...@gmail.com> wrote: > > I think you have confused the statement of this problem. The "(in > > sorted order)" comment makes no sense because a median is exactly one > > number. One number is always sorted. > > > After every stream element is read, you want to be able to get the > > median of all elements read so far. > > > You're correct that the way to do this is maintain the elements in > > some kind of sorted data structure where you have O(1) access to the > > middle element. An array or list will work fine, but each stream > > element will require O(n) to insert in the sorted order (just as you'd > > do for insertion sort). It's easy to use a balanced tree instead. > > This reduces the processing time for each element to O(log n). You > > must maintain the invariant that the root of the tree is the median, > > so access time is still O(1). When a new element is read, it goes in > > either the left or right subtree of the root. This may cause the > > median to shift by 0 or 1 position in either direction. In this case, > > you'll always be able to pull the successor or predecessor of the > > root--whichever is the new median--up to the root by using e.g. AVL > > rotations. You'd have to prove that this does not make the tree too > > unbalanced so that the O(log n) insertion is hurt, but I don't think > > this would be hard. > > > On Jul 24, 10:32 am, jalaj jaiswal <jalaj.jaiswa...@gmail.com> 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. > > >> Eg: 0 1 2 3 4 > >> Right FIND MEDIAN returns 2 as median > > >> Now input is -2 -4 > >> So Stream = 0 1 2 3 -2 -2 -4 > >> Sorted Stream would be -4 -2 0 1 2 3 4 and FIND MEDIAN returns 1 > > >> -- > >> With Regards, > >> Jalaj Jaiswal > >> +919026283397 > >> B.TECH IT > >> IIIT ALLAHABAD > > > -- > > 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 > > athttp://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.
