Amazon Interview Question for Software Engineer / Developers

• 0

Country: India
Interview Type: In-Person

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

i think it can be done using a similar concept of inorder traversal using stack(without recursion).

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

1. Take an array which will contain the pointer of nodes of tree.
2. Start with the index  of the array and put the pointer of root , i.e ar[i] = root;
3. if node has left child put ar[2*i] = node-> leftchild; if node has right child put ar[2*i + 1] = node-> rightchild;
4. repeat step 3 for every node.
5. now from the last index of the array repeat the following step
6. if(ar[i]==null) i-- ; continue;
7. if ar[i] contains the pointer of leaf node ; (ar[i]) -> leftchild == NULL && (ar[i])-> rightchild == NULL; j=i;
8 while(j !=0) { print(ar[j] -> data); j= j/2}

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

Can you give programming example for this ?
Especially how to repeat step 3 without using recursion.

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

But this is still the additional array you are talking about. If the tree is having too many nodes, the cost will be still high.

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

I think you mean to store the complete tree in an array assuming it to be a complete tree ( or storing null if it is not). This is huge space even in average case though printing path might work.

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

If the question is about binary tree,you can do a level order traversal with some modification.
public class Tree
{
public Tree left;
public Tree right;
public int val;
}
public class TreeNodePath
{
public TreeNodePath(Tree node,StringBuffer path)
{
this.node=node;
this.path=path;
}
public Tree node;
public StringBuffer path;
}
public static void printAllPathToLeafNonRecursive(Tree root) {

if (root == null) {
return;
}

TreeNodePath treeNodePath=new TreeNodePath();
treeNodePath.node=root;
treeNodePath.path=new StringBuffer(root.val);
while(!q.isEmpty()){
TreeNodePath pathNode=q.poll();
Tree root1 = pathNode.node;
StringBuffer currPath= pathNode.path;

if(root1.left==null && root1.right==null){
System.out.println(currPath.toString());
continue;
}

if(root1.left!=null){
StringBuffer newPath= currPath.append(",").append(root1.left.val);
}

if(root1.right!=null){
StringBuffer newPath= currPath.append(",").append(root1.right.val);
}
}

}

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

What kind of tree it was? It was not a BST, was it?

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

If it was not a BST, a randomized iterative DFS would do well.

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

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

wat u want man...? was it a binary tree or binary search tree?

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

First of all I apologize for being late. I was out for a while.

We will use a stack for DFS instead of recursion. You can find out more about iterative DFS at Wikipedia.
Whenever we reach the target node, we stop the DFS right there, and start popping nodes out of a stack and construct the path, like in the code below:

// This code is for the stage after halting the DFS
// cur is the current node. It is the target node at the beginning
// DFSStack is our stack
// ans is the path

node * cur = DFSStack.top();
DFSStack.pop();

list <node *> ans;
ans.push_front(cur);

node *tmp;
while(!(DFSStack.empty()))
{
tmp = DFSStack.top();
DFSStack.pop();
if(tmp->left == cur || tmp->right == cur)
{
cur = tmp;
ans.push_front(cur);
}
}

By randomized I mean to visit children of any node in a random order, in order to have an acceptable performance for any test case. That is, when a mean adversary queries the last leaf every time, on average, we will be searching half of the tree. By doing this, our space usage will decrease a bit for the worst case :-)

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

You will need to have a stack and a completed array. completed array denotes if you have seen both the children of the tree.
Now push a node in the stack and increment its children count. when the completed count is 2 you can pop out the node.
The code can be written as:

void printpath()
{
int i=0;
for(i=0;i<in;i++)
printf("%d\t",stack[i]->val);
printf("\n");
}

void allpaths(struct tnode *root)
{
int done=0;
int completed;
int i=0;
for(i=0;i<100;i++)
completed[i]=0;
struct tnode *cur = root;
while(done!=1)
{
if(cur!=NULL)
{
push(cur);
completed[cur->val]++;
cur = cur->left;
}
else
{
cur = front();
while(cur != NULL && completed[cur->val]==2)
{
if(cur->left==NULL && cur->right==NULL)
printpath();
pop();
cur = front();
}
if(cur!=NULL)
{
completed[cur->val]++;
cur = cur->right;
}
else
done =1 ;
}
}
}

void paths(struct tnode *root,int num)
{
int done=0;
int complete;
int i=0;
for(i=0;i<100;i++)
complete[i]=0;
struct tnode *cur = root;
while(done != 1)
{
if(cur!=NULL)
{
push(cur);
if(cur->val==num)
break;
complete[cur->val]++;
cur = cur->left;
}
else
{
cur = front();
while(cur != NULL && complete[cur->val]==2)
{
pop();
cur = front();
}
if(cur != NULL)
{
complete[cur->val]++;
cur =  cur->right;
}
else
done = 1;
}
}
if(done==0)
printpath();
}

