Microsoft Interview Question for Software Engineer / Developers

Country: India
Interview Type: In-Person

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

Possible ways to find the right node first
1) Check if the parent has right children, if yes get the next left child if not the right.
2) If parents doesn't have right child, go to its parent with level++ and go down on the right of that parent using the same first condition recursively till that level becomes zero.
3) If didn't find, return null.

I may be wrong, please correct me.

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

From what I understand the problem to be you are almost correct.

Initialize:
parent pointer = current node
grandparent = parent of parent pointer.

Algorithm.
1. Keep moving to the parent until you find a parent , grandparent pair such that grandfather->left = parent. ( you have to maintain the level as you go up )
2. Move to right of grandparent. level-- ( if no right child repeat 1)
3. Find the first child of the grandparent whose level is same as that of node. you travel the left subtree first and then the right to ensure that nearest node is captured first.
4. If there is no node repeat step 1 until we reach parent.

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

@uuuouou you could do better

1) use parent pointer to find the level of the two nodes. --> O(height) = O(lgn) for balanced tree and O(n) for unbalanced tree.

2) Now, keep two pointers: one pointing to the deeper node and second pointing to the shallower node. Also keep two lists: one for putting the nodes in the path from first node to the lowest common ancestor. Another for putting nodes in the path from second node to LCA node in reverse order (i.e. always insert in front of the list).

3) Move deeper pointer up (one parent each time) for delta=level-level2 times. Also add nodes to the proper list accordingly. --> O(lgn) for balanced tree and O(n) for unbalanced tree.

4) Now, two pointers are leveled. Move up both pointer at the same time up one parent until the pointers hit to the common parent (lca). While going up we already populate first list by the nodes in the path from first node to lca in forward order; and populated 2nd list by the nodes in the path from second node to lca in reverse order. --> O(lgn) for balanced tree and O(n) for unbalanced tree

5) concat second list with first list and voila! we have our answer. --> O(1)

overall complexity is O(lgn) for balanced tree and O(n) for unbalanced tree.

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

use parent pointer to find the level of the two nodes. I guess the intent was that with just having one node , find the second node and it's path as well.

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

Since this is listed as a C interview question (not C++) I did an answer in C99.

Most of the code is test cases and linked-list handling (for the paths). The real solution is the 3 routines at the beginning

The algorithm is simple:
(1) Find a pointer to the right sibling O(n) worst case: chosen node is leftmost child on lowest level of full binary tree that has no other children at our node's depth.
(2) Create a path between the initial node and the right sibling by following their parent pointers up until they reach a common ancestor. O(path length)

Finding the right sibling is also a simple recursive routine:
If this is the left child and the parent has a right child, that is this node's right sibling. Otherwise, keep finding right siblings of the parent and choose the leftmost of their children. If none of the parent's right siblings has children, there is no right sibling for this node.

``````#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef struct node_struct {
struct node_struct* left;
struct node_struct* right;
struct node_struct* parent;
int data;
} node;

typedef struct path_node_struct {
struct path_node_struct* next;
node* path_elt;
} path_node;

path_node* empty_path();
void move_first_onto_front_of_path(path_node** to_move, path_node** dest);

/**
* Return a path as a linked list to the first node to the right on
* the same level as this node.  Return empty path if there is no node
* to the right
*/
path_node* path_to_right(node*cur){
node* right_neighbor(node* cur);
path_node* path_between_siblings(node*start, node*end);
if(cur == NULL){ return NULL; }
node* neighbor;
if(cur->parent == NULL){
return NULL;
}else{
neighbor = right_neighbor(cur);
if(neighbor == NULL){
return NULL;
}else{
return path_between_siblings(cur, neighbor);
}
}
}

/**
* Return a pointer to the first node to the right of cur on the same
* level or NULL if there is no such node.
*/
node* right_neighbor(node* cur){
node*parent_of_sibling;

assert(cur != NULL);
if(cur->parent == NULL){ //At root
return NULL;
}else{
if(cur->parent->left == cur){ //Am left child
if(cur->parent->right != NULL){ //With a right sibling
return cur->parent->right;
}
}
//Am right child or don't have a right sibling from same parent
//So must look at children of right siblings of parent in order
parent_of_sibling = right_neighbor(cur->parent);
while(parent_of_sibling != NULL){
if(parent_of_sibling->left != NULL){
return parent_of_sibling->left;
}else if(parent_of_sibling->right != NULL){
return parent_of_sibling->right;
}
parent_of_sibling = right_neighbor(parent_of_sibling);
}
//No siblings of my parent have appropriate children thus I have no
//right neighbor
return NULL;
}
}

