## Amazon Interview Question for Software Engineer / Developers

Country: India
Interview Type: In-Person

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

``````int a[n][n] = 0;

setArray(std::vector<int> arr, node)
{

if(node == NULL)
return;

arr.push_back(node->val);

setArray(arr, node->left);
setArray(arr, node->right);

arr.pop_back();

for (std::vector<int>::iterator it = myvector.begin() ; it != myvector.end(); ++it)
a[*it][node->val] = 1;

}``````

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

Perhaps you want to replace myvector with arr in the for loop.

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

Do a level order traversal. Remember for null leaves enter blank in an array
eg
1
2 3
4 6 7

post order traversal is : 1234_67
Now here we follow the property that child will always be at 2i and 2i+1 index or vise versa parent is always at |i/2| index
therefore parent of 1 will be no one
parent of 2 = 2/2 = 1 i.e 1
parent of 3 = 3/2 = 1 i.e 1
parent of 4 = 4/2 = 2 i.e 2 and rest copy from 2
parent of 6 = 6/2 = 3 i.e 3 and rest copy from 3
parent of 7 = 7/2 = 3 i.e 3 and rest copy from 3

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

nice solution.

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

The tree is numbered as 1...N so the tree that you have taken as an example will actually be :

--------1
------2---3
----4----5--6

where 2 doesn't have a right child so you're formula will not work here.

To apply your concept you need to change the numbers of each node but then you won't be able to find the right index of that node in the matrix.

Another solution will be to keep another value associated with each node but will cost you Θ(N) space complexity.

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

Ashish can you please explain how it will not work>
For no right child I am using a blank in the array.

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

This will work only if tree is balanced, another solution is you can use DFS as you reach node b put Arr[a][b] =1 for all a (nodes present in the stack of DFS)

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

parent of 2nd index element = 2/2 = 1st index element
parent of 3rd index element = 3/2 = 1st element element
parent of 4th index element = 4/2 = 2nd index element
and rest copy from 2

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

To find all ancestor relationship, you do an in-order traversal of the tree using recursion, while keeping the current path from the root in a stack by pushing each node we traverse into the stack (and popping it when we are done with it). To find the ancestors of a node, we iterate the items in the stack and mark an ancestor relationship between each item and the current node.

The time complexity is O(Nh) because we iterate all the nodes in the tree which is O(N), and for each node we iterate all its ancestors, which is O(h) - the height of the tree. Since h=O(N) in the worst case (if the tree is single list), then the time is O(N^2), which is optimal because the number of possible ancestor relationships is N^2 (the size of the matrix).

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

If the tree is balanced then h=O(log N), thus the time complexity is O(N log N).

The space complexity is O(h), which is O(N) for unbalanced tree or O(log N) for a balanced tree.

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

@gen-y-s: I think what you mean is this right?:
Suppose you have binary tree of this form:

``````8
6        11
5   7   10   12``````

We have postorder code as below which is slightly modified:

``````postorder(node)
if node == null then return
put_in_stack(node)
postorder(node.left)
postorder(node.right)
visit(node)``````

algorithm:
1.Start doing post order traversal.
2.put all the nodes in the stack as shown above i.e. basically all the paths from root to the current node.
3. Once you reach the node i.e. visit(node) in the above algorithm then just pop the node and do as below:
while(reach from bottom to top of stack) {
element = bottom_of_stack;
matrix[element][popped_node]=1.
bottom_of_stack++
}

code below:

``````#include<stdlib.h>
#include<stdio.h>

struct bin_tree {
int data;
struct bin_tree * right, * left;
};
typedef struct bin_tree node;

void insert(node ** tree, int val)
{
node *temp = NULL;
if(!(*tree))
{
temp = (node *)malloc(sizeof(node));
temp->left = temp->right = NULL;
temp->data = val;
*tree = temp;
return;
}

if(val < (*tree)->data)
{
insert(&(*tree)->left, val);
}
else if(val > (*tree)->data)
{
insert(&(*tree)->right, val);
}

}

void print_postorder(node * tree)
{
if (tree)
{
printf("stack %d\n", tree->data);
print_postorder(tree->left);
print_postorder(tree->right);
printf("%d\n",tree->data);
}
}

