## Amazon Interview Question for Software Engineer / Developers

Country: India
Interview Type: In-Person

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

Rows represent the ancestors and columns represent the children

Hence Root Node is the column with all zeros

Step1. find root node O(m*n)
Step2. using depth first traversal reconstruct the tree O(m*n)

total time = O(m*n)

``````Node createTree(int[][] m){
if(m.length == 0) return null;

//find root node
int r = findRoot(m);

if(r == -1) return null;
Node rn = makeTree(m, r);
}

Node makeTree(int[][] m, r) {
Node curr = new Node(r);
ArrayList<Node> children = null;

for(int col=0; col < m[0].length; col++){
if(m[r][col] == 1){
Node child = makeTree(m, col);
if(children == null){
children = new ArrayList<Node>();
}
}
}
return curr;
}

//return root node or -1 if invalid matrix
// that is if there is a loop in the graph/tree
// or more than one ancestor for a node
int findRoot(int[][] m) {
int root = -1;
for(int col=0; i < m[0].length;col++)
int count = 0;
for(int row=0; row < m.length; row++) {
count = count + m[col][row];
}
if(count == 0) {
//more then one root node
root = col;
}
if(count > 1){
//some node has more than one parent
return -1;
}
}
return root;
}``````

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

In the above approach the space complexity is O(h) where h is the height of the tree. In worst case h=m.

Once can reconstruct the tree with Bread first traversal. But the time and space requirements would be the same.

in the function createTree() finally rn is returned

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

Looks like a topological sort question.

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

I also think so...

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

A tree data structure is such that a node can have only 1 parents, all nodes are connected and no cycles [Wiki is my source].

Leet, your first step is correct to find the root. Then you can simply start with the root and find all its children, connect them to root and also push them to queue. As long as queue is not empty, remove first element from queue, add all its children and push its children to the queue. In the end you will have a tree. [Basically this is kind of reverse BFS]

Why? Since all nodes are connected, you will find all nodes as you traverse the above algorithm. Since all nodes have only one parent, they are pushed into the queue only once and processed only once.

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

I probably don't understand, but when you "find all its children", aren't you also bound to find grandchildren? In other words, assuming that you mean that for a root whose row == r, if you find all m[r][j] == 1, you will find all of the grandchildren and great grandchildren, etc as well, right? Do you connect them to root and push them to queue as well?

It seems like the other solutions listed here also do not take this into account, so maybe there is something I am missing. Thanks.

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

when you find the root,set the matrix[row][root] =0 nad the row of of root as -1,find the rows with all zeroes to find the children

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

How about putting in the Queue during BFS of the tree the <children,parent> pair when we traverse the adjacent list of parent. So that when we dequeue from the Q, it becomes easy to connect the dequeued node to the parent easily without any confusion. Else we will have to search over n over again to find the correct parent of the node with the provided matrix.

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

Few observations i found while looking at the matrix.

No of 1s in the column denotes the level of a given node.
This could be used to speed up or understand the finding of next nodes to be put in the queue.

e.g. column with 0 1's is the root and the column with 2 1's are level 2 and so on.

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

won't root be element with column =0's coz A[0][i] ain't its ancestor, A[1][i] isn't...A[n][i] isn't its ancestor.?

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

Why do you need a queue for it? Can't you just recurse? I know it will utilize the stack. But writing code would be simpler.
1) Create a node
2) Iterate through the node's row in matrix
3) recursively call the function to create the node.
4) Add the completed child to the child list

we can get away with queues

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

public class BuildTreeFromAncesterMatrix {
public static final int[][] matrix = new int[][] {
{0, 1, 0, 1, 0},
{0, 0, 1, 0, 1},
{0, 0, 0 ,0, 0},
{0, 0, 0, 0, 0},
{0, 0, 0, 0, 0}
};

public static final int size = 5;
public static final int ary = 3;

public class TreeNode {
public TreeNode(int name) {
this.name = name;
}
public TreeNode[] children = new TreeNode[ary];
public int name;
}

@Test
public void test() {
printSubTree(buildTree());
}

public void printSubTree(TreeNode node) {
String str;
str = node.name + " children: ";
int index = 0;
while(node.children[index++] != null) {
str += node.children[index -1].name + " ";
printSubTree(node.children[index -1]);
}
System.out.println(str);
}

public TreeNode buildTree() {
TreeNode[] nodes = new TreeNode[size];
for (TreeNode n : nodes) {
n = null;
}
for (int i = 0; i < size; ++i) {
}
for (int j : head) {
if (j == 0)
}
}

public TreeNode leave(TreeNode[] nodes, int i, int[] head) {
if (nodes[i] != null) return nodes[i];
nodes[i] = new TreeNode(i);
int index = 0;
for (int j = 0; j < size; ++j) {
if (matrix[i][j] == 1) {
}
}
return nodes[i];
}

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

public class BuildTreeFromAncesterMatrix {
public static final int[][] matrix = new int[][] {
{0, 1, 0, 1, 0},
{0, 0, 1, 0, 1},
{0, 0, 0 ,0, 0},
{0, 0, 0, 0, 0},
{0, 0, 0, 0, 0}
};

public static final int size = 5;
public static final int ary = 3;

public class TreeNode {
public TreeNode(int name) {
this.name = name;
}
public TreeNode[] children = new TreeNode[ary];
public int name;
}

@Test
public void test() {
printSubTree(buildTree());
}

public void printSubTree(TreeNode node) {
String str;
str = node.name + " children: ";
int index = 0;
while(node.children[index++] != null) {
str += node.children[index -1].name + " ";
printSubTree(node.children[index -1]);
}
System.out.println(str);
}

public TreeNode buildTree() {
TreeNode[] nodes = new TreeNode[size];
for (TreeNode n : nodes) {
n = null;
}
for (int i = 0; i < size; ++i) {
}
for (int j : head) {
if (j == 0)
}
}

public TreeNode leave(TreeNode[] nodes, int i, int[] head) {
if (nodes[i] != null) return nodes[i];
nodes[i] = new TreeNode(i);
int index = 0;
for (int j = 0; j < size; ++j) {
if (matrix[i][j] == 1) {
}
}
return nodes[i];
}

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

1. Traverse the matrix in row order and calculate the sum of each row.
2. Create lists of row numbers corresponding to every sum. 0 will have only 1 row, 1 will have n row numbers, and so on. Each of these lists now represent the levels of n-ary tree.
3. Now start with list with sum 0 and create root node. Add all row numbers contained in list sum 1 as children of the root node.
4. Now set root node column to 0 for all rows. So level 2 rows will just have their parent's column set as 1. For all level 2 rows find the only column set as 1 and add current row as a child of that node.

Repeat for all levels.

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

Simple way:

1. Calculate the sum of each row. and wave it in an array.(0(n2))

Now Loop into this arr ( till you hit all the non zero elements (O(n2)))
1. each time find for least element and delete that element from array.
2. take the node which corresponds to the selected element from the array.
3. Add all its children if the are not added to any of the other nodes earlier.

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.