/**
* Given that start and end are on the same level, return the path
* between them as a linked list.
*/
path_node* path_between_siblings(node*start, node*end){
path_node* start_to_LCA = empty_path();
path_node* LCA_to_end = empty_path();
node* start_ancestor = start;
node* end_ancestor = end;
assert(start != NULL);
assert(end != NULL);
while(start_ancestor != end_ancestor){
assert(start_ancestor != NULL); //Verify that really were siblings
assert(end_ancestor != NULL);
push_onto_front_of_path(&start_to_LCA, start_ancestor);
push_onto_front_of_path(&LCA_to_end, end_ancestor);
start_ancestor = start_ancestor->parent;
end_ancestor = end_ancestor->parent;
}
push_onto_front_of_path(&LCA_to_end, end_ancestor);
while(start_to_LCA != NULL){
move_first_onto_front_of_path(&start_to_LCA, &LCA_to_end);
}

return LCA_to_end;
}

///////////
// Path and Tree manipulation
///////////

}
}

path_node* empty_path(){
return NULL;
}

path_node* new = (path_node*)malloc(sizeof(path_node));
new->path_elt = path_elt;
}

void move_first_onto_front_of_path(path_node** to_move, path_node** dest){
path_node* temp = *to_move;
assert(to_move != NULL);
assert(dest != NULL);

if(temp != NULL){
*to_move = temp->next;
temp->next = *dest;
*dest = temp;
}else{
//Moving the first of an empty list. Maybe this should log a
//warning somewhere. Doing nothing right now (though crashing in
//debug
assert(temp != NULL);
}
}

void delete_tree(node* to_delete){
if(to_delete == NULL) return;
delete_tree(to_delete->left);
delete_tree(to_delete->right);
free(to_delete);
}

void print_tree(node* root, int depth){
int i;
if(root != NULL){
print_tree(root->left, depth+1);
}
for(i = 0; i+1 < depth; ++i){
printf("|");
}
if(root != NULL){
printf("_%d @ (%d)\n",root->data, depth);
}else{
printf("_NULL @ (%d)\n", depth);
}
if(root != NULL){
print_tree(root->right, depth+1);
}
}

node* make_node(int value, node* left, node* right){
node* to_ret = (node*)malloc(sizeof(node));
to_ret->left = left;
if(left != NULL){
left->parent = to_ret;
}
to_ret->right = right;
if(right != NULL){
right->parent = to_ret;
}
to_ret->parent = NULL;
to_ret->data = value;
}

}
printf("\n");
}

/**
* Test code (just uses assert, nothing fancy)
*/

