Amazon Interview Question for Software Engineer / Developers


Country: India
Interview Type: Phone Interview




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

/* Sum of all leaves in binary tree*/
	private static Integer sumOfLeaves(BinaryTreeNode root) {
		BinaryTreeNode temp = null;
		Queue<BinaryTreeNode> q = new LinkedBlockingDeque<BinaryTreeNode>();
		q.add(root);
		int sum = 0;
		while (!q.isEmpty()) {
			temp = q.poll();
			if (temp.getLeft() == null && temp.getRight() == null) {
				sum+=temp.getData();
			}
			if (temp.getLeft() != null)
				q.add(temp.getLeft());
			if (temp.getRight() != null)
				q.add(temp.getRight());
		}

		return sum;

	}

- Vir Pratap Uttam May 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
8
of 8 vote

class Node{
 int data;
 Node right;
 Node left;
}
int leavesSum(Node root){
 if(root == null)
  return 0;
 if(root.left == null && root.right == null)
  return root.data;
 return(leavesSum(root.right) + leavesSum(root.left));
}

- CodeSpace October 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
6
of 6 vote

int sumleaves (btree* t) {
        if (!t->left && !t->right) {
            return (t->val);
        }
        else {
            return ( ((t->left)?sumleaves(t->left):0) + ((t->right)?sumleaves(t->right):0 );
        }
    }

- guest128 October 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

If you give this code in an interview, you will have points cut off.

1) No null checks.

2) A ridiculous attempt to write concise code. This is a simple problem so if I showed this to a co-worker, he might be able to understand easily, but that if you did this everytime?

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

Meh. Do you subject every method you write with torturous null checks? If you look closely, most of your code will be written with certain assumptions in mind. If those assumptions are broke, pretty much your entire system is broken.

- dr.house October 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@dr.house: Huh? Of course you do. Robust error handling is a major portion of writing production code.

Besides, the interviewer will scrutinize you to these standards. Did you not understand the first sentence of what Anonymous is saying? Even if you don't do it yourself, the interviewer will likely do, and ding you for it.

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

(Of course, not _every_ method).

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

We can use any of the traversal mechanism (in/pre/post order)and at node we can check if left && right nodes are null then Update the running counter

