MicroStrategy Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
Looks like this won't work.
Compare this tree:
*
/ \
* *
With this tree:
*
\
*
matches for the left trees will return false...
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.
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).
-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.
@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?
boolean overlaps(Node u, Node v)
{
return !u || !v || u.val == v.val && overlaps(u.left, v.left) && overlaps(u.right, v.right) ;
}
you do not have to check the values of u and v since we only care the structures of tree u and tree v.
A solution with a stack in Objective C
/* Stack */
@interface Stack : NSObject{
NSMutableArray* stack;
}
-(void)push:(id)item;
-(id)pop;
-(id)peek;
-(int)count;
@property(nonatomic,readonly) 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;
}
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));
}
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));
}
My answer was a recursive function:
- nosyDeveloper November 22, 2013boolean 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); }