*
*
*Using partition Logic of Quick Sort:
*
*Algoritm:*
1. pivot = 1st element.
2. Find the position of pivot in the array using partition logic of Quick
sort
3. If Rank lies on the right side of the position then call this function
with the right array
4. If rank lies on the left side of the position, then call this function
with the left array.
5. If rank == position
- return the element at position
On Sun, Jul 25, 2010 at 4:44 AM, Algoose chase <harishp...@gmail.com> wrote:
> 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
> <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<algogeeks%2bunsubscr...@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<algogeeks%2bunsubscr...@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.
