Microsoft Interview Question for Software Engineer in Tests


Country: United States
Interview Type: In-Person




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

Do a BFS to find the last element of tree with a small modification. Every time you remove an element from queue, store it in a variable and keep it updating. At end of BFS, this element will hold the parent of last element in tree.

So now you have root  -> say r,
  last element -> say e,
and parent of last element -> say p
now do as follows
left = r.left
right = r.right
r.left = null
r.right = null
e.left = left;
e.right = right;
if (p.right != null)  {
     p.right = r;
}
else {
      p.left = r;
}

- anonymous June 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

void BST::replaceRootWithLastLeafUsingBFS()
{
	if ( ! root_ || isLeaf(root_) ) 
		return;

	queue<Node*> Q;
	Q.push(root_);

	Node *last_parent = NULL, *last_child = NULL;

	while(!Q.empty())
	{
		Node* node = Q.front();
		Q.pop();

		if(isLeaf(node))
			last_child = node;
		else
			last_parent = node;

		if ( node->left_ )
			Q.push(node->left_);
		if( node->right_ )
			Q.push(node->right_);
	}

	/* swap last_child with root*/

	if ( last_parent->left_ == last_child )
		last_parent->left_ = root_;
	else
		last_parent->right_ = root_;

	last_child->left_ = root_->left_;
	last_child->right_ = root_->right_;

	root_->left_ = NULL;
	root_->right_ = NULL;

	root_ = last_child;

}

- Sunny_Boy February 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

does the word last elements means the rightmost element in the tree?!!

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

does the word last elements means the rightmost element in the tree?!!

- vinodh November 02, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

well its something like this

A 
B C 
D E

so here A is root which has two child as B & C. And B has two child D & E. There are no child of C. So the output should be

F 
B C
D A

- naphstor November 02, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Just small mistake in output

Replace F with E then everything will be fine.

- Nani November 03, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

sorry it was a typo in above. The output will be

E
  B   C
D   A

- naphstor November 02, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Anybody going to try posting an algo?

The tricky part of this is finding the parent of the rightmost node. This is easy in a heap structure. For any given element, its parent is going to be index / 2. So create a list<T> of Nodes. The root node is added twice (to make the root node index 1 and not zero to preserve the heap parent / child calculation). Set an enumerator to the List's 1st position. "Pop" the first position by Pushing each child node of the current node onto the list, then advance the enumerator one position. Continue doing so until all nodes are on the list. The last node will be at List.Count -1; Its parent node will be (List.Count - 1) / 2; Examine that parent node to find out if it has a right node. If not, the root node is added to the parent's left side. If it does have a right node, the root node is added to the parent's right side. The last node's left and right pointer are set to the root's left and right. The new rightmost node's left and right pointer are set to null.

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

Why not exchange the contents of last node with root node

- Doctor.Sai December 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

you do know that each node has a parent right?

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

Can anyone give the code for it??

- coding for fun December 11, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

won't using a function like this work to swap last node in the queue and root node(that is already stored as head)
function call: last_node=replace(head,last_node);
.
and function definition goes like this:
node * replace(node *head, node *curr_node)
{
node *root=head;
head=curr_node;
return head;
}

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

public void exchangeLastwithFirst(TreeNode node)
	{
		if(node == null)
			return;
		if(node.getLeft()!=null)
			queue.insert(node.getLeft());
		if(node.getRight()!=null)
			queue.insert(node.getRight());
		if(queue.getSize()!=1)
			exchangeLastwithFirst(queue.remove());
		else
		{
			Char temp = queue.peek().getData();
			queue.remove().setData(this.root.getData());
			this.root.setData(temp);
		}
	}

- Chris December 27, 2011 | 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