Amazon Interview Question for Software Engineers


Country: United States
Interview Type: In-Person




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

This can be done with a BFS traversal of the tree. O(n) complexity and O(n) memory:

private static class Node{
    int value;
    Node left, right;
}

private static void zigZagTree(Node root){
    if(root == null){
        throw new NullPointerException();
    }
    
    Node node;
    boolean isZig;
    LinkedList<Node> unprocessedNodes = new LinkedList<Node>();
    LinkedList<Node> nextNodes = new LinkedList<Node>();
    LinkedList<Node> temp;
    StingBuilder builder = new StringBuilder();
    unprocessedNodes.add(root);
    while(!unprocessedNodes.isEmpty()){
        if(isZig){
            while(!unprocessedNodes.isEmpty()){
                 node = unprocessedNodes.removeFirst();
    		 builder.append(Integer.toString(node.value);
                 builder.append(", ");             
                 if(node.left != null){
                     nextNodes.add(node.left);
                 }
                 if(node.right != null){
                     nextNodes.add(node.right);
                 }
            }
        }
        else{
            while(!unprocessedNodes.isEmpty()){
                node = unprocessedNodes.removeLast();
                builder.append(Integer.toString(node.value);
                builder.append(", ");
                if(node.right != null){
                     nextNodes.addFirst(node.right);
                }
                if(node.left != null){
                     nextNodes.addFirst(node.left);
                }
            }
        }
        isZig = !isZag;
        temp = unprocessedNodes;
        unprocessedNodes = nextNodes;
        nextNodes = temp;
    }
    java.lang.System.out.println(builder.toString());
}

- zortlord July 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

cleaner version

public class ZigZagfs {

	Node root = null;
	Map<Integer, Node> nodes = new HashMap<Integer,Node>();
	
	static class Node {
		int value;
		Node left;
		Node right;
		
		public Node ( int value ){
			this.value = value;
		}
		
		public String toString(){
			return ""+this.value;
		}
	}

	public ZigZagfs(String fileName) {
		try (BufferedReader rdr = new BufferedReader(new FileReader(fileName))) {
			String line = null;
			while ((line = rdr.readLine()) != null) {
				Node n = parseLine(line);
				if ( root == null ) root = n;
			}
		} 
		catch (IOException ioe) {
			System.err.println("error: " + ioe);
		}
	}
	
	Node parseNode( String str ) {
		if ( str == null ) return null;
		str = str.trim();
		if ( str.length() == 0 ) return null;
		
		int val = Integer.parseInt(str);
		if ( nodes.containsKey(val)  ) return nodes.get(val);
		
		Node n = new Node(val);
		nodes.put(val, n);
		return n;	
	}

	Node parseLine(String line) {
		int idx = line.indexOf(":");
        Node n =  parseNode( line.substring(0, idx) );
        
		String[] children = line.substring(idx + 1).split(",");
		
		if ( children.length > 0 ) n.left = parseNode(children[0]);
		if ( children.length > 1 ) n.right = parseNode(children[1]);
				
		System.out.println(n.value + ": " + n.left + ","  + n.right);
		return n;
	}

	void print() {

        Node node = root;
		
		Deque<Node> q1 = new LinkedList<Node>();
		q1.add(node);

		Queue<Node> q2 = new LinkedList<Node>();

		String comma = "";
		while (!q1.isEmpty() || !q2.isEmpty()) {

			while (!q1.isEmpty()) {
				node = q1.removeLast();
				System.out.print(comma + node.value);
				if (node.left != null)
					q2.add(node.left);
				if (node.right != null)
					q2.add(node.right);
				comma = ",";
			}
			
			System.out.println("");
			comma = "";
			while (!q2.isEmpty()) {
				node = q2.remove();
				System.out.print(comma + node.value);
				if (node.left != null) 
					q1.add(node.left);
				if (node.right != null)
					q1.add(node.right);
				comma = ",";
			}
			System.out.println("");
			comma = "";
		}
	}

	static public void main(String[] args) {
		ZigZagfs zigZag = new ZigZagfs(args[0]);
		zigZag.print();
	}

}

- stephenpince July 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//Use 2 stacks O(n) time O(2^h) space (if we have a perfect binary tree).

public class Node 
{
	private int value;
	private Node left;
	private Node right;
}

public class ZigZagService
{
	public void zigZagTraverse(Node n)
	{
		if(n==null)
		{
			System.out.println("error input tree is null");
		}
		Stack<Node> lr=new Stack<Node>();//will be used to print nodes in left to right order
		Stack<Node> rl=new Stack<Node>();//will be used to print nodes in right to left order

           rl.push(n);
	while(true)
	{
			if(rl.isEmpty()&&lr.isEmpty())
			{
				break;
			}
			while(!rl.isEmpty())
			{
				Node top=rl.pop();
				System.out.print(top.value());
				if(top.right!=null)
				{
					lr.push(top.right);
				}
				if(top.left!=null)
				{
					lr.push(top.left);
				}
			}
			while(!lr.isEmpty())
			{
				Node top=lr.pop();
				System.out.print(top.value);
				if(top.left!=null)
				{
					rl.push(top.left);
				}
				if(top.right!=null)
				{
					rl.push(top.right);
				}
			}
		}
	}
		
	}
}

- Anonymous July 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//Use two stacks O(n) time and O(2^h) space if we have a perfect tree

public class Node
{
	private int value;
	private Node left;
	private Node right;
}

public class ZigZagService
{
		public void ZigZagTraverse(Node n)
		{
			if(n==null)
			{
				System.out.println("error input is null");
			}
			Stack<Node> lr=new Stack<Node>();//Will print nodes from left to right
			Stack<Node> rl=new Stack<Node>();//Will print nodes from right to left
			rl.push(n);
			while(true)
			{
				if(lr.isEmpty() && rl.isEmpty())
				{
					break;
				}
				while(!lr.isEmpty())
				{
					Node x=lr.pop();
					System.out.print(x.value);
					if(x.left!=null)
					{
						rl.push(x.left);
					}
					if(x.right!=null)
					{
						rl.push(x.right);
					}
				}
				while(!rl.isEmpty())
				{
					Node x=rl.pop();
					System.out.print(x.value);
					if(x.right!=null)
					{
						lr.push(x.right);
					}
					if(x.left!=null)
					{
						lr.push(x.left);
					}
				}
				
			}

}

- divm01986 July 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void zigZagTraverse(Node n) {
	var leftToRight = new Stack<Node>();
	var rightToLeft = new Stack<Node>();

	if (n == null)
		return;

	rightToLeft.Push(n);

	visitRightToLeft(n, leftToRight, rightToLeft);
}

private void visitLeftToRight(Stack<Node> leftToRight, Stack<Node> rightToLeft) {
	while (leftToRight.Peek() != null) {
		var nn = leftToRight.Pop();
		print n;
		if (n.Left != null)
			rightToLeft.Push(n.Left);
		if (n.Right != null)
			rightToLeft.Push(n.Right);
	}

	if (rightToLeft.Peek() != null)
		visitRightToLeft(n, leftToRight, rightToLeft);
}


private void visitRightToLeft(Stack<Node> leftToRight, Stack<Node> rightToLeft) {
	while (rightToLeft.Peek() != null) {
		var n = rightToLeft.Pop();
		print n;
		if (n.Right != null)
			leftToRight.Push(n.Right);
		if (n.Left != null)
			leftToRight.Push(n.Left);
	}
	
	if (leftToRight.Peek() != null)
		visitLeftToRight(n, leftToRight, rightToLeft);
}

- erika.r July 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class BinaryTree<K>{

    private class Node{
        K value;
        Node left;
        Node right;
        Node(K val){
            value = val;
            left = null;
            right = null;
        }
    }
/* Queue/Stack Implementation */
    private class Queue{
        
        private class NodeQ{
            Node valNode;
            NodeQ next;
            NodeQ(Node val){
                this.valNode = val;
            }
        }
        private NodeQ HEAD = null;
        private NodeQ TAIL = null;
        private void enque(Node val){
            if(val == null) return;
            NodeQ nodeq = new NodeQ(val);
            if(TAIL == null){
                TAIL = nodeq;
                HEAD = nodeq;
            }
            else{
                TAIL.next = nodeq;
                TAIL = nodeq;
            }
        }

       private void push(Node val){
           if(val == null) return;
           NodeQ nodeq = new NodeQ(val);
           if(HEAD == null){//empty queue
               HEAD = nodeq;
               TAIL = nodeq;
           }
           else{
               nodeq.next = HEAD;
               HEAD = nodeq;
           }
       }

       private Node deque(){
           if(HEAD == null)
               return null;
           Node retNode = HEAD.valNode;
           HEAD = HEAD.next;

           if(HEAD == null)
               TAIL = null;//queue is empty
           return retNode;
       }
       private boolean isEmpty(){
           return (HEAD == null);
       }
    }
/* End of Queue implementation*/

    private Node root;
/* Fill method in horizontal manner*/
    public void put(K val){
        Node node = new Node(val);
        if(root == null){
            root = node;
            return;
        }
        Node rt = root;
        Queue q = new Queue();
        q.enque(rt);
        while(!q.isEmpty()){
            Node popped = q.deque();
            if(popped.left == null){
                popped.left = node;
                return;
            }
            else
                q.enque(popped.left);

            if(popped.right == null){
                popped.right = node;
                return;
            }
            else
                q.enque(popped.right);
        }
    }

/* In order traverse*/
    public void inOrdertraverse(){
        traverseIn(root);
    }

    private void traverseIn(Node r){
        if(r == null) return;
        traverseIn(r.left);
        System.out.println(r.value);
        traverseIn(r.right);
    }

    public void horizontalTraverse(){
        Node rt = root;
        Queue q = new Queue();
        q.enque(rt);
        while(!q.isEmpty()){
            Node popped = q.deque();
            System.out.println(popped.value);
            if(popped.left != null){
                q.enque(popped.left);
            }

            if(popped.right != null){
                q.enque(popped.right);
            }
        }
    }

    public void zigzagTx(){
        Queue queue = new Queue();
        Node rt = root;
        queue.enque(rt);
        if(rt!= null)
            System.out.println(rt.value);
        boolean toggled = false;
        while(true){
            Queue Q1 = new Queue();//to carry fwd the process
            Queue Q2 = new Queue();//for prints
            while(!queue.isEmpty()){
                Node x = queue.deque();
                if(x.left != null){
                    Q1.enque(x.left);
                    if(!toggled)
                        Q2.enque(x.left);
                    else
                        Q2.push(x.left);
                }
                if(x.right != null){
                     Q1.enque(x.right);
                     if(!toggled)
                         Q2.enque(x.right);
                     else
                         Q2.push(x.right);
                }
            }
            if(Q1.isEmpty()) break;
            queue = Q1;
            while(!Q2.isEmpty()){
                System.out.println(Q2.deque().value);
            }
            if(toggled)
                toggled = false;
            else
                toggled = true;
        }
    }
}

- blurred July 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static class TreeNode<T>
	{
		TreeNode(T value, TreeNode left, TreeNode right)
		{
			this.value = value;
			this.left = left;
			this.right = right;
		}
		T value;
		TreeNode left;
		TreeNode right;
		
		@Override
		public String toString()
		{
			return value.toString();
		}
		
	}
	
	public static void printZigZagTree( TreeNode head )
	{
		List<TreeNode> buffer = new ArrayList<TreeNode>();
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.add(head);
		//add the 'dummy' node:
		queue.add( new TreeNode(null, null, null) );
		boolean isLeftToRight = 
				//true;
				false;
		
		while( ! queue.isEmpty() )
		{
			TreeNode node = queue.poll();
			if(node.value == null)	//if this is dummy, we know that it is a new "level" in the tree. so handle the previous level (in the buffer)...
			{
				if(isLeftToRight)
				{
					for(TreeNode tn : buffer)
					{
						System.out.print(tn);
					}
				}
				else
				{
					for(int i = buffer.size()-1; i >= 0 ; --i)
					{
						System.out.print(buffer.get(i));
					}
				}
				
				System.out.println();
				buffer.clear();
				isLeftToRight = !isLeftToRight;
				
				//add the dummy only if the Q is not empty - o/w we run into endless loop:
				if(!queue.isEmpty())
					queue.add(node);
			}
			else
			{
				buffer.add(node);
				
				//add its child to queue:
				if(node.left != null) 
					queue.add(node.left);
				if(node.right != null) 
					queue.add(node.right);				
			}
			
		}		
	}

- ohadr.developer July 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res=new ArrayList<List<Integer>>();
helper(res,1,root);

return res;
}
public void helper(List<List<Integer>> list,int level,TreeNode root){
if(root==null) return;
if(list.size()<level){
List<Integer> items=new ArrayList<Integer>();
items.add(root.val);

list.add(items);

}else{
if(level%2!=0) list.get(level-1).add(root.val);
else list.get(level-1).add(0,root.val);
}
helper(list,level+1,root.left);
helper(list,level+1,root.right);


}

}

