Amazon Interview Question for Senior Software Development Engineers


Team: Amazon Digital Ad
Country: United States
Interview Type: Phone Interview




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

Do a level traversal (in order) you will end up with a List of Lists, each one representing one level, now start from last element of array and keep iterating backwards (this will print all leaf nodes first until you reach root which is the desired answer). Time: O (n) Space O (n)

- Anonymous November 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

This is an Objective-C solution O(n) time and O(n) extra space using a queue and stack and traverse the tree by level.

-(void)getLevelOrderTraversalReverse:(TreeNode *)root{
    
    if(root == nil){
        
        return;
    }
    
    NSMutableArray *queue = [NSMutableArray new];
    NSMutableArray *stack = [NSMutableArray new];
    NSMutableString *result = [[NSMutableString alloc] init];
    
    [queue addObject:root];
    
    while ([queue count] > 0) {
        
        root = [queue objectAtIndex:0];
        [queue removeObjectAtIndex:0];
        
        if(root.rigth != nil){
            
            root.rigth.level = root.level + 1;
            [queue addObject:root.rigth];
        }
        
        if(root.left != nil){
            
            root.left.level = root.level + 1;
            [queue addObject:root.left];
        }

        [stack addObject:root];
    }
    
    while([stack count] > 0){
        
        root = [stack lastObject];
        [stack removeLastObject];
        
        [result appendString:[NSString stringWithFormat:@"%i ", root.value]];
    }
    
    NSLog(@"\n\nBy Level Reverse: %@\n", result);
}

- oscarsanchez1937 November 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

gekko is correct, it is meaningless. But..
In any case, given this json :

{
  "value" : 1 , "children" : [
    { "value" : 2 , "children" : [ 
       { "value" : 4 , "children" : [] },
       { "value" : 5 , "children" : [] }
    ] } ,
    { "value" : 3 , "children" : [ 
       { "value" : 6 , "children" : [] },
       { "value" : 7 , "children" : [] }
    ] }
  ]
}

This code is going to work out well for the reverse God knows what level order thing:

/* 
A Level order traversal.
The key is to understand that, 
you need to maintain two queues, one for current,
another for next level.
After a level is exhausted, 
one needs to replace that queue by the one from built up.
As we can see, this won't solve Amazon's problem,
Which is a reverse level order traversal.
So, we need to use a stack to store the per level nodes 
which are to be stored in a queue! Thus, 
The solution becomes , storing the queue in a stack!
But then, who needs queues? We can simply use a list! 
*/
def reverse_level_order( root ){
  cur = list( root ) // current level 
  stack  = list() ; stack.push( list( cur ) )    
  while ( !empty(cur) ){
     next = list() 
     for ( node : cur ){
        for ( child : node.children ){
           next += child 
        }
     }
     // push the level into the stack 
     stack.push ( list( next) )
     cur = next 
  }
  // now unwind the stack 
  while ( !empty(stack) ){
    level = stack.pop()
    for ( node : level ){
      printf( ' %s ' , node.value )
    }
  }
  println()
}
// call it 
reverse_level_order( json( 'tree.json' ,true ) )

I am using imperative paradigm - to ensure that it stays comprehensible.

- NoOne November 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 4 vote

This is a reverse level order traversal problem. Modify the level order traversal code , insert a statement to insert the data into the stack where you would normally print the data. After you visited all the nodes. Now pop everything from stack, as you pop and print you should see node's data printed in reverse level order traversal.

some one down voted my answer, can you explain why this is not correct

- smurugu November 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

func PrintByLevel(root *TreeNode)  {
	data := [][]int{}
	_ByLevel(root, 0, &data)
	for i:= len(data) - 1; i >= 0; i-- {
		for _, v := range data[i] {
			fmt.Print(v)
		}
	}
}

func _ByLevel(root *TreeNode, level int, data *[][]int) {
	if root == nil {
		return
	}
	if len(*data) <= level {
		*data = append(*data, []int{})
	}
	(*data)[level] = append((*data)[level], root.val)
	_ByLevel(root.left, level + 1, data)
	_ByLevel(root.right, level + 1, data)
}

