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;
}

size = q.size();
while(size != 0) {

for(int i = 0;i<size;i++) {
sum = sum + q.remove().data * flip;
if(n.hasLeft())

if(n.hasRight())

}

size = q.size();
flip = flip* -1;

}

return sum;

}``````

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

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
}``````

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

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

int getChildTotal(Node* node, int level, int total) {
if (node == NULL) {
} 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);
}
}``````

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

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);

}

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
}

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

``````//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
}``````

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);
}

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;
if (root == null)
return 0;
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;
}
count--;
}

}
return oddSum - evenSum;
}``````

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)));
}

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);
}
}``````

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

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

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;
}``````

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;
}

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);
}
}``````

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);
}
}``````

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;
}``````

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);
}``````

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);
}``````

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.

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

+1 for not simply pasting code

any traversal visiting all the nodes will work

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);
}``````

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) {
} 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);
}
}``````

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.

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;
}

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.

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.