Yahoo Interview Question for Software Engineer / Developers


Country: United States




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

O(n) solution:

public TreeNode rightMostCousin(TreeNode root, int targetKey)
{
	LinkedList<TreeNode> q = new LinkedList<TreeNode>();
	
	int count = 0;
	q.add(root);	
	count++;
	boolean targetLevel = false;
	
	while(!q.isEmpty())
	{
		TreeNode node = q.remove();	
		count--;
		if((node.left!=null && node.left.key == targetKey) || (node.right!=null && node.right.key == targetKey))
			targetLevel = true;			
		
		if(node.left != null) q.add(node.left);
		if(node.right != null) q.add(node.right);
		

		if(count == 0)
		{			
			count = q.size();
			
			if(targetLevel)
			{

				TreeNode cousin = null;
				while(!q.isEmpty())
				{
					cousin = q.remove();															
				}
								
				return cousin;
			}
		}
	}
	
	return null;
}

- zahidbuet106 May 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 8 vote

what's a cousin?

- micvog October 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

O(n) solution:

public TreeNode rightMostCousin(TreeNode root, int targetKey)
{
	LinkedList<TreeNode> q = new LinkedList<TreeNode>();
	
	int count = 0;
	q.add(root);	
	count++;
	boolean targetLevel = false;
	
	while(!q.isEmpty())
	{
		TreeNode node = q.remove();	
		count--;
		if((node.left!=null && node.left.key == targetKey) || (node.right!=null && node.right.key == targetKey))
			targetLevel = true;			
		
		if(node.left != null) q.add(node.left);
		if(node.right != null) q.add(node.right);
		

		if(count == 0)
		{			
			count = q.size();
			
			if(targetLevel)
			{

				TreeNode cousin = null;
				while(!q.isEmpty())
				{
					cousin = q.remove();															
				}
								
				return cousin;
			}
		}
	}
	
	return null;
}

- zahidbuet106 May 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

The way I solved it was first to find the grandfather node of a tree(if one exists) using recursion. Then I checked if the target node was a part of the subtree rooted at the left child of grandfather. If so, there is a rightmost cousin. And we find the same in the subtree rooted at the right child of grandfather. Here is the code in C++.

General::TreeNode<int>* getGrandFather(General::TreeNode<int>* root, int target, 
	General::TreeNode<int>* father,General::TreeNode<int>* grand_father)
{
	if(!root)
		return NULL;

	if(root->value()==target)
		return grand_father;

	General::TreeNode<int>* left_res;
	General::TreeNode<int>* right_res;	
	left_res = getGrandFather(root->getLeftChild(),target,root,father);
	right_res = getGrandFather(root->getRightChild(),target,root,father);

	if(!left_res)
		return right_res;
	else if(!right_res)
		return left_res;
	else return NULL;
}

General::TreeNode<int>* getCousin(General::TreeNode<int>* root,int target)
{
	General::TreeNode<int>* grandpa = getGrandFather(root,target,NULL,NULL);
	std::cout << grandpa->value();
	int grandson1,grandson2,grandson3,grandson4;
	if(grandpa)
	{
		grandson1 = grandpa->getLeftChild()->getLeftChild()->value();
		grandson2 = grandpa->getLeftChild()->getRightChild()->value();
		if(grandson1==target || grandson2==target)
		{
			if(grandpa->getRightChild())
				if(grandpa->getRightChild()->getRightChild())
					return grandpa->getRightChild()->getRightChild();
				else
					return grandpa->getRightChild()->getLeftChild();
			else
				return NULL;
		}
	}
	return NULL;
}

- Hingle McCringleBerry October 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

what if the we had left leaves of grandpa and only left leave of father. Some very top most ancestor of the grandpa had right leaf which is a subtree. Then our right most cousin is not at all within the subtrees of grandpa.

- anonymus December 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

findit(Node x, Node target)
{
    if(x==nil) return -1;   //target not down this path
    if(x==target) return 0;  //target found, return 0 as dist. above it
    
    // else check for target down all paths (children)
    distanceabove = -1;
    for(temp=x.children; temp!=nil ; temp=temp.nextchild)
    {
        distabove=findit(temp, target);
        if( distabove >= 2 ) return 2; //helps prune tree (optimization .. I hope!)
        if( distabove != -1 ) break;   //target was along this path
    }
    if(distabove == -1) return -1;  //target is nowhere in our subtree
    
    distabove++;  //add 1 to distance (for extra hop up to us)
 
    if(distabove == 2) {   //we are 2 hops above target, thus grandma
    
        for(temp=x.children; temp && temp.next; )  //find rightmost aunt of target
            temp=temp.nextchild;  
             
        for(temp=temp.children, prev=nil; temp && temp.next; ) //aunt's 2 r.m. daughters
            prev=temp, temp=temp.nextchild;
            
        if(temp && temp != target) 
            cout << temp << " is rightmost cousin\n"; //rightmost daughter if not me
        elif(temp && prev ) 
            cout << prev<< " is rightmost cousin\n"; //else try second rightmost
    }
    
    return distabove;
}