- freeniza October 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes
maintain a global variable sum. initialize sum as 0. sample code: {{{ void sum(node *root){ if(root==null) return; if(root!=null && root->right==null && root->left==null){ sum+=(root->data); return; } sum(root->right); sum(root->left); } - pradegup October 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Instead of global variable, you can use a integer pointer as part of your function prototype. Use this integer to maintain your sum.

void sum (node *root, int *summation);

- kill -9 October 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

// Normal pre-order traversal and adding to the sum as we traverse
void sum_leaf_binary_tree(struct node* root, int& sum = 0) {
	if(root) {
		if(root->left == NULL && root->right == NULL) {
			sum += root->data; // leaf node
			return;
		}

		if(root->left)
			sum_leaf_binary_tree(root->left, sum);

		if(root->right)
			sum_leaf_binary_tree(root->right, sum);
	}
}

- mr October 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Idea is to do a depth first search, maintaining a running.
C++ like code. Note that sum is passed by reference. If you want to do C, then you can pass a pointer.

long LeafSum(Node *root) {
    long sum = 0;
    LeafSumInternal(root, sum);
    return sum;
}
void LeafSumInternal(Node *n, long & sum) {
    if (n == null) return;
    // Found a leaf node! Add to sum.
    if (!n->left && !n->right) {
        sum += n->data;
        return;
    }
    
    if (n->left) { LeafSumInternal(n->left, sum) };
    if (n->right) {LeafSumInternal(n->right, sum)};
}

- Anonymous October 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Java code

public static int sumLeaves(TreeNode r) {
    if (r == null) {
        return Integer.MIN_VALUE;
    }   

    if (r.left == null && r.right == null) {
        return r.data;
    }   

    int sum = 0;
    if (r.left != null) {
        sum += sumLeaves(r.left);
    }

    if (r.right != null) {
        sum += sumLeaves(r.right);
    }   

    return sum;
}

- nixfish October 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//print sum of leaves of binary tree
/*
1.Traverse the tree
2.Find the leaf node and return its value
*/

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

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

struct node* newnode(int key){
struct node* leaf = (struct node*)malloc(sizeof(struct node));
leaf->data = key;
leaf->left =NULL;
leaf->right =NULL;
}

int sumofleaves(struct node* n){
if(n!=NULL){
if(n->left==NULL && n->right==NULL)
return n->data;
else
return sumofleaves(n->left)+sumofleaves(n->right);
}
return 0;
}

int main(){
/* 5
/ \
3 9
/\ / \
2 4 7 10

*/

struct node *root=newnode(5);
root->left = newnode(3);
root->right = newnode(9);
root->left->left = newnode(2);
root->left->right = newnode(4);
root->right->left = newnode(7);
root->right->right = newnode(10);

printf("%d",sumofleaves(root));
// inorder(root);
// printf("\n");
// preorder(root);
// printf("\n");
// postorder(root);
printf("\n");
return 0;
}

- madmonkey October 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int sum_leaves(struct node* root)
{
    static int sum=0;
    if(root==NULL)
    {
        return 0;
    }
    if(root->right==NULL&&root->left==NULL)
    {

        return root->info;
    }
    else
    {
        sum=sum_leaves(root->left)+sum_leaves(root->right);
        return sum;
    }
}

- Anshul October 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about this

public static int countLeavesSum(node tree){
		if(tree==null)
			return 0;
		if(tree.left==null && tree.right==null)
			 return tree.data;
		 return (countLeavesSum(tree.left)+countLeavesSum(tree.right));
	}

- coder October 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static int sum = 0;
leafnode(struct node *ptr)
{
if(ptr->left == NULL && ptr->right==NULL)
{
sum = sum+ptr->data;
}
else
{
leafnode(ptr->left);
leafnode(ptr->right);
}
}

- csgeeg October 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class BinaryTree {

class Node
{
Node(int i)
{
data=i;
}
int data;
Node nodeLeft;
Node nodeRight;
}

static BinaryTree tree = new BinaryTree();

static Node createTree()
{
Node l1_1 = tree.new Node(30);
Node l2_1 = tree.new Node(25);
Node l2_2 = tree.new Node(35);
Node l3_1 = tree.new Node(20);
Node l3_2 = tree.new Node(28);
Node l3_3 = tree.new Node(32);
Node l3_4 = tree.new Node(50);
Node l4_1 = tree.new Node(10);
Node l4_2 = tree.new Node(22);
Node l4_3 = tree.new Node(27);
Node l4_4 = tree.new Node(29);
Node l4_5 = tree.new Node(31);
Node l4_6 = tree.new Node(34);
Node l4_7 = tree.new Node(38);
Node l4_8 = tree.new Node(55);

l1_1.nodeLeft=l2_1;
l1_1.nodeRight=l2_2;

l2_1.nodeLeft=l3_1;
l2_1.nodeRight=l3_2;
l2_2.nodeLeft=l3_3;
l2_2.nodeRight=l3_4;

l3_1.nodeLeft=l4_1;
l3_1.nodeRight=l4_2;
l3_2.nodeLeft=l4_3;
l3_2.nodeRight=l4_4;
l3_3.nodeLeft=l4_5;
l3_3.nodeRight=l4_6;
l3_4.nodeLeft=l4_7;
l3_4.nodeRight=l4_8;

return l1_1;
}

public static void main(String p[])
{
Node root= null;
root = tree.createTree();
System.out.println(sumOfLeaves(root));
}

static int sumOfLeaves(Node node)
{
int total = 0;

if(node.nodeLeft != null)
total += sumOfLeaves(node.nodeLeft);
else
{
if(node.nodeRight == null)
return node.data;
else
return 0;
}
//total += node.data;

if(node.nodeRight != null)
total += sumOfLeaves(node.nodeRight);
else
{
if(node.nodeLeft == null)
return sumOfLeaves(node.nodeRight);
else
return 0;
}
return total;
}
}

- jaikuadwani October 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int getSumOfLeaves(Node root) {
		
		if ( root == null ) {
			return 0;
		}
		
		if ( root.getLeft() == null
				&& root.getRight() == null ) {
			return root.getValue();
		}

		return getSumOfLeaves(root.getLeft()) + getSumOfLeaves(root.getRight());
		
	}

- belligerentCoder October 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is wrong code

- Varun April 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

sum(BinaryTree *root )
{
int sum = 0;
if(root != null)
{
if(root->leftchild != null && root->rightchild != null)
{
sum(root->leftchild);
}
else
{
sum = sum + *root;
}
if(root->rightchild != null && root->leftchild != null)
{
sum(root->rightchild);
}
else
{
sum = sum + *root;
}
}
return sum;
}

- Nishant Kumar October 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

sum(BinaryTree *root )
{
int sum = 0;
if(root != null)
  {
   if(root->leftchild != null)
    {
          sum(root->leftchild);
    }
   else if (root->rightchild != null)
   {
   sum(root->rightchild);
   }
   else
   {
    sum = sum + *root;
   }
}
return sum;

}

- Nishant Kumar October 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I really doubt such an easy question was asked !

- amit December 07, 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