## Amazon Interview Question for Software Engineer / Developers

• 0

Country: India
Interview Type: In-Person

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

if(root == null) return null;

if(l == null && r == null) {
n.appendToTheFront(root.data);
return arr;
}else if(l == null && r != null){
for(int i=0;i<r.size();i++){
r.get(i).appendToTheFront(root.data);
}
return r;
}else if(l != null && r == null){
for(int i=0;i<l.size();i++){
l.get(i).appendToTheFront(root.data);
}
return l;
}else{
if(l.get(0).sum > r.get(0).sum) {
for(int i=0;i<l.size();i++){
l.get(i).appendToTheFront(root.data);
}
return l;
}else if(l.get(0).sum < r.get(0).sum){
for(int i=0;i<r.size();i++){
r.get(i).appendToTheFront(root.data);
}
return r;
}else{
for(int i=0;i<l.size();i++){
l.get(i).appendToTheFront(root.data);
}
for(int i=0;i<r.size();i++){
r.get(i).appendToTheFront(root.data);
}
return l;
}
}

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

My idea is similar to the Vincent above. You have to use the parent pointer to save the time complexity. The whole idea explains as followings:
1) when constructing the tree, each node saves these information:
value, left pointer, right pointer, and an additional parent pointer.
2) Use BFS trick to traversing the tree, and calculate the sum of path from root to current node. If the node:
a. has all child node(s) non-positive
b. has no child node
then store this node to the candidate array. (This is because that only these two types of node can be the maximum path.)
3. After the traverse, we found the maximum, then traverse the candidate array, and print the maximum path(s) following the parent link.
Note that the size of candidate array is smaller than N.

The total time complexity is O(N).

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

As we go from parent node to it's child node in binary tree, we send current path sum to all it's childern, we maintain two global variable one is max_sum and another is count, we set count to be zero and now start from root node, it send it's node value to it's childern, then add it with their value and send final sum to their childerns, whenever someone reaches to end(leaf node), it check weather it's sum is greater or equal or less, if equal then it increment count, if less, then do nothing, if greater then set count = 1 and max_sum to it's sum.
so after one tree trival we get both max_sum and count.
Now if we want to print the paths also then we do following
as we know how many max_sum path exist, Now we create that many arrays of integer element, each array have some unique Id, now we start again with the same procedure but with one difference, we send current sum to childern nodes, but we want something from them, what we want is a structure which contain a integer(which tells how many path having max_sum are having current node in comman) and id's of all arrays., once we get these data from all it;s childerns, then we print the node value in all those arrays, and return total sum and all array's id, which we get from both or one of it's childern. if we get zero as integer value from all childern then we return zero.
but ya here we visit all nodes on the tree 3 times, once when we find out max_count, and second time when we go forward to locate leaf node of all the paths whose sum is max_sum and thrid time when we return from all these leaf node to root node.

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

You can use BFS in order to solve this problem.

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

I think use dfs better than bfs

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

traverse just once? does recursive solution count as once?

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

Every node in the tree has exactly one path. The trick here for best time complexity is to calculate the sum at each node as you're traversing. Preorder traversal seems like the best option. Here is a solution you can test out. This includes updates for all three of the requirements of the problem.

The time complexity of this algorithm is O(n). Required space will be equal to the size of the binary tree plus the size of each max path. The worst (and rare) case for space requirements would be if all nodes in the tree were equal to zero, as a linked list must be stored for every path.

``````public class Main {
public static class ListNode {
public int value;

public ListNode(int d1) {
value = d1;
}

//Print ListNodedata
System.out.print(value + " ");
}
}

private ListNode first;

first = null;
}

//Returns true if list is empty
public boolean isEmpty() {
return first == null;
}

//Inserts a new ListNode at the first of the list
public void insert(int d1) {
}

//Deletes the ListNode at the first of the list
public ListNode delete() {
ListNode temp = first;
return temp;
}

//Prints list data
public void printList() {
}
System.out.println("");
}
}

public static class TreeNode {
public TreeNode leftChild = null;
public TreeNode rightChild = null;
int mValue;
TreeNode(int v) {
mValue = v;
}
public int getValue() {
return mValue;
}
}

public static class BinaryTree {
public TreeNode root;
public int currentMax = 0;

public BinaryTree(int rootValue) {
root = new TreeNode(rootValue);

/* Test case */
fillTestTree();

}

public void fillTestTree() {
root.leftChild = new TreeNode(4);
root.rightChild = new TreeNode(-1);
root.leftChild.leftChild = new TreeNode(1);
root.rightChild.leftChild = new TreeNode(5);
root.leftChild.rightChild = new TreeNode(0);
root.rightChild.rightChild = new TreeNode(6);
}

}
newList.insert(value);
return newList;
}

public void printPaths() {
System.out.println("Max paths are: ");
for(int i = 0; i < pathsToMax.size(); i++) {
pathsToMax.get(i).printList();
}
}

