Microsoft Interview Question for Software Engineer in Tests

• 1
of 1 vote

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
10
of 14 vote

You can easily note here that for any given node:
the x-coordinate is its cardinal (order) in an inorder traversal; and
the y coordinate is the number of levels in the tree rooted at that node;

Using these 2 pieces you can easily get the output shown above...

makes sense?

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

your logic would work only if the tree is a perfect binary tree. it will fail otherwise... suppose root has only right subtree with one children i.e - tree=> a c

c - 2 0
a - 1 1

but as per your solution it would be

c - 1 0
a - 0 1

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

I think the soluin will work
if tree is

a
c

a 0,1
c 1,0

and thats what the above solution will give

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

@sahil
root - 0,0 - as it is the left most node
root's right child - (-1,-1)

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

Here is my solution in C#. GetHeight method is used to calculate the height of the tree and called once before PrintXY method to calculate the height input.

static int xcoord = 0;

public static int GetHeight(TNode root)
{
if (root == null)
return -1;
else return Math.Max(GetHeight(root.left), GetHeight(root.right)) + 1;
}

public static void PrintXY(TNode node, int level, int height)
{
if (node != null)
{
PrintXY(node.left, level+1, height);
Console.WriteLine(node.data + "," + xcoord++ + "," + (height - level));
PrintXY(node.right, level+1, height);
}
}

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

assuming the tree is perfectly balanced:

int print(node* n, int &count) {
if (!n) return -1;
int height = print(n->left, count) + 1;
printf("%d,%d,%d", n->data, count++, height);
print(n->right, count);
return height;
}
print(root, 0);

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

Initialize baseX, and baseY to -1
Do and inorder traversal, and when processing a node its X and Y co-ordinates are computed as:

X = baseX+1
if (baseY==-1)
Y=0; baseY=height_of_node;
else
Y=height_of_node - baseY

Implementation:

int main() {
printCoord(root,0);
return 0;
}

void printCoord(Node *node, int height) {
if (!node) return;
int x, y;
static int baseX=-1;
static int baseY=-1;
printCoord(node->left,height+1);
x=baseX+1;
if (baseY==-1){
y=0; baseY=height;
}
else y=height-baseY;
cout << node->val << ": (" << x << ", " << y << ")" << endl;
}

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

In my above code forgot to add the recursive call to right Child. Here is the corrected code:

int main() {
printCoord(root,0);
return 0;
}

void printCoord(Node *node, int height) {
if (!node) return;
int x, y;
static int baseX=-1;
static int baseY=-1;
printCoord(node->left,height+1);
x=baseX+1;
if (baseY==-1){
y=0; baseY=height;
}
else y=height-baseY;
cout << node->val << ": (" << x << ", " << y << ")" << endl;
printCoord(node->right,height+1);
}

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

There is a recursive implementation
1.) get the root - in my case since I use a matrix it will be the most left-bottom Character
2.) recursively go inorder --> left (leftY = pY * 2), childX = pX - 1 then print the curr character then rightY = leftY + 1

Here is a java implementation:

public void printInorderCartesian(Character[][] tree) {
int rootX = tree.length - 1, rootY = 0;
printInorderCartesian(tree, rootX, rootY);
}

private void printInorderCartesian(Character[][] tree, int x, int y) {
int childX = x - 1;
int leftY = parentY << 1;
int rightY = leftY + 1;

if (x  >= 0 && y < tree.length) {
printInorderCartesian(tree, childX, leftY)
System.out.println(tree[x][y]);
printInorderCartesian(tree, childX, rightY)
}
}

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

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

Posting implementation for feedback

class Node{
Node left;
Node right;
char data;
};
static int x, y;
void printTree(Node root){
x = -1;
y = -1;
printTreeRecursive(root);
}
void printTreeRecursive(Node root){
if(root == null)
return null;
if(root.left == null && x == -1){
x = 0;
y = 0;
}
if(root.left !=  null){
if(x != -1){
y--;
}
printTreeRecursive(root.left);
y++;
}
System.out.println("%c,%d,%d", root.data, x, y);
x++;
if(root.right != null){
y--;
printTreeRecursive(root.right);
y++;
}
}

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

Tested this. does not work.
it is printing incorrect x, y values

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

I also tested the code and it does work for me using the data set in the question.
What data set are you using for testing?
How did you construct you binary tree?
Did you verify that the contents of your binary tree is correct?
Is there any additional information you can provide to help me reproduce what you might be seeing?

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

@CodeSpace: here is the tree I am constructing:

struct node* root = newNode (1);
root->left = newNode (2);
root->right = newNode (3);
root->left->left = newNode (4);
root->left->right = newNode (5);
root->right->left = newNode (6);
root->right->right = newNode (7);
root->right->left->left = newNode (8);

so it if of the form:

------------------------- 1---------------------------------
---------------------2----------3--------------------------
----------------4-------5----6------7--------------------
-----------------------------8-----------------------------

does the tree make sense?

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

@JustCoding: Thanks. I ran my code against your data set and the results I got is correct. See below. What are the results you are getting? Do you feel the results below is incorrect?

4,0,0
2,1,1
5,2,0
1,3,2
8,4,-1
6,5,0
3,6,1
7,7,0

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

you will note that 1 has 3 levels of nodes below it... so 1 should output 1, 3, 3

also, by the definition I have given above, 8 should output 8, 4, 0 since it is the 4th cardinal in the inorder traversal, and has 0 levels below it...

so I think you first need to find the height of the tree, and then use that value while giving the y-coordinate...

does this make sense?

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

yeah but never mind... it will become complicated if we try this... your solution appears to work fine...

actually @yakku should check and comment on the expected answer and compare against your solution... that will give better picture...

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

The questions states "...leftmost node is placed at point (0,0)..." So, this means that 4 (the left most node) will be at (0,0) and 1's y-axis will be 2 since it is 2 cardinal points on top of our reference point (0,0). 8 y-axis will be -1 since it is 1 cardinal point below the (0,0) reference point.

With the output you are expecting you can not have 4 at (0, 0) which is a requirement from the question.

Does this make sense?

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.