Facebook Interview Question for Software Developers


Country: United States




Comment hidden because of low score. Click to expand.
3
of 5 vote

import java.util.Map;
import java.util.HashMap;
import java.util.ArrayList;
import java.util.List;

public class ValidBinaryTree
{
	public static void main(String args[])
	{
		ValidBinaryTree v = new ValidBinaryTree();

		Node n3 = new Node(3);
		Node n2 = new Node(2);
		Node n4 = new Node(4);
		Node n5 = new Node(5);
		Node n1 = new Node(1);
		n2.left = n4;
		n2.right = n5;

		n1.left = n2;
		n1.right = n3;

		List<Node> list = new ArrayList<>();
		list.add(n3);
		list.add(n2);
		list.add(n4);
		list.add(n5);
		list.add(n1);

		System.out.println(v.isValid(list));
	}

	public boolean isValid(List<Node> list)
	{
		//create a freqMap
		Map<Integer, Integer> freqMap = new HashMap<>();
		for(Node node : list)
		{
			//if the node is not present in the map
			//add the node
			if(!freqMap.containsKey(node.val))
			{
				freqMap.put(node.val, 1);
			}
			else
			{
				//if the node is present 
				//then decrease the frequency my 1
				freqMap.put(node.val, freqMap.get(node.val)-1);
			}
			//similarly for the left and right child
			if(node.left!=null)
			{
				if(!freqMap.containsKey(node.left.val))
				{
					freqMap.put(node.left.val, 1);
				}
				else
				{
					freqMap.put(node.left.val, freqMap.get(node.left.val)-1);
				}
			}

			if(node.right!=null)
			{
				if(node.right!=null && !freqMap.containsKey(node.right.val))
				{
					freqMap.put(node.right.val, 1);
				}
				else
				{
					freqMap.put(node.right.val, freqMap.get(node.right.val)-1);
				}
			}

		}

		int count = 0;
		//count the elements in the freq map with frequency not equal to
		for(Map.Entry<Integer, Integer> entry : freqMap.entrySet())	
		{
			if(entry.getValue()!=0)
				count++;
		}
		System.out.println(count);
		return count==1;
	}
}

class Node
{
	Node left;
	Node right;

	int val;
	Node(int val)
	{
		this.val = val;
	}
}

- noob October 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Simple. Use a map with indexes of the nodes in the list as keys and integer value. For every node pointed to, increase the integer value. Valid if the map has only ONE entry with value 0 and the rest having value 1.

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

List of nodes are in sorted??

- Mohammed October 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package   something;

import java.util.*;

public class FindIfNodesInListAreFromABinaryTree {

    public static void main(String[] args) {
        System.out.println("== valid tree");
        List<Node> tree = cleanTree();
        boolean areTree = isValidTree(tree);
        System.out.println(areTree); // will PRINT true

        System.out.println("== forest ");
        tree = twoTrees();
        areTree = isValidTree(tree);
        System.out.println(areTree); // will PRINT false

        // tree with at last one node where node.left is pointing to
        // some ancestor
        System.out.println("== invalid tree,  with cycle");
        tree = cyclicTree();
        areTree = isValidTree(tree);
        System.out.println(areTree); // will PRINT true

    }



    private static boolean isValidTree(List<Node> listOfNodes) {
        Objects.requireNonNull(listOfNodes);
        if (listOfNodes.size() <= 1) return true;
        Set<Node> roots = findRoots(listOfNodes);
        if (roots.size() != 1) {
            System.out.printf("No single root could be found, found %d roots %n", roots.size());
            return false;
        }
        Node root = roots.iterator().next();
        System.out.println("root is " + root.d);

        Set<Integer> allNodes = new HashSet<>();
        for (Node n : listOfNodes)
            allNodes.add(System.identityHashCode(n));
        Set<Integer> allNodesCheck = new HashSet<>();
        // visit all nodes in possible tree and add to allNodesCheck
        try {
            saveIdentities(root, allNodes, allNodesCheck);
        } catch (Exception e) {
            System.out.println("Cycle detected..");
            return false;
        }
        return allNodes.equals(allNodesCheck);

    }

