Facebook Interview Question for Software Developers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
2
of 2 vote

// Utility function to store vertical order in map 'm' 
    // 'hd' is horizontal distance of current node from root. 
    // 'hd' is initially passed as 0 
    static void getVerticalOrder(Node root, int hd, 
                                TreeMap<Integer,Vector<Integer>> m) 
    { 
        // Base case 
        if(root == null) 
            return; 
          
        //get the vector list at 'hd' 
        Vector<Integer> get =  m.get(hd); 
          
        // Store current node in map 'm' 
        if(get == null) 
        { 
            get = new Vector<>(); 
            get.add(root.key); 
        } 
        else
            get.add(root.key); 
          
        m.put(hd, get); 
          
        // Store nodes in left subtree 
        getVerticalOrder(root.left, hd-1, m); 
          
        // Store nodes in right subtree 
        getVerticalOrder(root.right, hd+1, m); 
    } 
      
    // The main function to print vertical oder of a binary tree 
    // with given root 
    static void printVerticalOrder(Node root) 
    { 
        // Create a map and store vertical oder in map using 
        // function getVerticalOrder() 
        TreeMap<Integer,Vector<Integer>> m = new TreeMap<>(); 
        int hd =0; 
        getVerticalOrder(root,hd,m); 
          
        // Traverse the map and print nodes at every horigontal 
        // distance (hd) 
        for (Entry<Integer, Vector<Integer>> entry : m.entrySet()) 
        { 
            System.out.println(entry.getValue()); 
        } 
    }

- gera October 27, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

static void print(Node n) {
		Deque<Node> stack = new ArrayDeque<>();
		while (n != null) {
			stack.push(n);
			n = n.l;
		}
		doStack(stack);
	}
	
	static void doStack(Deque<Node> stack) {
		if (stack.isEmpty()) {return;}
		Node prev = stack.pop();
		System.out.println(prev.v);
		while (!stack.isEmpty()) {
			Node n = stack.pop();
			System.out.println(n.v);
			print(prev.r);
			prev = n;
		}
		print(prev.r);
	}

- kadok October 28, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

beautiful

- miki October 31, 2018 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Clever but supports only tree example in question. It doesn't support tree like this:
*
* ..............6
* ............/...\
* ...........9.....4
* ........../..\....\
* .........5....1....6
* ..........\......../
* ...........0.... .7
* .............\.......
* ..............11
* ................\
* .................12
* ...................\
* ...................13
* .....................\
* ......................14
*/

- kziomek0000 November 04, 2018 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I do not think it will work for this tree either:

/*
.........0
......../  \
.......-1..1
.........\
.........0
......../
......-1
....../
....-2
*/

It will print the upper -1 instead of the -2.

- ofekpearl November 17, 2018 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

6 is the root. the space didn't come along well.

- Champaklal October 26, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

in-order traversal

- Kumar October 27, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

in-order traversal?

- anonymous October 27, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Node:
    def __init__(self,val):
        self.val = val
        self.left = None
        self.right = None


def getcoldistance(root,horzdist,mydict):
    if not root:
        return None
    if horzdist in mydict:
        mydict[horzdist].append(root.val)
    else:
        mydict[horzdist] = [root.val]
    getcoldistance(root.left,horzdist-1,mydict)
    getcoldistance(root.right,horzdist+1,mydict)

def printvertdist(root):
    m = {}
    getcoldistance(root,0,m)
    for key in sorted(m):
        for val in m[key]:
            print(val,end='')


root =  Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
root.right.left.right = Node(8)
root.right.right.right = Node(9)

printvertdist(root)

- svdynamic October 28, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

using level order traversal and keeping a hash map to preserve the order

void printTree(TreeNode root){
Queue<Pair> q = new LinkedList<Pair>();

TreeMap<Integer,LinkedList<Integer>> map = new TreeMap<Integer,LinkedList<TreeNode>> ();
if(root==null){
return;
}
q.add(new Pair(root,0));
int hd =0;
addValue(map, 0, root.val)



while(q.size()>0){
Pair pair = (Pair)q.poll();
TreeNode temp = q.getTreeNode();
hd = q.getHd();
if(temp.left!=null){
q.add(new Pair(temp.left,hd-1));
addValue(map, hd-1, temp.val);
}
if(temp.right!=null){
q.add(new Pair(temp.right,hd+1));
addValue(map, hd+1, temp.val);
}
}

Iterator<Integer> itr = map.getKeySet();
while(itr.hasNext()){
int key = (Integer)itr.next();
LinkedList l = map.get(key);
while(l!=null){
System.out.print(l.val+" ");
l= l.next;
}
}
}

