Google Interview Question for Software Engineers


Country: United States




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

Could you clarify please?
We need to find a vertex with both left and right subtrees being identical such that subtree size is maximum?
Or we need to to find the largest subtree that repeats two/three times?

- emb May 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

find the largest subtree that has atleast two other duplicate subtrees. So definitely not your second guess. Not the first either as the duplicate subtress may not necessarily be rooted at the left and right child (but can be a subtree of them as well)

- geekofthegeeks May 22, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I retract what I said. It will be your first guess.

- geekofthegeeks May 22, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Node resultNode;
  private void postOrder(Node root, StringBuffer result)
  {
      if(root!=null)
          {
          StringBuffer leftBuf = new StringBuffer();
          StringBuffer rightBuf = new StringBuffer();
          
          postOrder(root.left,leftBuf);
          postOrder(root.right,rightBuf);
          
          if(leftBuf.equals(rightBuf))
              {
              // we got it, continue to see if there is bigger result. it will be overwritten by higher level node. 
              resultNode = root;
          }
          result.append(leftBuf);
          result.append(rightBuf);
          
          result.append(root.val);
      }

}

- skumaringuva May 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Node resultNode;
  private void postOrder(Node root, StringBuffer result)
  {
      if(root!=null)
          {
          StringBuffer leftBuf = new StringBuffer();
          StringBuffer rightBuf = new StringBuffer();
          
          postOrder(root.left,leftBuf);
          postOrder(root.right,rightBuf);
          
          if(leftBuf.equals(rightBuf))
              {
              // we got it, continue to see if there is bigger result. it will be overwritten by higher level node. 
              resultNode = root;
          }
          result.append(leftBuf);
          result.append(rightBuf);
          
          result.append(root.val);
      }

}

- skumaringuva May 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In-Order traversal, compare subtree from left and right, when Max subtree size found return max. Repeat for each subtree and compare with global max found.

public static void main(String[] args) {
		
		/*
		 *      4
		 *     / \
		 *    2   2
		 *   / \  /\
		 *   1 3 1  3
		 */

		Node n2a = new Node(1, null, null);
		Node n2b = new Node(3, null, null);
		Node n2c = new Node(1, null, null);
		Node n2d = new Node(3, null, null);
		
		Node n1a = new Node(2, n2a, n2b);
		Node n1b = new Node(2, n2c, n2d);
		
		Node n0 = new Node(4, n1a, n1b);
		
		System.out.println(maxDuplicateSubtree(n0, new StringBuilder(), 0));		
                // output - 3
	}  

	public static int maxDuplicateSubtree(Node root, StringBuilder path, int maxSubtree) {
		if (root == null) {
			return 0;
		}
		StringBuilder leftPath = new StringBuilder();
        StringBuilder rightPath = new StringBuilder();
        int max = 0;
		int maxLeft = maxDuplicateSubtree(root.left, leftPath, maxSubtree);

		path.append(leftPath).append(root.v);
		
		int maxRight = maxDuplicateSubtree(root.right, rightPath, maxSubtree);
		max = Math.max(maxLeft, maxRight);
		
		path.append(rightPath);

		if (leftPath.toString().equals(rightPath.toString())) {
			max = Math.max(leftPath.length(), max);
		}		
		maxSubtree = Math.max(max, maxSubtree);
		
		return maxSubtree;
}

- guilhebl May 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Humm something like this came to mind first. This is pretty bad since its n^2, I also figured a linear time solution based on hashing but it might be a pain if we wanted to avoid hash collisions.

struct node {
	node * left;
	node * right;
	node() {
		left = nullptr;
		right = nullptr;
	}
};

string getDesc(node * n, map<string, int> & m, map<node*, int> & cnts, node ** best) {
	string ans;
	if (n->left != nullptr) {
		ans += "L" + getDesc(n->left);
	}
	if (n->right != nullptr) {
		ans += "R" + getDesc(n->right);
	}
	int cnt = 0;
	for (auto c : ans) {
		if (c == 'R' || c == 'L') {
			cnt++;
		}
	}
	cnts[n] = cnt;
	m[ans]++;
	if (best == nullptr || (cnts[*best] < cnt && m[ans] >= 2)) {
		*best = n;
	}
	ans += "B";
	return ans;
}