    /**
     * as you descend the tree do the following for each node
     * if node is null return
     * find hashCode of this Node object
     * check that this hash exists in the list of all hashCodes
     * check that this hash was NOT seen before
     * add this to the list of seen hash codes
     * recurse with left subtree
     * recurse with right subtree
     *
     * @param root
     * @param allNodes
     * @param allNodesCheck
     * @throws Exception
     */
    private static void saveIdentities(Node root, Set<Integer> allNodes, Set<Integer> allNodesCheck) throws Exception {
        if (root == null) return;
        int h = System.identityHashCode(root);
        if (!allNodes.contains(h)) throw new Exception("Node in tree not found in the list ");
        if (allNodesCheck.contains(h)) throw new Exception("Possible loop ");
        //we established that it is in the original list and it was not seen earlier
        //we now add this node to allNodesCheck
        allNodesCheck.add(h);
        saveIdentities(root.left, allNodes, allNodesCheck);
        saveIdentities(root.right, allNodes, allNodesCheck);

    }

    /**
     * The root node is the one that is NOT pointed to by anyone else
     *
     * @param listOfNodes
     * @return
     */
    private static Set<Node> findRoots(List<Node> listOfNodes) {
        Set<Node> allNodes = new HashSet<>();
        allNodes.addAll(listOfNodes);
        for (Node n : listOfNodes) {
            allNodes.remove(n.left);
            allNodes.remove(n.right);
        }
        System.out.println("size of remaining list that should contain root =" + allNodes.size());
        return allNodes;

    }
    // == mostly boiler plate

    private static List<Node> cyclicTree() {
        Node n1 = Node.of(1);
        Node n3 = Node.of(3);
        Node n5 = Node.of(5);
        Node n6 = Node.of(6);
        Node n12 = Node.of(12);
        Node n7 = Node.of(7);
        List<Node> list = new ArrayList<>();
        list.add(n1);
        list.add(n3);
        list.add(n5);
        list.add(n6);
        list.add(n12);
        list.add(n7);
        n1.left = n3;
        n1.right = n5;
        n3.left = n6;
        n3.right = n12;
        n5.left = n7;
        n7.right = n3; // a node in RIGHT subtree is pointing to a node in the left subtree

        return list;
    }

    private static List<Node> twoTrees() {
        Node n2 = Node.of(2);
        Node n7 = Node.of(7);
        Node n5 = Node.of(5);
        n2.left = n7;
        n2.right = n5;
        Node n11 = Node.of(11);
        Node n15 = Node.of(15);
        n11.left = n15;
        List<Node> list = new ArrayList<>();
        list.add(n2);
        list.add(n7);
        list.add(n5);
        list.add(n11);
        list.add(n15);
        return list;
    }

    private static List<Node> cleanTree() {
        Node n2 = Node.of(2);
        Node n7 = Node.of(7);
        Node n5 = Node.of(5);
        Node n11 = Node.of(11);
        Node n22 = Node.of(22);
        Node n12 = Node.of(12);
        Node n13 = Node.of(13);
        Node n15 = Node.of(15);
        List<Node> list = new ArrayList<>();
        list.add(n2);
        list.add(n7);
        list.add(n5);
        list.add(n11);
        list.add(n22);
        list.add(n12);
        list.add(n13);
        list.add(n15);
        n2.left = n7;
        n2.right = n5;
        n7.right = n11;
        n11.left = n22;
        n5.left = n12;
        n5.right = n13;
        n13.left = n15;
        return list;
    }

    private static class Node {
        Node left, right;
        int d;

        public Node(int d) {
            this.d = d;
        }

        public static Node of(int d) {
            return new Node(d);
        }
    }
}

- Makarand October 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
I wanted to mention here how I have interpreted this problem!

Assume you have a valid binary tree. Take each node from this tree and
add these nodes to a list (array). This is the list the problem is talking about.
While the nodes are placed in this list - they still point to their
original left tree and right sub tree

The method should return TRUE if the list had nodes 
from a valid binary tree

The method should return FALSE if the list had nodes from more 
than one distinct binary tree ( forest )