void addValue(map, int key, int val){
if(map.get(key)==null){
LinkedList<Integer> l = new LinkedList<Integer>();
l.add(root.val);
map.put(0,l);
} else{
LinkedList<Integer> l = (LinkedList<Integer>)map.get(key);
l.add(val);
}
}

class Pair {
TreeNode node;
int hd;
public Pair(TreeNode node,int hd){
this.node = node;
this.hd =hd;
}
}

- HadoopUser October 28, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Traverse Breadth-First to preserve order for nodes with the same horizontal distance. Horizontal distance is used to find nodes in the same column I.e. horizontal distance for nodes 4, 7 and 12 is 1.
/*
..............6
............/...\
...........9.....4
........../..\....\
.........5....1....6
..........\......../
...........0.... .7
.............\.......
..............11
................\
.................12
...................\
...................13
.....................\
......................14
*/

private void printInVerticalOrder(Node root) {
        if (root == null){
            return;
        }
        TreeMap<Integer, List<Integer>> hdToValues = collectHorizontalDistancesToValues(root);
        print(hdToValues);
    }

    private TreeMap<Integer, List<Integer>> collectHorizontalDistancesToValues(Node root) {
        TreeMap<Integer, List<Integer>> hdToValues = new TreeMap<>();

        LinkedList<HDNode> nodes = new LinkedList<>();
        nodes.add(new HDNode(0, root));
        while (!nodes.isEmpty()) {
            HDNode hdNode = nodes.removeFirst();

            hdToValues.putIfAbsent(hdNode.hd, new ArrayList<>());
            hdToValues.get(hdNode.hd).add(hdNode.node.value);

            if(hdNode.node.left != null){
                nodes.add(new HDNode(hdNode.hd - 1, hdNode.node.left));
            }
            if(hdNode.node.right != null){
                nodes.add(new HDNode(hdNode.hd + 1, hdNode.node.right));
            }
        }
        return hdToValues;
    }

    private void print(TreeMap<Integer, List<Integer>> hdToValues) {
        while (!hdToValues.isEmpty()) {
            Map.Entry<Integer, List<Integer>> entry = hdToValues.pollFirstEntry();
            entry.getValue().forEach(v -> System.out.print(v + " "));
            System.out.println("\n");
        }
    }

    private class HDNode {
        int hd;
        Node node;

        HDNode(int hd, Node node) {
            this.hd = hd;
            this.node = node;
        }
    }

- kziomek0000 November 04, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Class Data {
	public int nodeVal;
	public int dist;

	public Data(int n, int d) { nodeVal = n; dist = d;}
}

void stupidTreePrint(Node root) {
	List<Data> arr = new ArrayList<>();
	auxFunc(root, 0, arr);

	// stable sort
	Collection.sort(arr, (o1, o2) -> Integer.signum(o1.dist-o2.dist));

	arr.foreach(e -> System.out.println(" " + e.nodeval + " "));
}

void auxFunc(Node root, int dist, List<Data> arr) {
	if(root == null) return;

	Data tmp = new Data(root.value, dist);
	arr.add(tmp);

	auxFunc(root.left, dist - 1, arr);
	auxFunc(root.right, dist + 1, arr);
}

- Montijack November 14, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

python implementation
/*
..............6
............/...\
...........9.....4
........../..\....\
.........5....1....6
..........\......../
...........0.... .7
.............\.......
..............11
................\
.................12
...................\
...................13
.....................\
......................14
*/

class Node:
    def __init__(self, val:int, left=None, right=None):
        self.val,self.left,self.right = val,left,right
    def __repr__(self): return f'{self.val}'

def mark_nodes(root, index, depth, res):
    cut = None
    if root.left is not None:
        mark_nodes(root.left, index-1, depth+1, res)
    res.append((root, index, depth))
    if root.right is not None:
        mark_nodes(root.right, index+1, depth+1, res)

