## Amazon Interview Question

Country: United States

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

Without further assumptions, this binary tree may be just a line with depth N. Hence, in such cases, each node has O(N) predecessors. So, just writing the results to the matrix uses O(N^2)

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

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

I have to say the same about you. Predecessor != Parent

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

i not know what exact mean of Predecessor but i think it should be any node that come before a node in in order travesal all are Predecessor

``````6
/ \
2   3

i think for 3 there are two Predecessor  2 & 3 bcoz both come before 3 in in order travesal...

plz correct me if i am wrong``````

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

I believe the predecessor term here is the same as ancestor. Meaning that a predecessor appears in the path between the root and the node.

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

Not sure what it means by doing it better than in O(N^2). The number of array elements is O(N^2) and it takes at least O(N^2) steps to initialize the matrix. Also, is a node predecessor of itself?

Suppose the matrix was initialized with 0s. The next steps are to put 1s in it satisfying the above criterion.

Use recursion to solve this problem. During the unwinding of recursion -
1) If you are at the leaf node, do nothing.
2) else
2a. Copy 1s from the rows of left and right children
2b. Set M[currentNode][leftChild] = 1 and, M[currentNode][rightChild] = 1

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

If we must initialize matrix always, we can exclude matrix initialization from bing O analysis and please read what does the term predecessor mean

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

I guess the O(n^2) constraint is on reading the binary tree i.e. don't read it n times. For filling up the array we do need O(n^2) time. Here is one approach
The predecessors of a node are the predecessors of its parent + its parent.
Using this logic we need to read the binary tree only once.
Tree traversal will be done as preorder.

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

that doesn't help. each parent's predecessors in the matrix still has O(N) elements. it still is O(N^2)

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

XOR is full of him/herself.

First, "better than O(n^2)" is a meaningless statement! This shows a clear lack of understanding of what BigOh really means.

Repeat after me: BigOh is an UPPER F**K**G BOUND.

Assuming (s)he reallys mean "give an o(n^2) algorithm" (Yes, SmallOh, which is very different from BigOh), then (s)he wants us to fill an n^2 matrix, in o(n^2) time, which is impossible (unless you use some sparse matrix implementation where you pay the initialization cost on access, {yes, that is possible}).

XOR. LOL at ya.

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

Assuming the initial matrix is pre filed with -1 indicating no relationship. we will traverse and set the values.
two scenarios:
1) if its a balanced tree
The height of a balanced binary tree will be maximum logn. we can manage all the predecessors in a stack while doing a traversal(post order). the stack will contain the list of predecessors and for each n nodes there can be maximum logn predecessor. so time complexity is o(nlogn).
2) If its a non balanced tree, in that case worst case is that it can be a skewed tree or a linked list. In can of linked list we need to fill one diagonal half of the entire matrix. That itself is (n^2)/2 cells. Time complexity in that case will be o(n^2).

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

``````#include<iostream>
#include<stdlib.h>
using namespace std;

struct Node
{
int data;
Node *left;
Node *right;
public:
Node(int d = 0, Node * l = NULL, Node * r = NULL): data(d),left(l),right(r)
{

}
};

void Insert(Node **root, int d)
{
if(*root == NULL)
{
*root = new Node(d);
return;
}

Node* temp = *root;

if(temp->data > d)
{
Insert(&(temp->left),d);
}
else if(temp->data < d)
{
Insert(&(temp->right),d);
}
else
{

}
}

void Inorder(Node *root)
{
if(root == NULL) return;

Inorder(root->left);
cout<<root->data<<"  ";
Inorder(root->right);

}

void GetPrecessorder(Node* root,int **m,int &row, int &col)
{
if(root == NULL)
{
return;
}

GetPrecessorder(root->left,m,row,col);

if(row == -1)
{
row = root->data-1;
m[row][col] = root->data;
col++;
}
else
{
m[row][col++] = root->data;
}
GetPrecessorder(root->right,m,row,col);
}
void FillMatrix(Node* root, int**m, int n)
{
if(root == NULL) return;
int row = -1;
int col = 0;
//All precessorder are stored in one row that row not have any precessorder so finally we make that as 0
GetPrecessorder(root,m,row,col);

for(int i = 0; i < n; i++)
{
int r = m[row][i] -1;
for(int j = i-1; j >= 0; --j)
{
int c = m[row][j] - 1;
m[r][c] = 1;
}
}

memset(m[row],0,sizeof(int)*n);
}
int main()
{
Node *root = NULL;

root = new Node(4,NULL,NULL);

Node *a = root->left = new Node(1,NULL,NULL);
Node *b = root->right = new Node(6,NULL,NULL);
a->left = new Node(5,NULL,NULL);

b->left = new Node(3,NULL,NULL);
b->right = new Node(2,NULL,NULL);

int n = 6;

int**m = new int*[n];

//O(n) Time complexity to fill all matrix elements as 0
for(int i = 0; i < n; i++)
{
m[i] = new int[n];
memset(m[i],0,sizeof(int)*n);
}

FillMatrix(root,m,n);

for(int i = 0; i < 6; i++)
{
for(int j = 0; j < 6; j++)
{
cout<<m[i][j]<<"  ";
}
cout<<endl;
}
return 0;
}``````

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