- dmitry.labutin November 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Write level order traversal algo, just store the element in array and print the array in reverse order.

- dinkar1708 November 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be solved either using iterative breadth or recursive depth first search.

// breadth first approach, O(N)
    private static Stack<LinkedList<TreeNode>> createLevelLinkedListBFS(TreeNode root) {
        Stack<LinkedList<TreeNode>> result = new Stack<>();
        LinkedList<TreeNode> workingTree = new LinkedList<>();
        workingTree.add(root);
        while (!workingTree.isEmpty()) {
            result.add(workingTree);
            LinkedList<TreeNode> levelNodes = workingTree;
            workingTree = new LinkedList<>();
            for (TreeNode node : levelNodes) {
                if (node.left != null) {
                    workingTree.add(node.left);
                }
                if (node.right != null) {
                    workingTree.add(node.right);
                }
            }
        }
        return result;
    }

    // depth first approach, O(N)
    private static Stack<LinkedList<TreeNode>> createLevelLinkedListDFS(TreeNode root) {
        ArrayList<LinkedList<TreeNode>> levelsList = new ArrayList<>();
        createLevelLinkedListDFS(root, levelsList, 0);
        Stack<LinkedList<TreeNode>> result = new Stack<>();
        for (LinkedList<TreeNode> nodes : levelsList) {
            result.push(nodes);
        }
        return result;
    }

    private static void createLevelLinkedListDFS(TreeNode root, ArrayList<LinkedList<TreeNode>> result, int level) {
        if (result.size() == level) {
            result.add(new LinkedList<>());
        }
        LinkedList<TreeNode> nodes = result.get(level);
        nodes.add(root);
        if (root.left != null) {
            createLevelLinkedListDFS(root.left, result, level + 1);
        }
        if (root.right != null) {
            createLevelLinkedListDFS(root.right, result, level + 1);
        }
    }

- Coder November 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

BFS in largest first order, and then reverse the result:

public static String bottomsUp(Node root){
		StringBuilder sb = new StringBuilder();
		Queue<Node> q = new LinkedList<>();
		q.add(root);
		while(!q.isEmpty()) {
			Node n = q.poll();
			sb.append(n.value);
			if (n.right != null) {
				q.add(n.right);
			}
			if (n.left != null) {
				q.add(n.left);
			}
		}		
		return sb.reverse().toString();
	}

- Doug November 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void traverse(root){
	Queue q = new Queue();
	q.addLast(root)
	while(!q.isEmpty()){
		root r = q.removeFirst();
		res += r.val;
		q.addLast(r.right);
		q.addLast(r.left);
	}
	sout(res.reverse().toString());
}

- Tamil selvan November 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's the solution in Python.

Traverse the tree with breadth-first search, going right to left, and add the values to a list.

Reverse the values in the list to get a reverse breadth-first search, going left to right.

root = Node(1, Node(2, Node(4), Node(5)), Node(3, Node(6), Node(7)))

from collections import deque
queue = deque([root])
values = []
while queue:
    node = queue.popleft()
    if node.right is not None:
        queue.append(node.right)
    if node.left is not None:
        queue.append(node.left)
    values.append(node.value)

# print the values in reverse
print(''.join([str(i) for i in values[::-1]]))

- Tangestani November 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static int mid=0;
public void level_order_tree(node root,int i){
stack = new node[size+1];
if(mid == 0 && root != null){
stack[mid] = root;
mid++;
}
while(root != null){
if(root.left != null && root.right !=null){
stack[mid] = root.right;
mid++;
stack[mid] = root.left;
mid++;
root = stack[i];
i++;
}else if(root.left != null && root.right == null){
stack[mid] = root.left;
mid++;
root = stack[i];
i++;
}else if(root.right != null && root.left == null){
stack[mid] = root.right;
mid++;
root = stack[i];
i++;
}else{
root = stack[i];
i++;
}
}
for(int j = mid-1;j>=0;j--){
System.out.print(stack[j].data);
}}

- nitesh mangla November 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use BFS with two stacks, that will do it!

