## Google Interview Question for Software Engineers

Country: United States

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

the solution is to perform in-order traversal, and obtain 2 sequences:
seq of nodes and seq of levels.
Then find duplicate sub sequences while comparing the corresponding sub sequences of levels and additionally checking the proper begin and end of sub sequence (explained in examples 3 and 4).
If we find a pair: 2 identical subseqs of nodes and 2 identical subseqs of levels then the answer is true (i.e. tree has sub trees).

Example 1:
D
| \
B B
| \ \ \
A C A C
In-order traversal result:
ABCDABC
212 0 212
We have 2 identical pairs: {ABC, 212} and {ABC, 212}, so the tree has duplicate sub trees.

Example 2:
A
| \
B C
| \ \ \
A C B D
In-order traversal result:
ABCABCD
212 021 2
Though we have 2 duplicate nodes subseqs: ABC and ABC, but the corresponding levels subseqs are not identical: 212 and 021. So there are no duplicate sub trees in the tree.

Example 3:
D
| \
B B
| \ \
A C A
In-order traversal result:
ABCDAB
212 0 21
We have 2 identical pairs: {AB, 21} and {AB, 21}, but additional check fails. First AB is not a valid subseq because the next level after 21 is 2, this means that the sub tree has one more node ('cause 2 > 1), that is why the first pair should be {ABC, 212}.
So, {ABC, 212} and {AB, 21} are not identical, so again there are no duplicate sub trees in the tree.

Example 4:
D
| \
B B
\ \ \
C A C
In-order traversal result:
BCDABC
12 0 212
We have 2 identical pairs: {BC, 12} and {BC, 12}, but additional check fails. Second BC is not a valid subseq because the prev level before 1 is 2, this means that the sub tree has one more node ('cause 2 > 1), that is why the second pair should be {ABC, 212}.
So, {BC, 12} and {ABC, 212} are not identical, so again there are no duplicate sub trees in the tree.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

I don't believe the assumptions you make about levels are valid. In the following example, your solution will fail:

M
/ \
A A
|\ |\
E F E G
| |
B B
|\ |\
C D C D

inorder: E A C B D F M E A C B D G
levels: 3 2 5 4 5 3 1 3 2 5 4 5 3

Pair: {ACBD, 2545}

According to your algorithm, this would return true... however, ACBD is not a subtree.

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

sorry, but your in-order traversal is wrong. Depending on direction of edges it should start either ECBDA... or CBDEA...
Also, from your picture it is obvious that the end of in-order traversal must be ...MEAG.
But you wrote something different.
So, I can say nothing definite about your conclusion, 'cause it is based on wrong idea.
Can you specify the tree more accurately, in such notation:
M( A ( E ( <left>, <right> ), F ( <left>, <right> ) ), A ( E, G ) )

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

sorry, looks like you are totally wrong.
I examined all the possible trees, which can be made up from your picture.
They are (in-order traversals):
1) ECBDACBDFMEAG
2) ECBDAFCBDMEAG
3) CBDEACBDFMEAG
4) CBDEAFCBDMEAG
My solution works greatly on all these variants. The answer is true, because the result pair is {CBD, 434}.

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

@zr.roman, what will be the answer for

B
/ \
A C
/ \ / \
C D E F
/ \
E F

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

thanks, this is a great observation.
really, my solution does not handle this situation.
A small improvement is needed: when we receive 2 identical nodes sequence, then we must check if the respective levels sequence can be reduced one to another via iterative subtracting 1 from each digit of a respective seq.
Example:
{ABC, 212} and {ABC, 021} - the answer is no, because we cannot reduce 212 to 021 (and vice versa).
{ECF, 323} and {ECF, 212} - the answer is yes (the tree has duplicate sub trees), because we can reduce 323 to 212 via iterative subtracting 1 from each digit in first number (323). So, here we need 1 iteration.
Thanks again, you helped to improve the solution.

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

How do you find common substring(longest may be) in single string. In your example1 inorder is ABCDABC.
What algorithm to use to find, substring in same same string. I am aware of DP solution for different strings.

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

this can be done using hashtable. There may be variations in implementation, but general idea is as follows:
let's have ABCDABC in-order traversal result.
So, we start from position 0 and put all letters one by one into hashtable:
1) {'A', 0}
2) {'B', 1}
3) {'C', 2}
4) {'D', 3}
Then when we'll try to put {'A', 4}, we'll get an exception. This is the signal that we found duplication. So, starting from positions 0 and 4 we obtain duplicate parts and do all the necessary checks (described in solution). If the checks are passed we are done. Otherwise we proceed putting into hashtable remaining characters.
Certainly, this is much faster than O(n^2), but maybe a little slower than O(n). Actually, this is order O(n) or at most O(n logn).

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

to find two identical substrings of a string one can build a suffix tree.

If zr.roman elaborated his solution with hashtable it would be nice.

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

This algo works with the correction in one of the comments.
If the question is to find if there are such subtrees of a given length L (yes/no) or just if there are subtrees (which is equivalent to subtrees of a given length 2) , it's possible to implement this in O(N). If the question is to find all such subtrees (any possibl length), it becomes O(N^3).

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

If two subtrees of length h are equal then two subtrees of length h-1 are also equal.

So just need to check if there exists duplicate edges using hash function. Problem stmt is not clear but whatever is stmt is given I can write mentioned solution.

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