def print_lrtd(sorted_nodes):
    accum = []
    mark_nodes(root, 0, 0, accum)
    sorted_nodes = sorted(accum, key=lambda x: (x[1],x[2]))
    return [i[0] for i in sorted_nodes]


Output:
stem = Node(0, None, Node(11, None, Node(12, None, Node(13, None, Node(14)))))
root = Node(6, Node(9, Node(5, None, stem), Node(1)), Node(4, None, Node(3, Node(7))))
print_lrtd(root)

- ashaw November 16, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Algorithm:
- Do a inorder tree traversal with following changes
Root Node is denoted with Row Ordinal and Column Ordinal as 0
Every time traversal take a left, Column Ordinal is decremented by 1
Every time traversal take a right, Column Ordinal is incremented by 1
Every time traversal takes to children, Row Ordinal is incremented by 1
Every time traversal moves back to parent, Row Ordinal is decremented by 1
- Sort Nodes based on Column Ordinal, if Column Ordinal matches, then use Row Ordinal
- Print Sorted Nodes

Psuedo-Code:

- Class Node definition is (Value, Left, Right)
- Class NodeEx definition is (Value, RowOrdinal, ColumnOrdinal)

class TreePrinter {
  private Node treeRootNode; 
  private ArrayList<NodeEx> nodes; 
  
  public TreePrinter(Node rootNode) {
    this.treeRootNode = rootNode;
    this.nodes = new ArrayList<NodeEx>();
  }
  
  public void printTree() {
    this.nodes.clear();
    traverseInOrder(rootNode, 0, 0);
    sortNodesByOrdinals();
    printNodes();
  }
  
  private void traverseInOrder(Node node, int rowOrdinal, int columnOrdinal) {
    if (null == node) return;
    this.nodes.append(new NodeEx(node.value, rowOrdinal, columnOrdinal));    
    traverseInOrder(node.Left, rowOrdinal+1, columnOrdinal-1);
    traverseInOrder(node.Right, rowOrdinal+1, columnOrdinal+1);
  }
  
  private sortNodesByOrdinals() {
    nodes.sort_by(node1, node2) {
      if node1.ColumnOrdinal < node2.ColumnOrdinal return -1;
      else node1.ColumnOrdinal > node2.ColumnOrdinal return +1;
      else if node1.RowOrdinal < node2.RowOrdinal return -1;
      else if node1.RowOrdinal > node2.RowOrdinal return +1;
      else return 0;
    }
  }
}

- Laxmi Narsimha Rao Oruganti November 26, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class ByColumnTree {

  public static void main(String[] args) {

    Node root = root(6);
    Node n9 = root.left(9);
    n9.left(5).right(0);
    n9.right(1);
    root.right(4).right(3).left(7);

    List<Node> fringe = new LinkedList<>();

    traverse(fringe, root);
    
    Collections.sort(fringe);
    System.out.println(fringe);
  }

  private static void traverse(List<Node> fringe, Node node) {
    fringe.add(node);
    if(node.left != null) traverse(fringe, node.left);
    if(node.right !=  null) traverse(fringe, node.right);
  }

  static class Node implements Comparable<Node> {
    Node left;
    Node right;
    int val;

    int displacement;
    int depth;
    Node parent;

    static Node root(int val) {
      var node = new Node();
      node.val = val;
      return node;
    }

    Node left(int val) {
      var node = new Node();
      node.val = val;
      node.depth = this.depth + 1;
      node.displacement = this.displacement + 1;
      node.parent = this;
      this.left = node;
      return node;
    }

    Node right(int val) {
      var node = new Node();
      node.val = val;
      node.depth = this.depth + 1;
      node.displacement = this.displacement - 1;
      node.parent = this;
      this.right = node;
      return node;
    }

    @Override
    public int compareTo(Node other) {
      int d = Integer.compare(other.displacement, this.displacement);
      if (d != 0) return d;
      return Integer.compare(this.depth, other.depth);
    }

    @Override
    public String toString() {
      return String.valueOf(val);
    }
  }
}

- Emiliano November 27, 2018 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More