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();
  }
}