## Amazon Interview Question for SDE-2s

Country: United States
Interview Type: In-Person

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

``````package com.test;

import java.util.ArrayList;
import java.util.List;

public class TreeAsAMatrix {
public static void main(String[] args) {
printTree(tree);
}

boolean[][] matrix = new boolean[6][];
//                                           0      1      2      3      4      5
matrix[0] = new boolean[] { false, true , true , true , true , true  };
matrix[1] = new boolean[] { false, false, false, false, false, false };
matrix[2] = new boolean[] { false, false, false, false, false, false };
matrix[3] = new boolean[] { false, false, false, false, false, false };
matrix[4] = new boolean[] { false, false, false, false, false, false };
matrix[5] = new boolean[] { false, false, false, false, false, false };

return matrix;
}

private static TreeNode buildTree(boolean[][] adj) {
for(int i=0; i < adj.length; i++) {
for(int j=0; j < adj.length; j++) {
if (nodes[i] == null)
nodes[i] = new TreeNode(i);
if (nodes[j] == null)
nodes[j] = new TreeNode(j);
hasParent[j] = true;
}
}
}

for(int i=0; i < hasParent.length; i++)
if(nodes[i] != null && !hasParent[i])
return nodes[i];

return null;
}

private static void printTree(TreeNode root) {
if(root == null)
System.out.println("Tree is empty");
else
printNode(root, "");
}

private static void printNode(TreeNode node, String prefix) {
System.out.println(prefix + " -> " + node.data);
for(TreeNode child : node.children)
printNode(child, prefix + "   ");
}

private static class TreeNode {
int data;
List<TreeNode> children = new ArrayList<TreeNode>();
TreeNode(int data) {
this.data = data;
}
}

}``````

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

We can say , the Adjancy matrix representation of the graph is given , You have to create the tree from given 2D matrix.

I would have some other question as well to the Interviewer such as-
1- Graph is also a kind of tree , Printing a graph is answer? If yes then I will use BFS to print it.
If No.
2- How many child a tree can maximum have ?
Lets say 2
Then i will have to do following things-
1- Find the root Node from the graph, we can get the root by traversing the matrix and put every child in the set . One node must not be part of that set. That will be root.
2- Once we got the root... We can create a node in tree with root value.
3- Start DFS from root node and insert every node one by one.

We have to use DFS here because it will be easy to pass the parent as well with child to the calling function.

Node class for tree

``````class Node {
int val;
Node left, right;

public Node(int val) {
this.val = val;
}
}``````

``````public Node dfs(Node parent, int child, boolean visited[],int[][] G) {
Node temp = new Node(child);
visited[child] = true;

if (parent.left == null) {
parent.left = temp;
}else {
parent.right = temp;
}
int n = G.length;
for(int j=0;j<n;j++)
if(!visited[j] && G[child][j]==1)
dfs(temp,j,visited,G);
return parent ;
}``````

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

``````package main

import "fmt"

type Node struct {
Value    int
Children []*Node
}

func PrintTree(root *Node) {
fmt.Print(root.Value, " -> {")
for _, node := range root.Children {
fmt.Print(node.Value, " ")
}
fmt.Println("}")
for _, node := range root.Children {
PrintTree(node)
}
}

func MakeTree(matrix [][]bool) *Node {
nodes := make([]*Node, len(matrix))
hasParent := make([]bool, len(matrix))
for i := 0; i < len(matrix); i++ {
for j := 0; j < len(matrix); j++ {
if matrix[i][j] {
if nodes[i] == nil {
nodes[i] = &Node{i, []*Node{}}
}
if nodes[j] == nil {
nodes[j] = &Node{j, []*Node{}}
}
nodes[i].Children = append(nodes[i].Children, nodes[j])
hasParent[j] = true
}
}
}
for i := 0; i < len(hasParent); i++ {
if !hasParent[i] {
return nodes[i]
}
}
return nil
}

func main() {
matrix := make([][]bool, 6)
matrix[0] = []bool{false, true, true, true, false, false}
matrix[1] = []bool{false, false, false, false, false, false}
matrix[2] = []bool{false, false, false, false, true, true}
matrix[3] = []bool{false, false, false, false, false, false}
matrix[4] = []bool{false, false, false, false, false, false}
matrix[5] = []bool{false, false, false, false, false, false}
PrintTree(MakeTree(matrix))
}``````

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

//Node number and list of childrens it has.
HashMap<Integer,ArrayList<Integer>> hm = new HashMap();

//Will be used to find root
boolean is_child_of_someone[n+1];

rows = n;
cols = n;
for(i<rows)
{
for(j<cols)
{
//If j is child of i
if(mat[i][j] == 1)
{
if(!hm.containsKey(i))
hm.put(i,new ArrayList());

//as j is child of i
is_child_of_someone[j] = true;
}
}
}

int root=-1;

//Finding root
for( i<n )
{
if(!is_child_of_someone[i])
{
root = i;
break;
}
}

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

``````//Node number and list of childrens it has.
HashMap<Integer,ArrayList<Integer>> hm = new HashMap();

//Will be used to find root
boolean is_child_of_someone[n+1];

rows = n;
cols = n;
for(i<rows)
{
for(j<cols)
{
//If j is child of i
if(mat[i][j] == 1)
{
if(!hm.containsKey(i))
hm.put(i,new ArrayList());

//as j is child of i
is_child_of_someone[j] = true;
}
}
}

int root=-1;

//Finding root
for( i<n )
{
if(!is_child_of_someone[i])
{
root = i;
break;
}
}``````

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

``````import java.util.*;
public class MatrixToTree
{
public static void main(String args[])
{
int[][] mat = {{0, 1, 0, 0, 0},
{0, 0, 1, 0, 0},
{0, 0, 0, 1, 0},
{0, 0, 0, 0, 1},
{0, 0, 0, 0, 0}};
MatrixToTree  m = new MatrixToTree();
TreeNode root = m.create(mat);
m.print(root);

}

public TreeNode create(int[][] mat)
{
Map<Integer, TreeNode> map = new HashMap<>();

for(int i=0;i<mat.length;i++)
{
for(int j=0;j<mat[i].length;j++)
{
if(mat[i][j]==1)
{
helper(i, j, map);
}
}
}

int root = findRoot(mat);
return map.get(root);
}

private void helper(int p, int c, Map<Integer, TreeNode> map)
{
TreeNode parent = map.getOrDefault(p, new TreeNode(p));
TreeNode child = map.getOrDefault(c, new TreeNode(c));

map.put(p, parent);
map.put(c, child);
}

private int findRoot(int[][] mat)
{
for(int col = 0; col<mat[0].length; col++)
{
boolean isRoot = true;
for(int row = 0; row<mat.length; row++)
{
if(mat[row][col]==1)
{
isRoot = false;
break;
}
}
if(isRoot)
return col;
}
return -1;
}

private void print(TreeNode root)
{
Queue<TreeNode> curr = null;
next.offer(root);

while(!next.isEmpty())
{
curr = next;

while(!curr.isEmpty())
{
TreeNode temp = curr.poll();
System.out.print(temp.val+"\t");
for(TreeNode child: temp.children)
{
next.offer(child);
}
}
System.out.println();
}
}
}

class TreeNode
{
int val;
List<TreeNode> children;

TreeNode(int val)
{
this.val= val;
children = new ArrayList<>();
}

public String toString()
{
return val+ ": "+children;
}
}``````

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.