node * best;
best = nullptr;
map<string, int> m;
map<node*, int> cnts;

getDesc(root, m, cnts, &best);

- Anonymous May 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

There must be something wrong with the way the problem is stated or this is a trick problem. We are asked to find the largest subtree, a tree can be thought of is a subtree of itself. Hence if there are two duplicate subtrees of the input tree the function will return the tree itself otherwise it should return null.

If there are at least two leaf nodes that are identical we can be assured that there is at least two duplicate sub trees made out of just those two leaf nodes.

Hence the problem is reduced to finding two identical leaf nodes in the tree

import java.util.*;
static class Node
{
public int val;
public Node left,right;
}
public static boolean findDuplicateNodes(HashSet<Integer> vals,Node n)
{
	if(n==null)
		return false;
	if(vals.contains(n.val))
	{
		return true;
	}
	vals.add(n.val);
	if(findDuplicateNodes(vals,n.left))
		return true;
	if(findDuplicateNodes(vals,n.right))
		return true;
	return false;
}

- tmat May 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Note: not an answer, I'm asking again for clarification, but couldn't comment for some reason :(
So basically a smarter version of the following brute-force pseudocode is required?

def size(node): return 0 if node is None else 1 + size(node.left) + size(node.right)
def compare(a, b): return a is None and b is None or a is not None and b is not None and  compare(a.left, b.left) and compare(a.right, b.right)
def find_max(node):
    if node is None or compare(node.left, node.right):
        return size(node), node
    return max(find_max(node.left), find_max(node.right))

- emb May 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think this can be solved by representing the 2 trees as an array and solving the problem of the longest common subsequence.

- Cougler June 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Find the size of leftTree
2. Find the size of rightTree

if leftTree is < (half the size of right Tree)
then answer is in rightTree - return results from right tree
else
answer is in leftTree + node + rightTree

Same condition applies for rightTree < (half the nodes of leftTree)

- sample August 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It should be O(nlogn) solution if I calculate correctly.
isEqual method runs in O(n) because O(n) = 2O(n/2) + c
getMaxStubTree runs in O(nlogn) because O(n) = 2O(n/2) + O(n)

public class Solution {

    public static void main(String [] args) {

        Node node6 = new Node(6);
        Node node5 = new Node(5);
        Node node7 = new Node(7);
        Node node4a = new Node(4);
        Node node4b = new Node(4);
        Node node3a = new Node(3);
        Node node3b = new Node(3);
        Node node3c = new Node(3);
        Node node3d = new Node(3);
        Node node1a = new Node(1);
        Node node2a = new Node(2);
        Node node1b = new Node(1);
        Node node2b = new Node(2);

        node6.left = node5;
        node6.right = node7;
        node5.left = node4a;
        node5.right = node4b;
        node4a.left = node3a;
        node4a.right = node3b;
        node4b.left = node3c;
        node4b.right = node3d;
        node3a.left = node1a;
        node3a.right = node2a;
        node3b.left = node1b;
        node3b.right = node2b;

        System.out.println(isEqual(node3a, node3b));

        System.out.println(isEqual(node3c, node3d));

        System.out.println(isEqual(node5, node7));

        getMaxSubtree(node6).ifPresent(System.out::println);
    }

    public static Optional<Result> getMaxSubtree(Node node) {

        if (node == null) {
            return Optional.empty();
        }

        int isEqual = isEqual(node.left, node.right);

        if (isEqual >= 0) {
            return Optional.of(new Result(node, isEqual+1));
        }

        Optional<Result> leftOptional = getMaxSubtree(node.left);
        Optional<Result> rightOptional = getMaxSubtree(node.right);

        if (leftOptional.isPresent() && rightOptional.isPresent()) {
            return leftOptional.get().height > rightOptional.get().height ?
                    leftOptional : rightOptional;
        } else if (leftOptional.isPresent() && !rightOptional.isPresent()) {
            return leftOptional;
        } else if (!leftOptional.isPresent() && rightOptional.isPresent()) {
            return rightOptional;
        } else {
            return Optional.empty();
        }
    }

    /**
     * if node1 == node2 return the height of the tree
     * @param node1
     * @param node2
     * @return
     */
    public static int isEqual(Node node1, Node node2) {
        if (node1 == null && node2 == null) {
            return 0;
        }

        if (node1 == null && node2 != null) {
            return -1;
        }

        if (node2 == null && node1 != null) {
            return -1;
        }

        if (node1.value != node2.value) {
            return -1;
        }

        int left = isEqual(node1.left, node2.left);
        int right = isEqual(node1.right, node2.right);

        if (left >= 0 && right >= 0) {
            return Integer.max(left, right) + 1;
        } else {
            return -1;
        }
    }
}

class Result {
    Node node;
    int height;

    public Result(Node node, int height) {
        this.node = node;
        this.height = height;
    }

    @Override
    public String toString() {
        return "Result{" +
                "node=" + node.value +
                ", height=" + height +
                '}';
    }
}

class Node {

    final int value;
    Node left;
    Node right;

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

- ugurdonmez87 August 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Make a merkle tree out of it and do a BFS from the root of it looking for a node that has equal hashes for both of its children.

- sleepy October 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Took a stab: "Calculate the hash of each node's subtree. Store it in a hash table, key is <hash code of entire subtree> and value is List<<node, size of subtree that's has this node as the root>>.
In second phase, find from the hashtable, the node with the largest size subtree and where number of elements in the list > 2"

public class Node
    {
        public Node(int value)
        {
            this.Value = value;
        }

        public Node(int value, int left, int right)
        {
            this.Value = value;
            this.Left = new Node(left);
            this.Right = new Node(right);
        }

        public Node(int value, Node left, Node right)
        {
            this.Value = value;
            this.Left = left;
            this.Right = right;
        }

        public int Value { get; set; }
        public Node Left { get; set; }
        public Node Right { get; set; }

        public override string ToString()
        {
            return string.Format("Value: [{0}] \n, Left: [{1}], Right: [{2}]", this.Value, this.Left, this.Right);
        }

        public static Node FindLargestSubTreeWithDuplicate(Node node)
        {
            if (null == node)
            {
                return null;
            }

            IDictionary<int, IList<NodeWithSize>> hash = new Dictionary<int, IList<NodeWithSize>>();
            int nodeCount = 0;
            PopulateHash(hash, node, out nodeCount);
            return FindLargestDuplicate(hash);
        }

        private static Node FindLargestDuplicate(IDictionary<int, IList<NodeWithSize>> hash)
        {
            int maxSubTreeSize = 0;
            Node result = null;
            foreach (IList<NodeWithSize> matchingSubTrees in hash.Values)
            {
                if (matchingSubTrees == null || matchingSubTrees.Count <= 1)
                {
                    continue;
                }

                // find the one with max height
                foreach (NodeWithSize node in matchingSubTrees)
                {
                    if (node.CountSubtree > maxSubTreeSize)
                    {
                        maxSubTreeSize = node.CountSubtree;
                        result = node.Node;
                    }
                }
            }

            return result;
        }

        private static int PopulateHash(IDictionary<int, IList<NodeWithSize>> hash, Node node, out int nodeCount)
        {
            if (null == node)
            {
                nodeCount = 0;
                return 0;
            }

            int leftCount;
            int rightCount;
            int hashValue = PopulateHash(hash, node.Left, out leftCount) + node.Value.GetHashCode() + PopulateHash(hash, node.Right, out rightCount);
            nodeCount = leftCount + 1 + rightCount;
            NodeWithSize nodeWithSize = new NodeWithSize { Node = node, CountSubtree = nodeCount };
            if (hash.ContainsKey(hashValue))
            {
                hash[hashValue].Add(nodeWithSize);
            }
            else
            {
                hash.Add(hashValue, new List<NodeWithSize>() { nodeWithSize });
            }

            return hashValue;
        }

        private class NodeWithSize
        {
            public Node Node { get; set; }
            public int CountSubtree { get; set; }

            public override string ToString()
            {
                return string.Format(
                    "Size = {3} && Value: [{0}] \n, Left: [{1}], Right: [{2}]", this.Node.Value, this.Node.Left, this.Node.Right, this.CountSubtree);
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Node treeWithDupes = Program.BuildTreeWithDuplicateSubTree();
            Node largestDupe = Node.FindLargestSubTreeWithDuplicate(treeWithDupes);
            Console.WriteLine(largestDupe.ToString());
	}
}

- Ppratap April 30, 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