## Amazon Interview Question for Software Engineer / Developers

Team: SDE
Country: India
Interview Type: In-Person

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

``````int matrix[N][N] = {0};

int main()
{
//Build a tree of n elements
int arr[N];  // This array is used to store paths from root to leaf
ancestorMatrix(root, arr, 0);
return 0;
}

void ancestorMatrix(struct node *root, int arr[], int level, int matrix[])
{
if (!root)
return;
for(int i = level - 1; i >= 0; i --)
matrix[root->data][result[i]] = 1; // The array contains all the predecessors of the current node
result[level++] = node->data; //Add your current node to the path array and send this array to its descendants
if (root->left)
ancestorMatrix(root->left, arr, level, matrix);
if (root->right)
ancestorMatrix(root->right, arr, level, matrix);
}``````

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

Little mistake i think. In the loop it should be matrix[root->data][result[i]] = 1;

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

Thanks for pointing out. I have corrected it.

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

What is the use of result array ? You havnt specified its use

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

Not exactly sure what the binary tree has to do with the matrix? Can you explain in more detail?

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

Just a basic doubt, r the elements of tree have values from 1.....n only or can have any value?

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

Yes, the values of nodes can be from 1 to n and every node has a unique value.

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

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

struct tNode
{
int d;
struct tNode* l;
struct tNode* r;
};
struct tNode* newtNode(int data)
{
struct tNode* tNode = (struct tNode*)
malloc(sizeof(struct tNode));
tNode->d = data;
tNode->l = NULL;
tNode->r = NULL;

return(tNode);
}
void fillMat(struct tNode *root,int mat[][5],int count)
{
if(root==NULL)
return;

if((root->l!=NULL) && (root->r!=NULL))
{
mat[root->d-1][(root->l)->d-1]=1;
mat[root->d-1][(root->r)->d-1]=1;
}
else if((root->l!=NULL) && (root->r==NULL))
{
mat[root->d-1][(root->l)->d-1]=1;
}
else if((root->l==NULL) && (root->r!=NULL))
{
mat[root->d-1][(root->r)->d-1]=1;
}
else
{
return;
}
fillMat(root->l,mat,count);
fillMat(root->r,mat,count);
}
/* Driver program to test above functions*/
int main()
{

/* Constructed binary tree is
1
/ \
2 3
/ \
4 5
*/
int mat[5][5];
int i,j;

struct tNode *root = newtNode(1);
root->l = newtNode(2);
root->r = newtNode(3);
root->l->l = newtNode(4);
root->l->r = newtNode(5);
for(i=0;i<5;i++)
{
for(j=0;j<5;j++)
{
mat[i][j]=0;
}
}
fillMat(root,mat,0);
for(i=0;i<5;i++)
{
for(j=0;j<5;j++)
{
printf("%d",mat[i][j]);
}
printf("\n");
}
return 0;
}

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

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

struct tNode
{
int d;
struct tNode* l;
struct tNode* r;
};
struct tNode* newtNode(int data)
{
struct tNode* tNode = (struct tNode*)
malloc(sizeof(struct tNode));
tNode->d = data;
tNode->l = NULL;
tNode->r = NULL;

return(tNode);
}
void fillMat(struct tNode *root,int mat[][5],int count)
{
if(root==NULL)
return;

if((root->l!=NULL) && (root->r!=NULL))
{
mat[root->d-1][(root->l)->d-1]=1;
mat[root->d-1][(root->r)->d-1]=1;
}
else if((root->l!=NULL) && (root->r==NULL))
{
mat[root->d-1][(root->l)->d-1]=1;
}
else if((root->l==NULL) && (root->r!=NULL))
{
mat[root->d-1][(root->r)->d-1]=1;
}
else
{
return;
}
fillMat(root->l,mat,count);
fillMat(root->r,mat,count);
}
/* Driver program to test above functions*/
int main()
{

/* Constructed binary tree is
1
/ \
2 3
/ \
4 5
*/
int mat[5][5];
int i,j;

struct tNode *root = newtNode(1);
root->l = newtNode(2);
root->r = newtNode(3);
root->l->l = newtNode(4);
root->l->r = newtNode(5);
for(i=0;i<5;i++)
{
for(j=0;j<5;j++)
{
mat[i][j]=0;
}
}
fillMat(root,mat,0);
for(i=0;i<5;i++)
{
for(j=0;j<5;j++)
{
printf("%d",mat[i][j]);
}
printf("\n");
}
return 0;
}

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

@Nascent: Your solution s wrong one.... coz it should consider all predecessors not oly the immediate one..

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

Copy the predecessors of parent of the node and also mark parent as the predecessor of node

Assume node->val represents node ID in the matrix.

void mark_pred(tree *root, tree * parent, int *M)
{
if(root == NULL) return;
if(parent != NULL){
for (i=0; i < n; i++){
if(M[i][parent->val] == 1)
M[i][root->val = 1;
}
M[parent->val] [root->val] = 1;
}

mark_pred(root->left,root,M);
mark_pred(root->right,root,M);
}

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

I think pre order traversal should work. During pre order traversal, we can check node's left and right
child.
public void preOrder(Node root, Integer i, int[][] matrix){
if(root==null) return;
int parentIndex = i.intValue();
if(root.left() != null){
matrix[parentIndex][i++] = 1;
preOrder(root.left(), i, matrix);
}
if(root.right() != null){
matrix[parentIndex][i++] = 1;
preOrder(root.right(), i, matrix);
}
}

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

``````M = An nxn matrix initialized to all False

def pred(root, M):
if root != None:
# dfs
pred(root.left, M)
pred(root.right, M)
row = M[root.data]
row[root.data] = True # every node is in pred relationship with itself
if root.left != None:
row = row or M[root.left.data]
if root.right != None:
row = row or M[root.right.data]``````

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

``````public static int[][] predecessorMatrix(BinaryTreeNode<Integer> root, int n) {
int[][] matrix = new int[n][n];
dofindAncestorsOfNodes(root, matrix);
return matrix;
}

private static void dofindAncestorsOfNodes(BinaryTreeNode<Integer> root, int[][] matrix) {

if (root == null) {
return ;
}

if (root.hasLeftChild()) {
dofindAncestorsOfNodes(root.getLeft(),  matrix);
}
if (root.hasRightChild()) {
dofindAncestorsOfNodes(root.getRight(),  matrix);
}

if (root.isLeafNode()) {
return ;
}

if (root.hasLeftChild()) {
matrix[root.getData()][root.getLeft().getData()] = 1;
int[] row = matrix[root.getLeft().getData()];
for (int i = 0; i < row.length; i++) {
if (row[i] == 1) {
matrix[root.getData()][i] = 1;
}
}

}
if (root.hasRightChild()) {
matrix[root.getData()][root.getRight().getData()] = 1;
int[] row = matrix[root.getRight().getData()];
for (int i = 0; i < row.length; i++) {
if (row[i] == 1) {
matrix[root.getData()][i] = 1;
}
}
}
}``````

}

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.