``````public void checkIfDupSubTrees(ArrayList<TreeNode> dump, ArrayList<TreeNode> ans)
{
for(int i=0; i<dump.size()-1; i++)
{
for (int j=i+1; j<dump.size(); j++)
{
TreeNode check = checkEqualTrees(dump.get(i), dump.get(j));
if (check!=null && (check.getLeft()!=null || check.getRight()!=null))
}
}
ArrayList<TreeNode> newDump = new ArrayList<TreeNode>();
for(int i=0; i<dump.size(); i++)
{
TreeNode left = dump.get(i).getLeft();
TreeNode right = dump.get(i).getRight();
if (left!=null)
if (right!=null)
}
if (newDump.size()>=1)
checkIfDupSubTrees(newDump, ans);
}
private TreeNode checkEqualTrees(TreeNode one, TreeNode two)
{
if (one.getVal()!=two.getVal())
return null;
else
{
TreeNode ans = new TreeNode(one.getVal());
if (one.getLeft()!=null && two.getLeft()!=null)
ans.setLeft(checkEqualTrees(one.getLeft(), two.getLeft()));
else
ans.setLeft(null);
if (one.getRight()!=null && two.getRight()!=null)
ans.setLeft(checkEqualTrees(one.getRight(), two.getRight()));
else
ans.setRight(null);
return ans;
}
}

public void checkIfDupSubTrees()
{
TreeNode root = new TreeNode(3);
TreeNode one = new TreeNode(6);
TreeNode two = new TreeNode(8);
TreeNode three = new TreeNode(5);
TreeNode four = new TreeNode(5);
TreeNode five = new TreeNode(4);
TreeNode six = new TreeNode(20);
TreeNode seven = new TreeNode(20);
TreeNode eight = new TreeNode(2);
TreeNode nine = new TreeNode(25);
TreeNode ten = new TreeNode(4);
TreeNode eleven = new TreeNode(2);
TreeNode twelve = new TreeNode(9);
TreeNode thirteen = new TreeNode(11);

root.setLeft(one);
root.setRight(two);
one.setLeft(three);
two.setRight(four);
three.setLeft(five);
three.setRight(six);
five.setLeft(seven);
five.setRight(eight);
seven.setRight(nine);
four.setLeft(ten);
ten.setLeft(twelve);
ten.setRight(eleven);
twelve.setRight(thirteen);

ArrayList<TreeNode> dump = new ArrayList<TreeNode>();
ArrayList<TreeNode> ans = new ArrayList<TreeNode>();
checkIfDupSubTrees(dump, ans);
System.out.println("CheckIfDupSubTrees===========================");
System.out.println("Root Tree===========================");
printTree(root);
System.out.println("===========================");
for(int i=0; i<ans.size();i++)
{
System.out.println("DupSubTrees===========================");
printTree(ans.get(i));
System.out.println("===========================");
}
}

public void printTree(TreeNode t)
{
System.out.print(t.getVal());
if (t.getLeft()!=null)
System.out.print("-->Left-"+t.getLeft().getVal());
if (t.getRight()!=null)
System.out.print("-->Right-"+t.getRight().getVal());
System.out.println();
if (t.getLeft()!=null)
printTree(t.getLeft());
if (t.getRight()!=null)
printTree(t.getRight());
}``````

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

So, is it O(n^3) of what? Anyway would be nice to have very succinct description of the algorithm.

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

a single node could be considered as a sub tree (connected with no circles), therefor, it could be achieved in O(n) :

