Amazon Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




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

/*
* use Depth First Search approach and pre-order tree traversal
* push current node and its current node height into the stacks, s1 and s2
* use a local variable height to keep track on the maximum tree height
*/
public void getHeight(Node p)
{
int height = 0; //keep track on the max tree height
Stack s1 = new Stack(); //keep track on the tree node
Stack s2 = new Stack(); //parallel with s1 to keep track on the tree node height

if (p!= null)
{
s1.push(p);
s2.push(1);
}

while (!s1.isEmpty())
{
p = s1.pop();
level = s2.pop();

if (level > height) //update maximum tree height
height = level;

if (p.left != null)
{
s1.push(p.left);
s2.push(level+1);
}
if (p.right != null)
{
s1.push(p.right);
s2.push(level++);
}
}

return level;
}

- g September 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

return height;

- anonymous September 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Well, BFS its when we using queue - we go through all nodes on the first level, then through all nodes on the second level etc

When we use stack situation is different. Using stack is the same as using recursive function. It will work just as DFS:

{
     Stack nodes = new Stack();
     Stack levels = new Stack();
     stack.push(root);
     levels.push(0);
     int maxLevel = 0;

      while(!stack.isEmpty()) {
               
            Node currentNode = stack.pop();
            int currentLevel = levels.pop();

           if(currentLevel > maxLevel) {
                 maxLevel = currentLevel;
            }
            
            if(currentNode.getRightChild() != null) {
                 stack.push(currentNode.getRightChild());
            }

            if(currentNode.getLeftChild() != null) {
            	stack.push(currentNode.getLeftChild());
            }
      }
  
  return maxLevel;
}

To ensure that it works just like DFS assume we have such tree

1
/ \
2 3
/ \ / \
4 5 6 7

then procedure acts like this:
1) adds 1 to the stack
2) pops 1 from the stack, pushes 3 to the stack then pushes 2 to the stack, 2 is in the head
3) pops 2 from the stack, pushes 5 to the stack then pushes 4 to the stack
4) pops 4 and pushes nothing
5) pops 5 and pushes nothing
6) pops 3, pushes 7 and 6
7) pops 6 and 7 and that's it

so the route is like 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7
just like in the BSF.
Cheers!

- Andrey September 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Oh, sorry, I forgot to update levels on each step, so we should change this

if(currentNode.getRightChild() != null) {
                 stack.push(currentNode.getRightChild());
      }
      
          if(currentNode.getRightChild() != null) {
                 stack.push(currentNode.getRightChild());
            }

to this:

if(currentNode.getRightChild() != null) {
            stack.push(currentNode.getRightChild());
            levels.push(currentLevel + 1);  
      }
      
          if(currentNode.getRightChild() != null) {
                 stack.push(currentNode.getRightChild());
                 levels.push(currentLevel + 1);
            }

- Andrey September 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

}} public void getHeight(Node p)

- Anonymous September 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

So much code why?????

//With recursion
int findHeight(Node n)
{
	if(n==null)
		return 0;
	int maxH=0;
	for(Node n=n.child.head; n; n=n.next)
		MAX(maxH,findHeight(n));
	return maxH+1;
}

now if can't use the run time stack (why you would ever do that I do not know...

class StackFrame
{
public:
	int height;
	node n;
	StackFrame(Node n, int h){this.n=n; height=h;}
}

int findHeight(Node n)
{	
	if(n==null)
		return 0;
	Stack<StackFrame> frames=new Stack<StackFrame>;
	int maxH=0;
	frames.push(new StackFrame(n, 1));
	
	while(frames.size()>0)
	{
		StackFrame f=frames.pop();
		maxH=MAX(maxH,f.height);
		for(Node c : f.children)	//assume public children list 
			frames.push(c, f.height+1);
	}
	return maxH;

}

- Anonymous September 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

well that up there without the typos ;-)

- Anonymous September 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This question is basically asking for iterative version of DFS or more specifically Postorder (which is also a DFS). So idea is do a iterative postorder using stack(one or two stack, depends you want complicated or simple solution) and then keep track of the size of stack.

- rgaut September 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you explain how to use 1 stack method ?

- !@# September 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

just google it dude postorder with one stack !!!!

- rgaut September 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

For this question, you want to use DFS using post order traversal - that is visit left, right and self.

To calculate the height, the stack will always represent a *single* path of the tree. Therefore, during the self node valuation, just take the maximum of current stack size and the max thus far.

