Google Interview Question for Software Engineer / Developers


Country: United States




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

There are three properties that must be satisfied for the array to be a binary tree:
*For every node, the binary tree property must be satisfied (left must be <= val, right must be >= val)
*There must be one node with no parents (the root)
*Every other node must have one parent.

We determine this by filling a hash table with the number of times each node is referenced by another; aka, the number of parents it has.

#include <vector>
#include <unordered_map>

bool IsBTree(std::vector<node>& nodes)
{
   std::unordered_map<node*, int> counts;

   for (int i = 0; i < (int)nodes.size(); i++)
   {
      if ((nodes[i].pLeft->val > nodes[i].val) || (nodes[i].pRight->val < nodes[i].val))
         return false;
      counts[nodes[i].pLeft]++;
      counts[nodes[i].pRight]++;      
   }

   int parentless = 0, singleParent = 0;
   for (auto elt : counts)
   {
      parentless += elt.second == 0;
      singleParent += elt.second == 1;
   }
   return ((parentless == 1) && (singleParent == nodes.size()-1));
}

- tjcbs2 March 28, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
3
of 3 vote

Following are the properties of the binary tree
1) each node can have at max two children.
2) each node in the tree has only one path from the root node reaching to it.

For this questions, we also have to make sure it is only one tree, not a set of trees, so the answer would be yes only when all the input nodes can be formed as one tree satisfying above two properties

Now, we can have two solutions

First one has O(N) time complexity and O(1) space complexity but it makes updates in tree data.
Here is how it goes

public boolean canForm(TreeNode[] Node)
{
	int lowestval = 0;
	foreach(TreeNode node in Node)
	{
		if (lowestval > node.val)
		{
			lowestval = node.val;
		}
	}
	lowestval = lowestval - 100; // putting more lower value is not present in any of the nodes
	foreach(TreeNode node in Node)
	{
		if(node.left != null)
		{
			if(node.left.val != lowestval)
			{
				node.left.val = lowestval;
			}
			else
			{
				return false;
			}
		}
		if(node.right != null)
		{
			if(node.right.val != lowestval)
			{
				node.right.val = lowestval;
			}
			else
			{
				return false;
			}
		}
	}
	int rootnode = 0;
	foreach(TreeNode node in Node)
	{
		if (node.val != lowestval)
		{
			rootnode++;
		}
	}
	if(rootnode != 1)
	{
		return false;
	}
	return true;
}

The Second one has O(N) time complexity and O(N) space complexity where it does not updates in tree data.
Here is how it goes

public boolean canForm(TreeNode[] Node)
{
	HashSet<TreeNode> hashset = new HashSet<TreeNode>();

	foreach(TreeNode node in Node)
	{
		if(node.left != null)
		{
			if(hashset.Contains(node.left))
			{
				return false;
			}
			else
			{
				hashset.Add(node.left);
			}
		}
		if(node.right != null)
		{
			if(hashset.Contains(node.right))
			{
				return false;
			}
			else
			{
				hashset.Add(node.right);
			}
		}
	}
	int rootnode = 0;
	foreach(TreeNode node in Node)
	{
		if(!hashset.Contains(node))
		{
			rootnode++;
		}
	}
	if(rootnode != 1)
	{
		return false;
	}
	return true;
}

- sonesh March 28, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Criteria: each node has one parent except one node (which is root.)

We store the parent for each node in a hash. If the node appears more than once then it's not a binary tree.

At the end we check that the size of the hash is one less than the size of the input array.

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

def canForm(nodes):
    parents = dict() # child -> parent relationship, a child should appear at most once
    for node in nodes:
        if node.left is not None:
            if node.left in parents:
                return False
            parents[node.left] = node
            
        if node.right is not None:
            if node.right in parents:
                return False
            parents[node.right] = node
            
    return len(parents) == len(nodes) - 1

- gxg March 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I feel this question can be solved using Union Found

- tiandiao123 September 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Since based on this question's description, the author only lets us to confirm whether they can form a binary tree, so we only need to check whether it only has a single tree, so we can use Union Found algorithm to solve the question.

- tiandiao123 September 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What can be wrong with the nodes:
1. Several nodes have no parent.
2. The node is its own parent.
3. The node has left or right child that is not present in nodes.

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

using namespace std;

class Node
{
	public:
		Node(int val)
			: val_(val), left_(NULL), right_(NULL) {}
		int val_;
		Node *left_, *right_;
};

bool CanFormBinaryTree(const vector<Node*>& nodes)
{
	unordered_set<Node*> children;
	for (auto& n : nodes)
	{
		if (!n) {
			return false;
		}
		if (n->left_)
		{
			if (n->left_ == n ||
				children.find(n->left_) != children.end())
			{
				return false;
			}
			children.insert(n->left_);
		}
		if (n->right_)
		{
			if (n->right_ == n ||
				children.find(n->right_) != children.end())
			{
				return false;
			}
			children.insert(n->right_);
		}
	}

	// Each node is someone's child, except for the root
	if (children.size() != nodes.size() - 1)
	{
		return false;
	}

	// For cases when a child is a node that doesn't exist in nodes
	for (auto& n : nodes)
	{
		children.erase(n);
	}
	return children.empty();
}

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

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

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

@tjcbs2. It looks lie the question is not about binary search tree. If it was about BST, the property of BST is something like "for each node in the tree, any value of the left subtree nodes must be < than the node's value, and any value of the right subtree nodes must be >= than the node's value".

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

bool CanForm(TreeNode[] ns) {
	if(ns.Length == 0) return true;
	var rs = new HashSet<TreeNode>(ns);
	foreach(var n in ns) rs.Remove(n); // finding root elements
	if(rs.Count() != 1) return false; // Non empty tree must have only one root
	
	var n = rs[0];
	var vt = new HashSet<node>(); // set of visited nodes to find cycles
 	var rst = new List<int>();
	
	var hasCycle = InOrder(n, rst, vt);
	if(hasCycle || rst.Count() != ns.Length) return false;
	for(var i=0; i+1 < rst.Count(); i++){
		if(ns[i]>ns[i+1]) return false; 
	}
	return true;
}

bool InOrder(Node n, List<int> rst, HashSet<Node> vt){
	if(!vt.Add(n)) return true; // found a cycle
	if(n.left != null){
		if(InOrder(n.left, rst, vt)) return true;
	}

	rst.Add(n.val);

	if(n.right != null){
		if(InOrder(n.right, rst, vt)) return true;
	}
	return false;
}

- mvs.usp March 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Doesn't the question ask for checking only for binary tree(and not binary search tree)
Isn't it always possible to form a binary tree for list of such node

so answer can only be

Public boolean canForm(TreeNode[] nodes){ 
	return true;
}

- Mo April 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

isn't the code just asking to check a 'binary tree', not binary search tree.?

Public boolean canForm(TreeNode[] nodes){
return true;
}

- Mo April 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

isn't the code just asking to check a 'binary tree', not binary search tree.?

Public boolean canForm(TreeNode[] nodes){ 
	return true;
}

- Mo April 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

isn't the code just asking to check a 'binary tree', not binary search tree.?

Public boolean canForm(TreeNode[] nodes){ 
	return true;
}

- Mohit April 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

May be?

if(rst[i]>rst[i+1]) return false;

- dmitry.labutin March 27, 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