Yahoo Interview Question for Software Engineer / Developers






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

Modified Inorder Traversal(node *head1,node *head2)
{
if(both head1 head2 are NULL)
return true;
if(one of head1 n head2 NULL)
return false;
if data(head1) == data(head2)
return inorder(head1>left,head2->left)&&inorder(head1->right,head2->right);
return false;
}

- Random Guy June 21, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

doesn't your 2 inorder loops scan the whole tree twice? remember inorder traverses the whole tree, not half tree?

- son_of_a_thread August 03, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

NO ! If you observe the code carefully there are no loops ! :P
Solution is perfect.

- maximum_latency August 05, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Remember, the question does not say whether it is a BT or BST. So this could be any kind of tree with n-children

- Sumit September 02, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Traverse one tree and keep a hash map, for each node add a <key,pair<,>> pair where key is the parent node info and pair are the two children (duplicates can be resolved via chaining). Now traverse next tree and see if same node (value) has same children as found in previous tree based on the hash table values.

- Second Attempt February 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

As significant optimization:

if( tree1.size() != tree2.size() ){
    return false;
}

// TODO: make in-order (or any other) traversation and compare

- m@}{ June 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

computing the size of tree requires O(n) where n is the number of nodes in tree.

- wolverine December 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

breadth first traversal on each tree ,each time comparing the values.

- mrn July 13, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool isSame(struct node* head1, struct node* head2)
{
  if(head1==null && head2==null) return true;
  if(head1==null || head2==null) return false;
  if(head1->data != head2->data) return false;
  if(!isSame(head1->left, head2->left) || !isSame(head1->right, head2->right)) return false;
  else return true;
}

- Anonymous July 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

nice answer, if we can rewrite like this

bool isSame(struct node* head1, struct node* head2)
{
  if(head1==null && head2==null) return true;
  if(head1==null || head2==null) return false;

  if(head1->data == head2->data && isSame(head1->left, head2->left) && isSame(head1->right, head2->right)) 
      return true;
  else 
      return false;
}

- wolverine December 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#define LEFT(n) (n->left == NULL) ? 0 : 1
#define RIGHT(n) (n->right == NULL) ? 0 : 1

bool sameTree(btree *p, btree *q)
{
	if(p == NULL && q == NULL)
		return true;

	if(p->key != q->key)
		return false;

	if(LEFT(p) != LEFT(q))
		return false;

	if(RIGHT(p) != RIGHT(q))
		return false;

	return sameTree(p->left, q->left) && sameTree(p->right, q->right);
}

- Anonymous July 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Well this is just a simple recursion.

int check(struct node *root1, struct node *root2) {
    if(root1 == NULL && root2 == NULL) {
             return 1;
    }
    else if(root1 && root2) {
         return(root1->data == root2->data && check(root1->left,root2->left) && check(root1->right,root2->right));
    }
    else {
         return 0;
    }
}

- Spock July 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If it BST, Do an In order traversal for both the trees, it will be in sorted sequence, then compare the values from left to right

- Hari July 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Traverse both trees recursively together. This will even check if they have the same structures.

isEqual(root1, root2);


boolean isEqual(Node node1, Node node2){
if(node1.data == node2.data){
return isEqual(node1.left, node2.left)
&& isEqual(node1.right, node2.right);
}
return false;
}

- someone February 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Traverse both trees recursively together. This will even check if they have the same structures.

isEqual(root1, root2);

boolean isEqual(Node node1, Node node2){
if(node1==null && node2 == null){
return true;
}else if(node1==null){// this means only node2 is null
return false;
}
if(node1.data == node2.data){
return isEqual(node1.left, node2.left)
&& isEqual(node1.right, node2.right);
}
return false;
}

- someone cool February 02, 2013 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More