Amazon Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




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

private static int findDiff(BTNode node,int level) {
if(node == null)
return 0;
int lv = findDiff(node.left, level+1);
int rv = findDiff(node.right, level+1);

if(level % 2 == 0){
return node.value + lv + rv;
}
else{
return node.value*-1 + lv +rv;
}
}

- MVVSK December 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

That %2 business is not required. Just return node.value - lv - rv no matter what. That'll give you odd - even, assuming the root is at odd level. Invert the value obtained in the end to get even - odd.

f(root) = root.value - f(root.left) - f(root.right)
           = root.value - [root.left.value - f(root.left.left) -      
f(root.left.right)] - [root.right.value - f(root.right.left) - f(root.right.right)]
           = root.value - root.left.value - root.right.value + f(root.left.right) + f(root.left.left) + f(root.right.left) + f(root.right.right)

You see where it's going.

- Jagat January 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

/// public static int findDiff(Tree root)
{
if (root == null)
return 0;
return root.item - (findDiff(root.left) + findDiff(root.right));
}
\\\

- Anshul December 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

don't even bother to check the level of the node

if the root is level 1, return -findDiff(root)
if the root is level 0, return findDiff(root)

- dgbfs December 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

@Fresh man to me question statement does not make any sense. Can you please update it??

- MrAnderson December 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Return the difference in sum of nodes at even and odd levels of a binary tree.

- rams December 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

int SumEven = 0;
int SumOdd = 0;
void findsum (node * ptr, int level)
{
assert(ptr != NULL);

if (is_even(level))
SumEven += ptr->value;
else
SumOdd += ptr->value;

if(ptr->left)
findsum(ptr->left,level +1);

if(ptr->right)
findsum(ptr->right,level +1);
}

- ashu December 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

int calcDifference(bool odd, Node root)
{
if(root == NULL)
return 0;

if(odd == true){
return (root->value +calcDifference(false, root->left) +calcDifference(false, root->right));
}
else{
return (-root->value + calcDifference(true, root->left) + calcDifference(true, root->right));
}
}

- Sachin December 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Difference of nodes' values at odd and even level is nothing but root's value-(sum of root immediate children nodes' values)

private static int findDiff(Node node) {
		if (node == null)
			return 0;
		int leftValue = findDiff(node.left);
		int rightValue = findDiff(node.right);
		return node.value - (leftValue + rightValue);
	}

Thanks.

- Fresh_man December 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int calcDiff(Node root){
Node temp = root;
int odd =0;
int even =0;
while(temp!=null){
odd=odd+temp.val;
temp=temp.next.next;
}
temp =root.next;
while(temp!=null){
even =even+temp.val;
temp=temp.next.next;
}
return odd-even;
}

- Setu Poddar December 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Setu My bad, i forgot to mention "Tree" in Q. Its updated now. Your code should work for linkedList fine.

- Fresh_man December 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

it might be a answer to the question:

public class Main {

	public int calculateDiff(TreeNode rootNode) {
		return calculateNodeValue(rootNode, true);
	}

	public int calculateNodeValue(TreeNode theNode, boolean isOdd) {
		if (theNode == null)
			return 0;
		int childsValue = 0;
		if (theNode.childs != null)
			for (TreeNode childNode : theNode.childs) {
				childsValue += calculateNodeValue(childNode, !isOdd);
			}

		return theNode.value - childsValue;
	}

	class TreeNode {
		public int value;
		public List<TreeNode> childs;
	}

}

- Moin_e December 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Question Should be -
Write a function to calculate the difference between ( the sum of all node-values at even levels) and (sum of node-values at odd levels) of a Tree .
So much for Attention to details.

- Aztec warrior December 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Here is the recursive implementation

int treeNodeSum ( TreeNode* root, int level, bool isEvenSum )
{
	if(!root) return 0;
    

    int leftChildSum = treeNodeSum(root->left, level+1, isEvenSum);
    int rightChildSum = treeNodeSum(root->right, level+1, isEvenSum);
    
    if( ( isEvenSum && level%2 == 0 )|| (!isEvenSum && level%2 == 1)) {
    	return root->data + leftChildSum + rightChildSum;
    }
    
    return 0;
}

//invoke using call once for even once for odd with root and lvl 0

int diff == treeNodeSum(root, 0, true) - treeNodeSum(root, 0, false);

- Aztec warrior December 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

template <class T>
int BinaryTree<T>::DiffBWOddAndEvenLevelSums()
{
    int evemsum = 0;
    int oddsum = 0;

    _DiffBWOddAndEvenLevelSums(m_Root, evemsum, oddsum);

    return (evemsum - oddsum);
}



template <class T>
void BinaryTree<T>::_DiffBWOddAndEvenLevelSums(BinaryTreeNode<T>* node, int& sum1, int& sum2)
{
    if (node)
    {
        sum1 += node->m_Data;

        _DiffBWOddAndEvenLevelSums(node->m_Left, sum2, sum1);
        _DiffBWOddAndEvenLevelSums(node->m_Right, sum2, sum1);
    }
}

- Gupt December 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int find_level_diff(Tree t,int level){
if(t==null)
return 0;
return (t.data*level)+find_level_diff(t.left,-1*level)+ find_level_diff(t.right,-1*level);
}

- winner December 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// +1 for odd level and -1 for even
public static int find_level_diff(Main t,int level){
if(t==null)
return 0;
return (t.data*level)+find_level_diff(t.left,-1*level)+ find_level_diff(t.right,-1*level);
}

- winner December 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void sum_nodes_at_even_level(btnode* root, int level, int& sum) 
{
   if(!root) return;
     
   if(level%2==0) sum+=root->data;
   
   sum_nodes_at_even_level(root->left, level+1, sum);
   sum_nodes_at_even_level(root->right, level+1, sum);
}

- foobar December 11, 2012 | 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