Google Interview Question
Software EngineersCountry: United States
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?
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)
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);
}
}
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);
}
}
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;
}
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);
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))
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;
}
}
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());
}
}
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
- tmat May 23, 2016