``````traverse the tree (in-order, post-order..doesn't really matter):
- add current node to hash_table:
- if node of the same value was already inserted: return that there is a duplicate

(after traverse is finished) return there's no duplicates``````

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

Here we need to have hashCode implemented for the Node, which in worse case scenario needs to go through every node (for the tree root), which is O(n), hence final complexity would be O(n^2)

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

Mistake

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

What about finding sequences of 3 nodes (head, left, right) as duplicates in the tree? Would have a lognlogn complexity.

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

``````public void checkIfDupSubTrees(ArrayList<TreeNode> dump, ArrayList<TreeNode> ans)
{
for(int i=0; i<dump.size()-1; i++)
{
for (int j=i+1; j<dump.size(); j++)
{
TreeNode check = checkEqualTrees(dump.get(i), dump.get(j));
if (check!=null && (check.getLeft()!=null || check.getRight()!=null))
}
}
ArrayList<TreeNode> newDump = new ArrayList<TreeNode>();
for(int i=0; i<dump.size(); i++)
{
TreeNode left = dump.get(i).getLeft();
TreeNode right = dump.get(i).getRight();
if (left!=null)
if (right!=null)
}
if (newDump.size()>=1)
checkIfDupSubTrees(newDump, ans);
}
private TreeNode checkEqualTrees(TreeNode one, TreeNode two)
{
if (one.getVal()!=two.getVal())
return null;
else
{
TreeNode ans = new TreeNode(one.getVal());
if (one.getLeft()!=null && two.getLeft()!=null)
ans.setLeft(checkEqualTrees(one.getLeft(), two.getLeft()));
else
ans.setLeft(null);
if (one.getRight()!=null && two.getRight()!=null)
ans.setLeft(checkEqualTrees(one.getRight(), two.getRight()));
else
ans.setRight(null);
return ans;
}
}

public void checkIfDupSubTrees()
{
TreeNode root = new TreeNode(3);
TreeNode one = new TreeNode(6);
TreeNode two = new TreeNode(8);
TreeNode three = new TreeNode(5);
TreeNode four = new TreeNode(5);
TreeNode five = new TreeNode(4);
TreeNode six = new TreeNode(20);
TreeNode seven = new TreeNode(20);
TreeNode eight = new TreeNode(2);
TreeNode nine = new TreeNode(25);
TreeNode ten = new TreeNode(4);
TreeNode eleven = new TreeNode(2);
TreeNode twelve = new TreeNode(9);
TreeNode thirteen = new TreeNode(11);

root.setLeft(one);
root.setRight(two);
one.setLeft(three);
two.setRight(four);
three.setLeft(five);
three.setRight(six);
five.setLeft(seven);
five.setRight(eight);
seven.setRight(nine);
four.setLeft(ten);
ten.setLeft(twelve);
ten.setRight(eleven);
twelve.setRight(thirteen);

ArrayList<TreeNode> dump = new ArrayList<TreeNode>();
ArrayList<TreeNode> ans = new ArrayList<TreeNode>();
checkIfDupSubTrees(dump, ans);
System.out.println("CheckIfDupSubTrees===========================");
System.out.println("Root Tree===========================");
printTree(root);
System.out.println("===========================");
for(int i=0; i<ans.size();i++)
{
System.out.println("DupSubTrees===========================");
printTree(ans.get(i));
System.out.println("===========================");
}
}

public void printTree(TreeNode t)
{
System.out.print(t.getVal());
if (t.getLeft()!=null)
System.out.print("-->Left-"+t.getLeft().getVal());
if (t.getRight()!=null)
System.out.print("-->Right-"+t.getRight().getVal());
System.out.println();
if (t.getLeft()!=null)
printTree(t.getLeft());
if (t.getRight()!=null)
printTree(t.getRight());
}``````

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

Given T, find:

1. Let array A be the in-order traversal of T.left
2. Let array B be the in-order traversal of T.right

Both A and B can be produced in one pass - make sure to add a marker for whenever you see a null on one side but not the other - this guarantees A and B will have the same size, which will come in handy in further steps.

3. Let array C be the pre-order traversal of T.left
4. Let array D be the pre-order traversal of T.right

Likewise, both C and D can be produced in one pass - make sure to add a marker for whenever you see a null on one side but not the other - this guarantees C and D will have the same size.

5. Check if A has a sequence which is also in B (since A and B are the same size, this can be done in O(n) )

6. Check if C has a sequence which is also in D (since C and D are the same size, this can be done in O(n) )

7. If both 5 and 6 are true, continue, otherwise we can return false

8. If the sequences found in 5 and 6 are a permutation of each other (can be done in O(n)), then return true.

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

The duplicate sub-trees can occur along the same arm of the tree. I mean, in T.left, there's a possibility that you may find 2 duplicate subtrees. Similarly, in T.right itself, there may be duplicate sub trees.

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

How would you solve #6 in o(n) ?
"6. Check if A has a sequence which is also in B (since A and B are the same size, this can be done in O(n) )"

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

1. Add a data field with childcount which helps in visible bit and subtree rule scheme.
2. perform post order traversal ,
3. If we encountered a node , whose value is defined and also defined as subtree ( i.e >=3) , terminate and declare it as solution.
4. Set current node child count as 1+ left + right child count.

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

a single node could be considered as a sub-tree(connected and non-cyclic graph)
O(n) one traverse, use a hash table to insert the nodes to, and check if the current node was previously added, if so then return true. after the traverse finish, means there's no duplicates

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

1.Prepare hashmap of node value and list of tree node (Map<String,List<TreeNode>>) while doing pre-order traversal
2.Get List<TreeNode> from map where List size is greater then 2
3.call recursive tree match method on the TreeNodes from the list.

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

``````private boolean duplicateFound = false;
private List<Node> subTreeRoots = new ArrayList<TreeBuilder.Node>();

private void traverseTree(Node node) {
if (!duplicateFound) {
if (node != null) {
//is a parent
if (node.left != null || node.right != null) {
for (Node compareNode : subTreeRoots) {
//before comparison, we could add a check to see if compareNode is it's parent, then don't compare.
duplicateFound = isIdentical(compareNode, node);
if (duplicateFound) {
System.out.println("Dup1 is " + node + " Dup2 is " + compareNode);
break;
}
}
}
traverseTree(node.left);
traverseTree(node.right);
}
}
}

private boolean isIdentical(TreeBuilder.Node node1, TreeBuilder.Node node2) {
if (node1 == null && node2 == null) {
return true;
}

if (node1 == null || node2 == null) {
return false;
}

return node1.id.equals(node2.id)
&& isIdentical(node1.left, node2.left)
&& isIdentical(node1.right, node2.right);
}``````

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

``````public class Node
{
int value;
Node left;
Node right;
}

public boolean hasDupSubtrees(Node n)
{
if(n==null||(n.left==null && n.right==null))
{
return false;
}
ArrayList<Integer> ls=new ArrayList<Integer>();
return checkSubtrees(n,ls,0);
}

private boolean checkSubtrees(Node n, ArrayList<Integer> ls, int start)
{
if(n==null)
{
return false;
}
boolean left=checkSubtrees(n.left,ls,start);
boolean right=true;
if(!left)
{
int leftTreeSize=ls.size()-start;
right=checkSubtrees(n.right,ls,start+leftTreeSize);
}
if(!right)
{
int rightTreeSize=ls.size()-leftTreeSize;
if(rightTreeSize==leftTreeSize && leftTreeSize>1)
{
right=checkNodeValues(ls,start,leftTreeSize);
}
}
return (left||right);
}
private boolean checkNodeValues(ArrayList<Integer> ls, int start, int treeSize)
{
int leftIdx=start;
int leftEnd=start+treeSize;
int rightIdx=leftEnd;
while(leftIdx<leftEnd)
{
if(!ls.get(leftIdx).equals(ls.get(rightIdx)))
{
return false;
}
}
return true;
}

//Time: O(nlogn) Space: O(n) where n is the number of nodes in the tree.``````

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

``````**Forgot just 2 lines see below:

private boolean checkNodeValues(ArrayList<Integer> ls, int start, int treeSize)
{
int leftIdx=start;
int leftEnd=start+treeSize;
int rightIdx=leftEnd;
while(leftIdx<leftEnd)
{
if(!ls.get(leftIdx).equals(ls.get(rightIdx)))
{
return false;
}
leftIdx++;//Missing line 1
rightIdx++//Missing line 2
}
return true;
}``````

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

Crafted a dynamic solution and it avoids all the problem shown in the approach of in-order solution because it is to compare the tree exactly match. Details: cpluspluslearning-petert.blogspot.co.uk/2016/01/dynamic-programming-find-if-given-tree.html

Test

``````void TestFindDuplicateSubTree()
{
{
TreeNode<int>* root = nullptr;
TreeNode<int>* entry1;
TreeNode<int>* entry2;
assert(HaveDuplicateSubTree_R(root, entry1, entry2) == false);
}

{
const std::vector<int> testInput = { 1, 2 };
auto root = ConstructTreeRecursive(testInput);
assert(root != nullptr);
assert(GetTreeSize_R(root) == testInput.size());
TreeNode<int>* entry1;
TreeNode<int>* entry2;
assert(HaveDuplicateSubTree_R(root, entry1, entry2) == false);
DeleteTree(&root);
}

{
const std::vector<int> testInput = { 1, 2, 3 };
auto root = ConstructTreeRecursive(testInput);
assert(root != nullptr);
assert(GetTreeSize_R(root) == testInput.size());
TreeNode<int>* entry1;
TreeNode<int>* entry2;
assert(HaveDuplicateSubTree_R(root, entry1, entry2) == false);
DeleteTree(&root);
}

{
const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
auto root = ConstructTreeRecursive(testInput);
assert(root != nullptr);
assert(GetTreeSize_R(root) == testInput.size());
TreeNode<int>* entry1;
TreeNode<int>* entry2;
assert(HaveDuplicateSubTree_R(root, entry1, entry2) == false);
DeleteTree(&root);
}

{
const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
auto root = ConstructTreeRecursive(testInput);
assert(root != nullptr);
assert(GetTreeSize_R(root) == testInput.size());
TreeNode<int>* entry1;
TreeNode<int>* entry2;
assert(HaveDuplicateSubTree_R(root, entry1, entry2) == false);

const std::vector<int> subTreeInput = { 100, 101 };
auto subTree1 = ConstructTreeRecursive(subTreeInput);
auto subTree2 = ConstructTreeRecursive(subTreeInput);
assert(GetTreeSize_R(subTree1) == subTreeInput.size());
assert(GetTreeSize_R(subTree2) == subTreeInput.size());
assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

auto leftestNode = FindLeftestNode(root);
auto rightestNode = FindRightestNode(root);
assert(leftestNode != nullptr);
assert(leftestNode->left == nullptr);
assert(rightestNode != nullptr);
assert(rightestNode->right == nullptr);
assert(*leftestNode->data == 1);
assert(*rightestNode->data == 10);

leftestNode->left = subTree1;
rightestNode->right = subTree2;
assert(HaveDuplicateSubTree_R(root, entry1, entry2) == false);

DeleteTree(&root);
}

{
const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
auto root = ConstructTreeRecursive(testInput);
assert(root != nullptr);
assert(GetTreeSize_R(root) == testInput.size());
TreeNode<int>* entry1;
TreeNode<int>* entry2;
assert(HaveDuplicateSubTree_R(root, entry1, entry2) == false);

const std::vector<int> subTreeInput = { 100, 101, 102 };
auto subTree1 = ConstructTreeRecursive(subTreeInput);
auto subTree2 = ConstructTreeRecursive(subTreeInput);
assert(GetTreeSize_R(subTree1) == subTreeInput.size());
assert(GetTreeSize_R(subTree2) == subTreeInput.size());
assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

auto leftestNode = FindLeftestNode(root);
auto rightestNode = FindRightestNode(root);
assert(leftestNode != nullptr);
assert(leftestNode->left == nullptr);
assert(rightestNode != nullptr);
assert(rightestNode->right == nullptr);
assert(*leftestNode->data == 1);
assert(*rightestNode->data == 10);

leftestNode->left = subTree1;
rightestNode->right = subTree2;
assert(HaveDuplicateSubTree_R(root, entry1, entry2) == true);
assert(entry1 != nullptr);
assert(entry2 != nullptr);
assert(CheckTwoTreesWithSameValues(entry1, subTree1));
assert(CheckTwoTreesWithSameValues(entry2, subTree2));
assert(CheckTwoTreesWithSameValues(entry1, entry2));

DeleteTree(&root);
}

{
const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
auto root = ConstructTreeRecursive(testInput);
assert(root != nullptr);
assert(GetTreeSize_R(root) == testInput.size());
TreeNode<int>* entry1;
TreeNode<int>* entry2;
assert(HaveDuplicateSubTree_R(root, entry1, entry2) == false);

const std::vector<int> subTreeInput = { 100, 101, 102 };
auto subTree1 = ConstructTreeRecursive(subTreeInput);
auto subTree2 = ConstructTreeRecursive(subTreeInput);
assert(GetTreeSize_R(subTree1) == subTreeInput.size());
assert(GetTreeSize_R(subTree2) == subTreeInput.size());
assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

auto leftestNode = FindLeftestNode(root->left);
auto rightestNode = FindRightestNode(root->left);
assert(leftestNode != nullptr);
assert(leftestNode->left == nullptr);
assert(rightestNode != nullptr);
assert(rightestNode->right == nullptr);
assert(*leftestNode->data == 1);
assert(*rightestNode->data == 4);

leftestNode->left = subTree1;
rightestNode->right = subTree2;
assert(HaveDuplicateSubTree_R(root, entry1, entry2) == true);
assert(entry1 != nullptr);
assert(entry2 != nullptr);
assert(CheckTwoTreesWithSameValues(entry1, subTree1));
assert(CheckTwoTreesWithSameValues(entry2, subTree2));
assert(CheckTwoTreesWithSameValues(entry1, entry2));

DeleteTree(&root);
}

{
const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
auto root = ConstructTreeRecursive(testInput);
assert(root != nullptr);
assert(GetTreeSize_R(root) == testInput.size());
TreeNode<int>* entry1;
TreeNode<int>* entry2;
assert(HaveDuplicateSubTree_R(root, entry1, entry2) == false);

const std::vector<int> subTreeInput = { 100, 101, 102 };
auto subTree1 = ConstructTreeRecursive(subTreeInput);
auto subTree2 = ConstructTreeRecursive(subTreeInput);
assert(GetTreeSize_R(subTree1) == subTreeInput.size());
assert(GetTreeSize_R(subTree2) == subTreeInput.size());
assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

auto leftestNode = FindLeftestNode(root->right);
auto rightestNode = FindRightestNode(root->right);
assert(leftestNode != nullptr);
assert(leftestNode->left == nullptr);
assert(rightestNode != nullptr);
assert(rightestNode->right == nullptr);
assert(*leftestNode->data == 6);
assert(*rightestNode->data == 10);

leftestNode->left = subTree1;
rightestNode->right = subTree2;
assert(HaveDuplicateSubTree_R(root, entry1, entry2) == true);
assert(entry1 != nullptr);
assert(entry2 != nullptr);
assert(CheckTwoTreesWithSameValues(entry1, subTree1));
assert(CheckTwoTreesWithSameValues(entry2, subTree2));
assert(CheckTwoTreesWithSameValues(entry1, entry2));

DeleteTree(&root);
}
}``````

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

Crafted a linear solution (to size of tree). The idea is to calculate hash for each node that includes all the information of its sub-tree. Then compare those nodes with same hash code. Details: cpluspluslearning-petert.blogspot.co.uk/2016/01/dynamic-programming-find-if-given-tree_69.html

Test

``````void TestFindDuplicateSubTree2()
{
{
TreeNode<int>* root = nullptr;
TreeNode<int>* entry1;
TreeNode<int>* entry2;
assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);
}

{
const std::vector<int> testInput = { 1, 2 };
auto root = ConstructTreeRecursive(testInput);
assert(root != nullptr);
assert(GetTreeSize_R(root) == testInput.size());
TreeNode<int>* entry1;
TreeNode<int>* entry2;
assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);
DeleteTree(&root);
}

