## Amazon Interview Question for SDE1s

Country: India

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

Can be done in n log n if tree is balanced.
Algo:
1. Conduct a depth first traversal
2. At each stage, maintain a list of ancestors (size log n if balanced)
3. For each ancestor, add to sum if condition is met
4. Add self to list of ancestors and traverse children
5. Get the sum calculated during the traversal of the children

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

public static interface TreeNode {
public TreeNode getLeft();
public TreeNode getRight();
public int getValue();
public TreeNode setValue(int value);
}

public static interface NodeVisitor {
public void visit (TreeNode node);
public void afterAllVisited();
}

public static class SumVisitor implements NodeVisitor {
public void visit (TreeNode visitedNode) {
if (meetsCondition(visitedNode)) {
operate(visitedNode);
}
}

public SumVisitor(TreeNode node) {
this.startingNode = node;
}

private boolean meetsCondition (TreeNode visitedNode) {
return visitedNode.getValue() < startingNode.getValue();
}
private void operate (TreeNode visitedNode) {
sum += visitedNode.getValue();
}

public void afterAllVisited() {
startingNode.setValue(sum);
}

private final TreeNode startingNode;
private int sum = 0;
}

public static interface VisitorFactory {
public NodeVisitor createVisitor (TreeNode node);
}
public static class SumVisitorFactory implements VisitorFactory {
public NodeVisitor createVisitor (TreeNode node) {
return new SumVisitor(node);
}
}

public List<NodeVisitor> traverseTree (TreeNode node, List<NodeVisitor> visitors, VisitorFactory factory) {
for (NodeVisitor visitor: visitors) {
visitor.visit(node);
}

NodeVisitor visitor = factory.createVisitor(node);
if (node.getLeft() != null) {
traverseTree(node.getLeft(), visitors, factory);
}
if (node.getRight() != null) {
traverseTree(node.getRight(), visitors, factory);
}

visitors.remove(visitors.size());
visitor.afterAllVisited();
return visitors;
}

}``````

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

Is it possible to do better than O(n^2)?

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

traverse the given tree with maps which contain pairs of node's value and sum.
in the example shown, while traversing the node '80', the traversing method is given a map which has entries with keys 60, 50. it sums values less than 60 or 50 among the children below the node (by recursion), and update the sums to the map.
the computation complexity is O(n) and storage complexity is O(logn).

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

At every node, will it be required to iterate over the entries in the map and add to sum if the condition is met? If so, time complexity will be be n * log n

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

you are right, my mistake. O(nlogn) is right. thank you for your fix.

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

you are right. it takes O(nlogn). thank you for your fix.

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

you are right. it takes O(nlogn). thank you for your fix.

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

Clarifying the question,

Given an unbalanced tree, how would you replace each node's value with the sum
of all the values in its subtree that are smaller than the node's value ?

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

The actual run time depends upon the type of tree. If it is skew tree, then it will be O(n2), otherwise if it is balanced tree, then O(nlgn).

``````#include    <iostream>
#include    <unordered_map>
using namespace std;

struct tree{
int data;
struct tree *left,*right;

tree(int data) {
this->data = data;
left = right = NULL;
}
};
void find(tree *root,unordered_map<tree *,pair<int,int> > &m)
{
if(!root)   return;
for(auto i : m)
if(root->data < i.second.first)
m[i.first].second += root->data;

m[root] = make_pair(root->data,0);
find(root->left,m);
find(root->right,m);
cout<<m[root].second<<" ";
}
int main()
{
tree *root = new tree(6);
root->left = new tree(3);
root->right = new tree(5);
root->right->left = new tree(18);
root->right->right = new tree(5);
root->left->left = new tree(4);
root->left->right = new tree(2);
unordered_map<tree *,pair<int,int> > m;
find(root,m);
return 0;
}``````

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

shouldn't the output be 90->40->0->0?
Because 40 will the leaf node. Hence it should have a value of 0.

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

Inorder traversal will do the job

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

``````public int sum(Node root) {
if (root == null)
return 0;

int sum = sum(root.left) + sum(root.right);
int totalSum = sum + root.data;
if ( root.data < sum)
root.data = sum;
}``````

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.