## MicroStrategy Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

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

My answer was a recursive function:

``````boolean matches(Node node1, Node node2){
if(node1==node2)
return true;
if(node1==null && node2!=null)
return false;
if(node1!=null && node2==null)
return false;
return matches(node1.left,node2.left)&&matches(node1.right,node2.right);
}``````

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

Looks like this won't work.

``````Compare this tree:

*
/  \
*   *

With this tree:

*
\
*``````

matches for the left trees will return false...

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

Yes it will. Do a dry run, for the root1 and root2 nodes, none of the if's will fulfill and therefore what will execute is:

``return matches (left1,left2) && matches(right1, right2)``

where matches(left1, left2) will return you a false, since left2 is null (3rd if).
Even though matches(right1, right2) returns a true, the output is false since it is an AND operation.

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

Oh you mean an exact match?

the use of 'overlap' misled me there. In the above example, I was expecting a true return, while your code gives false (as you explained).

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

-1 for

``````if(node1==node2)
return true;``````

it will return true only it they correspond to same node. If this is true they why do you need to check further. mean as both node is same then data/child will also be same.

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

LOL@ niraj.

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

@Niraj If u are passing same nodes of course it WILL and SHOULD return true and not check further. If they are not the same, then it returns true if BOTH nodes are NULL. Please support your down vote with another example. Did you care to do a dry run on any specific example?

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

does structure doesn't mean data of the node should also match.

Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{ boolean overlaps(Node u, Node v) { return !u || !v || u.val == v.val && overlaps(u.left, v.left) && overlaps(u.right, v.right) ; }
Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{ boolean overlaps(Node u, Node v) { return !u || !v || u.val == v.val && overlaps(u.left, v.left) && overlaps(u.right, v.right) ; }
Comment hidden because of low score. Click to expand.
0
of 0 vote

``````boolean overlaps(Node u, Node v)
{
return !u || !v ||  u.val == v.val && overlaps(u.left, v.left) && overlaps(u.right, v.right) ;
}``````

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

you do not have to check the values of u and v since we only care the structures of tree u and tree v.

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

if u or v are null, the u.left and similar operations will get u null pointer exception.

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

A solution with a stack in Objective C

``````/* Stack */
@interface Stack : NSObject{
NSMutableArray* stack;
}
-(void)push:(id)item;
-(id)pop;
-(id)peek;
-(int)count;
@end

/* Node */
@interface Node : NSObject{
int value;
Node* left;
Node* right

}
@property unsigned int value;
@property (nonatomic,strong) Node *left;
@property (nonatomic,strong) Node *right;
@end

- (bool) areEqual:(Node *) rootA and:(Node *)rootB
{
[stack push:rootA];
[stack push:rootB];
while([stack count] != 0){
Node *tempA = (Node *)[stack pop];
Node *tempB = (Node *)[stack pop];

//Right
if(([[tempA right] class] == [[tempB right] class])  ){
if([tempA right] != nil){
[stack push:[tempA right]];
[stack push:[tempB right]];
}
} else {
return false;
}

//Left
if(([[tempA left] class] == [[tempB left] class]) ){
if([tempA left] != nil){
[stack push:[tempA left]];
[stack push:[tempB left]];
}
} else {

return false;
}

}
return true;
}``````

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

``````isSameBTree(node ptr1, node ptr2){
if(ptr1==ptr2)
return true; // both null or both are same node
else if(ptr1.data != ptr2.data)
return false;
return (isSameBTree(node ptr1.left, node ptr2.left)
&& isSameBTree(node ptr1.right, node ptr2.right));
}``````

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

correction

``````isSameBTree(node ptr1, node ptr2){
if(ptr1==ptr2)
return true; // both null or both are same node
else if((prt1==null)||(ptr2==null))
return false;
else if(ptr1.data != ptr2.data)
return false;
return (isSameBTree(node ptr1.left, node ptr2.left)
&& isSameBTree(node ptr1.right, node ptr2.right));
}``````

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

BTree? LOL.

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

``````boolean compareTrees(node n1, node n2)
{
while(1)
{
if(n1!=null && n2!=null)
{
compareTrees(n1->left, n2->left);
compareTrees(n1->left, n2->left);
}
else
{
break;
}
return true;
}

return false;

}``````

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.