{
const std::vector<int> testInput = { 1, 2, 3 };
auto root = ConstructTreeRecursive(testInput);
assert(root != nullptr);
assert(GetTreeSize_R(root) == testInput.size());
TreeNode<int>* entry1;
TreeNode<int>* entry2;
assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);
DeleteTree(&root);
}

{
const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
auto root = ConstructTreeRecursive(testInput);
assert(root != nullptr);
assert(GetTreeSize_R(root) == testInput.size());
TreeNode<int>* entry1;
TreeNode<int>* entry2;
assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);
DeleteTree(&root);
}

{
const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
auto root = ConstructTreeRecursive(testInput);
assert(root != nullptr);
assert(GetTreeSize_R(root) == testInput.size());
TreeNode<int>* entry1;
TreeNode<int>* entry2;
assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);

const std::vector<int> subTreeInput = { 100, 101 };
auto subTree1 = ConstructTreeRecursive(subTreeInput);
auto subTree2 = ConstructTreeRecursive(subTreeInput);
assert(GetTreeSize_R(subTree1) == subTreeInput.size());
assert(GetTreeSize_R(subTree2) == subTreeInput.size());
assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

auto leftestNode = FindLeftestNode(root);
auto rightestNode = FindRightestNode(root);
assert(leftestNode != nullptr);
assert(leftestNode->left == nullptr);
assert(rightestNode != nullptr);
assert(rightestNode->right == nullptr);
assert(*leftestNode->data == 1);
assert(*rightestNode->data == 10);

