Interview Question

Software Engineer Interview Menlo Park, CA

How would you implement division without +, - or

  multiplication
Answer

Interview Answer

9 Answers

4

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

Anonymous on Dec 12, 2013
10

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.

Han Liu on Jan 5, 2014
2

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.

Merlin on Jan 13, 2014
3

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

Merlin on Jan 13, 2014
2

// 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;
    }

ledger on May 10, 2014
2

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

Anon on Aug 7, 2014
0

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

Anonymous on Nov 10, 2014
0

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

Anonymous on Jan 7, 2015
0

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.

Given 10,000 servers containing a Billion integers each how would you find how to find the median? on Feb 11, 2015

Add Answers or Comments

To comment on this, Sign In or Sign Up.