bfsModTraversal(Node root){
Stack<Node> visitStack = new Stack<Node>();
Stack<Node> traversalStack = new Stack<Node>();

	visitedStack.push(root);
	while(!visitStack.isEmpty()) {
		
		Node curr = visistStack.pop();
		traversalStack.push(curr);
		for(Node var in curr.children)
			visistStack.push(var);
	}
	
	while(!traversalStack.isEmpty()) {
		System.out.println(traversalStack.pop().data);
	}
}

- liju.leelives November 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include "stdafx.h"
#include <boost/core/is_same.hpp>

#include <boost/core/demangle.hpp>
#include <typeinfo>
#include <unordered_set>

#include <vector>
#include <thread>
#include <future>
#include <numeric>
#include <iostream>
#include <chrono>

#include <algorithm>
#include <utility>
#include <atomic>

 using std::unordered_set;
 using namespace std;

 struct node
 {
	 int data;
	 node* left;
	 node* right;

	 node() :left(nullptr), right(nullptr) {}
 };

 void PrintByLevel(node * root,
	 std::vector <std::vector < int>> &v,
	 int level)
 {
	 if (root == nullptr) return;
	 if (level >= v.size()) v.push_back({});

	 v[level].push_back(root->data);

	 ++level;

	 PrintByLevel(root->left, v, level);

	 PrintByLevel(root->right, v, level);
 }

 void LevelOrder(node * root)
 {
	 if (root == nullptr) return;

	 std::vector <std::vector < int> > v(1);

	 PrintByLevel(root,
		 v,
		 0);

	 for (auto & line : v)
		 for (auto & i : line)
			 cout << i << " ";
 }

 void LevelBackOrder(node * root)
 {
	 if (root == nullptr) return;

	 std::vector <std::vector < int> > v(1);

	 PrintByLevel(root,
		 v,
		 0);

	 for (auto rit = v.rbegin(); rit != v.rend(); ++rit)
	 {
		 for (auto &it : *rit)
			cout << it;
	 }


	 /*
	 for (auto rit = v.rbegin(); rit != v.rend; ++rit)
		 for (int i = *rit[0]; i < )
			 cout << *rit << " ";
	 */
 }

 int main()
 {
	 node * root = new node();
	 root->data = 1;

	 node * leftNode = new node();
	 leftNode->data = 2;

	 node * rightNode = new node();
	 rightNode->data = 3;

	 root->left = leftNode;
	 root->right = rightNode;

	 node * leftleftNode = new node();
	 leftleftNode->data = 4;

	 node * leftrightNode = new node();
	 leftrightNode->data = 5;

	 leftNode->left = leftleftNode;
	 leftNode->right = leftrightNode;

	 node * rightleftNode = new node();
	 rightleftNode->data = 6;

	 rightNode->right = rightleftNode;

	 node * leftrightNode3 = new node();
	 leftrightNode3->data = 7;
	 leftrightNode->left = leftrightNode3;


	 //LevelOrder(root);
	 LevelBackOrder(root);
	 //

	 /*
				     1
			    2		  3
		     4	   5		6
				  7 
	 */

 }

- AndreasCorreras November 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void void printTreeLevelFromBottom(Node root) {
Queue<Node> queue = new LinkedList<>();
List<Integer> printTreeList = new ArrayList<>();
printTreeList.add(root.data);
queue.add(root);
while (!queue.isEmpty()) {
Node node = queue.poll();
Node leftNode = node.left;
Node rightNode = node.right;

if (rightNode != null) {
printTreeList.add(rightNode.data);
queue.add(rightNode);
}

if (leftNode != null) {
printTreeList.add(leftNode.data);
queue.add(leftNode);
}
}

for (int index = printTreeList.size() - 1; index >= 0; index--) {
System.out.print(printTreeList.get(index) + " ");
}


}

- Brijesh Thakur November 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void void printTreeLevelFromBottom(Node root) {
        Queue<Node> queue = new LinkedList<>();
        List<Integer> printTreeList = new ArrayList<>();
        printTreeList.add(root.data);
        queue.add(root);
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            Node leftNode = node.left;
            Node rightNode = node.right;

            if (rightNode != null) {
                printTreeList.add(rightNode.data);
                queue.add(rightNode);
            }

            if (leftNode != null) {
                printTreeList.add(leftNode.data);
                queue.add(leftNode);
            }
        }

        for (int index = printTreeList.size() - 1; index >= 0; index--) {
            System.out.print(printTreeList.get(index) + " ");
        }
}

