## Amazon Interview Question for Software Engineer / Developers

Country: India
Interview Type: Written Test

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

Just recursion

int calcDiff(node * root)
{
if(root==NULL)
return 0;
int tmp= root->val - calcDiff(root->left)-calcDiff(root->right);

return tmp;

};

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

perfect.

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

Where is odd values summing going on ??? We have to add the values at odd levels of left and subtract it from odd levels of value of right !

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

He makes the value of each node equal to it's value minus the value of it's children. Because each node negates its children, and summing doesn't matter what order we do it in, this works out. Example:

A root of value 10 with children values 5 and 3 will have total value 10 - (5+3) = 2.

If the 3 node has another child of value 2, then we subtract that before proceeding, getting
10 - (5 + (3 - 2)) =
10 - (5 + 3) + 2 = 4

The last child will effectively get negated twice, making it positive again. Though really it just collapses into the 3, reducing it to 1.

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

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

awesome....

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

Explanation for Peng's solution
sum[h1] - sum[h2] + sum[h3] - sum[h4] .....
= sum[h1] - (sum[h2] - (sum[h3] - (sum[h4] -...

where h1 represents the nodes at height 1 and so on

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

posted wrong solution, deleted

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

``````public static int calcDifference(TreeNode root)
{
int[] result =  findOddSumAndEvenSum(root, true, new int[]{0,0});
return result[0] - result[1];
}

public static int[] findOddSumAndEvenSum(TreeNode root, boolean isOdd, int[] oddEvenSum)
{
if(root == null)
return new int[]{0, 0};

if(isOdd)
oddEvenSum[0] = oddEvenSum[0] + root.getValue();
else
oddEvenSum[1] = oddEvenSum[1] + root.getValue();

findOddSumAndEvenSum(root.getLeftNode(), !isOdd, oddEvenSum);

findOddSumAndEvenSum(root.getRightNode(), !isOdd, oddEvenSum);

return oddEvenSum;

}``````

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

A small correction
if(root.getLeftNode()!=null){
findOddSumAndEvenSum(root.getLeftNode(), !isOdd, oddEvenSum);
}
if(root.getRightNode()!=null){
findOddSumAndEvenSum(root.getRightNode(), !isOdd, oddEvenSum);
}

otherwise you will end up returning {0,0} as soon as you encounter the leftchild as null

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

``````#include<iostream.h>
#include<queue.h>

using namespace std;

struct node {
int data;
node * left;
node * right;
};
struct node * newNode( int x )
{
struct node * temp = (struct node*)malloc (sizeof(struct node));
temp->data =x;
temp->left = NULL;
temp->right = NULL;

}

int printDifference( struct node * root)
{

if(root == NULL)
return  0 ;
int odd = -1;
queue<node*> q;
q.push (root);
int currentlevel = 1;
int nextlevel = 0;
int oddsum=0;
int evensum =0;
while( !q.empty())
{
node * current = q.front();

q.pop();
currentlevel--;
if(current)
{
//printf("%d ", current->data);
if(odd)
{
oddsum = oddsum + current->data;
}
else
evensum = evensum+current->data;
if(current->left)
{
q.push(current->left);
nextlevel++;
}
if(current->right)
{
q.push(current->right);
nextlevel++;
}
}
if(currentlevel == 0)
{
//printf("\n");
currentlevel = nextlevel;
nextlevel = 0;
//printf("%d\n", odd);
odd = ~odd;
//printf("%d\n", odd);
}
}
// printf("%d\n", oddsum);
//printf("%d\n", evensum);
return (oddsum-evensum);
}

int main ()
{

node *root = newNode(2);
root->left = newNode(4);
root->right = newNode(12);

root->left->left = newNode(8);
root->left->right = newNode(6);

root->right->left = newNode(10);
root->right->right = newNode(14);
printf ("%d ", printDifference(root));
getchar();
return 0;
}``````

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

``````int OddLevelSum=0, EvenLevelSum=0;
int calcDiff(node *Root, int level){
if(level%2){/*Odd Level*/
OddLevelSum=OddLevelSum+Root->info;
}else{/*Even Level*/
EvenLevelSum=EvenLevelSum+Root->info;
}
calcDiff(Root->left, level+1);
calcDiff(Root->right, level+1);
return modDiff(OddLevelSum, EvenLevelSum);
}``````

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

A little correction in the existing code

``````int OddLevelSum=0, EvenLevelSum=0;

int main() {
calcDiff(Root, 1);
printf("Result : %d", (OddLevelSum - EvenLevelSum));
return 0;
}

void calcDiff(node *Root, int level){
if(level%2){/*Odd Level*/
OddLevelSum=OddLevelSum+Root->info;
}else{/*Even Level*/
EvenLevelSum=EvenLevelSum+Root->info;
}
calcDiff(Root->left, level+1);
calcDiff(Root->right, level+1);
return;
}``````

I removed the return at the end of calcDiff() function because return will be called many times upon the popping of system stack at the end of " calcDiff(Root->right, level+1);" line.

I hope am on the right track. Please correct me if am wrong some where.
Cheers

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

class TreeNode {

int data;
TreeNode left;
TreeNode right;

public TreeNode(int data)
{

this.data = data;
left = right =null;
}
}

/**
* Actual Calculation is implemented in calcDiff(root) where the root node is
* passed.
*
*/
class Calc {

public static void main(String [] args)
{
TreeNode root = new TreeNode(1);

root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);
System.out.println(diff(root));

}
public static int diff(TreeNode n) {
return sumtree(n, 1);
}

public static int sumtree(TreeNode n, int level) {

if (n == null) return 0;

if (level % 2 == 0) {
return sumtree(n.left, level + 1) + sumtree(n.right, level +1 ) - n.data;
} else {
return sumtree(n.left, level + 1) + sumtree(n.right, level + 1) + n.data;
}
}
}

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

I use two queue to do this work. And it works well, because I take level traversal, so the time using is O(n).
#include<iostream>
#include<queue>
using namespace std;

typedef struct node{
int data;
struct node *left, *right;
}BTNode, *Tree;

#define NIL 0
int a[] = {1, 2, 4, 0, 0, 5, 0, 0, 3, 6, 0, 0, 7, 0, 0};
static int i = 0;
void pre_order_create(Tree &T) {
int num = a[i++];
if(num == NIL) {
T = NULL;
} else {
T = (BTNode*)malloc(sizeof(BTNode));
T->data = num;
pre_order_create(T->left);
pre_order_create(T->right);
}
}

calculate_diff(Tree T, int *odd_sum, int *even_sum) {
queue<BTNode*> *m_queue1 = new queue<BTNode*>();
queue<BTNode*> *m_queue2 = new queue<BTNode*>();
queue<BTNode*> *temp_queue;
BTNode *temp;
int level = 1;
int *sum;
m_queue1->push(T);
while(!m_queue1->empty()) {
if(level % 2 == 1) {
sum = odd_sum;
} else {
sum = even_sum;
}
while(m_queue1->size() > 0) {
temp = m_queue1->front();
(*sum) += temp->data;
if(temp->left) {
m_queue2->push(temp->left);
}
if(temp->right) {
m_queue2->push(temp->right);
}
m_queue1->pop();
}
level++;
temp_queue = m_queue1;
m_queue1 = m_queue2;
m_queue2 = temp_queue;
}
}

void main() {
Tree T = NULL;
pre_order_create(T);
int odd_sum = 0;
int even_sum = 0;
calculate_diff(T, &odd_sum, &even_sum);
cout << "odd_sum=" << odd_sum << ",even_sum=" << even_sum << endl;
getchar();
}

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

private static void calcDifference(final Node root) {
ArrayList<Node> list, tList;
list = new ArrayList<>();
int evenListSum = 0, oddListSum = root.value, height = 1;
while (true) {
int size = list.size();
if (size == 0) {
return;
}
int i = 0;
tList = new ArrayList<>();
while (i < size) {
Node n = list.remove(0);
if (n.left != null) {
if (height % 2 != 0) {
evenListSum = evenListSum + n.left.value;
} else {
oddListSum = oddListSum + n.left.value;
}
}
if (n.right != null) {
if (size % 2 != 0) {
evenListSum = evenListSum + n.right.value;
} else {
oddListSum = oddListSum + n.right.value;
}
}
}
list = tList;
height++;
i++;
}
}

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

void SumDiff(Tree *root, int num, int *Sum1, int *Sum2)
{
if(root != NULL)
{
if(num % 2 == 0)
{
*Sum2+= root->data;
SumDiff(root->left, num +1, Sum1, Sum2);
SumDiff(root->right, num +1, Sum1, Sum2);
}
else
{
*Sum1+= root->data;
SumDiff(root->left, num +1, Sum1, Sum2);
SumDiff(root->right, num +1, Sum1, Sum2);
}
}

}

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

``````private static void findEvenOddSum(Node node) {
List<Node> list = new ArrayList<Node>();
// Pass the arguments,
//list : Nodes to process at current level, isOdd : level is odd or even 3. difference : difference between odd and even
findSum(list, true, 0);
}

private static void findSum(List<Node> list, boolean isOdd , int difference) {
final int elementSize = list.size();
//If no more elements to process
if(elementSize == 0){
System.out.println("Difference between odd and even is : " + difference);
return;
}

int sumAtLevel = 0;
//Find the nodes for processing
for(int i=0; i< elementSize; i++){
//Take from the list and remove. We can use queue instead
Node n = list.get(0);
list.remove(0);

//Add to sum at current level
sumAtLevel += n.data;

// Find the left node for further processing
if(n.left != null)

//Find the right node for further processing
if(n.right != null)
}

// Operate on difference based on the level
if(isOdd)
difference += sumAtLevel;
else
difference -= sumAtLevel;

// Switch the level and pass the other items
findSum(list, !isOdd, difference);

}``````

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.