Add Each number from the stream to a Doubly linked list in sorted fashion
i = 1;
j = 1;
while( stream not empty)
{
if( i == 1&& j == 1)
{
Median = Cur ; /*Create New list with ist Number*/
}
Add_Node_In_Sorted_Order(Cur);
If( If new node is added after median )
i++; /*if the current median is 3rd node and new
node is added @ 5th position*/
bAddedBeforeMedian = False;
else
j++;
bAddedBeforeMedian = true;
if( i %2 == 1 && !bAddedBeforeMedian)
Median = median ->next;
else if (j%2==1 && bAddedBeforeMeidan)
Median = Median->prev
}
return Median->Data;
At any given point in time Median will point to the median among the numbers
seen so far
---------------------------------------------------------------------------------------------
On Sat, Jul 24, 2010 at 8:02 PM, jalaj jaiswal <[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.
>
> 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[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.