public void getMaxSum(TreeNode n, int currentSum, LinkedList l) {
//Visit current node
if(n == null) {
//throw...
}

int sumAtCurrentNode = n.getValue() + currentSum;

if(sumAtCurrentNode >= currentMax) {
if(sumAtCurrentNode > currentMax) {
pathsToMax = null;
}
currentMax = sumAtCurrentNode;
//Blow away our current set of paths due to the new max

}

//Traverse left
if(n.leftChild != null) {
getMaxSum(n.leftChild, sumAtCurrentNode, appendToNewList(l, n.leftChild.getValue()));
}
//Traverse right
if(n.rightChild != null) {
getMaxSum(n.rightChild, sumAtCurrentNode, appendToNewList(l, n.rightChild.getValue()));
}
}
}

public static void main(String[] args) {
//Test list and tree
BinaryTree btree = new BinaryTree(-1);
btree.getMaxSum(btree.root, 0, btree.appendToNewList(l, -1));
btree.printPaths();
System.out.println("Max sum is: " + btree.currentMax);
}
}``````

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

your solution find's only max sum . (1) of problem . what about (2) and (3) ?

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

You're right. I specified at the end to be sure to store away the path to the node with the maxSum and to be prepared to store multiple paths. You'd just pass a linked list (with a getTail() method) as you went through the traversal along with the currentSum. And you would need a way to distinguish two nodes that had the same value, so you would want to make sure that each node had a unique identifier. Either that, or you could just store an array of directions like "Left Right Right".

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

there are n nodes. so there can be n path's . how will you store all n path's in O(n).

you'll need to copy linked list [path] for both childs of a parent . ie. O(n)
in for every parent node . thus making it O(n^2)

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

The time complexity is O(n), which is what I believe the interviewer was asking for. I don't think it is possible to store all possible combinations of LinkedLists to each node with storage space of O(n). Consider the case where every node is equal to zero.

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

does this count as once? basically you are traversing the node and get back to it later. not sure whether this is what the author means.

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

This is a standard preorder traversal. Every node is visited exactly one time. When I say "visited", for this problem, I mean it is examined, the value of the path is calculated, and the currentMax is updated. This is, indeed, O(n) time complexity. If you're not convinced, drop my program in Eclipse and set a break at "int sumAtCurrentNode = n.getValue() + currentSum;". It will be hit n times.

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

I know it's preorder and supposed to be O(n). I'm just confused with why it specifies twice doesn't count as O(n). You know when you do recursive functions, you are storing the state in the stack so that you can get back to it later. you are not calculating the sum twice but technically you are visiting the same node more than once. I probably misunderstood the statement.

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

ArrayList path = new Arraylist();
StringBuffer a = new Stringbuffer();
int max = 0;

{
{
if(max< sum)
{
max = sum;
s = append(i,false);
}
if(max == sum)
s = append(build,true);
}

return s;

}
append(i,flag)
{
if(!flag)
s ="";
for(int j =0;j<i;j++)
{
s= s+path.get(j);
}

}

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

Small correction

if(max< sum)
{
max = sum;
s = append(i,false);
}
if(max == sum)
s = append(i,true);
}

append function should take i as the input parameter

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

"root to any node" u r checking for leaf only.

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

Since the question is for finding the max path, max path can be formed only when we traverse till the leaf node..
Correct if i am wrong

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

No.

``````2
/    \
1       4
/       /  \
3      -3   -4``````

here : max is 6: 2 paths . 2,4 | 2,1,3

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

Here is solution of multiple path & single path.

``````char PATH[N];//N = (Number of Node in BT)X(Max Number of Leaf in BT)
int PATH_Len=0;
int path_cunt=0
int max_sum = 0;
void main()
{
char path[N];
int sum = 0, l = 0;
NODE *BT == CreateBT(4,6,1,3,9,20,56,88,21,22,15);
path='R'; l=1;

MaxPath(BT, sum, path, l);//This will evalute one path.
printf("\nMax Sum: %d, PATH: %s", max_sum, PATH);
memset(PATH, 0, N);
path='R'; l=1; max_sum=0; path_cunt=0;

Multi_MaxPath(BT, sum, path, l);//This will evalute multiple path of same max.
for(int i=0, int temp=0; i<path_cunt; i++){
int temp_l=strlen(PATH+temp);
printf("Max Sum: %d, PATH: %s", max_sum, PATH+temp);
temp += temp_l+1;
}
}

void MaxPath(NODE *Root, int sum, char path[], int l)
{
if(!Root) return;
sum += Root->info;
if(sum>max_sum){
strcpy(PATH, path, l);
max_sum = sum;
}
path[l] = 'L';
MaxPath(Root->Left, sum, path, l+1);
path[l] = 'R';
MaxPath(Root->Left, sum, path, l+1);
}

