Amazon Interview Question for Software Engineer / Developers






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

modification of level order display ...
Do simple level order display with one queue, with the modification that,
1.whenever nullnode comes as a result of deque(or any other indicator u use for next level), dequeue all elements one by one and push in an stack. At the same time, enqueue the children. Now display all elems of stack and enqueue a null node in queue.

- xyz May 26, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

No need to use additional stack. Just pass another parameter that shows the current level is even or odd. If it is even (the root is 0), starting from right child to enqueue all the children from the right; otherwise, starting from the left child to enqueue all the children from the left.

- chenming831@gmail.com May 30, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

/* The class name doesn't have to be Main, as long as the class is not public. */
class Main
{

void printTree(Node root){
  //declare variables
  Queue<Node> q = new LinkedList<Node>();
  int currentLevel = 1;
  int children = 0; // number of children of current level
  int counter = 1; // number of pop in order to advance next level
  q.push(root);

  while(!q.isEmpty()){
     Node e = q.pop();
     System.out.print(e);
     count--;
     if(currentLevel %2 ==1){
       if(e.left!=null){
         q.add(e.left);
         children++;
       }
       if(e.right!=null){
         q.add(e.right);
         children++;
       }
     }else{
       if(e.left!=null){
         q.add(e.left);
         children++;
       }
       if(e.right!=null){
         q.add(e.right);
         children++;
       }
     }
     if(count == 0){
        count = children;
        currentLevel ++;
        children=0;
      }

  }


}

}

- chris June 06, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The following is the java code which is working..


public void printTreeZigZag(Node root){
Queue<Node> q = new LinkedList<Node>();
Stack<Node> nl = new Stack<Node>();
q.offer(root);
q.offer(null);
boolean flip=false;
while(!q.isEmpty()){
Node n = q.poll();
if(n!=null)
nl.push(n);
else{
while(!nl.empty()){
Node p = nl.pop();
System.out.print(p.getData()+"\t");
if(flip){
if(p.getRight()!=null)
q.offer(p.getRight());

if(p.getLeft()!=null)
q.offer(p.getLeft());
}else{
if(p.getLeft()!=null)
q.offer(p.getLeft());
if(p.getRight()!=null)
q.offer(p.getRight());
}

}
q.offer(null);
}
if(q.peek()==null){
flip=!flip;
}
}
}

- Sandeep May 29, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The following is the java code which is working.. re-submiting just to keep the fomat

public void printTreeZigZag(Node root){
	Queue<Node> q = new LinkedList<Node>();
	Stack<Node> nl = new Stack<Node>();
	q.offer(root);
	q.offer(null);
	boolean flip=false;		
	while(!q.isEmpty()){			
		Node n = q.poll();			
		if(n!=null)
			nl.push(n);
		else{
			while(!nl.empty()){
				Node p = nl.pop();
				System.out.print(p.getData()+"\t");
				if(flip){
					if(p.getRight()!=null)
						q.offer(p.getRight());
						
					if(p.getLeft()!=null)
						q.offer(p.getLeft());				
					}else{
						if(p.getLeft()!=null)
							q.offer(p.getLeft());
						if(p.getRight()!=null)
							q.offer(p.getRight());				
					}

				}
				q.offer(null);
			}
			if(q.peek()==null){
				flip=!flip;					
			}				
		}
	}

- Sandeep May 29, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Small Correction to avoid the infinite loop

public void printTreeZigZag(Node root){
		Queue<Node> q = new LinkedList<Node>();
		Stack<Node> nl = new Stack<Node>();
		q.offer(root);
		q.offer(null);		
		boolean flip=false;		
		while(!q.isEmpty()){			
			Node n = q.poll();			
			if(n!=null)
				nl.push(n);
			else{
				boolean fillnull=false;
				while(!nl.empty()){
					Node p = nl.pop();
					System.out.print(p.getData()+"\t");
					if(flip){
						fillnull = true;
						if(p.getRight()!=null)
							q.offer(p.getRight());
						
						if(p.getLeft()!=null)
							q.offer(p.getLeft());				
					}else{
						fillnull = true;
						if(p.getLeft()!=null)
							q.offer(p.getLeft());
						if(p.getRight()!=null)
							q.offer(p.getRight());				
					}
				}
				if(fillnull)
					q.offer(null);
				
			}
			if(q.peek()==null){
				flip=!flip;	
			
			}				
		}
	}