public int getHeight(Node node) {
     if (node == null)
	return -1;

     int max = -1;
     Stack<Node> stack = new Stack<Node>();
     stack.add(node);
     
     while (!stack.isEmpty()) {
 	Node current = stack.peek();

	if (current.left != null) {
		stack.add(current.left);
		continue;
	}

	if (current.right != null) {
		stack.add(current.right);
		continue;
	}
	
	max = Math.max(max, stack.size() - 1);
	stack.pop();
     }
    
     return max;
}

For the N-ary tree, it's bit tricky. You want to use the same strategy for the BST DFS, however since there is N number of children, you must keep track of the nodes that's visited or keep an index on each children node that you're processing.

public int height(GraphNode node) {
	Set<GraphNode> visitedNodeSet = new HashSet<>();
	Stack<GraphNode> stack = new Stack<GraphNode>();
	int max = -1;

	if (node == null)
		return max;

	while (!stack.isEmpty()) {
		GraphNode currentNode = stack.peek();
		
		for (GraphNode childNode : currentNode.children()) {	
			if (!visitedNodeSet.contains(childNode)) {
				stack.add(childNode);
				visitedNodeSet.add(childNode);
				continue;
			}
		}

		max = Math.max(max, stack.height() - 1);
		stack.pop();
	}

	return max;
}

On a side note, it's pretty terrible they asked to use a stack. It's so much less code to do it recursively.

- frankierock September 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

first code doesn't work, it just goes into infinite recursion, you need to mark nodes visited

- alisovenko September 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

package binarytree;

import java.util.ArrayDeque;
import java.util.Deque;

import org.junit.Assert;
import org.junit.Test;

public class BinaryTreeHeightNonRecursive {
	/**
	 * Calculates height for binary tree using stack
	 * 
	 * @param root
	 *            the root node of binary tree
	 * @return height of tree
	 */
	public int height(Node<Integer> root) {
		if (root == null)
			return 0;
		Deque<NodeWrapper<Integer>> stack = new ArrayDeque<>();
		int height = 0;
		NodeWrapper<Integer> wrapper = new NodeWrapper<>(root, height);
		stack.push(wrapper);
		while (!stack.isEmpty()) {
			NodeWrapper<Integer> current = stack.pop();
			if (height < current.height) {
				height = current.height;
			}
			Node<Integer> left = current.node.left;
			if (left != null) {
				wrapper = new NodeWrapper<>(left, current.height + 1);
				stack.push(wrapper);
			}
			Node<Integer> right = current.node.right;
			if (right != null) {
				wrapper = new NodeWrapper<>(right, current.height + 1);
				stack.push(wrapper);
			}
		}

		return height;
	}

	@Test
	public void testHeight() {
		Node<Integer> node = new Node<>(10);
		node.left = new Node<>(8);
		node.right = new Node<>(13);
		node.left.left = new Node<>(5);
		node.left.right = new Node<>(9);
		node.right.right = new Node<>(17);
		node.right.right.right = new Node<>(19);
		int height = height(node);
		Assert.assertEquals(3, height);
	}

	/**
	 * Wrapper class for Node to keep height
	 * 
	 * @param <T>
	 */
	public class NodeWrapper<T> {
		Node<T> node;
		int height;

		public NodeWrapper(Node<T> node, int height) {
			this.node = node;
			this.height = height;
		}
	}

	/**
	 * Wrapper class for BTreeNode to keep height
	 * 
	 * @param <T>
	 */
	public class BTreeNodeWrapper<T> {
		BTreeNode<T> node;
		int height;

		public BTreeNodeWrapper(BTreeNode<T> node, int height) {
			this.node = node;
			this.height = height;
		}
	}

	/**
	 * Calculates height for n-ary tree using stack
	 * 
	 * BTree is used for an example
	 * 
	 * @param root
	 *            the root node of BTree
	 * @return height of tree
	 */
	public int height(BTreeNode<Integer> root) {
		if (root == null)
			return 0;
		Deque<BTreeNodeWrapper<Integer>> stack = new ArrayDeque<>();
		int height = 0;
		BTreeNodeWrapper<Integer> wrapper = new BTreeNodeWrapper<>(root, height);
		stack.push(wrapper);
		while (!stack.isEmpty()) {
			BTreeNodeWrapper<Integer> current = stack.pop();
			if (height < current.height) {
				height = current.height;
			}

			BTreeNode<Integer>[] children = current.node.children;
			for (int i = 0; i < children.length; i++) {
				if (children[i] != null) {
					wrapper = new BTreeNodeWrapper<>(children[i],
							current.height + 1);
					stack.push(wrapper);
				}
			}
		}

		return height;
	}