where we have to find path from root to num.

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

I think this can be done with a stack with similar concept used in DFS using stack.

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

If you perform a slight modification on the nodes of your tree, you could store both the data and the level (depth) of the node

{
struct node
{
int data;
int level;
node* p_left;
node* p_right;
};

}

Once you have your tree built and having in mind that each node stores its level, you could perform an iterative preorder traversal. Once you find the desired value, you return from the function:

{
void preOrder(node * root, int value, int * path, int & level)
{
if(root == NULL)
return;
stack<node*> s;
s.push(root);
while(!s.empty())
{
node * aux = s.top();
s.pop();
path[aux->level] = aux->data;
if(aux->data == value)
{
level = aux->level;
return;
}
if(aux->p_right != NULL)
s.push(aux->p_right);
if(aux->p_left != NULL)
s.push(aux->p_left);
}
}

}

The rest is just cout'in the path array from 0 to level

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

Assuming it is a BST that was asked for:

void printRootToLeafPathWithoutRecursion(node *root,int n)
{
if(root==NULL)
{
cout<<"Sorry! The node you searched for doesn't exist.";
return;
}
else
{
node *currentNode;
currentNode=root;
while(currentNode!=NULL)
{
if(n==currentNode->info)
{
cout<<currentNode->info<<"-";
return;
}
else if(n<currentNode->info)
{
cout<<currentNode->info<<"-L-";
currentNode=currentNode->left;
}
else if(n>currentNode->info)
{
cout<<currentNode->info<<"-R-";
currentNode=currentNode->right;
}
}
cout<<"Sorry! The node you searched for doesn't exist.";
}
}

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

You can maintain a stack implemented via doubly ll and perform a preorder
Traversal on the tree and populate the stack with the visited node. When
You reach a leaf node in preorder traversal, print the complete stack and then
Continue with the preorder traversal.

Note: the tail of the ll should have the top pointer.

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

boolean isLeaf(Node<T> root2) {
return root2.getLeftNode()==null && root2.getRightNode() == null;
}
void printAllPathRecursive(Node<T> root,String path) {
if(root!=null && isLeaf(root)){
System.out.println(path+","+root.getData());
return;
}else{
if(root.getLeftNode()!=null)
printAllPathRecursive(root.getLeftNode(),path+","+root.getData());
if(root.getRightNode()!=null)
printAllPathRecursive(root.getRightNode(),path+","+root.getData());
}
}

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

boolean isLeaf(Node<T> root2) {
return root2.getLeftNode()==null && root2.getRightNode() == null;
}
void printAllPathRecursive(Node<T> root,String path) {
if(root!=null && isLeaf(root)){
System.out.println(path+","+root.getData());
return;
}else{
if(root.getLeftNode()!=null)
printAllPathRecursive(root.getLeftNode(),path+","+root.getData());
if(root.getRightNode()!=null)
printAllPathRecursive(root.getRightNode(),path+","+root.getData());
}
}

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

Idea above is to pass the path traversed to the next node until it reaches leaf node where we print the path. simple solution with O(n) complexity. Please let me know if I am missing someting

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

Algorithm :-
1.)Start from the root node of the tree.
2.)If the node has left child , store the node in a stack ,mark its right as unvisited in another stack and move to its left . Continue this step until you can find a left child.
3.)Now mark the current node's right child as visited and move to the right child. If the right child is empty , print the content of the stack , else go to step 2.

void root2leaf(node* tree){
struct stack{
node* arr;
int visited;
int tos;
};

stack st;
st.tos = -1;

do{
while(tree!='\0'){
st.arr[++st.tos]=tree;
st.visited[st.tos]=0;
tree=tree->left;
}

tree=st.arr[st.tos];
st.visited[st.tos]=1;
tree=tree->right;

if(tree=='\0'){
for(int i=0;i<=st.tos;i++){
printf("%d ",st.arr[i]->info);
}
printf("\n");
st.tos-=1;
while(st.visited[st.tos]==1){
st.tos-=1;
}
}

}while(st.tos!=-1);
}

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

We can do this by BFS.... just keep one array where each node will store its parent address... not when we reach our leaf using this array we can get the path..
please tell if this is wrong or not optimized..

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

Algorithm : Based on similar concept of recursion , recursion requires internal stack , I used an explicit stack to cover that feature.

Code is self explanatory. see comments

