Amazon Interview Question Software Engineer / Developers


Country: India
Interview Type: In-Person


Comment hidden because of low score. Click to expand.
8
of 10 vote

recursive:
checkLevel(node t, int level){
if(t.left != null && t.right != null){
      level ++;
      return min(checkLevel(t.left,level),checkLevel(t.right,level));
}
else
      return level;
}

- coderFromHell on July 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Actually there is no need for the level parameter :

int complete (node root) {
if(root == null)
	return -1;
else
	return 1 + Math.min(complete(root.left), complete(root.right));
}

- amritaansh123 on February 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The algorithm is awesome!

- TT on April 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

This the best i could think of iterative approach

static int binaryLevelnonRec(Tree head){
		if(head==null)
			return 0;
		LinkedList<Tree> stack1 = new LinkedList<Tree>();
		head.depth =1;
		stack1.push(head);
		int maxCompleteDepth = -1;
		while(!stack1.isEmpty()){
			Tree current = stack1.pop();
			int currDepth = current.depth;
			if(maxCompleteDepth !=-1 && maxCompleteDepth<currDepth)
				continue;
			if(current.leftChild!=null && current.rightChild!=null){
				current.leftChild.depth = currDepth+1;
				current.rightChild.depth = currDepth+1;
				stack1.push(current.leftChild);
				stack1.push(current.leftChild);
			} else 
				maxCompleteDepth = currDepth;
		}
		return maxCompleteDepth;
	}

- pratap.raavi on July 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

typo error. pushed leftChild twice :)

stack1.push(current.leftChild);
stack1.push(current.rightChild);

- pratap.raavi on July 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

why maxCompleteDepth<currDepth check in if(maxCompleteDepth !=-1 && maxCompleteDepth<currDepth) is necessary?
Because, once maxCompleteDepth has become != -1, other elements in the stack not be verified for the completeness check.
Pls correct me if I'm wrong!

- Anonymous on August 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

public static void printTheLevelAtWhichTheBinaryTreeIsComplete(TreeNode node) {

		if (node == null) {
			System.out.println("The tree is empty.");
			System.out.println("-1");
		}
		int level = 0;
		TreeNode delimeter = new TreeNode(-1);
		TreeNode temp = null;
		Queue<TreeNode> q = new LinkedList<TreeNode>();

		q.add(node);
		q.add(delimeter);

		while (!q.isEmpty()) {
			temp = q.remove();
			if (temp == delimeter) {
				level += 1;
				q.add(delimeter);
				continue;
			}
			if (temp.left != null && temp.right != null) {
				if (temp.left != null)
					q.add(temp.left);
				if(temp.right != null)
					q.add(temp.right);
			} else {
				break;
			}

		}
		System.out.println("At level " + level + " the Tree is balanced.");
	}

It is the working code.. Please check..:)

- KKR on July 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

1. Init completeLevel to 0
2. Start level order traversal (This can be done either by maintaining a delimeter for each level in the queue or by two queue method.)
3 Initialize a flag - isComplete to true.
4. Check for existence of both children for all nodes of current level
5. Break whenever we find isComplete to be false.
6. At completion of level, switch to next level and increment completeLevel.

- romilshah29 on July 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I write this code in eclipse, It can work...

public static boolean Whether_Balance(BinaryTreeNode head){
if(check_process(head,1)!=-1){
return true;
}
return false;
}
public static int check_process(BinaryTreeNode head,int height){
if((head.leftchild==null)&&(head.rightchild==null)){
return height;
}
else if((head.leftchild!=null)&&(head.rightchild!=null)){
int height_left=check_process(head.leftchild,height+1);
int height_right=check_process(head.rightchild,height+1);
if((height_left==-1)||(height_right==-1)){
return -1;
}
else if(height_left!=height_right){
return -1;
}
else
return height_left;

}
else
return -1;

}

- Chengyun Zuo on July 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

java recursive code

static int binaryLevelRec(Tree head){
		if(head==null)
			return 0;
		else
			return 1+ Math.min(binaryLevelRec(head.leftChild), binaryLevelRec(head.rightChild));
	}

- pratap.raavi on July 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Try using BFS for iteration

int findlevel (node root)
{
//using BFS
int level = 0;
Queue Q;

Q.insert(root);

//iterate till the Q is empty
While(!Q.isempty())
{
//For all the nodes of a level make sure if both the nodes are present.
int i = 2*level;
while(i>=0)
{
node n = Q.delete();
if(n.left != null && n.right != null)
{
Q.insert(n.left);
Q.insert(n.right);
}
else
{
break;
}
i--;
}

if(i >=0)
{
break;
}
else
{
level ++
}
}
return level;
}

- Anonymous on September 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

non recursive:
adding all the nodes at each level in a stack and checking the length of the stack.
If its 2 to the power level, at all levels ,we get a complete binary tree.

bool iterativ_check(node* root)
{
stack<node*> st1; // can also take qeue
st1.push(root);
while(st1.size!=0)
{ stack<node*>st2(st1);
st1.clear();
whille(st2.size!=0)
{ node* n1=st2.pop();
if(n1->left!=Null&&n2->rite!=NULL)
{
st1.push(st1[i].left)
st1.push(st1[i].rite)
st2.pop();
}
}
if(st1.size!=Math.power(count,2);
break;
}

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

Iterative

private static int fnIterative(Node root) {
        int level = 1;
        Queue<Node> q1 = new Queue<Node>(10);
        Node marker = new Node(999);
        q1.insert(root);
        q1.insert(marker);
        while (!q1.isEmpty()) {
            Node curr = q1.delete();
            if (curr.left == null || curr.right == null)
                break;
            else {
                q1.insert(curr.left);
                q1.insert(curr.right);
            }
            Node isMarker = q1.peek();
            if (isMarker == marker) {
                q1.delete();
                if (2 * level != q1.size()) {
                    break;
                }
                q1.insert(marker);
                level++;
            }
        }
        return level;

    }

Recursive

private static int fnrecursive(Node root, int level) {
        if (root == null) return -1;
        int l = fnrecursive(root.left, level + 1);
        int r = fnrecursive(root.right, level + 1);
        if (l > 0 && r > 0) {
            return l < r ? l : r;
        }
        return level;

    }

- PM on May 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through 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