Finding median of large set of numbers too big to fit into memory

Question

I was asked this question in an interview recently.

There are N numbers, too many to fit into memory. They are split across k database tables (unsorted), each of which can fit into memory. Find the median of all the numbers.

Wasn't quite sure about the answer to this one.

Answer 1

There's a few potential solutions:

• External merge sort - O(n log n)
  You basically sort the numbers on the first pass, then find the median on the second.
• Order statistics distributed selection algorithm - O(n)
  Simplify the problem to the original problem of finding the kth number in an unsorted array.
• Counting sort histogram O(n)
  You have to assume some properties about the range of the numbers - can the range fit in the memory?
• If anything is known about the distribution of the numbers other algorithms can be produced.

For more details and implementation see:
http://www.fusu.us/2013/07/median-in-large-set-across-1000-servers.html

Answer 2

This answer on quora explains the whole process clearly step by step http://qr.ae/dMkGc. Simply copying it down for non Quorans

Suppose you have a master node (or are able to use a consensus protocol to elect a master from among your servers). The master first queries the servers for the size of their sets of data, call this n, so that it knows to look for the k = n/2 largest element.

The master then selects a random server and queries it for a random element from the elements on that server. The master broadcasts this element to each server, and each server partitions its elements into those larger than or equal to the broadcasted element and those smaller than the broadcasted element.

Each server returns to the master the size of the larger-than partition, call this m. If the sum of these sizes is greater than k, the master indicates to each server to disregard the less-than set for the remainder of the algorithm. If it is less than k, then the master indicates to disregard the larger-than sets and updates k = k - m. If it is exactly k, the algorithm terminates and the value returned is the pivot selected at the beginning of the iteration.

If the algorithm does not terminate, recurse beginning with selecting a new random pivot from the remaining elements.

Analysis:

Let n be the total number of elements and s be the number of servers. Assume that the elements are roughly randomly and evenly distributed among servers (each server has O(n/s) elements). In iteration i, we expect to do about O(n/(s*2^i)) work on each server, as the size of each servers element sets will be approximately cut in half (remember, we assumed roughly random distribution of elements) and O(s) work on the master (for broadcasting/receiving messages and adding the sizes together). We expect O(log(n/s)) iterations. Adding these up over all iterations gives an expected runtime of O(n/s + slog(n/s)), and assuming s << sqrt(n) which is normally the case, this becomes simply (O(n/s)), which is the best you could possibly hope for.

Note also that this works not just for finding the median but also for finding the kth largest value for any value of k.