Amazon Interview Question for SDE1s


Team: TCS
Country: India
Interview Type: Written Test




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

int CalculateDifference(Node n){
		int sum = 0, flip = 1, size;
		
		if(null == n) {
			return sum;
		}
		
		q.add(n);
		size = q.size();
		while(size != 0) {
			
			for(int i = 0;i<size;i++) {
				sum = sum + q.remove().data * flip; 
				if(n.hasLeft()) 
					q.add(n.left);
			
				if(n.hasRight())
					q.add(n.right);
				
			}
			
			size = q.size();
			flip = flip* -1;
			
		}
		
		return sum;
		
	}

- joyboyhardik September 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 4 votes

I like your flip idea, let me modify my code for a variant of flip (but using a bool variable):

//external/global variables
BOOL evenlevel=true
evensum, oddsum (numeric type matching node values)

//wrapper for other function
sum(root)
{
	evensum=oddsum=0 // reset sums
	rec_sum(root)             // call main recursive function
	return evensum, oddsum  // or return difference
}

rec_sum( node )
{
		if( node == nil) return  

		if(evenlevel) evensum += node.val
		else              oddsum   += node.val

		evenlevel=!evenlevel  //children are diff type
		rec_sum(Node.left)
		rec_sum(Node.right)
		evenlevel=!evenlevel  //back to original type
}

- S O U N D W A V E September 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

// calling from main
int total = getChildTotal(root, 1, root.value)

int getChildTotal(Node* node, int level, int total) {
    if (node == NULL) {
        return total;
    } else {
        childTotal = (node->left == NULL?) 0 : node->left.value + (node->right == NULL)? 0 : node->right.value;
        if (level%2 == 0) {
            // current node is at even height. so children are at odd height
            childTotal = -childTotal;
        }
        total = total + childTotal;
        total = getChildTotal(node->left, level+1, total);
        total = getChildTotal(node->right, level+1, total);
        return total;
    }
}

- Anonymous October 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

void cal(struct node *t,int *d,int l ){

if(t==NULL) return;

if(l%2 ==0) *d=*d+t->data;
else *d=*d-t->data;
cal(t->left,d,l+1);
cal(t->right,d,l+1);

}

- Anonymous March 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 4 vote

GLOBAL VARS:
h=0, even, odd

//wrapper for other function
sum( node)
{
even=odd=0 // reset sums
h=0 // not really needed ( rec_sum will unwind it to 0 )
rec_sum(node)
return even, odd
}

rec_sum( node )
{
if( node == nil) return;

if(h%2==0)
even+= node.val
else
odd+= node.val

++h // increment height value for my children
sum(Node.left)
sum(Node.right)
--h // unwind height
}

- S O U N D W A V E September 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 4 votes

//external/global variables
h=0, even, odd

//wrapper for other function
sum( node)
{
	even=odd=0 // reset sums
	h=0               // not really needed 

	rec_sum(node)
	return even, odd
}

rec_sum( node )
{
	if( node == nil) return

	if(h%2==0) even+= node.val
	else             odd  += node.val

	++h // increment height value for my children
	sum(Node.left)
	sum(Node.right)
	--h // unwind height
}

- S O U N D W A V E September 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Here you go in C#:
int SumEvenOdd(Tree root)
{
return SumEvenOdd(root, true);
}

int SumEvenOdd(Tree root, bool isPositive)
{
if (root == null)
{
return 0;
}

int a = 1;
if (isPositive)
{
a = -1;
}

return root.Value * a + SumEvenOdd(root.Left, !isPositive) + SumEvenOdd(root.Right, !isPositive);
}

- Sethi Sirsa November 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sample Function In Java

public int heightDiff(Node root) {
            int evenSum = 0;
            int oddSum = 0;
            int height = 0;
            int count = 0;
            Queue<Node> queue = new LinkedList<Node>();
            if (root == null)
                return 0;
            queue.add(root);
            while (!queue.isEmpty()) {
                height++;
                count = queue.size();
                while (count > 0) {
                    root = queue.poll();
                    int x = Integer.parseInt(root.get().toString());
                    if (height % 2 == 0) {
                        evenSum += x;
                    } else {
                        oddSum += x;
                    }
                    if(root.left!=null) queue.add(root.left);
                    if(root.right!=null) queue.add(root.right);
                    count--;
                }

            }
            return oddSum - evenSum;
        }

- Prakash September 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int sumofNodes(TreeNode node, boolean oddLevel)
{


if (node == null)
return 0;
int sum=sumofNodes(node.leftchild, !oddLevel)
+ sumofNodes(node.rightchild, !oddLevel);
if (oddLevel)
return node.data + sum;
else
return sum;

}

public void oddEvenDifference(TreeNode node)
{
System.out.println(Math.abs(sumofNodes(node, true) - sumofNodes(node, false)));
}

- GT1 October 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int EvenSum=0,OddSum=0;
void SumEveOddLevels(struct tree *root,int level)
{
	if(root)
	{
		if(level%2)
			OddSum+=root->data;
		else
			EvenSum+=root->data;
		SumEveOddLevels(root->left,level+1);
		SumEveOddLevels(root->right,level+1);	
	}
}

- Gangadhara Pagadala October 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

int main()
{
	SumEveOddLevels(root,1);
	return 0;
}

- Gangadhara Pagadala October 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <stdlib.h>

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