leftestNode->left = subTree1;
rightestNode->right = subTree2;
assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);

DeleteTree(&root);
}

{
const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
auto root = ConstructTreeRecursive(testInput);
assert(root != nullptr);
assert(GetTreeSize_R(root) == testInput.size());
TreeNode<int>* entry1;
TreeNode<int>* entry2;
assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);

const std::vector<int> subTreeInput = { 100, 101, 102 };
auto subTree1 = ConstructTreeRecursive(subTreeInput);
auto subTree2 = ConstructTreeRecursive(subTreeInput);
assert(GetTreeSize_R(subTree1) == subTreeInput.size());
assert(GetTreeSize_R(subTree2) == subTreeInput.size());
assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

auto leftestNode = FindLeftestNode(root);
auto rightestNode = FindRightestNode(root);
assert(leftestNode != nullptr);
assert(leftestNode->left == nullptr);
assert(rightestNode != nullptr);
assert(rightestNode->right == nullptr);
assert(*leftestNode->data == 1);
assert(*rightestNode->data == 10);

leftestNode->left = subTree1;
rightestNode->right = subTree2;
assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == true);
assert(entry1 != nullptr);
assert(entry2 != nullptr);
assert(CheckTwoTreesWithSameValues(entry1, subTree1));
assert(CheckTwoTreesWithSameValues(entry2, subTree2));
assert(CheckTwoTreesWithSameValues(entry1, entry2));

