CareerCup

median of medians recursively?

selection algorithm?

It can be done by modifying the partition algo of quicksort...

it should be an external sort

it should be an AVL tree,then root is always the median.

Select Algorithm...no need to sort the array..linear time

Modify quick sort and partition until you reach the middle:
1. int index = Partition (A[1,N], billion / 2);
2. if index < billion/2 => Partition(A[index + 1, N, billion / 2 - index);
3. if index > billion/2 => Partition(A[0, N, index - billion/2);
4. if index == billion / 2 => Find index1 in A[index+1, N] such that index1 is min
5. Return (index + index1) / 2;

Use two heaps. I am assuming that you have two classes available (minheap and maxheap) and they each have a size method.

public double findMedian(final int[] numbers) {
  MinHeap min = new MinHeap(numbers.length);
  MaxHeap max = new MaxHeap();
  for (int i = 0; i < number.length; i++) {
    min.push(numbers[i]);
  }
  //now even out the sizes as close as possible
  if (min.size() % 2 == 0) {
    while (min.size() > max.size()) {
      max.push(min.pop());
    }
    return ((min.pop() + max.pop()) / 2);
  } else {
    while (min.size() > max.size()+1) {
      max.push(min.pop());
    }
    return min.pop();
  }
}

// have two heaps
//each heap will hold close to half if not half the elements in the array
//designate one heap to always be used to hold one extra element (maxHeap)
// maxHeap will hold elements < median
// minHeap will hold elements > median
//if number of elements is even, take average of top two elements from each heap
//if number of elements is odd, take the top of the heap which holds the one extra element

static priority_queue<int> maxHeap;
static priority_queue<int, vector<int>, greater<int> > minHeap;
int getMedian();

void balanceHeaps(priority_queue<int>& maxHeap, priority_queue<int, vector<int>, greater<int> >& minHeap)
{
	int temp = 0;
	
	if (maxHeap.size() == minHeap.size() || maxHeap.size() == minHeap.size() + 1)
		return;
	//move element from maxHeap to minHeap
	else if(maxHeap.size() > minHeap.size() + 1)
	{
		temp = maxHeap.top();
		maxHeap.pop();
		minHeap.push(temp);
	}	
	else
	{
		temp = minHeap.top();
		minHeap.pop();
		maxHeap.push(temp);		
	}
}

void insertNumber(int n, priority_queue<int>& maxHeap, priority_queue<int, vector<int>, greater<int> >& minHeap)
{
	//see if number goes in min heap or max heap
	if(n < getMedian())	// go in maxHeap
	{
		maxHeap.push(n);
	}
	else
	{
		minHeap.push(n);
	}
	balanceHeaps(maxHeap, minHeap);
}

int getMedian()
{
	if(maxHeap.size() != 0)
	{
		if(maxHeap.size() > minHeap.size())
			return maxHeap.top();
		else
			return (maxHeap.top()+ minHeap.top()) / 2;
	}
	else
		return 0;
}

void printMedian(int arr[], int n)
{	
	int median = 0;
	
	for(int i = 0; i < n; i++)
	{
		insertNumber(arr[i], maxHeap, minHeap);
		cout<<"Median: "<<getMedian()<<endl;
	}
}

int main()
{
	int arr[] = {5,15,1,3,2,8,7,9,10,6,11,4};
	printMedian(arr, 12);
	keep_window_open();
}