int main(){
///////////////
// Test path list
///////////////
path_node* test_list = NULL;
path_node* test_list2 = NULL;

// Make list 56,2,1
push_onto_front_of_path(&test_list, (node*)1);
assert(test_list->path_elt == (node*)1);
assert(test_list->next == NULL);

push_onto_front_of_path(&test_list, (node*)2);
assert(test_list->path_elt == (node*)2);
assert(test_list->next != NULL);
assert(test_list->next->path_elt == (node*)1);
assert(test_list->next->next == NULL);

push_onto_front_of_path(&test_list, (node*)56);
assert(test_list->path_elt == (node*)56);
assert(test_list->next != NULL);
assert(test_list->next->path_elt == (node*)2);
assert(test_list->next->next != NULL);
assert(test_list->next->next->path_elt == (node*)1);
assert(test_list->next->next->next == NULL);

// Make a second list -56,-2,-1
push_onto_front_of_path(&test_list2, (node*)-1);
assert(test_list2->path_elt == (node*)-1);
assert(test_list2->next == NULL);

push_onto_front_of_path(&test_list2, (node*)-2);
assert(test_list2->path_elt == (node*)-2);
assert(test_list2->next != NULL);
assert(test_list2->next->path_elt == (node*)-1);
assert(test_list2->next->next == NULL);

push_onto_front_of_path(&test_list2, (node*)-56);
assert(test_list2->path_elt == (node*)-56);
assert(test_list2->next != NULL);
assert(test_list2->next->path_elt == (node*)-2);
assert(test_list2->next->next != NULL);
assert(test_list2->next->next->path_elt == (node*)-1);
assert(test_list2->next->next->next == NULL);

// Move second list elements onto the first
move_first_onto_front_of_path(&test_list2, &test_list);

assert(test_list2->path_elt == (node*)-2);
assert(test_list2->next != NULL);
assert(test_list2->next->path_elt == (node*)-1);
assert(test_list2->next->next == NULL);

assert(test_list->path_elt == (node*)-56);
assert(test_list->next != NULL);
assert(test_list->next->path_elt == (node*)56);
assert(test_list->next->next != NULL);
assert(test_list->next->next->path_elt == (node*)2);
assert(test_list->next->next->next != NULL);
assert(test_list->next->next->next->path_elt == (node*)1);
assert(test_list->next->next->next->next == NULL);

// Delete the lists
delete_path(test_list); test_list = NULL;
delete_path(test_list2); test_list2 = NULL;

/////////////
// Test Tree stuff
/////////////

node* empty_tree = NULL;
node* single_node_tree = make_node(100, NULL, NULL);
node* tree_with_one_right =
make_node
(10,
NULL,
make_node(100, NULL, NULL)
);

node* tree_with_one_left =
make_node
(10,
make_node(100, NULL, NULL),
NULL
);

node* tree_with_both =
make_node
(10,
make_node(20, NULL, NULL),
make_node(40, NULL, NULL));

node* complex_tree =
make_node(1,
make_node(10,
make_node(100,
make_node(1000, NULL, NULL),
NULL),
make_node(200,
make_node(2000,NULL, NULL),
NULL)),
make_node(20,
NULL,
make_node(300,
make_node(3000,NULL, NULL),
make_node(4000,NULL, NULL))));

path_node* ans = NULL;

ans = path_to_right(empty_tree);
assert(ans == NULL);

ans = path_to_right(single_node_tree);
assert(ans == NULL);

ans = path_to_right(tree_with_one_left);
assert(ans == NULL);

ans = path_to_right(tree_with_one_left->left);
assert(ans == NULL);

ans = path_to_right(tree_with_one_right->right);
assert(ans == NULL);

ans = path_to_right(tree_with_both->right);
assert(ans == NULL);

ans = path_to_right(tree_with_both->left);
assert(ans != NULL);
assert(ans->path_elt == tree_with_both->left);
assert(ans->next->path_elt == tree_with_both);
assert(ans->next->next->path_elt == tree_with_both->right);
delete_path(ans);

ans = path_to_right(complex_tree->left->left->left);
assert(ans != NULL);
assert(ans->path_elt == complex_tree->left->left->left);
assert(ans->next->path_elt == complex_tree->left->left);
assert(ans->next->next->path_elt == complex_tree->left);
assert(ans->next->next->next->path_elt == complex_tree->left->right);
assert(ans->next->next->next->next->path_elt ==
complex_tree->left->right->left);
delete_path(ans);

ans = path_to_right(complex_tree->left->right->left);
assert(ans != NULL);
assert(ans->path_elt == complex_tree->left->right->left);
assert(ans->next->path_elt == complex_tree->left->right);
assert(ans->next->next->path_elt == complex_tree->left);
assert(ans->next->next->next->path_elt == complex_tree);
assert(ans->next->next->next->next->path_elt ==
complex_tree->right);
assert(ans->next->next->next->next->next->path_elt ==
complex_tree->right->right);
assert(ans->next->next->next->next->next->next->path_elt ==
complex_tree->right->right->left);
delete_path(ans);

ans = path_to_right(complex_tree->right->right->right);
assert(ans == NULL);

delete_tree(single_node_tree);
delete_tree(tree_with_one_right);
delete_tree(tree_with_one_left);
delete_tree(tree_with_both);
delete_tree(complex_tree);
}``````

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

[Not a solution]
You shouldn't be disheartened by what happened. Microsoft is known for doing strange things in their interview process. Sometimes they already have a decision made about you, even before you enter the interview room. Interview is just a formality, because Microsoft has committed the interview.

The question wasn't too difficult, practice more next time! Hope you do well.

Has happened to me before. And now, I work at Microsoft.

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

The problem can be divided into two steps:
(1)find the first common ancestor of the two nodes
(2)find path from left node to ancestor, say it is leftPath,
find path from right node to ancestor, say it is rightPath,
then path = leftPath - ancestor + reverse(rightPath)
In implementation, we can combine those two steps together. Following is code in C++:

