I keep reading about how Google always asks the interview question on how to pick the median of a large list in a distributed network. Here’s my answer, which I think is pretty optimal:
1. Randomly divide the list equally among all computers.
2. Pick one element (the key) of the list at random.
3. For each computer, for each element in that computer’s sublist, compare that element against the key. If it is less, move the element to the lesser list. If it is more, move it to the greater list.
4. Add up the sizes of the greater and less than lists among all computers.
5. If the sizes are equal, the key is the median. Done.
6. Else set the list to the greater than list. Go to 2