	@Test
	public void testHeightBTree() {
		BTreeNode<Integer> node = new BTreeNode<>(3, false);
		node.keys = new Integer[] { 10 };

		node.children[0] = new BTreeNode<>(3, false);
		node.children[0].keys = new Integer[] { 5 };
		node.children[2] = new BTreeNode<>(3, false);
		node.children[2].keys = new Integer[] { 13 };

		node.children[0].children[2] = new BTreeNode<>(3, true);
		node.children[0].children[2].keys = new Integer[] { 9 };

		node.children[2].children[2] = new BTreeNode<>(3, false);
		node.children[2].children[2].keys = new Integer[] { 17 };

		node.children[2].children[2].children[2] = new BTreeNode<>(3, true);
		node.children[2].children[2].children[2].keys = new Integer[] { 19 };

		int height = height(node);
		Assert.assertEquals(3, height);
	}
}


package binarytree;

public class Node<T> {
	T value;
	Node<T> left;
	Node<T> right;
	
	public Node(T value, Node<T> left, Node<T> right) {
		this.value = value;
		this.left = left;
		this.right = right;
	}

	public Node(T value) {
		this(value, null, null);
	}
	
	public String toString() {
		return "[Node:[value: " + this.value + "]]";
	}
}


package binarytree;

import java.lang.reflect.Array;

public class BTreeNode<T> {
	T[] keys;
	BTreeNode<T>[] children;
	int t; // number of keys
	boolean isLeaf;
	
	@SuppressWarnings("unchecked")
	public BTreeNode(int t, boolean isLeaf){
		this.t = t;
		this.isLeaf = isLeaf;
		keys = (T[])Array.newInstance(Object.class, 2*t -1);
		children = new BTreeNode[2*t];
	}	
}

- Hope September 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The correct solution is to use stack and get its size at the end of path, but it's important to avoid infinite recursion. So we need to mark branches, we have already processed: if we've already gone to left subtree, we need to mark its root as visitited:

public static int height(Node root) {
        LinkedList<Node> stack = new LinkedList<>();
        stack.add(root);
        Set<Node> marked = new HashSet<>();

        int maxHeight = 0;
        while (!stack.isEmpty()) {
            Node last = stack.getLast();
            if (last.left != null && !marked.contains(last.left)) {
                stack.addLast(last.left);
                marked.add(last.left);
            }
            else if (last.right != null && !marked.contains(last.right)) {
                stack.addLast(last.right);
                marked.add(last.right);
            }
            else {
                maxHeight = Math.max(maxHeight, stack.size());
                stack.removeLast();
            }
        }

        return maxHeight;
    }

    public static void main(String[] args) {
        Node root = new Node(null, 8);
        root.add(4);
        root.add(2);
        root.add(6);
        root.add(7);
        root.add(15);
        root.add(17);
        root.add(19);
        root.add(11);

        System.out.println(height(root));
    }

For multi-children variant we do the same but just iterate through children looking for unmarked nodes:

while (!stack.isEmpty()) {
            Node last = stack.getLast();
            Node child;
            if ((child = findNextNotMarked(last.children, marked)) != null) {
                stack.addLast(child);
                marked.add(child);
            }            
            else {
                maxHeight = Math.max(maxHeight, stack.size());
                stack.removeLast();
            }
        }

- alisovenko September 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int height =0;
int max_height =0;
do
{
stack.add(tree);
height ++;
while(tree != null)
{
stack.add(tree->left);
height = height +1;
tree = tree -> left;
}
if(height > max_height)
max_height = height;
tree = stack.pop();
height = height -1;
while( tree <0 ||tree->right != null)
{
if(tree < 0)
tree= - tree;
tree = stack.pop();
height = height -1;
}
p = -tree;
stack.add(p);
height = height +1;
tree = tree-> right;
}while(!stack.isEmpty())

- Anonymous September 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public void getheight(Node root)
	{
		int elementscnt=0;
		Node p=root;
		Queue<Node> queue=new PriorityQueue<Node>();
		if(p!=null)
		{
			queue.add(p);
			elementscnt+=1;
		}
		while(!queue.isEmpty())
		{
			p=queue.poll();
			
			System.out.println(p.key);
			if(p.left!=null)
			{
				queue.add(p.left);
				elementscnt+=1;
			}
			if(p.right!=null)
			{
				queue.add(p.right);
				elementscnt+=1;
			}
		}
		
		double height=Math.log(elementscnt+1)/Math.log(2.0);
	}

- lal September 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this isa kind of bfs solution. And asked to use only stack.

- Ghosh September 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this also assumed the tree is balanced tree.

- cindy September 29, 2014 | 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