I have 2 assumptions here:
The matrix is already filled with 0s.
The binary tree is full.

Represent the binary tree linearly in an array or a vector.
Calculate the predecessors recursively like this:

``````void getPredecessor(int start, int end)
{
int mid = (start + end) / 2;
for(int i=start; i<=end; i++)
{
predecessor[mid][i] = 1;
}
getPredecessor(start, mid-1);
getPredecessor(mid+1, end);
}``````

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

``````public static void fillMatrix(Node node, List<Node> path)
{
if(node == null)
return;

for(int i = 0 ; i < path.size(); i++)
{
Node previous = path.get(i);
M[previous.order][node.order] = 1;
}

ArrayList<Node> c1 = (ArrayList<Node>) ((ArrayList<Node>) path).clone();
ArrayList<Node> c2 = (ArrayList<Node>) ((ArrayList<Node>) path).clone();

fillMatrix(node.lchild, c1);
fillMatrix(node.rchild, c2);
}``````

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

question: How are we creating this array. What is 'i' and 'j' in arr[i][j] ? Each node in the tree has a number associated with it Or is the number based on some traversal ?

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

``````#include<stdio.h>
#include<stdlib.h>
struct node{
int data;
struct node *left;
struct node* right;
};
int matrix;
struct node *newNode(int data){
struct node *temp = (struct node*)malloc(sizeof(struct node));
temp->data=data;
temp->left=0;
temp->right=0;
}
void binaryTreePathMatrix(struct node *root, int path[], int len){
if(root==0)
return;
path[len]=root->data;
len++;
if(len>=2)
pathPrintOrMatrixFill(path,len-1,root->data);
binaryTreePathMatrix(root->left,path,len);
binaryTreePathMatrix(root->right,path,len);
}
void pathPrintOrMatrixFill(int path[], int len, int data){
int i;
for(i=0;path[i]!=data;i++){
printf("%d",path[i]);
matrix[path[i]][data]=1;
}
printf("\n");
}
void main(){
int path,i,j;
struct node *root = (struct node *)malloc(sizeof(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->left->left->right=newNode(8);
binaryTreePathMatrix(root,path,0);
for(i=0;i<=8;i++){
printf("\n");
for(j=0;j<=8;j++){
printf("%d  ",matrix[i][j]);
}
}
}``````

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

take an array of size n....populate it with the tree elements in BFS form but do not delete the elements......now start traversing the array from the end as such

``````while(i>0)
{
M[arr[i]/2][arr[i]]=1;
i--;``````

}

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

Is it a binary tree or a binary SEARCH tree? Predecessor has no meaning in the term of simple binary trees. (I think.)

In case of a binary search tree you can do an in-order traversal and fill the matrix in linear time assuming that are given a matrix initialized to all 0s by default.

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

I believe the predecessor term here is the same as ancestor. Meaning that a predecessor appears in the path between the root and the node.

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

This is done using dynamic programming

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

This can be done using dynamic programming

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

This can be done using dynamic programming

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

int i = 0, j=0, maxindex=0
Here, level of root is 0
Start traversing the tree level wise,starting from root

for 0<=j<n
arr[j]=1 //Root is predecessor of every node
arr[j]=0 //No node is the predecessor of root

Now since we are traversing level wise, we keep storing nodes which are at the same level in a queue ( Similar to a BFS is graph)
The largest index of the node at a level is stored in maxindex

Populating the matrix : so, once you have traversed the level, you have all the nodes at that level.
Start popping nodes. For every popped node i, make arr[i][j]=1 where j varies from maxindex+1 till n

This way, we traverse the tree once which takes O(n) since every node is just visited once.
The step of populating the matrix, at can take n-1 iterations for every node.

Thus order of solving this question is O(N^2)

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

1. In-order traverse binary tree, and get array of predecessors
2. Fill matrix using the array obtained in step 1
Complexity is O(2n).
Memory is O(n).

``````public class BinaryTreeNode
{
public BinaryTreeNode Left;
public BinaryTreeNode Right;
public int Data;
}

public class BinaryTree
{
public int Size;
public BinaryTreeNode Root;
}

public static int[,] FinPredecessorsMatrix(BinaryTree binaryTree)
{
var size = binaryTree.Size;
var arr = new int[size];
InOrderTraverse(binaryTree.Root, arr, 0);
var matrix = new int[size, size];

for (var i = 1; i < size; i++)
{
matrix[arr[i - 1], arr[i]] = 1;
}

return matrix;
}

private static int InOrderTraverse(BinaryTreeNode node, int[] arr, int index)
{
if (node == null)
return index;
index = InOrderTraverse(node.Left, arr, index);
arr[index] = node.Data;
index++;
return InOrderTraverse(node.Right, arr, index);
}``````

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

char p;
snprintf(p, sizeof(p), "This is a %.4s\n", "test
GARBAGE DATA");

But i am geting This is a 4s??????????????

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.