DeleteTree(&root);
}

{
const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
auto root = ConstructTreeRecursive(testInput);
assert(root != nullptr);
assert(GetTreeSize_R(root) == testInput.size());
TreeNode<int>* entry1;
TreeNode<int>* entry2;
assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);

const std::vector<int> subTreeInput = { 100, 101, 102 };
auto subTree1 = ConstructTreeRecursive(subTreeInput);
auto subTree2 = ConstructTreeRecursive(subTreeInput);
assert(GetTreeSize_R(subTree1) == subTreeInput.size());
assert(GetTreeSize_R(subTree2) == subTreeInput.size());
assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

auto leftestNode = FindLeftestNode(root->left);
auto rightestNode = FindRightestNode(root->left);
assert(leftestNode != nullptr);
assert(leftestNode->left == nullptr);
assert(rightestNode != nullptr);
assert(rightestNode->right == nullptr);
assert(*leftestNode->data == 1);
assert(*rightestNode->data == 4);

leftestNode->left = subTree1;
rightestNode->right = subTree2;
assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == true);
assert(entry1 != nullptr);
assert(entry2 != nullptr);
assert(CheckTwoTreesWithSameValues(entry1, subTree1));
assert(CheckTwoTreesWithSameValues(entry2, subTree2));
assert(CheckTwoTreesWithSameValues(entry1, entry2));

DeleteTree(&root);
}

{
const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
auto root = ConstructTreeRecursive(testInput);
assert(root != nullptr);
assert(GetTreeSize_R(root) == testInput.size());
TreeNode<int>* entry1;
TreeNode<int>* entry2;
assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);

const std::vector<int> subTreeInput = { 100, 101, 102 };
auto subTree1 = ConstructTreeRecursive(subTreeInput);
auto subTree2 = ConstructTreeRecursive(subTreeInput);
assert(GetTreeSize_R(subTree1) == subTreeInput.size());
assert(GetTreeSize_R(subTree2) == subTreeInput.size());
assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

auto leftestNode = FindLeftestNode(root->right);
auto rightestNode = FindRightestNode(root->right);
assert(leftestNode != nullptr);
assert(leftestNode->left == nullptr);
assert(rightestNode != nullptr);
assert(rightestNode->right == nullptr);
assert(*leftestNode->data == 6);
assert(*rightestNode->data == 10);

leftestNode->left = subTree1;
rightestNode->right = subTree2;
assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == true);
assert(entry1 != nullptr);
assert(entry2 != nullptr);
assert(CheckTwoTreesWithSameValues(entry1, subTree1));
assert(CheckTwoTreesWithSameValues(entry2, subTree2));
assert(CheckTwoTreesWithSameValues(entry1, entry2));

DeleteTree(&root);
}

{
const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
auto root = ConstructTreeRecursive(testInput);
assert(root != nullptr);
assert(GetTreeSize_R(root) == testInput.size());
TreeNode<int>* entry1 = nullptr;
TreeNode<int>* entry2 = nullptr;
assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);

const std::vector<int> subTreeInput1 = { 100, 101, 102 };
const std::vector<int> subTreeInput2 = { 102, 101, 100 };
auto subTree1 = ConstructTreeRecursive(subTreeInput1);
auto subTree2 = ConstructTreeRecursive(subTreeInput2);
assert(GetTreeSize_R(subTree1) == subTreeInput1.size());
assert(GetTreeSize_R(subTree2) == subTreeInput2.size());
assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

auto leftestNode = FindLeftestNode(root->right);
auto rightestNode = FindRightestNode(root->right);
assert(leftestNode != nullptr);
assert(leftestNode->left == nullptr);
assert(rightestNode != nullptr);
assert(rightestNode->right == nullptr);
assert(*leftestNode->data == 6);
assert(*rightestNode->data == 10);

leftestNode->left = subTree1;
rightestNode->right = subTree2;
assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);
assert(entry1 == nullptr);
assert(entry2 == nullptr);

DeleteTree(&root);
}

{
const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
auto root = ConstructTreeRecursive(testInput);
assert(root != nullptr);
assert(GetTreeSize_R(root) == testInput.size());
TreeNode<int>* entry1 = nullptr;
TreeNode<int>* entry2 = nullptr;
assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);

TreeNode<int>* subTree1 = new TreeNode<int>(1000);
subTree1->left = new TreeNode<int>(1001);
subTree1->left->left = new TreeNode<int>(1002);
TreeNode<int>* subTree2 = new TreeNode<int>(1000);
subTree2->right = new TreeNode<int>(1001);
subTree2->right->right = new TreeNode<int>(1002);
assert(GetTreeSize_R(subTree1) == 3);
assert(GetTreeSize_R(subTree2) == 3);
assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

auto leftestNode = FindLeftestNode(root->right);
auto rightestNode = FindRightestNode(root->right);
assert(leftestNode != nullptr);
assert(leftestNode->left == nullptr);
assert(rightestNode != nullptr);
assert(rightestNode->right == nullptr);
assert(*leftestNode->data == 6);
assert(*rightestNode->data == 10);

leftestNode->left = subTree1;
rightestNode->right = subTree2;
assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);
assert(entry1 == nullptr);
assert(entry2 == nullptr);

DeleteTree(&root);
}
{
const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
auto root = ConstructTreeRecursive(testInput);
assert(root != nullptr);
assert(GetTreeSize_R(root) == testInput.size());
TreeNode<int>* entry1 = nullptr;
TreeNode<int>* entry2 = nullptr;
assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);