The method should return FALSE if the list had nodes from a binary 
tree that contained cycles ( not a tree in the first place)

 */

- Makarand October 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Was this asked in a 45 minute interview?

- S October 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <unordered_set>
#include <vector>

using namespace std;

class Node {
	public:
		Node()
		{
			left_ = right_ = NULL;
		}
		Node *left_, *right_;
};

bool AddToChildren(Node *n, Node *parent, unordered_set<Node *> &children)
{
	if (n) {
		if (n == parent ||
			children.find(n) != children.end())
		{
			return false;
		}
		children.insert(n);
	}
	return true;
}

bool IsValidTree(vector<Node *> const &nodes)
{
	unordered_set<Node *> children;
	for (Node *n : nodes) {
		if (n) {
			if (!AddToChildren(n->left_, n, children) ||
				!AddToChildren(n->right_, n, children))
			{
				return false;
			}
		}
	}
	if (children.size() != nodes.size() - 1) {
		return false;
	}
	for (Node *n : nodes) {
		children.erase(n);
	}
	return children.empty();
}

int main() {
/*
       (1)
       / \
    (2)  (3)
    / \
  (4) (5)
*/
	Node n1, n2, n3, n4, n5;
	n1.left_ = &n2;
	n1.right_ = &n3;
	n2.left_ = &n4;
	n2.right_ = &n5;

	cout << IsValidTree({&n1, &n2, &n3, &n4, &n5}) << "\n";
	return 0;
}

- Alex October 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;

class CheckGraph {
	static class Node {
		int val;
		Node left, right;

		Node(int val, Node left, Node right) {
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}

	static boolean isValid(List<Node> nodes) {
		return nodes.stream()
				.anyMatch(n -> {
					Set<Node> toFind = new HashSet<>(nodes);
					return isValidInternal(n, toFind) &&
							toFind.size() == 0;
				});
	}

	private static boolean isValidInternal(Node head, Set<Node> toFind) {
		if (toFind.remove(head)) {
			return (head.left == null || isValidInternal(head.left, toFind)) &&
					(head.right == null || isValidInternal(head.right, toFind));
		} else {
			//cycle
			return false;
		}
	}

        //smoke test
	public static void main(String[] args) {
		Node n = new Node(1,
				new Node(2, new Node(3, null, null), new Node(4, null, null)),
				new Node(5, new Node(6, null, null), new Node(7, null, null)));
		List<Node> nodes = new ArrayList<>(
				Arrays.asList(n.left.left, n.right.left, n.left.right, n.right.right, n.left, n.right, n));
		System.err.println(isValid(nodes)); //prints true
		//add cycle
		n.right.right.right = n.right.left;
		System.err.println(isValid(nodes)); //prints false
		//add external node
		nodes.add(new Node(42, null, null));
		System.err.println(isValid(nodes)); //prints false
	}
}

- qmaur October 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Create an array that would store the number of parents of each node

2. Iterate through the given array of nodes and start filling the new array.

3. The given nodes form a valid binary tree if:
a. Number of nodes with no parents = 1 (the root).
b. No nodes have more than one parent.
c. Doing a tree traversal from the root node covers all the nodes in the list and no external node is referenced.

- S October 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;
public class MyClass {
public static void main(String args[]) {
List<Node> list = new ArrayList<Node>();
Node d = new Node("D");
Node e = new Node("E");
Node f = new Node("F");
Node g = new Node("G");
Node b = new Node(d, e, "B");
Node c = new Node(f, g, "C");
Node a = new Node(b, c, "A");
Node x = new Node("X");
list.add(a);list.add(b);list.add(c);list.add(d);
list.add(e);list.add(f);list.add(g);list.add(x);

System.out.println(isValidTree(list));
}

static boolean isValidTree(List<Node> list){
boolean visited[] = new boolean[list.size()];
boolean notAloof[] = new boolean[list.size()];
for(Node item:list){
if(item != null){
if(item.left !=null && item.right !=null)
if(!list.contains(item.left) || !list.contains(item.right)) return false;
visited[list.indexOf(item)] = true;
if(item.left !=null && item.right !=null){
if(visited[list.indexOf(item.left)] || visited[list.indexOf(item.right)]) return false;
notAloof[list.indexOf(item.right)] = true;
notAloof[list.indexOf(item.left)] = true;
}
if(item.left !=null && item.right !=null)
notAloof[list.indexOf(item)] = notAloof[list.indexOf(item.right)] || notAloof[list.indexOf(item.left)];
if(!notAloof[list.indexOf(item)]) return false;
}
}
return true;
}

static class Node{
Node left;
Node right;
Object data;

Node(Object a){
left = right = null;
data = a;
}
Node(Node a, Node b, Object d){
left = a;
right = b;
data = d;
}
}
}

- Mohan October 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;
public class MyClass {
    public static void main(String args[]) {
        List<Node> list = new ArrayList<Node>();
        Node d = new Node("D");
        Node e = new Node("E");
        Node f = new Node("F");
        Node g = new Node("G");
        Node b = new Node(d, e, "B");
        Node c = new Node(f, g, "C");
        Node a = new Node(b, c, "A");
        Node x = new Node("X");
        list.add(a);list.add(b);list.add(c);list.add(d);
        list.add(e);list.add(f);list.add(g);list.add(x);
        
        System.out.println(isValidTree(list));
    }
    