Typed it raw, expect the unexpected.

- S O U N D W A V E October 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

int printRightMostNeighbor(struct bs *b) //i.e., neighbor in level-order sense without using level-order or bfs
{
	int level1=0;
	int level2=0;
	if(b==NULL || b->parent==NULL)
		return NULL;
	if(b->parent->rc!=NULL && b->parent->rc!=b)
		return b->parent->rc;
	struct bst *tmp=NULL;
	struct bst *tmp1=b;
	while(b->parent!=NULL)
	{
		tmp=b;
		b=b->parent; 
		level1++;
		if(b->rc!=NULL && b->rc!=tmp)
			break;
	}
	while(level2!=level1-1)
	{
		if(b->rc==NULL)
			return NULL;
		b=b->rc;
		level2++;
	}
	if(b->rc==tmp1)
		return NULL;
	if(b->lc!=NULL)
		return b->lc;
	else if(b->rc!=NULL)
		return b->rc;
	else
		return NULL;
}

- Anonymous October 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Node structure will contain "level" field and "parent" field. Perform BFS on the tree. Keep track of the node that was inserted just before the current node. Once the target node is found look for level change. If the parent of the target node and the "before" node is the same after level changes, then the target node has no cousin. Else, the "before" node is the rightmost cousin.

- GK October 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I'm going to make three time-saving assumptions:

i. Children have a parent pointer
ii. Each node can have at most 2 children
iii. a cousin will be defined here as any node in the tree which has the same distance from the root as the input node.

All three of these can be easily remedied by adding onto the following design, but I'm lazy today.

TreeNode find_cousin(TreeNode a){
   int h = 0;
   TreeNode tmp = a;
   while(tmp.parent != null){
      tmp = tmp.parent;
      h++;
   }
   TreeNode x = find_rec(tmp, h, a);
   return x;
}

TreeNode find_rec(TreeNode a, int h, TreeNode avoid){
   if(a == null || a == avoid.parent) return null;
   if(h==0)return a;
   TreeNode x = find_rec(a.right, h - 1, avoid);
   if(x == null) x = find_rec(a.left, h - 1, avoid);
   return x;
}

Why does it work? It will seek out the rightmost cousin of the given node, even if that cousin is to the left of the given node. It will avoid the input node (given as avoid) and its sibling by rejecting at the parent level. If going right doesn't work, either because it hits the avoid's parent or because it reaches a leaf node before h = 0, it will attempt to go left. If necessary, it will traverse all nodes in the tree from the input's height and upwards, but will stop the moment it finds a node that is at the same height as the input, which we can assume is the rightmost since it will always look right as far as it can from any one parent node before moving on to try the left.

- Javeed October 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

// given question : Given Binary Tree, and a node, find the right most cousin, . In other words, given a node, find the right-most node in the same level;

TreeNode* rightMostCousin(TreeNode* root, TreeNode* gNode)
{
queue<TreeNode*> q;
int nCurrent(0), nNext(0);
TreeNode* ret(NULL);
if (root != NULL) { q.push(root); nCurrent++; }
while (!q.empty())
{
       TreeNode* cNode = q.front(); q.pop(); 
       nCurrent--;
       if (nNext == 0) { ret = cNode; }
       // if given node, then return ans, which is the rightmost-node in the given binary tree
       if (cNode == gNode) return ret;
       if (cNode->left != NULL) { q.push(cNode->right); nNext++; }
       if (cNode->right != NULL) { q.push(cNode->left); nNext++; }
       // go to the next level
       if (nCurrent == 0) {
           nCurrent = nNext; 
           nNext = 0;
       }
}
  return NULL;;
}

- Anonymous October 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

(1)As the tree's structure is unknown, we might have to use a general method.
(2)Because the rightest cousin is at the same level with the given node, we can traverse the tree by level to find the level of the given node. Meanwhile the fact is when we find the given node in a level loop, the last node of the loop will just be our target!
Following is my C++ code:

Node* getRightestCousin(Node* root, Node* p)
{
    if(root == NULL || p == NULL || root == p) return NULL;

    queue<Node*> q;
    Node* tmp;
    int levelCount, i;

    q.push(root);
    while(!q.empty()){
        for(i = 0, levelCount = q.size(); i < levelCount; ++i){
            tmp = q.front();
            q.pop();
            if(tmp != p){	//may not in this level, so push in next level's nodes
                if(tmp->left) q.push(tmp->left);
                if(tmp->right) q.push(tmp->right);
            }
            else{        	//only need to find the last node in this level
                Node* t = NULL;	//this is because p may be the rightest node in its level
                for(++i; i < levelCount; ++i){
                    t = q.front();
                    q.pop();
                }
                return t;
            }
        }
    }

    return NULL;	 	//can not find p in this tree
}

- uuuouou November 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

1.Perform DFS on the given tree until you find the target node.
2.Note the height h of this node.
3.Now that you know the height, keep going to the 'right' from the root until you reach height h.
4.This is the rightmost cousin of the target node.

- Anonymous December 31, 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