## Amazon Interview Question for Backend Developers

Country: United States

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

``````My solution

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
*Longest Path from root to leaf Node
* */
public class LongestPath {
public static void main(String[] args) {
BinaryTree bt = new BinaryTree();
Node root =bt.constructTree(bt);
List path = printPath(root);
Iterator itr = path.iterator();
while (itr.hasNext()){
System.out.print(itr.next() +" ");
}
}
public static List<Integer> printPath(Node root){
if(root ==null){
return null;
}
List<Integer> path = new ArrayList<>();
List result = getMaxList(printPath(root.left), printPath(root.right));
if(result!=null) {
}
return path;
}
public static List<Integer> getMaxList(List<Integer> list1, List<Integer> list2){
if(list1==null && list2==null){
return null;
}
if(list1==null){
return list2;
}
if(list2 == null){
return list1;
}
if(list1.size()> list2.size()){
return list1;
}else {
return list2;
}
}
}

Binary Tree

class Node
{
int data;
Node left, right;

Node(int item)
{
data = item;
left = right = null;
}
}

class BinaryTree
{
Node root;
/* Get width of a given level */
int getWidth(Node node, int level)
{
if (node == null)
return 0;

if (level == 1)
return 1;
else if (level > 1)
return getWidth(node.left, level - 1)
+ getWidth(node.right, level - 1);
return 0;
}

/* UTILITY FUNCTIONS */

/* Compute the "height" of a tree -- the number of
nodes along the longest path from the root node
down to the farthest leaf node.*/
int height(Node node)
{
if (node == null)
return 0;
else
{
/* compute the height of each subtree */
int lHeight = height(node.left);
int rHeight = height(node.right);

/* use the larger one */
return (lHeight > rHeight) ? (lHeight + 1) : (rHeight + 1);
}
}

/* Driver program to test above functions */
public Node constructTree( BinaryTree tree) {
/*
Constructed binary tree is:
1
/  \
2    3
/  \    \
4   5     8
/  \
6   7
*/
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.right.right = new Node(8);
tree.root.right.right.left = new Node(6);
tree.root.right.right.right = new Node(7);
return tree.root;
}
}

**OUTPUT**
1 3 8 7``````

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

What I tried is to first calculate the height of the binary tree. Then store the nodes in an array and print when the height is equal to the array length. I know this is not a good approach. Hence I am here.

Here is my working code:

``````package com.company;