void main()
{
node *root;
node *tmp;

root = NULL;
/* Inserting nodes into tree */
insert(&root, 8);
insert(&root, 6);
insert(&root, 11);
insert(&root, 5);
insert(&root, 7);
insert(&root, 10);
insert(&root, 12);

printf("Post Order Display\n");
print_postorder(root);
}``````

``````dry run:
stack 8
stack 6
stack 5
5           {8,5} {6,5} ---> set the matrix and pop 5 from stack.
stack 7
7           {8,7} {6,7} ---> set the matrix and pop 7 from stack.
6           {8,6}         ---> set the matrix and pop 6 from stack.
stack 11
stack 10
10             {8,10} {11,10}         ---> set the matrix and pop 10 from stack.
stack 12
12            {8,12} {11,12}         ---> set the matrix and pop 12 from stack.
11             {8,11}                     ---> set the matrix and pop 11 from stack.
8              --->pop it off :)``````

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

Actually, the tree walk should be in pre-order, since we want to process parents before children.

``````def ancestors(root, mat):
def ancestors_int(node):
if node==None:
return
for item in stack:
mat[item.val][node.val]=1
stack.append(node)
ancestors_int(node.left)
ancestors_int(node.right)
stack.pop()
stack=[]
ancestors_int(root)``````

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

From the definition of Arr[A][B], node A is ancestor of B. So for Arr[i][j] j has i as ancestor and all ancestors of i are also ancestors of j. So for all i in Arr[i][j] copy Arr[k][i] == 1.
Start traversing the binary tree in level order fashion and update ancestors of parent node for the current node as the ancestors of the current node.

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

I guess its to write code to create the array Arr, isn't it?
Or something else is required?

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

A modified preorder traversal will do
Find my code snippets

``````public class Node {
int value;
Node leftChild;
Node rightChild;
Node parent;

public Node(int nodeVal) {
value = nodeVal;
leftChild = null;
rightChild = null;
parent = null;
}
}

private void modifiedPreOrderTraversal(Node currNode, int[][] ancestorMatrix) {
if(currNode == null) return;
else {
if(currNode.parent != null) {
int currNodePositionInAncestorMatrix = -1;
int parentNodePositionInAncestorMatrix = -1;
for(int i = 0; i < inputNodes.length; i++) {
if(inputNodes[i] == currNode.value) currNodePositionInAncestorMatrix = i;
if(inputNodes[i] == currNode.parent.value) parentNodePositionInAncestorMatrix = i;
}
//Parent Node of Current Node
ancestorMatrix[parentNodePositionInAncestorMatrix][currNodePositionInAncestorMatrix] = 1;

//Ancestor updation of Current Node
for(int i = 0; i < inputNodes.length; i++) {
if(ancestorMatrix[i][parentNodePositionInAncestorMatrix] == 1)
ancestorMatrix[i][currNodePositionInAncestorMatrix] = 1;
}
}
modifiedPreOrderTraversal(currNode.leftChild, ancestorMatrix);
modifiedPreOrderTraversal(currNode.rightChild, ancestorMatrix);
}
}

public int[][] getAncestorMatrix() {
int[][] ancestorMatrix = new int[inputNodes.length][inputNodes.length];
for(int i = 0; i < inputNodes.length; i++)
for(int j = 0; j < inputNodes.length; j++)
ancestorMatrix[i][j] = 0;

return ancestorMatrix;
}``````

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

If the tree is balanced then h=O(log N), thus the time complexity is O(N log N).

The space complexity is O(h), which is O(N) for unbalanced tree or O(log N) for a balanced tree.

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

``````void updateMatrixfromBinaryTree(int Arr[][], int parent[], node)
{
if(node.left == null && node.right == null)
{
//update all the parents of each leaf node to 1
for each(parent p in parent[])
{
a[p][node.data] = 1;
}
return;
}
updateMatrixfromBinaryTree(Arr[][],parent[],node.leftchild);
updateMatrixfromBinaryTree(Arr[][],parent[],node.rightchild);
}``````

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

Question here might resemble to some graph theory.May be Prim's Algo can be implemented here.

First, row first column will have all 0's.
Second row will have 1's to only those who are their ancestor. Now Algo follows the same pattern Subsequently except on one occasion, where if the node parent has marked 1 on its ancestor to some other node, then this node also have to mark 1 for that node .

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