TreeNode<int>* subTree1 = new TreeNode<int>(1000);
subTree1->left = new TreeNode<int>(1001);
subTree1->right = new TreeNode<int>(1002);
TreeNode<int>* subTree2 = new TreeNode<int>(1000);
subTree2->right = new TreeNode<int>(1001);
subTree2->right->right = new TreeNode<int>(1002);
assert(GetTreeSize_R(subTree1) == 3);
assert(GetTreeSize_R(subTree2) == 3);
assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

auto leftestNode = FindLeftestNode(root->right);
auto rightestNode = FindRightestNode(root->right);
assert(leftestNode != nullptr);
assert(leftestNode->left == nullptr);
assert(rightestNode != nullptr);
assert(rightestNode->right == nullptr);
assert(*leftestNode->data == 6);
assert(*rightestNode->data == 10);

leftestNode->left = subTree1;
rightestNode->right = subTree2;
assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);
assert(entry1 == nullptr);
assert(entry2 == nullptr);

DeleteTree(&root);
}

{
const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
auto root = ConstructTreeRecursive(testInput);
assert(root != nullptr);
assert(GetTreeSize_R(root) == testInput.size());
TreeNode<int>* entry1 = nullptr;
TreeNode<int>* entry2 = nullptr;
assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);

TreeNode<int>* subTree1 = new TreeNode<int>(1000);
subTree1->right = new TreeNode<int>(1002);
subTree1->right->right = new TreeNode<int>(1001);
TreeNode<int>* subTree2 = new TreeNode<int>(1000);
subTree2->right = new TreeNode<int>(1001);
subTree2->right->right = new TreeNode<int>(1002);
assert(GetTreeSize_R(subTree1) == 3);
assert(GetTreeSize_R(subTree2) == 3);
assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);

auto leftestNode = FindLeftestNode(root->right);
auto rightestNode = FindRightestNode(root->right);
assert(leftestNode != nullptr);
assert(leftestNode->left == nullptr);
assert(rightestNode != nullptr);
assert(rightestNode->right == nullptr);
assert(*leftestNode->data == 6);
assert(*rightestNode->data == 10);

leftestNode->left = subTree1;
rightestNode->right = subTree2;
assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);
assert(entry1 == nullptr);
assert(entry2 == nullptr);

DeleteTree(&root);
}
}``````

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

If a single node can be considered as a subtree the solution is trivial - just check duplicated leaf nodes. If the "subtree" should have at least 2 nodes, then we are ok to check all the triplets of "node, left child, right child" when both left and right children are either leafs or missing (but not both missing). Here's some code:

``````class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None

def isleaf(node):
if node is None:
return True
else:
if node.left is None and node.right is None:
return True
return False

def get_triplets(node):
res = []
if node.left is None:
res.append(None)
else:
res.append(node.left.value)
res.append(node.value)
if node.right is None:
res.append(None)
else:
res.append(node.right.value)
return ['|'.join([str(x) for x in res]), '|'.join([str(x) for x in res[::-1]])]

def find_triplets(node):
if node is None or isleaf(node):
return []
if isleaf(node.left) and isleaf(node.right):
return get_triplet(node)
return find_triplets(node.left) + find_triplets(node.right)

def hasdup(node):
unique = set()
for tr in find_triplets(node):
if tr in unique:
return True
return False

a = TreeNode(1)
b = TreeNode(2)
c = TreeNode(3)
a.left = b
a.right = c
d = TreeNode(1)
e = TreeNode(2)
f = TreeNode(5)
d.left = f
d.right = e
g = TreeNode(0)
g.left = a
g.right = d
print hasdup(g)``````

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

Any two duplicate subtrees have at least 3 nodes in common - root, left and right. In order to answer this question it is enough to find 2 subtrees having those 3 nodes equal.
Construct a hash multimap. Every new node goes into the map. If same value already exists, check if left=left and right=right. Stop if found. That's all.

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

Hi, my answer is quite simple:
A. go in-order traversal, and add each node to a Map<NodeValue, Node>
B. During in-order tranversal, if I find a already stored value, then I start to check if both are equal.

public class FindDuplicatedSubTrees {

private Map<Integer, List<TreeNode>> nodes;

/**
* @param args
*/
public static void main(String[] args) {
TreeNode root = new TreeNode(10);

root.left = new TreeNode(5);
root.left.right = new TreeNode(11);
root.left.left = new TreeNode(20);
root.left.left.left = new TreeNode(5);
root.left.left.right = new TreeNode(6);

root.right = new TreeNode(6);
root.right.left = new TreeNode(9);
root.right.right = new TreeNode(8);
root.right.right.left = new TreeNode(5);
root.right.right.left.right = new TreeNode(11);
root.right.right.left.left = new TreeNode(20);
root.right.right.left.left.left = new TreeNode(5);
root.right.right.left.left.right = new TreeNode(6);

System.out.println(new FindDuplicatedSubTrees().hasDuplicatedSubTrees(root));
}

public boolean hasDuplicatedSubTrees(TreeNode root) {
if (nodes == null) {
nodes = new HashMap<Integer, List<TreeNode>>();
}
if(root == null) {
return false;
}
if (root.left == null && root.right == null) {
return false;
}

if (!nodes.containsKey(root.data)) {
List<TreeNode> ns = new ArrayList<FindDuplicatedSubTrees.TreeNode>();
nodes.put(root.data, ns);
}
else {
List<TreeNode> ns = nodes.get(root.data);
for (TreeNode treeNode : ns) {
if (equals(treeNode, root, treeNode, root)) {
return true;
}

}
}

if (hasDuplicatedSubTrees(root.left)) {
return true;
}
return hasDuplicatedSubTrees(root.right);
}

private boolean equals(TreeNode na, TreeNode nb, TreeNode roota, TreeNode rootb) {
if (na == rootb || nb == roota) {
return false;
}

if (na != null && nb == null || na == null && nb != null) {
return false;
}

if (na == null && nb == null) {
return true;
}

if (na.data == nb.data) {
if (equals(na.left, nb.left, roota, rootb)) {
return equals(na.right, nb.right, roota, rootb);
}
}

return false;
}

private static class TreeNode {

int data;
TreeNode left;
TreeNode right;

public TreeNode(int data) {
super();
this.data = data;
}

* @see java.lang.Object#toString()
*/
@Override
public String toString() {
return data + "";
}

}

}

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

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