    static boolean isValidTree(List<Node> list){
        boolean visited[] = new boolean[list.size()];
        boolean notAloof[] = new boolean[list.size()];
        for(Node item:list){
            if(item != null){
                if(item.left !=null && item.right !=null)
                    if(!list.contains(item.left) || !list.contains(item.right)) return false;
                visited[list.indexOf(item)] = true;
                if(item.left !=null && item.right !=null){
                     if(visited[list.indexOf(item.left)] || visited[list.indexOf(item.right)]) return false;
                     notAloof[list.indexOf(item.right)] = true;
                     notAloof[list.indexOf(item.left)] = true;
                }
                if(item.left !=null && item.right !=null)
                     notAloof[list.indexOf(item)] = notAloof[list.indexOf(item.right)] || notAloof[list.indexOf(item.left)];
                if(!notAloof[list.indexOf(item)]) return false;
            }
        }
        return true;
    }
    
    static class Node{
        Node left;
        Node right;
        Object data;
        
        Node(Object a){
            left = right = null;
            data = a;
        }
        Node(Node a, Node b, Object d){
            left = a;
            right = b;
            data = d;
        }
    }
}

- Mohan October 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution using Python code. Find the node with max height. It should be the root. From the root traverse using BFS and conclude if it's a valid tree.

from Queue import Queue

def get_height(node):
    # algorithm will be O(n)
    if node is None:
        return 0
    return 1 + max(get_height(node.left), get_height(node.right))


def is_valid_binary_tree(nodes):
    if nodes is None or len(nodes) == 0:
        return True

    root = nodes[0]
    valid = {}

    for node in nodes:
        x = get_height(node)
        valid[node] = True
        if x > get_height(root):
            root = node

    # Found the highest node, now use hashmap
    bfs_queue = Queue()
    bfs_queue.put(root)

    while not bfs_queue.empty():
        current = bfs_queue.get()
        if current.left is not None:
            bfs_queue.put(current.left)

        if current.right is not None:
            bfs_queue.put(current.right)

        if current not in nodes:
            return False
        else:
            del valid[current]
            nodes.remove(current)

    return len(nodes) == 0


if __name__ == '__main__':
    n1 = TreeNode(0)
    n2 = TreeNode(1)
    n3 = TreeNode(2)
    n4 = TreeNode(3)
    n5 = TreeNode(4)
    n6 = TreeNode(6)

    n1.left = n2
    n1.right = n3
    n2.left = n4
    n3.right = n5