@hprem991: can you explain more?

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

My solution for this problem. The complexity is O(N*N).

``````typedef struct Node{
Node *left, *right;
int val, id;
};

void ancestor(Node * parent, Node *node, int **arr, int n) {
if (node == NULL)
return;
int n_id = node->id;
if (parent != NULL) {
int p_id = parent->id;
for (int i = 0; i < n; i++) {
arr[i][n_id] = arr[i][p_id];
}
arr[p_id][n_id] = 1;
}
ancestor(node, node->left, arr, n);
ancestor(node, node->right, arr,n);
}``````

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

``````public void UpdateMatrix(Node node, int[,] matrix)
{
if (node == null)
return;

if (node.Left != null)
{
UpdateMatrix(node.Left, matrix);
for (int i = 0; i < matrix.GetLength(1); i++)
matrix[node.Value - 1, i] = matrix[node.Value - 1, i] | matrix[node.Left.Value - 1, i];
matrix[node.Value - 1, node.Left.Value - 1] = 1;
}

if (node.Right != null)
{
UpdateMatrix(node.Right, matrix);
for (int i = 0; i < matrix.GetLength(1); i++)
matrix[node.Value - 1, i] = matrix[node.Value - 1, i] | matrix[node.Right.Value - 1, i];
matrix[node.Value - 1, node.Right.Value - 1] = 1;
}
}``````

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

may add try-catch block if the matrix assignment cause any IndexOutOfRangeException.

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

is there duplicate in this tree?

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

``````public static void treeToMatrix(Node node, int[][] a, Stack<Node> s) {
s.push(node);
if (node.getLeft() != null) {
treeToMatrix(node.getLeft(), a, s);

Node c = s.pop();
for (Node n : s) {
a[n.getValue()][c.getValue()] = 1;
}
}

if (node.getRight() != null) {
treeToMatrix(node.getRight(), a, s);

Node c = s.pop();
for (Node n : s) {
a[n.getValue()][c.getValue()] = 1;
}
}
}``````

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

public static List<Node> list=new List<Node>();
public static int[,] matrix=new int[n,n];
public static void Matrix(Node root,)
{
if(root==null)
return;
Matrix(root.Left);
Matrix(root.Right);
list.Remove(list[list.count-1]);
for(int i=0;i<list.count;++i)
{
matrix[list[i].ID,root.ID]=1;
}
}

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

``````struct TreeNode
{
TreeNode* left;
TreeNode* right;
bool visited;
int id;
};

struct DFSNode
{
TreeNode* node;
DFSNode* next;
DFSNode* prev;
};

void MarkAncestors(TreeNode* root, int Arr[][])
{
DFSNode* visitStack = new DFSNode();
visitStack->node = root;
DFSNode* top = visitStack;

while(top != NULL)
{
TreeNode* tn = top->node;

if(tn->left && !tn->left->visited)
{
tn->left->visited = true;

DFSNode* newChild = new DFSNode();
newChild->node = tn->left;

Arr[tn->id][tn->left->id] = 1;

top->next = newChild;
newChild->prev = top;
top = newChild;
}
else if(tn->right && !tn->right->visited)
{
tn->right->visited = true;

DFSNode* newChild = new DFSNode();
newChild->node = tn->right;

Arr[tn->id][tn->right->id] = 1;

top->next = newChild;
newChild->prev = top;
top = newChild;
}
else
{
DFSNode* old = top;
top = top->prev;

if(top != NULL)
{
top->next = NULL;
}

delete old;
}
}
}``````

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

Hi. So what is the question.

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

Construct the matrix.

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

1. Perform the Inorder traversal and insert nodes into an array (therefore, the entries are sorted). Then:

``````for(i=1;i<n;i++)
{
for(j=i-1;j>=0;j--)
a[i][j]=1;
}``````

However, the complexity is O(n^2)

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

arr[i][j]=1 if i is parent of j
arr[i][j]=1 if arr[i][parent of j]=1 i.e. i is ancestor of j if it is ancestor or parent of (parent of j)
else it remains zero...

and traverse the tree in level order traversal....
if the numbers are in increasing order from root to bottom in left to right fashion then no need for level order traversal...

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.