``````struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode* parent;
TreeNode(int value) : val(value) left(NULL), right(NULL), parent(NULL) {}
};
bool getPath(vector<TreeNode*>& path, TreeNode* start, TreeNode* dest)
{
path.clear();
//step 0: handling specail cases
if(start == NULL || dest == NULL) return false;
if(start == dest){//start is dest
path.push_back(start);
return true;
}
if(start->parent == NULL){//start is root
getPathToRoot(path, dest);
if(path.back() != start){//start and dest in different trees!
path.clear();
return false;
}
reversePath(path);
return true;
}
if(dest->parent == NULL){//dest is root
getPathToRoot(path, start);
if(path.back() != dest){//start and dest in different trees!
path.clear();
return false;
}
return true;
}
//step 1: find out two nodes' paths to root
vector<TreeNode*> startToRoot, destToRoot;
getPathToRoot(startToRoot, start);
getPathToRoot(destToRoot, dest);
//step 2: find out the first common ancestor by finding the first common node of two lists
size_t i, j, lenOfStart = startToRoot.size(), lenOfDest = destToRoot.size();
if(lenOfStart < lenOfDest){
i = 0;
j = lenOfDest - lenOfStart;
}
else{
i = lenOfStart - lenOfDest;
j = 0;
}
for(; j < lenOfDest; ++i, ++j){
if(startToRoot[i] == destToRoot[j]) break;//find common ancestor!
}
if(j == lenOfDest) return false;//start and dest in different trees!
//step 3: get fully path from start to dest
path.assign(startToRoot.begin(), startToRoot.begin() + i);
path.insert(path.end(), destToRoot.rbegin() + lenOfDest - 1 - j, destToRoot.rend());
return true;
}
void getPathToRoot(vector<TreeNode*>& path, TreeNode* p)
{
for(; p != NULL; p = p->parent) path.push_back(p);
}
void reversePath(vector<TreeNode*>& path)
{
if(path.size() < 2) return;
for(size_t i = 0, j = path.size() - 1; i < j; ++i, --j){
TreeNode* tmp = path[i];
path[i] = path[j];
path[j] = tmp;
}
}``````

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

Initially you will have to find the node to the right of the given node also

eg:

___________A
________B_____C
______D_____E___F

B and C are children of A

D is left child of B

E and F are children of C

Given D you need to first locate E, then print the path by the method you've mentioned

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

@uuuouou you could do better

1) use parent pointer to find the level of the two nodes. --> O(height) = O(lgn) for balanced tree and O(n) for unbalanced tree.

2) Now, keep two pointers: one pointing to the deeper node and second pointing to the shallower node. Also keep two lists: one for putting the nodes in the path from first node to the lowest common ancestor. Another for putting nodes in the path from second node to LCA node in reverse order (i.e. always insert in front of the list).

3) Move deeper pointer up (one parent each time) for delta=level-level2 times. Also add nodes to the proper list accordingly. --> O(lgn) for balanced tree and O(n) for unbalanced tree.

4) Now, two pointers are leveled. Move up both pointer at the same time up one parent until the pointers hit to the common parent (lca). While going up we already populate first list by the nodes in the path from first node to lca in forward order; and populated 2nd list by the nodes in the path from second node to lca in reverse order. --> O(lgn) for balanced tree and O(n) for unbalanced tree

5) concat second list with first list and voila! we have our answer. --> O(1)

overall complexity is O(lgn) for balanced tree and O(n) for unbalanced tree.

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

I think we can do something like this.

``````int main()
{
bool skip_this=false;
if(p->parent && p->parnet->right ==p)
skip_this==true;
if(p->parent==null)
{ //exit for root
return 0;
}
int rv= find_path(p->parent, 1, new string("p->val"), skip_this);
return rv;
}
bool find_path(tree *p, int level, string path, bool skip_this)
{
bool rv=false;
if(level==0)
{
PRINT(path);
rv=true;
}
else
{
if(p->right != null && skip_this!=true)
{
rv= find_path(p->right, level -1, path + p->val, false);
}
if(rv!=true)
{
if( p->parent != null)
{
rv= find_path(p->parent, level+1, string+p->val, false);
}
}
}
return rv;
}``````

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

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

My solution

``````public class Node
{
public Node left, right, parent;
public string Value;

public Node(string value)
{
Value = value;
}
}

static List<Node> PathToRightSibling(Node n)
{
Node current = n;
int level = 0;
List<Node> upwardPath = new List<Node>();

// Traverse up the tree
while (current.parent != null)
{
if (current.parent.left == current)
{
current = current.parent;
level++;

if (current.right != null)
{
List<Node> path = FindPath(current.right, level - 1);

if (path != null)
{
return upwardPath;
}
}
}
else
{
current = current.parent;
level++;
}
}

return null;
}

static List<Node> FindPath(Node root, int level)
{
List<Node> path = new List<Node>();
if (level == 0)
{
return path;
}

if (root.left != null)
{
List<Node> leftPath = FindPath(root.left, level - 1);
if (leftPath != null)
{
return path;
}
}

if (root.right != null)
{
List<Node> rightPath = FindPath(root.right, level - 1);
if (rightPath != null)
{
return path;
}
}

return null;
}``````

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.