void Multi_MaxPath(NODE *Root, int sum, char path[], int l)
{
if(!Root) return;
sum += Root->info;
if(sum == max_sum){
PATH[PATH_Len] = '\0'; PATH_Len++;
strcpy(PATH+PATH_Len, path, l);//Appending multiple Path String
PATH_Len += l;
path_cunt++;
} else if(sum>max_sum){
strcpy(PATH, path, l);
max_sum = sum;
path_cunt=1;
PATH_Len=l;
}
path[l] = 'L';
MaxPath(Root->Left, sum, path, l+1);
path[l] = 'R';
MaxPath(Root->Left, sum, path, l+1);
}``````

T(N) = O(N)
S(N) = (Number of Node in BT)X(Max Number of Leaf in BT)

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

.
some issues :
1) you can traverse tree only once .
2) you'll print some path's multiple time .[paths which don't end at leaf . u'll print them for both child branches ].
3) you are not supposed to print 'L' 'R' array. [as u are consedering strcpy() O(1) . which is actually O(n) ]

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

How about the solution I gave .!!!
Just above this one.

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

how about my code with c++ ,and i think i can print well the path .
I use a vector to store the path

``````int max_sum = 0;
vector<  vector<int> > max_sum_path;
void getMaxSum(struct node *head , int curr_sum ,vector<int> &path)
{

if(curr_sum > max_sum){
max_sum = curr_sum;
max_sum_path.erase(max_sum_path.begin() , max_sum_path.end());
}

path.push_back(1);// 1 :left 2 :rigth
path.pop_back();

}
path.push_back(2);// 1 :left 2 :rigth
path.pop_back();
}

if(curr_sum == max_sum){
max_sum_path.push_back(path);
}
}``````

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

seems wrong still

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

sorry for my error ,i update it .

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

Logic is not complete you have to reset pathList every time you get new maxValue. and print all paths when you have finished up traversing whole tree.

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

This problem can be solved by using parent pointer.

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

My solution:

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

public class MaxPathTree {

public static void main(String[] args) {
TreeItem root = init();

List<MaxPath> result = findMaxPath(root);

System.out.println(result);
}

private static List<MaxPath> findMaxPath(TreeItem root) {
int max = 0;

List<MaxPath> maxPaths = new ArrayList<>();
if (root.left != null) {
List<MaxPath> leftPaths = findMaxPath(root.left);
for (MaxPath maxPath : leftPaths) {
if (maxPath.sum > max) {
maxPaths.clear();
max = maxPath.sum;
} else if (maxPath.sum == max) {
}
}
}
if (root.right != null) {
List<MaxPath> rightPaths = findMaxPath(root.right);
for (MaxPath maxPath : rightPaths) {
if (maxPath.sum > max) {
maxPaths.clear();
max = maxPath.sum;
} else if (maxPath.sum == max) {
}
}
}

if (maxPaths.size() == 0) {
MaxPath maxPath = new MaxPath();
}

for (MaxPath maxPath : maxPaths) {
maxPath.sum += root.value;
}

return maxPaths;
}

private static TreeItem init() {
TreeItem A = new TreeItem("A", 1);
TreeItem B = new TreeItem("B", 2);
TreeItem C = new TreeItem("C", 3);
TreeItem D = new TreeItem("D", 4);
TreeItem E = new TreeItem("E", 5);
TreeItem F = new TreeItem("F", 6);

A.left = B;
A.right = C;
B.left = D;
B.right = E;
C.right = F;
return A;
}

public static class MaxPath {
public int sum;
public List<TreeItem> path = new ArrayList<>();
}

public static class TreeItem {
public TreeItem left;
public TreeItem right;
public int value;
public String id;

public TreeItem(String id, int value) {
this.id = id;
this.value = value;
}

@Override
public String toString() {
return id;
}
}

}``````

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

``````void printList(int arr[], int len, int *maxSum)
{
int i, sum=0;
for(i=0;i<len;i++)
{
sum+=arr[i];
fprintf(stderr,"%d ",arr[i]);
}
if(sum>*maxSum)
*maxSum = sum;
fprintf(stderr,"\n");

}

allThePaths(struct node *root, int *path, int pathLen, int *maxSum)
{

if(root == NULL)
return;

path[pathLen] = root->data;
pathLen++;
if((!(root->left)) && (!(root->right)))
printList(path,pathLen,maxSum);
else
{
allThePaths(root->left, path,pathLen, maxSum);
allThePaths(root->right, path,pathLen, maxSum);
}
}``````

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

allThePaths(struct node *root, int *path, int pathLen, int *maxSum)

Here *path is actually pointer to array passed from main function.

Do let me know if there is anything wrong or to improve with the code.

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

@drv
this is an entirely different problem. do not get confused.
<http://www.geeksforgeeks.org/find-the-maximum-sum-path-in-a-binary-tree/>

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

1) Find path from root to any node with max sum.

==>This is stored in maxSum passed from main.

2) As there can be many path's find all of them.

==>Traversing all paths are printed..

3) Print all such paths

==> Printing all the paths.

What else ?

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

Who ever voted it down, please take out a few moments to explain what is expected.

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.