void rec_calcDiff(struct node* root, int height, long int* evenSum, long int* oddSum) {
    if(root == NULL)
        return;
    rec_calcDiff(root->left, height+1, evenSum, oddSum);
    rec_calcDiff(root->right, height+1, evenSum, oddSum);
    if(height%2 == 0)
        *evenSum += root->val;
    else
        *oddSum += root->val;
    return;
}

long int calcDiff(struct node* root) {
    int height=1;
    long int evenSum=0, oddSum=0;
    rec_calcDiff(root, height, &evenSum, &oddSum);
    return (oddSum - evenSum);
}

struct node* createNode(int val) {
    struct node* newNode = (struct node*) malloc(sizeof(struct node)); 
    newNode->val = val;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

main()
{
    struct node* root = createNode(7);
    root->left = createNode(8);
    root->right = createNode(4);
    root->left->left = createNode(33);
    root->left->right = createNode(77);
    root->right->right = createNode(3);
    printf("%ld\n", calcDiff(root));
    return 0;
}

- sudhanshu97gupta October 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

why is itjt's answers downvoted? it works!
template<>
int tree<int>:: oddevensum()
{
deque<node<int>* > myq1;
deque<node<int>* > myq2;
node<int>* temp;
int sum=0;
myq1.push_back(root);

while(!(myq1.empty()) || !(myq2.empty()))
{
//odd levels
while( !(myq1.empty()) )
{
temp=myq1.front();
sum+= temp->val;
if(temp->left) myq2.push_back( temp->left );
if(temp->right) myq2.push_back( temp->right );
myq1.pop_front();
}

while( !(myq2.empty()) )
{
temp=myq2.front();
sum-= temp->val;
if(temp->left) myq1.push_back( temp->left );
if(temp->right) myq1.push_back( temp->right );
myq2.pop_front();
}
}
return sum;
}

- Guest October 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

diffOddEvenHeightsHelper(Node* root, int& even, int& odd, int level){
	if (root){
		diffOddEvenHeightsHelper(root->left, even, odd, level+1);
		if (level & 1)
			odd += root->data;
		else
			even += root->data;
		diffOddEvenHeightsHelper(root->right, even, odd, level + 1);
	}
}

- sirius March 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

diffOddEvenHeights(){
	int evenSum = 0;
	int oddSum = 0;
	diffOddEvenHeightsHelper(rootNode, evenSum, oddSum, 0);
	return oddSum - evenSum;
}
diffOddEvenHeightsHelper(Node* root, int& even, int& odd, int level){
	if (root){
		diffOddEvenHeightsHelper(root->left, even, odd, level+1);
		if (level & 1)
			odd += root->data;
		else
			even += root->data;
		diffOddEvenHeightsHelper(root->right, even, odd, level + 1);
	}
}

- Sirius March 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int calcDifference (NodePtr root){
  int sum = 0;
  if(root->left!=NULL)
  {
    sum-=calcDifference(root->left);
  }
  if(root->right!=NULL)
  {
    sum-=calcDifference(root->right);
  }
  if(root!=NULL)
    sum+=root->data;
  return sum;
}

- vyas.sathya February 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int alternateSum(Node root){
    return alternateSum(root, 1);
}
	
private int alternateSum(Node node, int sign){
    if(node == null)
        return 0;
    return sign * node.value + alternateSum(node.left, -sign) + alternateSum(node.right, -sign);
}

- TTT April 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int alternateSum(Node root){
		return alternateSum(root, 1);
	}
	
	private static int alternateSum(Node node, int sign){
		if(node == null)
			return 0;
		return sign * node.value + alternateSum(node.left, -sign) + alternateSum(node.right, -sign);
	}

- Anonymous April 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

Typical level order or breath first traversal to figure out the even and the odd sums. You only need a single queue and boolean flag toggling between even and odd. You can sum up the odd and even values using BFS and then print the difference.

- Vs September 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 3 votes

+1 for not simply pasting code

any traversal visiting all the nodes will work

- S O U N D W A V E September 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 3 vote

int sum(node root){
	
		if(!root) return0;
		return 
		root.data - sum(root.left) - sum(root.right);
	}

- Anonymous September 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

int total = getChildTotal(root, 1, root.value)

int getChildTotal(Node* node, int level, int total) {
    if (node == NULL) {
        return total;
    } else {
        childTotal = (node->left == NULL?) 0 : node->left.value + (node->right == NULL)? 0 : node->right.value;
        if (level%2 == 0) {
            // current node is at even height. so children are at odd height
            childTotal = -childTotal;
        }
        total = total + childTotal;
        total = getChildTotal(node->left, level+1, total);
        total = getChildTotal(node->right, level+1, total);
        return total;
    }
}

- Gopi October 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Pseudocode:

int calcDifference(start, odd, result) {
	if(odd)
		result += start.value;
	else
		result -= start.value
	result = calcDifference(start.left, !odd, result);
	result = calcDifference(start.right, !odd, result)
	return result;
}
calcDifference(root, true, 0);

The key is to traverse all of the nodes, flipping an odd/even flag as you go down a level.

- 0x0001 October 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I guess we do not need to keep track of odd and even levels. Recursion would take care of it for us.

int calcDifference(node *root)
{
return root ? (root->value - (calcDifference(root->left) + calcDifference(root->right))) : 0;
}

- Anonymous October 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

You could traverse the tree breadth first. Maintain two queues: an odd queue and an even queue. Enqueue the children of odd queue elements in the even queue and vice versa. You could use a signed diff variable and add to or subtract from it depending on whether it's an odd or even element.

- itjt September 28, 2013 | 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