Interview Question

Anonymous Interview Menlo Park, CA

How would you implement division without +, - or

  multiplication
Answer

Interview Answer

6 Answers

2

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
8

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
2

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
1

// 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
0

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

Add Answers or Comments

To comment on this question, Sign In with Facebook or Sign Up