I already saw the answer using 2 heaps but it loads all numbers in memory. http://stackoverflow.com/questions/10657503/find-running-median-from-a-stream-of-integers

// Flattening a linked list with an optional node assuming that public class Node { private Object payload; private Node nextNode; private Node optionalNode; public Node(Object payload, Node nextNode, Node optionalNode) { this.payload = payload; this.nextNode = nextNode; this.optionalNode = optionalNode; } public void setNextNode(Node nextNode) { this.nextNode = nextNode; } public Object getPayload() { return payload; } public Node getNextNode() { return nextNode; } public Node getOptionalNode() { return optionalNode; } public void setOptionalNode(Node optionalNode) { this.optionalNode = optionalNode; } } // flatten a linkedlist with optional node public static Node flattenLinkedList(Node head) { if (head == null) { return null; } Node node = head; while (node != null) { if (node.getOptionalNode() != null) { Node newNext = flattenLinkedList(node.getOptionalNode()); getLastNode(node.getOptionalNode()).setNextNode(node.getNextNode()); node.setNextNode(newNext); node.setOptionalNode(null); } node = node.getNextNode(); } return head; } // Given a head, return the last node of the list private static Node getLastNode(Node head) { if (head == null) return null; Node lastNode = head; while (head != null) { lastNode = head; head = head.getNextNode(); } return lastNode; }

Flattening can be done with recursion.. Node{ Node next, Node nested }; Node Flatten(Node h, Node tail) { if (h == null) return tail; if (h.nested != null) { h.next = Flatten(h.nested, Flatten(h.next, tail)); } else { h.next = Flatten(h.next, tail); } return h; }

public static void flatten(Node head) { Node curr = head; while (curr != null) { if (curr.nest != null) { Node tail = curr.nest; while (tail.next != null) { tail = tail.next; } tail.next = curr.next; curr.next = curr.nest; curr.nest = null; } curr = curr.next; } }

Finding _global_ median among 10000 servers is a very different problem. Here is the solution: 1. Sort all integers on all servers in parallel. 2. Find global minimum (GMIN) and global maximum (GMAX) in paralell 3. Use binary search with starting boundaries GMIN and GMAX to find value of global median. On each iteration a) make a guess: GMEDIAN = (GMIN + GMAX) / 2. b) check the global number of integers lower (GLOWER) and higher (GHIGHER) than GMEDIAN. c) if (GLOWER < GHIGHER) GMAX = GMEDIAN else GMIN = GMEDIAN. Repeat until GMAX - GMIN <= 1

There is given that there are 10,000 servers which means you can distribute the data across HDFS cluster using Hadoop. Then you need to Sort all these numbers using Map/Reduce and find the numbers existing at n/2 location. Map/reduce will integrate the list on all 10,000 computers automatically and once you have 10,000 * 10e9 numbers, You can find the median at n/2 or n/2 + 1 location.

For integer division by 2 of unsigned int, use the shift operator. For other type of divisions, need to think more :)

How do you find the median among a billion numbers using 2 heaps? I thought the answer was related to the algorithms median of medians and selection.