Amazon Interview Question for SDE1s


Team: Kindle
Country: India
Interview Type: Written Test




Comment hidden because of low score. Click to expand.
10
of 12 vote

private static void zigZagTraversal(BinaryTreeNode root) {
		int leftToRight = 1;
		BinaryTreeNode temp;
		Queue<BinaryTreeNode> currentLevel = new LinkedBlockingDeque<BinaryTreeNode>();
		Stack<BinaryTreeNode> nextLevel = new Stack<BinaryTreeNode>();

		System.out.println("Zig Zag Traversal");
		currentLevel.add(root);
		while (!currentLevel.isEmpty()) {
			temp = currentLevel.poll();
			if (temp != null) {
				System.out.print(" "+temp.getData());
				if (leftToRight == 0) {
					if (temp.getLeft() != null)
						nextLevel.push(temp.getLeft());
					if (temp.getRight() != null)
						nextLevel.push(temp.getRight());
				} else {
					if (temp.getRight() != null)
						nextLevel.push(temp.getRight());
					if (temp.getLeft() != null)
						nextLevel.push(temp.getLeft());
				}

			}
			
			if (currentLevel.isEmpty()) {
				System.out.println();
				leftToRight = 1 - leftToRight;
				while (!nextLevel.isEmpty()) {
					currentLevel.add(nextLevel.pop());
				}
			}

		}
	}

