Amazon Interview Question for Software Engineer in Tests


Country: United States
Interview Type: Phone Interview




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

/*
    balanced: check if a binary tree is balanced.
 */

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

/* standard tree node */
struct treenode {
        struct treenode *left;
        struct treenode *right;
};


/* max of two integers */
int
max(int a, int b)
{
        return (a > b) ? a : b;
}


/* start by assuming tree rooted at node is balanced.  Recurse
   to find left and right subtree heights.  Set balanced to false
   if tree rooted at node is not balanced.  Leaf height is 0
   and leaf is balanced.

   Note that balanced is untouched or set to false.
 */
int
height(struct treenode *node, int *balanced)
{
        if (!node)
                return 0;
        int leftheight = height(node->left, balanced);
        int rightheight = height(node->right, balanced);
        if (abs(leftheight - rightheight) > 1)
                *balanced = 0;
        return max(leftheight, rightheight) + 1;
}


int
main(void)
{
        struct treenode rightrightleaf = {
                .left = NULL,
                .right = NULL
        };
        struct treenode right = {
                .left = NULL,
                .right = &rightrightleaf
        };
        struct treenode root = {
                .left = NULL,
                .right = &right
        };
        int balanced = 1;
        height(&root, &balanced);
        printf("Tree is %s\n", balanced ? "balanced" : "not balanced");
        return 0;
}

- Event Horizon December 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In these two sentences "int leftheight = height(node->left, balanced); int rightheight = height(node->right, balanced);" If the left subtree is not balanced, while the right one is balanced, will the variable "balanced" change to 1 again?

- chengyuanzhang831 January 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static int height(BSTNode n)
{
if (n==null)
return 0;
else return max(height(n.lChild),height(n.rChild))+1;
}
private static int max(int a , int b)
{
return (a>=b?a:b);
}
public boolean balanced()
{
int diff = Math.abs(height(root.left)-height(root.right));
if (diff >1)
return false;
else return true;
}

- simplyankush December 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

only need to check max_depth-min_depth<=1

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

Just curious and pardon my ignorance. I have seen "WAP" in other questions. Why is it called WAP?

- algo_guy December 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

WAP means "Write a Program".. :)

- curious_coder December 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

github.com/techpanja/interviewproblems/blob/master/src/trees/treeproblems/CheckBalancedTree.java

- techpanja December 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Balanced Tree: for each node, the difference between left subtree and right subtree should be less than or equal to 1 and left and right subtree should be balanced.

int height(Node root) {
if(root==null)
return 0;
else
return (max(height(root.left),height(root.right)) +1);
}

boolean balanced(Node root) {

int diff = Math.abs(height(root.left) - height(root.right));
if(root == null)
return true;
else {
if (root.left ==null && root.right == null)
return true;
else if (diff <=1 && balanced(root.left) && balanced(root.right))
return true;
else
return false;
}
}

- SM January 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Balanced Tree: for each node, the difference between left subtree and right subtree should be less than or equal to 1 and left and right subtree should be balanced.

int height(Node root) {
	if(root==null)
		return 0;
	else
		return (max(height(root.left),height(root.right)) +1);
	}

boolean balanced(Node root) {
	
	int diff = Math.abs(height(root.left) - height(root.right));
	if(root == null)
	   return true;
	else {
	   if (root.left ==null && root.right == null)
		return true;
	   else if (diff <=1 && balanced(root.left) && balanced(root.right))
		return true;
	   else 
		return false;
	}
}

- SM January 06, 2014 | 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