Amazon Interview Question for SDE-2s


Country: United States
Interview Type: In-Person




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

Do a reverse in order traversal to get the desired output.

- Nitin May 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

Please suggest me solution better then this.

public class BST {

	int data;
	private BST lc;
	private BST rc;
	int sumSoFar;
	BST replaceRootWithSumofGreaterNode(BST root){
		
		if(root != null){
			root.rc = replaceRootWithSumofGreaterNode(root.rc);
			sumSoFar+= root.data;
			root.data = sumSoFar;
			root.lc = replaceRootWithSumofGreaterNode(root.lc);
		}	
		return root;
	}
	BST addNode(BST root, int data){
		
		if(root == null){
			root = new BST();
			root.data = data;
			root.lc = root.rc = null;
			return root;
		}else{
			if(data<root.data){
				root.lc = addNode(root.lc,data);
				return root;
			}
			else{
				root.rc = addNode(root.rc,data);
				return root;
			}
		}
	}
	 void inorder(BST root){
		 if(root!=null){
			 inorder(root.lc);
			 System.out.print(root.data+"->");
			 inorder(root.rc);
		 }
	 }
	public static void main(String[] args) {
		BST b = new BST();
		BST root = null;
		int arr[] = {5,3,8,6,10,1,4,7,9,2};
		for(int data: arr){
			root = b.addNode(root, data);
		}
		b.inorder(root);
		System.out.print("\n\n");
		b.sumSoFar = 0;
		root= b.replaceRootWithSumofGreaterNode(root);
		b.inorder(root);
	}

}

- Razz May 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

class Node {
  Node leftChild;
  Node rightChild;
  int element;

  static int sum;
  
  Node(int element) {
    this(null, null, element);
  }
  
  Node(Node leftChild, Node rightChild, int element) {
    this.leftChild = leftChild;
    this.rightChild = rightChild;
    this.element = element;
  }
}

  public void reverseOrderTraversalReplaceSum(Node n) {
	  if(n == null)
	      return;
	  else {
	      reverseOrderTraversalReplaceSum(n.rightChild);
	      sum = sum + n.element;
	      n.element = sum;
	      reverseOrderTraversalReplaceSum(n.leftChild);
	    }
  }

- Anonymous May 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void regenerateBinarySum()
  {
	// BFS uses Queue data structure
		Queue<Node> queue = new LinkedList<Node>();
		Queue<Node> queueToClean = new LinkedList<Node>();
		queue.add(this.root);
		queueToClean.add(root);
		if(root.right!=null)
			root.data=root.data+this.getBFSSum(root.right);
		root.visited = true;
		while(!queue.isEmpty()) {
			Node node = (Node)queue.remove();
			Node child=null;
			while((child=getUnvisitedChildNode(node))!=null) {
				child.visited=true;
				if(child.right!=null)
					child.data=child.data+this.getBFSSum(child.right);
				queue.add(child);
				queueToClean.add(child);
			}
		}
		// Clear visited property of nodes
		clearNodes(queueToClean);
  }
  
  private int getBFSSum(Node node)
  {
	// BFS uses Queue data structure
		Queue<Node> queue = new LinkedList<Node>();
		Queue<Node> queueToClean = new LinkedList<Node>();
		queue.add(node);
		queueToClean.add(node);
		int sum=node.data;
		node.visited = true;
		while(!queue.isEmpty()) {
			Node node1 = (Node)queue.remove();
			Node child=null;
			while((child=getUnvisitedChildNode(node1))!=null) {
				child.visited=true;
				sum+=child.data;
				queue.add(child);
				queueToClean.add(child);
			}
		}
		// Clear visited property of nodes
		clearNodes(queueToClean);
		return sum;
  }

- Vivek Grewal May 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I am just concentrating on the problem statement assuming the tree is already populated. Here is my private method which does the trick.

// call from any node. Inside the node class.
	public void replaceSum() {

		if (null == this.left && null == this.right ) {
			return;
		}
		replace(this);
	}

	private void replace(Node rootNode) {
		Node parent = rootNode;
		Node current = null;
		if (null == rootNode.left && null == rootNode.right) {
			return;
		}
		if (null !=rootNode.getLeft()) {
			current = rootNode.getLeft();
			replace(current);
		}
		
		if (null !=rootNode.getRight()) {
			current = rootNode.getRight();
			replace(current);
		}
		
		parent.setValue(parent.getValue()+ current.value);
	}

