## Amazon Interview Question for SDE1s

Country: United States

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

O(n) Solution will be to use recursion in each node to append the path generated from it via right subtree and via left subtree in a list

``````private static ArrayList<String> pathList = new ArrayList<String>();
private static ArrayList<String> computePath(Tree tree){
ArrayList<String> path = new ArrayList<String>();
ArrayList<String> leftPath = new ArrayList<String>();
ArrayList<String> rightPath = new ArrayList<String>();
if(tree.left==null && tree.right==null){
String pathFromNode = String.valueOf(tree.data);
return path;
}
if(tree.left!=null){
leftPath = computePath(tree.left);
for(int i=0;i<leftPath.size();i++){
String pathFromNode = String.valueOf(tree.data);
pathFromNode = pathFromNode +  " -> " + leftPath.get(i);
}
}
if(tree.right!=null){
rightPath = computePath(tree.right);
for(int i=0;i<rightPath.size();i++){
String pathFromNode = String.valueOf(tree.data);
pathFromNode = pathFromNode +  " -> " + rightPath.get(i);
}
}
return path;
}

public static ArrayList<String> getAllPaths(Tree tree){
computePath(tree);
return pathList;
}``````

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

Not a o(n) solution see in recursion for traversing each node we will have linear time.
For each Node u r looping through the list which will also have o(h) time if h is the height of tree and internally String.valueOf() method will also run with linear time.

So ur code will work in linear time if height is smaller . But for larger trees it is certainly not linear.

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

Generate all paths

``````public void allPaths(Node root , Node [] path,HashMap<String ,String>cycle)
{
if(root == null)
{
for(int i=0;i<path.size();i++)
{     System.out.println("");
for(int j=i;j<path.size();j++)
{
System.out.print(path[j].ndoename + " --");
}
}
else
{
if(! cycle.containsKey(root.nodename)
{
cycle.put(root.nodename,root.nodename);
allPaths(root.left ;path,cycle);
allPaths(root.right,path,cycle);
}
}
}``````

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

from Quora

``````Start with the root. Push root node to stack.
while(stack not empty)   //i'll take top=top_of_stack
mark top as visited
if(top.left_node exists AND not_visited)
push(top.left_node)
else if(top.right_node exists AND not_visited)
push(top.right_node)
else      //Leaf node
print stack
pop``````

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.