Facebook

  www.facebook.com
Work in HR? Unlock Free Profile

Facebook Software Engineer Interview Question

I interviewed in Menlo Park, CA and was asked:
"How would you implement division without +, - or multiplication"
Add Tags [?]
Answer

Part of a Software Engineer Interview Review - one of 1,076 Facebook Interview Reviews

Answers & Comments

2
of 5
votes

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
7
of 8
votes

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
of 3
votes

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
of 3
votes

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
of 1
vote

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

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

Tags are like keywords that help categorize interview questions that have something in common.