## Interview Question for Senior Software Development Engineers

Country: United States
Interview Type: In-Person

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

This is how I'd do it for Node with val and kids
if t1.val == t2.val match t2.kids in t1.kids is even one not found return false
else match t2 in t1.kids

``````boolean match(Node t1, Node t2) {
boolean ret = false;
if (t1.val == t2.val) {
ret = true; // true if no kids for t1 and t2
for (Node item : t2.kids) {
ret = false; // false if t2 has kids but t1 doesn't have one of t2.kids
for (Node other : t1.kids)
ret |= match(other, item);
if (!ret) break;
}
return ret;
}
for (Node other : t1.kids)
ret |= match(other, t2);
return ret;
}``````

I couldn't test it, so do post if this works for you

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

bool areIdentical(struct node* root1, struct node* root2) {
if (root1 == NULL && root2 == NULL) {
return true;
}
if (root1 == NULL || root2 == NULL) {
return false;
}
return (root1 -> data == root2 -> data && areIdentical(root1 -> left, root2 -> left) &&
areIdentical(root1 -> right, root2 -> right) );
}
bool isSubtree(struct node *T1, struct node *T2) {
if (T2 == NULL) {
return true;
}
if (T1 == NULL) {
return false;
}
if (areIdentical(T1, T2)) {
return true;
}
return isSubtree(T1 -> left, T2) || isSubtree(T1 -> right, T2);
}

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

``````public class CheckForSubTree<K extends Comparable> {
private static class MultiChildTreeNode<K> {
List<MultiChildTreeNode> children;
K data;
MultiChildTreeNode(K data){
this.data = data;
children = new ArrayList<>();
}
}

private boolean isSubTree(MultiChildTreeNode<K> t1, MultiChildTreeNode<K> t2){
if(t2 == null || t1 == null ) return true;
Stack<MultiChildTreeNode> n1 = new Stack<>();
n1.push(t1);//main tree traversal -> depth first search
Queue<MultiChildTreeNode> matchingQ = new LinkedList<>();//if matches found then convert main tree traversal to breadth first search and move on
boolean found = false;
while(!n2.isEmpty() && !n1.isEmpty()){
MultiChildTreeNode<K> nn2 = n2.poll();
MultiChildTreeNode<K> nn1;
if(found && !matchingQ.isEmpty()){
nn1 = matchingQ.poll();
} else {
nn1 = n1.pop();
}
if(nn2.data.compareTo(nn1.data) != 0) { //on mismatch reset
n2 = new LinkedList<>(); //start over again
found = false;
} else {
found = true;
for (int i = 0; i < nn2.children.size(); i++) {
}
for (int i = 0; i < nn1.children.size(); i++) {
}
}
for (int i = 0; i < nn1.children.size(); i++) {//always add main tree childrenn
n1.push(nn1.children.get(i));
}
}
return found;
}

public static void main(String[] args) {
/**
*      F
*    /  \
*   I    K
*/

MultiChildTreeNode<String> ff = new MultiChildTreeNode<>("F");
MultiChildTreeNode<String> iff = new MultiChildTreeNode<>("I");
MultiChildTreeNode<String> kff = new MultiChildTreeNode<>("K");
MultiChildTreeNode<String> t2 =  ff;//Subtree to find

//Main tree
MultiChildTreeNode<String> t1 = new MultiChildTreeNode<>("A");
MultiChildTreeNode<String> b = new MultiChildTreeNode<>("B");
MultiChildTreeNode<String> c = new MultiChildTreeNode<>("C");
MultiChildTreeNode<String> d = new MultiChildTreeNode<>("D");

MultiChildTreeNode<String> e = new MultiChildTreeNode<>("E");
MultiChildTreeNode<String> h = new MultiChildTreeNode<>("H");

MultiChildTreeNode<String> f = new MultiChildTreeNode<>("F");
MultiChildTreeNode<String> i = new MultiChildTreeNode<>("I");
MultiChildTreeNode<String> j = new MultiChildTreeNode<>("J");

/**
*            A
*       /    |    \
*      B     C..  D...
* /    |
*E..   F
*    /  \
*   I    J
*        |
*        F
*      /  \
*     I    K
*/
j.children.add(ff); //commenting out this line should give false otherwise true

MultiChildTreeNode<String> k = new MultiChildTreeNode<>("K");
MultiChildTreeNode<String> g = new MultiChildTreeNode<>("G");

MultiChildTreeNode<String> l = new MultiChildTreeNode<>("L");

MultiChildTreeNode<String> m = new MultiChildTreeNode<>("M");
MultiChildTreeNode<String> n = new MultiChildTreeNode<>("N");
MultiChildTreeNode<String> o = new MultiChildTreeNode<>("O");
CheckForSubTree<String> checker = new CheckForSubTree<>();
System.out.println (checker.isSubTree(t1, t2));
}``````

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.