- Brijesh Thakur November 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution with O(N) time and O(1) memory (modifying tree):
Let's convert binary tree into a linked list where a right link points to the next element. And print all elements in a linked list.

import java.io.*;
import java.util.*;

public class Main {

    static class TreeNode {
        int x;
        TreeNode left;
        TreeNode right;

        public TreeNode(int x) {
            this.x = x;
        }
    }

    static class Result {
        TreeNode start;
        TreeNode end;

        public Result(TreeNode start, TreeNode end) {
            this.start = start;
            this.end = end;
        }
    }

    private void solve(TreeNode root) {
        Result res = flatten(root);
        TreeNode curr = res.start;
        while (curr != null) {
            System.out.print(curr.x + " ");
            curr = curr.right;
        }
        System.out.println();
    }


    private Result flatten(TreeNode root) {
        if (root == null || (root.left == null && root.right == null)) {
            return new Result(root, root);
        }

        if (root.left == null) {
            Result right = flatten(root.right);
            right.end.right = root;
            root.right = null;
            return new Result(right.start, root);
        } else if (root.right == null) {
            Result left = flatten(root.left);
            left.end.right = root;
            root.right = null;
            return new Result(left.start, root);
        } else {
            Result left = flatten(root.left);
            Result right = flatten(root.right);
            left.end.right = right.start;
            right.end.right = root;
            root.right = null;
            return new Result(left.start, root);
        }
    }
}

- Acarus November 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// Reversed BFS traversal
using System;
using System.Collections.Generic;

public class Test
{
static Stack<Node> internalStack = new Stack<Node>();
class Node
{
public Node(int value, Node left, Node right)
{
Left = left;
Right = right;
Value = value;
}

public readonly Node Left;
public readonly Node Right;
public readonly int Value;
}
public static void Main()
{
// your code goes here
var root = new Node(1, new Node(2, new Node(4, null, null), new Node(5, null, null)),
new Node(3, new Node(6, null, null), new Node(7, null, null)));
internalStack.Push(root);
Visit(root);
while(internalStack.Count > 0)
{
var item = internalStack.Pop();
Console.Write(item.Value);
}
}


private static void Visit(Node root)
{
if(root == null) return;
if(root.Right != null)
{
internalStack.Push(root.Right);
}
if(root.Left != null)
{
internalStack.Push(root.Left);
}
Visit(root.Right);
Visit(root.Left);
}
}

- tsarapin November 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

can't we just use a stack and pre-order traversal here, i.e. stack.push(current), stack.push(left), stack.push(right)

- AD November 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I push the children nodes from right to left, so each level is printed from left to right:

public void printTree(Node root){
	Queue<Node> nodes = new Queue<>();


	if(root != null)
		nodes.add(root);


	Stack<Integer> result = new Stack<>();


	while(!nodes.isEmpty()){
		Node node = nodes.pop();
	
		result.add(node.val);


		if(node.right != null)
			nodes.add(node.right);


		if(node.left != null)
			nodes.add(node.left);
	}


	while(!result.isEmpty())
		System.out.print(result.pop() + “ “);


}

- libertythecoder November 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

can't you just do this with simple recursion?
Post Order Traversal

void postOrder(TreeNode* root){
	if (root== NULL) return;
	postOrder(root->left);
	postOrder(root->right);
	cout << root->val << " ";

}

- jajajaj1230105 November 29, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void downUp(BNode node) {
Queue<BNode> q = new LinkedList<BNode>();
Stack<Integer> s = new Stack<Integer>();
q.add(node);
while (!q.isEmpty()) {
BNode node1 = q.remove();
s.push(node1.val);

if (node1.right != null) {
q.add(node1.right);
}
if (node1.left != null) {
q.add(node1.left);
}
}
while (!s.isEmpty()) {
System.out.println(s.pop());
}
}

- Anonymous November 30, 2016 | 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