- madhu.palaparthi May 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static int replace(Node node)
        {
            if (node == null)
                return 0;

            if (node.left == null)
                return node.val;
            else
                replace(node.left);

            var sum = replace(node.right);
            var r = sum + node.val;
            node.val = sum;
            return r;
        }

- Anonymous May 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

That's mine. Since BST assumes greater keys are all to the right we are diving to left subtrees and summing only right ones. This is post-order tree traversal.

- v.shashenko May 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The problem does not state if the tree is balanced. I am also assuming there are no duplicate elements in the tree. The difficulty here is that since we are replacing the nodes values with new ones meaning that current structure of the tree may not still be valid after everything.

For example

5
                 /
               4
               /
             3

would be come

5
                 /
               9 (4+5)
               /
             12 (3+4+5)

So the algorithm I would use is
1) Use an in-order traversal to create sorted linked list (which is just a degenerate binary tree) O(N)
2) Recursively add the values (pretty much walk the degenerate tree to the end returning the running sum and add that to a nodes current value). At the end of everything this will still be a valid BST though a very poorly shaped one O(N)
3) Rebalance the tree using a number of left rotations O(N)

- Anonymous May 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void sumTree(Node root){
	Node start = findMax(root);
	int sum=0;
	while(start!=null){
		sum+=start.val;
		start.val = sum;
		start = findPredecessor(start);
	}
}

- Anonymous June 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

follow postorder traversal and add value of right node to root node but return value = right node+ left node in recursion

- Brijesh Patel August 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <iostream>

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


void add(node **root, int data){
        if(*root == NULL) {
        *root = (struct node*) malloc (sizeof(struct node));
        (*root)->left = (*root)->right = NULL;
        (*root)->data = data;
        } 
}

void inorder(node *root){
        if(root!=NULL) {
                inorder(root->left);
                printf("  %d  ", root->data);
                inorder(root->right);
        }
}

void replaceSums(node *root, int *num) {
        if(root != NULL) {
                replaceSums(root->right, num);
                *num += root->data;
                root->data = *num;
                replaceSums(root->left, num);
        }
}

int main(){
        node *root=NULL;
        add(&(root),10);
        add(&(root->left),4);
        add(&(root->left->left),1);
        add(&(root->left->right), 6);
        add(&(root->right), 13);
        add(&(root->right->left), 11);
        add(&(root->right->right), 15);

printf("\n\n INORDER ::  ");
        inorder(root);
printf("\n\nAFTER REPLACEMENT :: ");
        int a=0;
        replaceSums(root,&a);
        inorder(root);
        return 0;
}


Output:
INORDER ::    1    4    6    10    11    13    15  

AFTER REPLACEMENT ::   60    59    55    49    39    28    15

- Anup Rungta January 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
using namespace std;
 
// A Binary Tree Node
struct Node
{
    int data;
    Node *left, *right;
};
 
// A utility function to create a new Binary
// Tree Node
Node *newNode(int item)
{
    Node *temp =  new Node;
    temp->data = item;
    temp->left = temp->right = NULL;
    return temp;
}
 
int ConvertSumGTET(Node *root)
{
	if(root == NULL)
		return 0;
	ConvertSumGTET(root->left);
	root->data += ConvertSumGTET(root->right);
	return root->data;
}

void printTree(Node *root)
{
	if(root != NULL)
	{
		printTree(root->left);
		printTree(root->right);
		cout<<"-> "<<root->data;
	}
}

int main()
{
    Node *root = newNode(10);
    root->left = newNode(9);
    root->right = newNode(15);
    root->left->left = newNode(3);
    root->left->left->left = newNode(2);
    root->left->left->right = newNode(5);
    root->right->left = newNode(12);
    root->right->right = newNode(17);
    root->right->left->left = newNode(11);
    root->right->left->right = newNode(13);
    root->right->right->left = newNode(16);
    root->right->right->right = newNode(18);
    
 	printTree(root);
 	cout<<endl;
 	
    if(root != NULL)
    	root->data = ConvertSumGTET(root);
    	
    printTree(root);
    return 0;
}

- Ravi Jangra July 17, 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