void printroot2leaf(struct tnode *root){

vector<tnode*>vb;
stack<tnode*>st;
st.push(root);

while(!st.empty()){

struct tnode* curr=st.top();
st.pop();
vb.push_back(curr);

if(isleaf(curr)){
for(int i=0;i<vb.size();i++)
cout<<vb[i]->data<<' ';
cout<<endl;
}

if(curr->right)
st.push(curr->right);
if(curr->left)
st.push(curr->left);

/*this step  removes the node from vector if stack's top is not its left or right child .. trace manually for a proper understanding of this step. */         while(!vb.empty()&&!st.empty()&&!vb[vb.size()-1]->left==st.top()||vb[vb.size()-1]->right==st.top()))
vb.pop_back();

}

}

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

{
void paths(struct Node *root)
{
struct Node *current = root;
struct Stack *s = NULL;
bool done = 0;

while (!done)
{
if(current != NULL)
{
push(&s, current);
current = current->left;
}
else
{
if (!isEmpty(s))
{
current = pop(&s);
printStack(s); >>>> Prints current stack.

current = current->right;
}
else
done = 1;
}
}
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{ void printRootToLeafSumWithoutRecursion(TreeJ root){ int sum=0; Stack<TreeJ> st=new Stack<TreeJ>(); TreeJ temp=new TreeJ(0); st.push(temp); st.push(root); while(st.isEmpty()==false){ TreeJ popVal1=st.pop(); TreeJ popVal2=st.pop(); temp=popVal2; while(popVal1!=null){ temp.val=(Integer)temp.val+(Integer)popVal1.val; if(popVal1.right!=null){ st.push(new TreeJ(temp.val)); st.push(popVal1.right); } popVal1=popVal1.left; } System.out.println(temp.val+","); } } }}
Comment hidden because of low score. Click to expand.
0
of 0 vote

void printRootToLeafSumWithoutRecursion(TreeJ root){
int sum=0;
Stack<TreeJ> st=new Stack<TreeJ>();
TreeJ temp=new TreeJ(0);
st.push(temp);
st.push(root);
while(st.isEmpty()==false){
TreeJ popVal1=st.pop();
TreeJ popVal2=st.pop();
temp=popVal2;
while(popVal1!=null){
temp.val=(Integer)temp.val+(Integer)popVal1.val;
if(popVal1.right!=null){
st.push(new TreeJ(temp.val));
st.push(popVal1.right);
}
popVal1=popVal1.left;
}
System.out.println(temp.val+",");
}

}

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

create a struct which contains tree node and information if left is traversed, right is traversed or not.just traverse the tee. add each node in stack and also keep the path in a string.
code

struct stack_node
{
tree *p;
int nlr; //visited none =-1, left =0 right =1 (can use two bools instead)
stack_node(tree *p, int nlr){this->p= p; this->nlr=nlr;};
};

void print_all_path_iter(tree *p)
{
if(!p)
return;
if(!p->left && !p->right)
{
cout<<p->val;
return;
}
std::string path="";
int path_len=0;
std::stack<stack_node *> stck;
//push root
stck.push(new stack_node(p, -1));
path= path+ p->val;//assuming p->val is string
path_len++;
while(stck.empty()==false)
{
stack_node* S= stck.top();//dont pop
//check if this is leaf
if(S->p->left == false && S->p->right == false)
{
cout<<"\n"<<path.substr(0,path_len-1);//if leaf print the substring of path
stck.pop();
delete S;
path_len--;
}
//check if none is visited
else if(S->nlr== -1)
{
if(S->p->left != null)
{
stck.push(new stack_node(S->p->left, false));
S->nlr=0;//change state of left visited
path.at(path_len)=S->p->left->val;
path_len++;
}
else
{
stck.pop();
delete S;
path_len--;
}
}
//check if left is visited
else if(S->nlr == 0)
{
if(S->p->right != null)
{
stck.push(new stack_node(S->p->right, false));
S->nlr= 1;
path.at(path_len)=S->p->right->val;
path_len++;
}
else
{
stck.pop();
delete S;
path_len--;
}
}
//check if right is visited
else if(S->nlr == 1)
{
stck.pop();
delete S;
path_len--;
}
}
return;
}

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

This function will print each node without recursion

/* Function to traverse binary tree without recursion and
without stack */
void MorrisTraversal(struct tNode *root)
{
struct tNode *current,*pre;

if(root == NULL)
return;

current = root;
while(current != NULL)
{
if(current->left == NULL)
{
printf(" %d ", current->data);
current = current->right;
}
else
{
/* Find the inorder predecessor of current */
pre = current->left;
while(pre->right != NULL && pre->right != current)
pre = pre->right;

/* Make current as right child of its inorder predecessor */
if(pre->right == NULL)
{
pre->right = current;
current = current->left;
}

// MAGIC OF RESTORING the Tree happens here:
/* Revert the changes made in if part to restore the original
tree i.e., fix the right child of predecssor */
else
{
pre->right = NULL;
printf(" %d ",current->data);
current = current->right;
} /* End of if condition pre->right == NULL */
} /* End of if condition current->left == NULL*/
} /* End of while */
}

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

Your can use a single queue to print a tree. The idea is to push the node value in queue until the node's children are read. Once added to queue, add a null to mark end of that level. Hope this helps.

public int printTreeInLine(Tree root){

if(root == null)
return 0;

int level = 0;

while(!q.isEmpty()){
Tree temp = q.poll();

if(temp == null){
if(!q.isEmpty()){
level++;
System.out.println();
}
}
else{
//Printing Node value in tree
System.out.print(temp.getData()+" ");
if(temp.getLeft() != null){
}
if(temp.getRight() != null){
}
}
}

return ++level;
}

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

class NodePath(object):
def __init__(self, node, path):
self.cnode = node
self.cpath = list(path)

def printAllRootToLeaf(root):
path = []
stack = []
stack.append(NodePath(root, path))

while(len(stack) != 0):
pnode = stack.pop()
node = pnode.cnode
pnode.cpath.append(node)

if node.left == None and node.right == None:
out = str(pnode.cpath.data)
for i in pnode.cpath[1:]:
out += "-" + str(i.data)
print out

if node.left != None:
stack.append(NodePath(node.left, pnode.cpath))

if node.right != None:
stack.append(NodePath(node.right, pnode.cpath))

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

instead of pushing node itself to stack, having a class or struct that holds both node and path to that node will preserve a path to a node. When you push your children they will have same path as parent, so when you hit a leaf, all you need to do is print current path

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

Can be done similar to iterative post order as follows
Stack st;
Node n = root;
while(st.size() > 0){
if( n!= null)
{
st.push(n);
n = n.left;
} else {
node t = st.peek();
if(t.right == null) // leaf found
{ print stack so far at this point
printStack();
st.pop();
// now remove the nodes from stack which are parents of this node
while( st.peek.right == t)
{
t = st.pop();
}
} else {
node = t.right;
}

}
}

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

This problem can be solved using the iterative method. Only a stack is needed. Here is my code for this problem and works completely fine.

class Node{
Node left, right;
int data;
Node(int x){
data=x;
}
}
public class BinaryTreeIteratorMc {

Node root;
void InOrder(){
Stack<Node> stack=new Stack<Node>();
Node n=root;
if(n==null)
return;
while(n!=null){
stack.push(n);
n=n.left;
}

while(stack.size()>0){
n=stack.pop();
System.out.print(n.data+" ");

if(n.right!=null){
n=n.right;
//System.out.println("in if");
while(n!=null){
//System.out.println("in while");
n=n.left;

}
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
BinaryTreeIteratorMc tree=new BinaryTreeIteratorMc();
tree.root=new Node(1);
tree.root.left=new Node(2);
tree.root.right=new Node(3);
tree.root.left.left=new Node(4);
tree.root.left.right=new Node(5);
tree.root.right.right=new Node(6);
System.out.println("Inorder traversal is :");
tree.InOrder();

}

}

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

void printRootToLeaf(node *new_node){
node *my_array;
int i = 0, num_leaf = 0;
enqueue(new_node);
while(front != NULL){
while(front->tree_node->left != NULL || front->tree_node->right != NULL){
if(front->tree_node->left != NULL){
enqueue(front->tree_node->left);
}
if(front->tree_node->right != NULL){
enqueue(front->tree_node->right);
}
dequeue();
}
my_array[i] = front->tree_node;
i++;
dequeue();
}
num_leaf = i;
i = 0;

while(i < num_leaf){
printf("\nPath %d : \n",i+1);
new_node = root;
while(new_node->val != my_array[i]->val){
printf("\n%d\n",new_node->val);
if(my_array[i]->val < new_node->val){
new_node = new_node->left;
}
else{
new_node = new_node->right;
}
}
if(new_node->val == my_array[i]->val){
printf("\n%d\n",new_node->val);
}
i++;
}

}

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

We can do a level order traversal which requires a queue and does not require a recursion to print all the nodes.
1. Enqueue the root node in the queue.
2. Dequeue the queue and visit it (do the necessary operation)
3. If the node has children enqueue it.
Continue step 2 and 3 until the queue is empty.

public static void levelorder(Node n) {
if (n != null)
while (!nodequeue.isEmpty()) {
Node next = nodequeue.remove();
System.out.print(next.data + " ");
if (next.getLeft() != null) {
}
if (next.getRight() != null) {
}
}
}

getLeft and getRight are defined in Node class

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.