- Sandeep May 30, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

First convert the Binary tree into array representation and then use array and stack to print the above pattern

Void printTree(Node root){

Node [] arrNode = new Node[N] // N is the number of nodes in tree
ArrNode[0] = root;
For(int I = 0; I < d; I++) {// d depth of binary tree

	ArrNode[2*I + 1] = arr[0].leftPtr;
	ArrNode[2*I + 2] = arr[0].rightPtr;
}
Int start Index = 0;
Int j = 0;
Stack stack = new Stack(N);
For(int I = 0; I < d; I++){

	If(I == 1 || I % 2 != 0){
		Start Index = j;
		While( j < start Index + I powerOf 2){
			
			Stack.push(arrNode[j])
			J++;
		}
		While(start Index < j){
		
			ArrNode[startIndex] = stack.pop();
			StartIndex++;
		}
	}else{
		J = j + I powerOf 2;
	}
}

For(innt I=0; I < n; I++){
	System.out.println(arrNode[i]);
}
}

- Priyanka June 02, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This may be similar to Priyanka's answer. Covert the tree to a binary tree, then traverse it. At each level, the left-most or right-most node can be expressed as a function of height (starting at 1):

left-most-node(height) => 2 ^ (height - 1)

right-most-node(height) => (2 ^ height) - 1

Using this, a for loop can be coded as:

for(var i = 0, left-to-right = true; i < height; i++) {
    left-end = 2 ^ (i - 1)
    right-end = (2 ^ i) - 1

    if(left-to-right) {
        print array values from left-end to right-end
    }
    else {
        print array values from right-end to left-end
    }
}

- Anurag June 07, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Did I say convert a tree to a binary tree? Wow, I am dumb. I mean convert it to an Array.

- Anurag June 07, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void ZigZag_Traversal(Node root)
{
//uses two stack "even" and "odd" for storing even and odd members of the tree.
//tree starts with level 0 thats even. so keeps root in even stack
//when popping elements from even stack put its children in odd stack taken as left child pushed first and then right
//when popping elements from odd stack put its children in even stack taken as right child pushed first then left child.
//when current stack is empty process with next one and when both are empty stop.

Stack<Node> evenStack = new Stack<Node>();
Stack<Node> oddStack = new Stack<Node>();
Stack<Node> currStack;
Stack<Node> otherStack;
String level;
evenStack.push(root);

while((!evenStack.empty()) || (!oddStack.empty()))
{
if(!evenStack.empty())
{
currStack = evenStack;
otherStack = oddStack;
level = "even";
}
else
{
currStack = oddStack;
otherStack = evenStack;
level = "odd";
}

//start traversing the tree.
while(!currStack.empty())
{
if(level.equalsIgnoreCase("even"))
{
Node poppedNode = currStack.pop();
//print node value in order to print the tree in ZigZag manner.
System.out.print(poppedNode.value + ",");
//push it's children into otherStack taken from left child first then right child if not Null.
if(poppedNode.left != null)
{
otherStack.push(poppedNode.left);
}
if(poppedNode.right != null)
{
otherStack.push(poppedNode.right);
}
}
else
{

Node poppedNode = currStack.pop();
//print node value in order to print the tree in ZigZag manner.
System.out.print(poppedNode.value + ",");
//push it's children into otherStack taken from right child first then left child if not Null.
if(poppedNode.right != null)
{
otherStack.push(poppedNode.right);
}
if(poppedNode.left != null)
{
otherStack.push(poppedNode.left);
}

}
}//end of inner while
}
}

- shri June 14, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// writing the alogorithm here
print stack(int turn)
{
while stack[turn][i]!=null
{
pop and print;
if(turn==0)
{
push(stack[1], leftchildof(popped element));
push(stack[1], rightchildof(popped element));
}
if(turn==1)
{
push(stack[0], rightchildof(popped element));
push(stack[0], leftchildof(popped element));

}

if(turn==0)
turn=1;
else
turn=0;
if(stack[turn] not empty)
call(turn);
else
return

}

- aseemagarwal19 October 02, 2010 | Flag Reply


Add a Comment
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.

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