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 class TreeValueAdjuster {
  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);
    visitors.add(visitor);
    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;
  }

}

- Ankit Sinha February 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Victor February 10, 2015 | Flag Reply
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).

- error February 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Ankit Sinha February 16, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- error February 20, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- error February 20, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- error February 20, 2015 | Flag
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 ?

- Vib March 02, 2015 | Flag Reply
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;
}

- ~amit June 05, 2015 | Flag Reply
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.

- stickypens February 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Inorder traversal will do the job

- satyatej February 18, 2015 | Flag Reply
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;
  return totalSum;
}

- abousamra February 22, 2015 | 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