CareerCup

There's an elegant solution(publicized, not my own) to this problem.

Median of a continuous stream of numbers can be found out by:
>> Maintaining two heaps. 
>> Max heap and a Min heap
>> Max heap keeps track of first half of the numbers.
>> Min heap keeps track of the second half.
>> The root elements along with the TOTAL number of elements will give you enough info to find the median
>> Take care in adding new elements to the heaps. You might need to delete and push into the other heap.

hi all,

my answer was

1. create a BST and a counter.

2. each time you get a number insert it into the BST and increment the counter.

3. each node in the BST has a field "rank" that is the number of nodes in the subtree rooted at that node.

4. when median is asked return the node whose rank = counter/2 if counter is odd else return the node whose rank = (counter/2)-1

first the stream is 0,1,2,3,4. the tree will be
0(4)
\
1(3)
\
2(2)
\
3(1)
\
4(0)
counter = 5
now median is 2 as rank(2) = (counter/2).

now comes -2. the tree will be

0(5)
/ \
(0)-2 1(3)
\
2(2)
\
3(1)
\
4(0)
counter = 6
(counter/2)-1 = 2
median is node 2 as rank(2) = 2.

now comes -4. the tree will be

0(6)
/ \
(1)-2 1(3)
/ \
(0)-4 2(2)
\
3(1)
\
4(0)
counter = 7
counter/2 = 3
median = 1 as rank(1) = 3

please tell me if there is any problem in this algorithm. please try it on some other examples and if you find anything not working properly then please notify.

thanking you all

since the range is always sorted median will be at n/2 always.
lets say the median value at the beginning ie Array[n/2] is k.

from here whenever you are inserting any value to the array check if that value is > k or <k.. ie are you inserting in left half or right half.. and keep count the number of insertion in left half and in right half.
At the end calculate l
j+(lefthalfcount -righthalfcount)/2..
j+k would be the next median.. please tell me if you see any mistake

since the range is always sorted median will be at n/2 always.
lets say the median value at the beginning ie Array[n/2] is k.

from here whenever you are inserting any value to the array check if that value is > k or <k.. ie are you inserting in left half or right half.. and keep count the number of insertion in left half and in right half.
At the end calculate l
j+(lefthalfcount -righthalfcount)/2..
j+k would be the next median.. please tell me if you see any mistake

{its j= (lefthalfcount -righthalfcount)/2}

it can be simply maintaining an AVL tree. the median value will be the root always (in case number of nodes are odd)

Find sum of all numbers.
Multiply each integer with the total number of integers in the stream.
Median will be the integer which is more close to the sum,in case of even number of integers, find two such numbers else only one

store all elements in array den
int i,n;
for ( i = 0; i < 1000; i++ ) {
if ( array[i] == '\0' )
{ n=ceil((i-1)/2);
cout<<array[n];
break;
}
}

store all elements in array den
int i,n;
for ( i = 0; i < 1000; i++ ) {
if ( array[i] == '\0' )
{ n=ceil((i-1)/2);
cout<<array[n];
break;
}
}