## 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
of 0 votes

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
of 0 votes

Thanks for pointing out. I have corrected it.

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

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
of 0 votes

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
of 0 votes

@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;
}
}
}
}``````

}

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