Amazon Interview Question Software Engineer / Developers

  • amazon-interview-questions
    0
    of 0 votes
    15
    Answers

    Create the n-ary tree from the ancestor matrix.
    matrix[i][j]=1 if i is the ancestor of j.
    My answer-
    find the root (row with all zeroes).
    Set the column with a[i][root] =0
    find all the rows with all zeroes.insert into the tree all the children.and push all into the queue.
    pop and find the children ,insert into the tree with popped node as parent and push into the queue.
    Can not implement properly as it needed some modifications.
    This is asked from my friend at amazon bangalore.

    - grave on July 19, 2012 in India Report Duplicate | Flag
    Amazon Software Engineer / Developer Algorithm Arrays Data Structures Trees and Graphs

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>();
			}
			children.add(child);
		}
	}
	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;
	boolean alreadyFound = false;
	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
			if(alreadyFound) return -1;
			alreadyFound = true;
			root = col;
		}
		if(count > 1){
			//some node has more than one parent
			return -1;
		}
	}
	return root;
}

- Praveen Kumar on July 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Praveen Kumar K J V S on July 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Looks like a topological sort question.

- Anonymous on July 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I also think so...

- kurskk141 on July 20, 2012 | Flag
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.

- axecapone on July 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- jvo on July 20, 2012 | Flag
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

- grave on July 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Just a thought. Pls provide your comments.

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.

- mr on July 31, 2012 | Flag
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.

- mr on July 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.?

- Second Attempt on September 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anjana on October 05, 2012 | Flag
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;
}
int[] head = new int[size];
for (int i = 0; i < size; ++i) {
leave(nodes, i, head);
}
TreeNode headNode = null;
for (int j : head) {
if (j == 0)
headNode = nodes[j];
}
return headNode;
}


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) {
head[j] = 1;
nodes[i].children[index++] = leave(nodes, j, head);
}
}
return nodes[i];
}

- gfan on July 20, 2012 | Flag Reply
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;
}
int[] head = new int[size];
for (int i = 0; i < size; ++i) {
leave(nodes, i, head);
}
TreeNode headNode = null;
for (int j : head) {
if (j == 0)
headNode = nodes[j];
}
return headNode;
}


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) {
head[j] = 1;
nodes[i].children[index++] = leave(nodes, j, head);
}
}
return nodes[i];
}

- gfan on July 20, 2012 | Flag Reply
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.

- romilshah29 on July 25, 2012 | Flag Reply
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.

- Anonymous on September 03, 2012 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through 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