## Interview Question

## Interview Answer

9 Answers

for division, a adding function needs to be built first

int add(int x, int y) {

int a, b;

do {

a = x & y;

b = x ^ y;

x = a << 1;

y = b;

} while (a);

return b;

}

the following part would be easy.

For the median searching problem, do not seek to load all the data into memory once for all. Do it in a smarter way. And keep in mind, the total number of integers are finite, so ask how much memory you can use, and do it with possibly multiple passes.

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.

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.

## Add Answers or Comments

To comment on this, Sign In or Sign Up.

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