def detect_dup_sub(tree, tree_sets=set()):
if tree is None:
return False, tuple()

left_res, left_tree = detect_dup_sub(tree.left, tree_sets)
right_res, right_tree = detect_dup_sub(tree.right, tree_sets)

if left_res or right_res:
return True, tuple()

this_tree = left_tree + (tree.value,) + right_tree
# this_tree is a inorder list of the subtree
if len(this_tree) > 3 and this_tree in tree_sets:
return True, tuple()
else:
return False, this_tree``````

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

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

def detect_dup_sub(tree, tree_sets=set()):
if tree is None:
return False, tuple()

left_res, left_tree = detect_dup_sub(tree.left, tree_sets)
right_res, right_tree = detect_dup_sub(tree.right, tree_sets)

if left_res or right_res:
return True, tuple()

this_tree = left_tree + (tree.value,) + right_tree
# this_tree is a inorder list of the subtree
if len(this_tree) > 3 and this_tree in tree_sets:
return True, tuple()
else:
return False, this_tree

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

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

def detect_dup_sub(tree, tree_sets=set()):
if tree is None:
return False, tuple()

left_res, left_tree = detect_dup_sub(tree.left, tree_sets)
right_res, right_tree = detect_dup_sub(tree.right, tree_sets)

if left_res or right_res:
return True, tuple()

this_tree = left_tree + (tree.value,) + right_tree
# this_tree is a inorder list of the subtree
if len(this_tree) > 3 and this_tree in tree_sets:
return True, tuple()
else:
return False, this_tree``````

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

``````struct Node {
Node * left, *right;
Node() : left{ nullptr }, right{ nullptr } {}
};

string detect_duplicate_subtrees_helper(
Node * tree,
unordered_map<string, int> & storage
) {
if (tree == nullptr) {
return "";
}
else {
string l = detect_duplicate_subtrees_helper(tree->left, storage);
string r = detect_duplicate_subtrees_helper(tree->right, storage);
if (r < l) swap(l, r);
const string code = "0" + l + "10" + r + "1";
storage[code]++;
return code;
}
}

void detect_duplicate_subtrees(Node * tree) {
unordered_map<string, int> storage;
detect_duplicate_subtrees_helper(tree, storage);
for (auto & a : storage) {
if (a.second > 0) {
cout << a.first << " " << a.second << endl;
}
}
}

int main()
{
/*

root
/    \
a      b
\    /
c  d
\  \
e  f

*/
Node root, a, b, c, d, e, f;
root.left = &a;
root.right = &b;
a.right = &c;
c.right = &e;
b.left = &d;
d.right = &f;

detect_duplicate_subtrees(&root);

return 0;
}``````

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

``````public static boolean isContainsDuplicateTrees(TreeNode root) {

return isContainsDuplicateTrees(new TreeSet<>(), root);
}

public static boolean isContainsDuplicateTrees(Set<String> trees, TreeNode root) {

if (root != null) {
String tree = "";
if (root.leftNode != null) {
tree += root.leftNode.nodeName;
}

tree += root.nodeName;

if (root.rightNode != null) {
tree += root.rightNode.nodeName;
}

if (trees.contains(tree)) {
System.out.println(tree);
return true;
}
if (tree.length() == 3) {
System.out.println(tree);
}
boolean isLeftHave = false;
if (root.leftNode != null) {
isLeftHave = isContainsDuplicateTrees(trees, root.leftNode);
}

boolean isRightHave = false;
if (root.rightNode != null) {
isRightHave = isContainsDuplicateTrees(trees, root.rightNode);
}

return (isLeftHave || isRightHave);

}
return false;
}``````

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

``````class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right

subtrees = set()

def subDup(root):
if root == None:
return False, ""
lstr = ""
rstr = ""
xl = False
xr = False
if root.left:
(xl, lstr) = subDup(root.left)
if root.right:
(xr, rstr) = subDup(root.right)
if xl or xr:
return True, ""
s = root.value + lstr + rstr
if len(s) > 2 and s in subtrees:
return True, s
return False, s

root = TreeNode("A")
root.left = TreeNode("B")
root.left.left = TreeNode("E")
root.left.right = TreeNode("E")
root.right = TreeNode("C")
root.right.left = TreeNode("B")
root.right.left.left = TreeNode("E")
root.right.left.right = TreeNode("E")

print(subDup(root)[0])``````

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

find longest repeating seq over inorder traversal string for the tree.

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

no, it's not that simple,
consider the example:

A
/ \
B C
/ \ \ \
AC B D

In-order traversal: ABCABCD.
Longest repeating seq is ABC, but there are no duplicate sub trees in the tree.

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

Instead of A, B, C,.., what about LRV sequence? Then gzam's solution works fine.

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.

### 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.