- dezhihe September 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res=new ArrayList<List<Integer>>();
        helper(res,1,root);
        
        return res;
    }
    public void helper(List<List<Integer>> list,int level,TreeNode root){
        if(root==null) return;
        if(list.size()<level){
            List<Integer> items=new ArrayList<Integer>();
            items.add(root.val);
          
            list.add(items);
            
        }else{
          if(level%2!=0)  list.get(level-1).add(root.val);
          else list.get(level-1).add(0,root.val);
        }
        helper(list,level+1,root.left);
        helper(list,level+1,root.right);
        
        
    }

}

- dezhihe September 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/

public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res=new ArrayList<List<Integer>>();
        helper(res,1,root);
        
        return res;
    }
    public void helper(List<List<Integer>> list,int level,TreeNode root){
        if(root==null) return;
        if(list.size()<level){
            List<Integer> items=new ArrayList<Integer>();
            items.add(root.val);
          
            list.add(items);
            
        }else{
          if(level%2!=0)  list.get(level-1).add(root.val);
          else list.get(level-1).add(0,root.val);
        }
        helper(list,level+1,root.left);
        helper(list,level+1,root.right);
        
        
    }

}

- dezhihe September 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Notice that this problem is very similar to the lever-order tree traversal. This problem can be implemented by a queue.
The only difference is that while in odd levels we traverse left to right in the even layers me traverse right to left. We will traverse the the tree while keeping track of even/odd layer. This will affect the order we put the nodes on the queue.

- autoboli July 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your answer is not right.
0 will add 1,2 into the queue
then 1 will add 4, 3 into the queue
and 2 will add 6, 5 into the queue

it will look like 0, 1, 2, 4, 3, 6, 5

- ydu525 July 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You are absolutely right ydu525. I will edit the code. Thank you!

- autoboli July 17, 2015 | Flag


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