class Node{
Node left;
Node right;
int data;
Node(int data){
this.left = null;
this.right = null;
this.data = data;
}

}
public class Main {

public static void main(String[] args) {
int arr[] = new int[10];
int counter=0;
Node node = new Node(5);
node.left = new Node(2);
node.left.left = new Node(1);
node.left.left.left = new Node(7);
node.left.left.right = new Node(8);
node.left.right =  new Node(3);
node.left.right.left =  new Node(9);
node.right =  new Node(6);
node.right.left = new Node(11);
node.right.left.left = new Node(15);
node.right.left.left.right = new Node(10);
node.right.right = new Node(12);
int h = height(node);
printLongestPath(node, arr, counter, h);
}
private static void printLongestPath(Node node, int arr[], int counter, int h){
if(node==null) {
return;
}
arr[counter++] = node.data;
if(node.left == null && node.right == null){
printArray(arr,counter, h);
}
printLongestPath(node.left, arr, counter, h);
printLongestPath(node.right, arr, counter, h);

}
private static void printArray(int arr[], int counter, int h){
if(counter==h) {
for (int i = 0; i < counter; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
private static int height(Node node){
if(node==null)
return 0;
if(node.left == null && node.right == null) {
return 1;
}
else {
return 1 + Math.max(height(node.left), height(node.right));
}
}
}``````

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

It's clearer if you move the check if(counter==h) out of the method like:

``````if(node.left == null
&& node.right == null
&& counter==h)
{
printArray(arr,counter, h);
return; // since left and right are null
}``````

This approach requires two passes of the tree. If you use extra space to keep discovered paths in memory, you could do it with just one pass of the tree.

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

Yes. But what would be the breaking condition in that case.

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

I was thinking about that approach only. But I am unable to implement that. Can you throw some more light on it.?

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

'''

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

int finDepth(node *root)
{
if(root == NULL) return -1;
else
{
int ldepth = finDepth(root->left);
int rdepth = finDepth(root->right);

if(ldepth < rdepth) return rdepth + 1;
else return ldepth + 1;
}
}
'''

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

C++
'''
struct node
{
int data;
node *left;
node *right;
};

int finDepth(node *root)
{
if(root == NULL) return -1;
else
{
int ldepth = finDepth(root->left);
int rdepth = finDepth(root->right);

if(ldepth < rdepth) return rdepth + 1;
else return ldepth + 1;
}
}

'''

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

``````struct node
{
int data;
node *left;
node *right;
};
int finDepth(node *root)
{
if(root == NULL) return -1;
else
{
int ldepth = finDepth(root->left);
int rdepth = finDepth(root->right);

if(ldepth < rdepth) return rdepth + 1;
else return ldepth + 1;
}
}``````

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

``````var longestPath = function (root) {
var longestPathHelper = function (root) {
if(root == null) return ;
arr.push(root.val);
if (checkHeight(root.left) > checkHeight(root.right)) {
longestPathHelper(root.left);
}
else {
longestPathHelper(root.right);
}
}
var arr = [];
longestPathHelper(root);
return arr;
}
var checkHeight = function (root) {
if (root == null) return 0;
return 1 + Math.max(checkHeight(root.left), checkHeight(root.right));
}``````

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

I think encoding the path traversal while finding the max height can be useful information.

``````pair<int, string> longestPath(Node* node) {
if(!node) return make_pair(0, "");

auto L = longestPath(node->left);
auto R = longestPath(node->right);
if(L.first < R.first) return make_pair(R.first + 1, "R" + R.second);
else return make_pair(L.first + 1, "L" + L.second);
}

void printLongestPath(Node* node){
auto P = longestPath(node);
Node* n = node;
for(int i = 0; i < P.second.length(); i++) {
cout << n->val <<" ";
if(P.second[i] == 'L') n = n->left;
else n = n->right;
}
}``````

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

``````function traverse (node, path, length) {
if (!node) {
return {
path: path,
length: length
}
}
var l = traverse(node.left, path, length)
var r = traverse(node.right, path, length)
var o = {}
if (l.length >= r.length) {
path = l.path
length = l.length
direction = ' L'
} else {
path = r.path
length = r.length
direction = ' R'
}
o.length = ++length
o.path = (path.length ? direction + '->' : '') + path
o.path = node.value + o.path
return o
}
module.exports = function (root) {
var path = ''
var length = 0

return traverse(root, path, length)
}

var c = {}
c.value = 3
c.right = c.left = null
var b = {}
b.value = 7
b.right = b.left = null
var a = {}
a.value = 2
a.left = null
a.right = c
var root = {}
root.value = 4
root.left = a
root.right = b

var longest = module.exports(root)
console.log(longest.path, ', ',  longest.length)``````

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

Thanks for your replies. It would be great if I can get any answer in Java.

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

Here is the Java solution

``````import java.util.ArrayList;

public class LongestPath {
static class Node{
int data;
Node left = null;
Node right = null;
Node(int data){
this.data = data;
}
}

public static void main(String[] args) {
// TODO Auto-generated method stub
Node root = 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);
root.left = two;
root.right = three;
three.left = four;
three.right = five;
four.left = six;

//printGraph(root);

ArrayList<Integer> arr = new ArrayList<Integer>();
Node curr = root;
while(curr.left !=null || curr.right!=null){
if(checkDepth(curr.left)>=checkDepth(curr.right)){
curr =  curr.left;
System.out.println("Hello");
}
else {
curr = curr.right;
System.out.println("Hello2");
}
//System.out.println(curr.data);
}

System.out.println(arr.toString());

}

static void printGraph(Node root){
if(root == null)
return;
System.out.println(root.data);

if(root.left != null){
printGraph(root.left);
}

if(root.right != null){
printGraph(root.right);
}
}

static int checkDepth(Node root){
if(root == null)
return 0;

return 1+ Math.max(checkDepth(root.left), checkDepth(root.right));
}
}``````

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

Wouldn't this be O(n^2) time complexity ?

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

Time: O(n) Space: Constant

So here is the idea.
1. In the first iteration calculate the height and store it in a local variable.
2. In the second iteration send this height variable in the recursive method which returns true if this path has that height or returns false.
3. While returning from this method if the invocation of root.left or root.right returns true for this method, then we print the current node and return true so that its parent can be printed too.

``````public static boolean inLongestPath (Tree root, int height) {
if (root==null && height==0)
return true;
if (root==null)
return false;
if (inLongestPath(root.left, height) || inLongestPath(root.right, height)) {
System.out.println(root.val);
return true;
}
}``````

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

Hi guys, here is my working code, it only goes over the tree once, so it's O(n). It uses depth-first.

``````import java.util.ArrayList;
import java.util.List;

/**
* Created by nicolas on 1/11/17.
*/
public class LongestPath {

ArrayList<Node> longestPath = new ArrayList<>();
ArrayList<Node> currentPath = new ArrayList<>();

public static void main(String[] args){
Node node1 = new Node(1);

Node node2 = new Node(2);
Node node3 = new Node(3);

node1.left = node2;
node1.right = node3;

Node node4 = new Node(4);
Node node5 = new Node(5);

node2.left = node4;
node2.right = node5;

Node node8 = new Node(8);
Node node9 = new Node(9);

node4.left = node8;
node4.right = node9;

Node node10 = new Node(10);
Node node11 = new Node(11);

node9.left = node10;
node9.right = node11;

Node node6 = new Node(6);
Node node7 = new Node(7);

node3.left = node6;
node3.right = node7;

System.out.println(new LongestPath().printLongestPath(node1));
}

List<Node> printLongestPath(Node node){

if(node.left == null && node.right == null){
if(currentPath.size() > longestPath.size()){
longestPath = (ArrayList)currentPath.clone();
}
return longestPath;
}

if(node.left != null){
printLongestPath(node.left);
currentPath.remove(currentPath.size()-1);
}

if(node.right != null){
printLongestPath(node.right);
currentPath.remove(currentPath.size()-1);
}

return longestPath;
}
}

class Node{
Node left;
Node right;
int value;

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

@Override
public String toString() {
return " " + value;
}
}``````

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

am I missing something in this question, my python solution, just pass root node

``````def longPath(self,node):
if node is None or (node.left is None and node.right is None):
return 0
else:
return 1+ max(self.longPath(node.left),self.longPath(node.right))``````

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

``````System.out.println("Longest path length => " + calcLongest(root, 1));

private static int calcLongest(BinaryTreeNode<Integer> node , int pathLength){
int leftLongest = pathLength;
if(node.left != null){
leftLongest = calcLongest(node.left, pathLength + 1);
}``````

int rightLongest = pathLength;
if(node.right != null){
rightLongest = calcLongest(node.right, pathLength + 1);
}

return Math.max(leftLongest, rightLongest);
}

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

``````int height(node* pnode)
{
if (NULL == pnode)
return 0;

int lh = height(pnode->left);
int rh = height(pnode->right);
return (1 + max(lh, rh));
}

void print_nodes(node* pnode)
{
node* pcurnode = pnode;

while(pcurnode)
{
print_node(pcurnode);

int lh = height(pcurnode->left);
int rh = height(pcurnode->right);
pcurnode = lh > rh ? pcurnode->left : pcurnode->right;
}
}``````

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

printing in reverse order but in single pass to tree using power of recursion

``````def longest_path(tree, longest_path_arr):
if tree:
lh = longest_path(tree.left, longest_path_arr)
rh = longest_path(tree.right, longest_path_arr)
if lh > rh:
if tree.left:
longest_path_arr.append(tree.left.val)
return 1 + lh
else:
if tree.right:
longest_path_arr.append(tree.right.val)
return 1 + rh
return 0``````

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

Here is my implementation in C#:

A sample Node class:

``````class Node<T>
{
public T Data;
public Node<T> LeftChild;
public Node<T> RightChild;

public Node()
{ }

public Node(T data)
{
this.Data = data;
}
}``````

Longest path Function:

``````public List<T> LongestPathFromRootToNode(Node<T> node)
{
if (node == null)
{
return new List<T>();
}

var left_subtree_path = LongestPathFromRootToNode(node.LeftChild);
var right_subtree_path = LongestPathFromRootToNode(node.RightChild);
if (left_subtree_path.Count >= right_subtree_path.Count)
{
return left_subtree_path;
}
else
{
return right_subtree_path;
}
}``````

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

``````public class LongestPath {

private String longestPath = null;

public static void main(String[] args) {
LongestPath instance = new LongestPath();
TreeNode rootNode = instance.createTree();
System.out.println("Longest path is : " + instance.getLongestPath(rootNode));
}

private TreeNode createTree(){
TreeNode rootNode = new TreeNode(0);
TreeNode node1 = new TreeNode(1);
TreeNode node2 = new TreeNode(2);
TreeNode node3 = new TreeNode(3);
TreeNode node4 = new TreeNode(4);
TreeNode node5 = new TreeNode(5);
TreeNode node6 = new TreeNode(6);
TreeNode node7 = new TreeNode(7);
TreeNode node8 = new TreeNode(8);
TreeNode node9 = new TreeNode(9);
TreeNode node10 = new TreeNode(10);
TreeNode node11 = new TreeNode(11);
TreeNode node12 = new TreeNode(12);

rootNode.setLeft(node1);
rootNode.setRight(node2);

node1.setLeft(node3);
node1.setRight(node4);

node3.setLeft(node5);
node3.setRight(node6);
node6.setRight(node7);
node5.setLeft(node8);

node2.setLeft(node9);
node9.setLeft(node10);
node10.setLeft(node11);
//node11.setRight(node12);

return rootNode;
}
private String getLongestPath(TreeNode rootNode){
if(rootNode==null)
return null;

String path ="";
getPath(path, rootNode);
return longestPath;
}

private Integer getPath(String path, TreeNode node) {

path+="/"+node.value;
if(node.left==null && node.right==null){
String tempPath = longestPath;
if(longestPath!=null && longestPath.contains(","))
tempPath = longestPath.split(",")[0];
if(tempPath==null || tempPath.split("/").length<path.split("/").length)
longestPath = path;
else if(tempPath.split("/").length == path.split("/").length)
longestPath+=","+path;
return 1;
}
if(node.left==null && node.right!=null)
return 1+ getPath(path, node.right);
else if( node.left!=null && node.right==null)
return 1+ getPath(path, node.left);
else
return 1+ Math.max(getPath(path,node.left), getPath(path, node.right) );
}

}

class TreeNode {
TreeNode left;
TreeNode right;
Integer value;

public TreeNode(Integer value) {
left = null;
right= null;
this.value = value;
}

public void setLeft(TreeNode left) {
this.left = left;
}

public void setRight(TreeNode right) {
this.right = right;
}

@Override
public String toString() {
return "TreeNode [left=" + left + ", right=" + right + ", value=" + value + "]";
}
}``````

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

``````import bst
import random
def longest_path_length_bst(root):
if root is None:
return 0
return max(longest_path_length_bst(root.left), longest_path_length_bst(root.right)) + 1

def longest_path_bst(root):
if root is None:
return []

left_path = longest_path_bst(root.left)
right_path = longest_path_bst(root.right)

if len(right_path) > len(left_path):
max_path = right_path
else:
max_path = left_path

max_path.append(root.data)

return max_path

tree = bst.BST()
data = [random.randint(0, 1000000) for x in range(1000)]
tree.insert(data)
print longest_path_bst(tree.root)``````

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

``````import bst
import random
def longest_path_length_bst(root):
if root is None:
return 0
return max(longest_path_length_bst(root.left), longest_path_length_bst(root.right)) + 1

def longest_path_bst(root):
if root is None:
return []

left_path = longest_path_bst(root.left)
right_path = longest_path_bst(root.right)

if len(right_path) > len(left_path):
max_path = right_path
else:
max_path = left_path

max_path.append(root.data)

return max_path

tree = bst.BST()
data = [random.randint(0, 1000000) for x in range(1000)]
tree.insert(data)
print longest_path_bst(tree.root)``````

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

Very similar to question that has been asked at Google. Since no link allowed, id of the question is:

``id=5641503067078656``

The only one difference, in case of Google it was required to print all paths.

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

``````public Stack<Node> GetTallestNode(Node nd)
{

Stack<Node> lheight, rheight;

if (nd.Left != null)
{
lheight = GetTallestNode(nd.Left);
lheight.Push(nd);
}
else
{
lheight = new Stack<Node>();
lheight.Push(nd);
}
if (nd.Right != null)
{
rheight = GetTallestNode(nd.Right);
rheight.Push(nd);
}
else
{
rheight = new Stack<Node>();
rheight.Push(nd);
}
if (lheight.Count > rheight.Count)
{
return lheight;
}
else
{
return rheight;
}
}
public class Node
{
public Node (string val)
{
Value = val;
}
public string Value { get; set; }

public Node Left { get; set; }

public Node Right { get; set; }
}``````

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

public Stack<Node> GetTallestNode(Node nd)
{

Stack<Node> lheight, rheight;

if (nd.Left != null)
{
lheight = GetTallestNode(nd.Left);
lheight.Push(nd);
}
else
{
lheight = new Stack<Node>();
lheight.Push(nd);
}
if (nd.Right != null)
{
rheight = GetTallestNode(nd.Right);
rheight.Push(nd);
}
else
{
rheight = new Stack<Node>();
rheight.Push(nd);
}
if (lheight.Count > rheight.Count)
{
return lheight;
}
else
{
return rheight;
}
}
public class Node
{
public Node (string val)
{
Value = val;
}
public string Value { get; set; }

public Node Left { get; set; }

public Node Right { get; set; }
}

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.

### 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.

### 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.

### 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.