- Vir Pratap Uttam May 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is exactly the same solution that I did on an interview (but using C#) and I think the interviewer was totally confused.

- Nelson Perez May 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 vote

Traverse the tree using Breadth First approach.
On each level print the element, Print should be reversed on each level to have zigzag effect

- pc May 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is incorrect. Your code would output

1
2 3
5 4 7 6
9 8

- wut May 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

No the output should not be as you mentioned.
You jut need to ensure that printing is reversed on alternative iterations

- pc May 26, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

take one stack and one queue.
push root into stack..

while(!stack.empty() || !queue.empty())
{
while (!stack.empty())
{
elem=stack.pop();
print elem.value;
queue.push(elem->left);
queue.push(elem->right);
}
while(!queue.empty())
{
elem=queue.pop();
print elem;
stack.push(elem->left);
stack.push(elem->right);
}
}

- sanjay.2812 June 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static class TreeNode{
    TreeNode left, right;
    int val;
}

public static void printZigzag(TreeNode head){
    if(head == null){
        return;
    }
    boolean goRight = false;
    LinkedList<TreeNode> list = new LinkedList<TreeNode>();
    LinkedList<TreeNode> temp = new LinkedList<TreeNode>();
    list.add(head);
    StringBuilder lineBuilder = new StringBuilder();
    TreeNode node = null;
    //while there's still content
    while(!list.isEmpty()){
        //while there are still unprocessed TreeNodes for this line
        while(!list.isEmpty()){
            if(goRight){
                node = list.removeFirst();
            }
            else{
                 node = list.removeLast();
            }
            lineBuilder.append(node.val);
            lineBuilder.append(' ');
            if(node.left != null){
                temp.add(node.left);
            }
            if(node.right != null){
                temp.add(node.right);
            }
        }
        //make output and prep for next line
        java.lang.System.out.println(lineBuilder.toString());
        lineBuilder.setLength(0);
        LinkedList<TreeNode> holder = list;
        list = temp;
        temp = holder;
        goRight = !goRight;
    }
}

- A_Nony_Mouse May 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

typedef struct Node{
	int value;
	char type;
	struct Node * left_child;
	struct Node * right_child;
}Node;

Queue queue;
Stack stack;

void printZigZag(Node * head){
	if(head == null){
		return;
	}
	queue.push(head);
	int row_number = 0;
	int num_of_elements = 1;
	int elements_covered_so_far = 0;
	
	while(queue.size != 0){
		Node * node = queue.pop();
		if(node.type == PLACE_HOLDER){
			continue;
		}
		elements_covered_so_far ++;
		if(elements_covered_so_far == num_of_elements){
			Node * place_holder = (Node*)malloc(sizeof(Node));
			place_holder.type == PLACE_HOLDER;
			queue.push(place_holder);
			
			elements_covered_so_far = 0;
			num_of_elements = num_of_elements * 2;
			row_number++;
		}
		
		queue.push(node->left_child);
		queue.push(node->right_child);
		
		
		
		if(row_number % 2 ==1){
			//print in reverse order
			stack.push(node);
		}
		else{
			printf("%d ",node->value);
		}
		if(stack.size() == num_of_elements){
			while(!stack.is_empty()){
				Node * node = stack.pop();
				printf("%d ",node->value);
			}
		}
		
	}
}

- Sriparna Chakraborty May 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

typedef struct Node{
	int value;
	char type;
	struct Node * left_child;
	struct Node * right_child;
}Node;

Queue queue;
Stack stack;

void printZigZag(Node * head){
	if(head == null){
		return;
	}
	queue.push(head);
	int row_number = 0;
	int num_of_elements = 1;
	int elements_covered_so_far = 0;
	
	while(queue.size != 0){
		Node * node = queue.pop();
		if(node.type == PLACE_HOLDER){
			continue;
		}
		elements_covered_so_far ++;
		if(elements_covered_so_far == num_of_elements){
			Node * place_holder = (Node*)malloc(sizeof(Node));
			place_holder.type == PLACE_HOLDER;
			queue.push(place_holder);
			
			elements_covered_so_far = 0;
			num_of_elements = num_of_elements * 2;
			row_number++;
		}
		
		queue.push(node->left_child);
		queue.push(node->right_child);
		
		
		
		if(row_number % 2 ==1){
			//print in reverse order
			stack.push(node);
		}
		else{
			printf("%d ",node->value);
		}
		if(stack.size() == num_of_elements){
			while(!stack.is_empty()){
				Node * node = stack.pop();
				printf("%d ",node->value);
			}
		}
		
	}
}

- Sriparna Chakraborty May 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

typedef struct Node{
	int value;
	char type;
	struct Node * left_child;
	struct Node * right_child;
}Node;

Queue queue;
Stack stack;

void printZigZag(Node * head){
	if(head == null){
		return;
	}
	queue.push(head);
	int row_number = 0;
	int num_of_elements = 1;
	int elements_covered_so_far = 0;
	
	while(queue.size != 0){
		Node * node = queue.pop();
		if(node.type == PLACE_HOLDER){
			continue;
		}
		elements_covered_so_far ++;
		if(elements_covered_so_far == num_of_elements){
			Node * place_holder = (Node*)malloc(sizeof(Node));
			place_holder.type == PLACE_HOLDER;
			queue.push(place_holder);
			
			elements_covered_so_far = 0;
			num_of_elements = num_of_elements * 2;
			row_number++;
		}
		
		queue.push(node->left_child);
		queue.push(node->right_child);
		
		
		
		if(row_number % 2 ==1){
			//print in reverse order
			stack.push(node);
		}
		else{
			printf("%d ",node->value);
		}
		if(stack.size() == num_of_elements){
			while(!stack.is_empty()){
				Node * node = stack.pop();
				printf("%d ",node->value);
			}
		}
		
	}
}

- Sriparna Chakraborty May 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

typedef struct Node{
	int value;
	char type;
	struct Node * left_child;
	struct Node * right_child;
}Node;

Queue queue;
Stack stack;

void printZigZag(Node * head){
	if(head == null){
		return;
	}
	queue.push(head);
	int row_number = 0;
	int num_of_elements = 1;
	int elements_covered_so_far = 0;
	
	while(queue.size != 0){
		Node * node = queue.pop();
		if(node.type == PLACE_HOLDER){
			continue;
		}
		elements_covered_so_far ++;
		if(elements_covered_so_far == num_of_elements){
			Node * place_holder = (Node*)malloc(sizeof(Node));
			place_holder.type == PLACE_HOLDER;
			queue.push(place_holder);
			
			elements_covered_so_far = 0;
			num_of_elements = num_of_elements * 2;
			row_number++;
		}
		
		queue.push(node->left_child);
		queue.push(node->right_child);
		
		
		
		if(row_number % 2 ==1){
			//print in reverse order
			stack.push(node);
		}
		else{
			printf("%d ",node->value);
		}
		if(stack.size() == num_of_elements){
			while(!stack.is_empty()){
				Node * node = stack.pop();
				printf("%d ",node->value);
			}
		}
		
	}
}

- sriparna.c35 May 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Apologies for the multiple entries..

- sriparna.c35 May 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Maintain two stacks, and push the children of the first stack onto the second. This naturally alternates the order of the rows. When the first stack is empty, swap the stacks. If still empty, we are done.

void PrintZigZag(node* pNode)
{
   std::stack<node*> s1, s2, *pS1 = &s1, *pS2 = &s2;
   bool bOdd = true;
   s1.push(pNode);
   while (pS1->size())
   {
      printf("%d ", pS1->top()->val);
      node* pL = pS1->top()->pLeft;
      node* pR = pS1->top()->pRight;
      node* toPush[2] = {bOdd ? pR : pL, bOdd ? pL : pR};
      pS1->pop();
      for (node* pNext : toPush)
         if (pNext)
            pS2->push(pNext);
      if (!pS1->size())
      {
         std::swap(pS1, pS2);
         bOdd = !bOdd;
         printf("\n");
      }
   }
}

output:

1
2 3
7 6 5 4
8 9

- tjcbs2 May 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This problem is very similar to a Breath First Search graph algorithm where you go level by level and using a null value to mark the level.

I had this interview question once and I messed up. It worked but I used a Queue and Stack to reverse and a toggle flag to determine first Left then Right or first Right and then Left.

Instead of just dumping into a list and traverse using a toggle flag to determine the direction.

public static void PrintInZigZag(Node<T> root)
{
	Queue<Node<T>> q = new Queue<Node<T>>();
	bool left2right = false;

	List<T> output = new List<T>();
	q.Enquue(root);
	q.Enqueue(null);

	while(q.Count > 0)
	{
		Node val = q.Dequeue();

		if(val == null)
		{
			PrintList(output, left2rigth);
			left2rigth = ~left2rigth;
			output.Clear();

			q.Enqueue(null);
		}
		else
		{
			output.Add(val.Data);

			if(val.Left != null)
			{
				q.Enqueue(val.Left);
			}

			if(val.Rigth != null)
			{
				q.Enqueue(val.Rigth);
			}
		}
	}
}

private static void PrintList(List<T> output, bool forward)
{
	int start = 0;
	int end = output.Count -1;
	int plus = 1;
	if(!forward)
	{
		start = output.Count -1;
		end = 0;
		plus = -1;
	}

	for(int i = start; i != end; i += plus)
	{
		Console.Write(output[i].ToString() + " ");
	}

	Console.WriteLine(output[end]);
}

- Nelson Perez May 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Something like the following could help. I did a level order recursive traversal and introduced a variable for direction.

public static void main(String[] args) {
        ZigZagBT bt = new ZigZagBT();
        Node root = bt.createBT();
        int height = bt.getHeight(root, 0);
        boolean ltr = false;
        for (int i = 1; i <= height; i++) {
            bt.traverse(root, i, ltr);
            System.out.println();
            ltr = !ltr;
        }
    }

    private void traverse(Node node, int level, boolean ltr) {
        if (node == null)
            return;
        if (level == 1) {
            System.out.print(node.id);
        } else if (level > 1) {
            if (ltr) {
                if (node.left != null) {
                    traverse(node.left, level - 1, ltr);
                }
                if (node.right != null) {
                    traverse(node.right, level - 1, ltr);
                }
            }else{
                if (node.right != null) {
                    traverse(node.right, level - 1, ltr);
                }
                if (node.left != null) {
                    traverse(node.left, level - 1, ltr);
                }
            }
        }
    }

- Nilaksh Bajpai May 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Almost identical to the most voted solution, but since I did the work I wanted to post it anyways.

Do breadth first search with 2 stacks and a variable for specifying the direction we are moving (left or right) so we can add the child nodes to the stacks in correct order.

/*
 Tree:
        20
        /\
     10     30
     /\     /\
    5 15  25 35
   
  Output:
   20 
   10 30 
   35 25 15 5 
*/
  
function doZigZagOrderTest() {

  var tree = new Tree();

  [20, 10, 30, 5, 15, 25, 35].forEach(function (val) {
    tree.add(val);
  });
  
  zigZagOrder(tree);
}

function zigZagOrder(tree) {

  var currentStack = [tree.node];
  var nextStack = [];
  var printString = '';
  var left = true;

  while (currentStack.length > 0) {

    var n = currentStack.pop();

    if (n != null) {
      printString += n.value + ' ';

      if (left) {
        nextStack.push(n.right);
        nextStack.push(n.left);
      } else {
        nextStack.push(n.left);
        nextStack.push(n.right);
      }
    }

    if (currentStack.length === 0) {
      currentStack = nextStack;
      nextStack = [];
      console.log(printString);
      printString = '';
      left = !left;
    }
  }
}

function Tree() {
  this.node;
}

Tree.prototype.add = function (val) {
  if (!this.node) {
    this.node = new TreeNode(val);
  } else {
    this.node.add(val);
  }
}

function TreeNode(val) {
  this.value = val;
  this.left;
  this.right;
}

TreeNode.prototype.add = function (val) {
  if (val === this.value) {
    return;
  } else if (val < this.value) {
    if (!this.left) {
      this.left = new TreeNode(val);
    } else {
      this.left.add(val);
    }
  } else {
    if (!this.right) {
      this.right = new TreeNode(val);
    } else {
      this.right.add(val);
    }
  }
}

- justinm May 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Similar to what the folk here posted, but maybe slightly more structured and human-readable, but of course longer:

import java.util.Deque;
import java.util.LinkedList;

/**
 * Created by Igor_Sokolov on 5/18/2015.
 */
public class CareerCup_5177676899811328 {
    private static class Node {
        int value;

        Node left;
        Node right;

        public Node(int value) {
            this.value = value;
        }

        @Override
        public String toString() {
           return String.valueOf(value);
        }
    }

    private static Node prepareData() {
        Node one = new Node(1);

        Node two = new Node(2);
        Node three = new Node(3);
        Node four = new Node(4);
        Node five = new Node(5);
        Node six = new Node(6);
        Node seven = new Node(7);
        Node eight = new Node(8);
        Node nine = new Node(9);

        one.left = two;
        one.right = three;

        two.left = four;
        two.right = five;

        three.left = six;
        three.right = seven;

        four.left = eight;
        four.right = nine;

        return one;
    }

    public static void main(String[] args) {
        Node root = prepareData();
        printZigzag(root);
    }

    private static class Entry {
        Node node;
        int level;

        public Entry(Node node) {
            this.node = node;
            this.level = 0;
        }

        public Entry(Node node, int level) {
            this.node = node;
            this.level = level;
        }

        public Entry subLeft() {
            return (this.node.left != null) ? new Entry(this.node.left, this.level + 1): null;
        }

        public Entry subRight() {
            return (this.node.right != null) ? new Entry(this.node.right, this.level + 1) : null;
        }
    }

    private static void printZigzag(Node root) {
        Deque<Entry>[] lists = new Deque[] {new LinkedList<>(), new LinkedList<>()};

        add(lists, new Entry(root));
        int level = 0;

        while (!isEmpty(lists)) {
            Entry e = enqueue(lists, level);

            if (level != e.level) {
                System.out.println();
            }
            System.out.print(e.node + " ");

            Entry subLeft = e.subLeft();
            if (subLeft != null) {
                add(lists, subLeft);
            }

            Entry subRight = e.subRight();
            if (subRight != null) {
                add(lists, subRight);
            }

            level = e.level;
        }
    }

    private static Entry enqueue(Deque<Entry>[] lists, int level) {
        int idx = level % 2;
        if (lists[idx].isEmpty()) {
            return lists[(level + 1) % 2].removeFirst();
        } else {
            return lists[idx].removeFirst();
        }
    }

    private static boolean isEmpty(Deque<Entry>[] lists) {
        return lists[0].isEmpty() && lists[1].isEmpty();
    }

    private static void add(Deque<Entry>[] lists, Entry entry) {
        if (entry.level % 2 == 0) {
            lists[0].addFirst(entry);
        } else {
            lists[1].addLast(entry);
        }
    }
}

- igor.s.sokolov May 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Using 2 stack approach

public String zigzag(Node root) {
        StringBuilder ret = new StringBuilder();

        Stack<Node> currentLevel = new Stack<>();
        Stack<Node> nextLevel = new Stack<>();

        boolean ltr = false;

        currentLevel.push(root);

        while (!currentLevel.isEmpty()) {
            Node node = currentLevel.pop();

            ret.append(node.value);
            ret.append(", ");

            if (ltr) {
                if (node.left != null) {
                    nextLevel.add(node.left);
                }
                if (node.right != null) {
                    nextLevel.add(node.right);
                }
            }
            else {
                if (node.right != null) {
                    nextLevel.add(node.right);
                }
                if (node.left != null) {
                    nextLevel.add(node.left);
                }
            }

            if (currentLevel.isEmpty()) {
                ltr = !ltr;

                Stack<Node> temp = currentLevel;
                currentLevel = nextLevel;
                nextLevel = temp;
            }
        }

        return ret.toString().trim();
    }

- lordbritishix May 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<bits/stdc++.h>
using namespace std;
typedef struct Node
{
int data;
Node *left;
Node *right;
};

stack<Node *> tmp;
stack<Node *> tmp1;
stack<Node *> hhh;
queue <Node *> Qu;


Node * Create(int data)
{
Node *xx=(Node *)malloc(sizeof(Node));
xx->data=data;
xx->left=NULL;
xx->right=NULL;
return xx;
}
void display(Node *root)
{
Node* a,b;
Qu.push(root);
while(!Qu.empty())
{
a=Qu.front();
Qu.pop();
cout<<" "<<a->data<<" "<<endl;
if(a->left)
Qu.push(a->left);
if(a->right)
Qu.push(a->right);

}
}
void zigzag(Node *root)
{
Node* a,b;
int i=1;
tmp.push(root);
while(!tmp.empty())
{
a=tmp.top();
cout<<a->data<<endl;
tmp.pop();
if(i%2==1)
{
if(a->right)
tmp1.push(a->right);
if(a->left)
tmp1.push(a->left);
}
if(i%2==0)
{
if(a->left)
tmp1.push(a->left);
if(a->right)
tmp1.push(a->right);
}
if(tmp.empty())
{
hhh=tmp;
tmp=tmp1;
tmp1=hhh;
i++;
}
}
}


int main()
{
Node *root=Create(1);
root->left=Create(2);
root->right=Create(3);
root->left->left=Create(4);
root->left->right=Create(5);
root->right->left=Create(6);
root->right->right=Create(7);
root->left->left->left=Create(8);
root->left->left->right=Create(9);
display(root);
zigzag(root);
return 0;
}

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

Here is C++ code using two stacks

void zigZagTraversal (treeNode *node)
{  
    using namespace std;
    std::stack <treeNode *> LRQueue;
    std::stack <treeNode *> RLQueue;
    treeNode *currentNode;
    bool leftToRight =true;

    LRQueue.push (node);

    while (!LRQueue.empty () || !RLQueue.empty ()) {
        if (leftToRight) {

              currentNode = LRQueue.top();
	      printf (" %d ", currentNode->x);
	      if (currentNode->r)
		      RLQueue.push (currentNode->r);   //Insert right first
	      if (currentNode->l)
		      RLQueue.push (currentNode->l);
	      LRQueue.pop ();
              if (LRQueue.empty ()) {
		      leftToRight=false;
		      printf ("\n");
	      }
	}
	else {

              currentNode = RLQueue.top();
	      printf (" %d ", currentNode->x);
	      if (currentNode->l)
	      	LRQueue.push (currentNode->l);   //Insert left first
	      if (currentNode->r)
	      LRQueue.push (currentNode->r);
	      RLQueue.pop ();
              if (RLQueue.empty ()) {
		      leftToRight=true;
		      printf ("\n");
	      }

	}
    }
    printf ("\n");
}

- Sach May 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Use BFS approach. Print all nodes of a given level in the same line, then print a new line

for i = 1 to height of tree {
call the recursive function breadthFirst below
System.out.println("*****");
}

private void breadthFirst(Node<V> node, int level) {
    if (node == null) {
      return;
    }if (level == 0) {
      System.out.print(node.value + " ");
      } else if (level >= 1) {
      breadthFirst(node.leftChild, level - 1);
      breadthFirst(node.rightChild, level - 1);
    }
  }

- angshu1986 May 12, 2015 | 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