    print is_valid_binary_tree([n1, n2, n3, n4, n5])
    print is_valid_binary_tree([n1])
    print is_valid_binary_tree([n1, n2, n3, n4, n5, n6])
    print is_valid_binary_tree([n1, n1, n3, n4, n5, n6])

- hpham October 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It can be done in O(n) time complexity (save the list into a Hashset for fast look up).

Iterate each node in the list and check the following conditions:
1. Its left and right node are null.We move the node from the list to a hashset, called "lookForParent".

2. Its left or right node does not belong to the list nor appear in the "lookForParent",
It violates rule #1 or #2, we can simply return false.

3. Its left and/or right node belongs to the list or appears in 'lookForParent".
(a) Remove this node from the list.
(b) Check if this node's child(ren) are in the list or in the "lookForParent" recursively
(if not, it violates rule #1 or #2 and return false) and remove the node from the list
or from the "lookForParent".
(c) Move this node to "lookForParent".

At the end if the "lookForParent" hashset contains one node (it is the root), return true. Otherwise return false (violates rule #3).

public boolean isValidTree(List<Node> list){
	Set<Node> set = new HashSet<Node>(list);
	HashSet<Node> lookForParent = new HashSet<Node>();
	for(Node each:list){
		if(set.contains(each){
			if(each.left == null && each.right == null){
				set.remove(each);
				lookForParent.add(each);
			}
			else if(each.left != null || each.right != null){
				Node tmp = each;
				boolean good = checkChildren(each.left,set,lookForParent) &&
                                                                 checkChildren(each.right,set,lookForParent);
				if(good){
					lookForParent.add(tmp);
				}
				else{
					return false;
				}
			}
		}
	}
	if(lookForParent.size() == 1){
		return true;
	}
	return false;
}
public boolean checkChildren(Node node, HashSet<Node> set, HashSet<Node> lookForParent){
	if(node == null) return true;
	else if(lookForParent.contains(node)){
		lookForParent.remove(node);
		return true;
	}
	else if(set.contains(node)){
		set.remove(node);
		return checkChildren(each.left,set,lookForParent) && 
                               checkChildren(each.right,set,lookForParent);
	}
	return false;

}

- jiahuang October 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean findAll(List<TreeNode> list){
         if(list==null || list.size()<1){
             return false;
         }
        
         Map<TreeNode,Integer> map = new HashMap<>();
         for(TreeNode ele:list){
             if(!map.containsKey(ele)){
                 map.put(ele,0);
             }
             if(ele.left!=null){
                 map.put(ele.left,map.getOrDefault(ele.left,0)+1);
             }
             if(ele.right!=null){
                 map.put(ele.right,map.getOrDefault(ele.right,0)+1);
             }
         }
        
         TreeNode root = null;
         for(TreeNode ele:list){
             int val = map.get(ele);
             if(val==0&&root!=null){
                 return false;
             }else if(val==0 && root==null){
                 root=ele;
             }else if(val>1){
                 return false;
             }
         }
        
         preorderTree(root,map);
          
         return map.size()==0;
    }
    
    public static void preorderTree(TreeNode root,Map<TreeNode,Integer> map){
        
        if(root==null){
            return;
        }
        
        preorderTree(root.left,map);
        preorderTree(root.right,map);
        map.remove(root);
    }

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

public static boolean findAll(List<TreeNode> list){
         if(list==null || list.size()<1){
             return false;
         }
        
         Map<TreeNode,Integer> map = new HashMap<>();
         for(TreeNode ele:list){
             if(!map.containsKey(ele)){
                 map.put(ele,0);
             }
             if(ele.left!=null){
                 map.put(ele.left,map.getOrDefault(ele.left,0)+1);
             }
             if(ele.right!=null){
                 map.put(ele.right,map.getOrDefault(ele.right,0)+1);
             }
         }
        
         TreeNode root = null;
         for(TreeNode ele:list){
             int val = map.get(ele);
             if(val==0&&root!=null){
                 return false;
             }else if(val==0 && root==null){
                 root=ele;
             }else if(val>1){
                 return false;
             }
         }
        
         preorderTree(root,map);
          
         return map.size()==0;
    }
    
    public static void preorderTree(TreeNode root,Map<TreeNode,Integer> map){
        
        if(root==null){
            return;
        }
        
        preorderTree(root.left,map);
        preorderTree(root.right,map);
        map.remove(root);
    }

- tiandiao123 October 26, 2017 | 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