CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

Amazon Interview Question for SDE1s


Team: Kindle
Country: India
Interview Type: Written Test



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

calling------------------ isFoldable(root.getLeft(),root.getRight()));

private static BinaryTreeNode createBinaryTreeFoldable() {
		// TODO Auto-generated method stub
		BinaryTreeNode node1 = new BinaryTreeNode(10);
		BinaryTreeNode node2 = new BinaryTreeNode(20);
		BinaryTreeNode node3 = new BinaryTreeNode(20);
		BinaryTreeNode node4 = new BinaryTreeNode(30);
		BinaryTreeNode node5 = new BinaryTreeNode(40);
		BinaryTreeNode node6 = new BinaryTreeNode(40);
		BinaryTreeNode node7 = new BinaryTreeNode(30);

		node1.setLeft(node2);
		node1.setRight(node3);
		node2.setLeft(node4);
		node2.setRight(node5);
		node3.setLeft(node6);
		node3.setRight(node7);
		return node1;
	}


private static boolean isFoldable(BinaryTreeNode root1, BinaryTreeNode root2) {
		if (root1 == null && root2 == null)
			return true;
		if ((root1 == null && root2 != null)
				|| (root1 != null && root2 == null))
			return false;

		if (root1.getData() != root2.getData())
			return false;
		else
			return isFoldable(root1.getLeft(), root2.getRight())
					&& isFoldable(root1.getRight(), root2.getLeft());
	}

- Vir Pratap Uttam May 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

public boolean isMirrorIter(BinaryNode root) {
			if (root == null) {
				return false;
			}
			Deque<BinaryNode> list = new LinkedList<BinaryNode>();
			Deque<BinaryNode> list1 = null;
			list.add(root);
			int i = list.size();
			while (list.size() > 0) {
				i = list.size();
				list1 = new LinkedList<BinaryNode>();
				while (i > 0) {
					if (i > 1) {
						BinaryNode first = list.pollFirst();
						BinaryNode last = list.pollLast();
						if (first == null && last != null)
							return false;
						if (last == null && first != null)
							return false;
						if (first != null && last != null) {
							if (first.getData() != last.getData()) {
								return false;
							} else {
								list1.add(first.getLeft());
								list1.add(first.getRight());
								list1.add(last.getLeft());
								list1.add(last.getRight());
							}
						}
						i = i - 2;
					}
					if (i == 1) {
						BinaryNode first = list.pollFirst();
						list1.add(first.getLeft());
						list1.add(first.getRight());
						i--;
					}
				}
				list = list1;
			}
			return true;
		}

- Sheetal May 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Question is : check for mirror image. Step for that
1) Go for BFS at each depth
2) Add Null node also at each depth
3) Check at each depth Data must be Palindrome.

If at each depth, data is palindrome than tree will be mirror image.

- Rajesh Kumar May 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean isMirrorIter(BinaryNode root) {
			if (root == null) {
				return false;
			}
			Deque<BinaryNode> list = new LinkedList<BinaryNode>();
			Deque<BinaryNode> list1 = null;
			list.add(root);
			int i = list.size();
			while (list.size() > 0) {
				i = list.size();
				list1 = new LinkedList<BinaryNode>();
				while (i > 0) {
					if (i > 1) {
						BinaryNode first = list.pollFirst();
						BinaryNode last = list.pollLast();
						if (first == null && last != null)
							return false;
						if (last == null && first != null)
							return false;
						if (first != null && last != null) {
							if (first.getData() != last.getData()) {
								return false;
							} else {
								list1.add(first.getLeft());
								list1.add(first.getRight());
								list1.add(last.getLeft());
								list1.add(last.getRight());
							}
						}
						i = i - 2;
					}
					if (i == 1) {
						BinaryNode first = list.pollFirst();
						list1.add(first.getLeft());
						list1.add(first.getRight());
						i--;
					}
				}
				list = list1;
			}
			return true;
		}

- sheetal May 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean isMirrorIter(BinaryNode root) {
if (root == null) {
return false;
}
Deque<BinaryNode> list = new LinkedList<BinaryNode>();
Deque<BinaryNode> list1 = null;
list.add(root);
int i = list.size();
while (list.size() > 0) {
i = list.size();
list1 = new LinkedList<BinaryNode>();
while (i > 0) {
if (i > 1) {
BinaryNode first = list.pollFirst();
BinaryNode last = list.pollLast();
if (first == null && last != null)
return false;
if (last == null && first != null)
return false;
if (first != null && last != null) {
if (first.getData() != last.getData()) {
return false;
} else {
list1.add(first.getLeft());
list1.add(first.getRight());
list1.add(last.getLeft());
list1.add(last.getRight());
}
}
i = i - 2;
}
if (i == 1) {
BinaryNode first = list.pollFirst();
list1.add(first.getLeft());
list1.add(first.getRight());
i--;
}
}
list = list1;
}
return true;
}

- sheetal May 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean isMirrorIter(BinaryNode root) {
if (root == null) {
return false;
}
Deque<BinaryNode> list = new LinkedList<BinaryNode>();
Deque<BinaryNode> list1 = null;
list.add(root);
int i = list.size();
while (list.size() > 0) {
i = list.size();
list1 = new LinkedList<BinaryNode>();
while (i > 0) {
if (i > 1) {
BinaryNode first = list.pollFirst();
BinaryNode last = list.pollLast();
if (first == null && last != null)
return false;
if (last == null && first != null)
return false;
if (first != null && last != null) {
if (first.getData() != last.getData()) {
return false;
} else {
list1.add(first.getLeft());
list1.add(first.getRight());
list1.add(last.getLeft());
list1.add(last.getRight());
}
}
i = i - 2;
}
if (i == 1) {
BinaryNode first = list.pollFirst();
list1.add(first.getLeft());
list1.add(first.getRight());
i--;
}
}
list = list1;
}
return true;
}

- sheetal May 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Recursive approach:

private static boolean isFoldable(BinaryTree t1, BinaryTree t2) {
	
		if (t1 == null && t2 == null)
			return true;

		if (t1 == null || t2 == null)
			return false;

		if (t1.getData() != t2.getData())
			return false;

		return isFoldable(t1.getLeft(), t2.getRight()) && isFoldable(t1.getRight(), t2.getLeft());
	}

- Dilbert Einstein May 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#define TRUE 1
#define FALSE 0

int isFoldable(Node * head){
	char [] leftSequence = left_to_right_preorder(head->left_child);
	char [] rightSequence = right_to_left_preorder(head->right_child);
	
	if(is_equal(leftSequence, rightSequence)){
		return TRUE;		
	}
	return FALSE;
}

char[] left_to_right_preorder(Node * node){
	Queue queue;
	enqueue_left_to_right_in_queue(&queue, node);	
	char result[queue.size() + 1];
	result[0] = queue.size();
	for(int i = 1;i <= queue.size(); i++){
		result[i] = queue.pop().value;
	}
	return result;
}

void enqueue_left_to_right_in_queue(Queue * queue, Node * node){
	if(node != null){
		queue.push(node);
		enqueue_left_to_right_in_queue(queue, node->left);
		enqueue_left_to_right_in_queue(queue, node->right);
	}	
}

char[] right_to_left_preorder(Node * node){
	Queue queue;
	enqueue_right_to_left_in_queue(&queue, node);
	
	char result[queue.size()+ 1] ;
	result[0] = queue.size();
	
	for(int i = 1 ; i <= queue.size(); i++){
		result[i] = queue.pop().value;
	}
	return result;
}

void enqueue_right_to_left_in_queue(Queue * queue, Node * node){
	if(node != null){
		queue.push(queue, node);
		enqueue_right_to_left_in_queue(queue, node->right_child);
		enqueue_right_to_left_in_queue(queue, node->left_child);
	}
}

int is_equal(char* first, char* second){
	if(first[0] != second[0]){
		return 0;
	}
	for(int i = 1; i <= first[0]; i++){
		if(first[i] != second[i]){
			return 0;
		}
	}
	return 1;
}

- sriparna.c35 May 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Take left child of root. Say it's rLC
Take right child of root. Say it's rRC.
If both of them are null the tree is foldable.

Else
preOrder traversal of rLC where left subtree is always visited before right subtree.
preOrder traversal of rRC where right subtree is always visited before left subtree.

If the result is equal String then the answer is true.

- s100banerjee May 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Non-recursive method in javascript.
Add pairs of nodes to compare to the queue.
Pop the left/right pairs off and compare if their structure is the same (null/not null).
Then repeat for left.left + right.right and left.right, right.left.

function isFoldable(node) {

  var queue = [node.left, node.right];

  while (queue.length > 0) {

    var left = queue.shift();
    var right = queue.shift();

    if (left == null && right == null) {
      continue
    }
    if (left == null || right == null) {
      return false;
    }

    queue.push(left.left);
    queue.push(right.right);
    queue.push(left.right);
    queue.push(right.left);
  }

  return true;
}

- justinm May 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Similar recursive approach with a little shorter check of null vs not null:

/**
 * Created by Igor_Sokolov on 5/18/2015.
 */
public class CareerCup_5092252147777536 {
    private static class Node {
        int value;

        Node left;
        Node right;

        public Node(int value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return String.valueOf(value);
        }

        Node setLeft(Node left) {
            this.left = left;
            return this;
        }

        Node setRight(Node right) {
            this.right = right;
            return this;
        }
    }

    private static Node prepareData() {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(2);
        Node node4 = new Node(3);
        Node node5 = new Node(4);
        Node node6 = new Node(3);
        Node node7 = new Node(4);

        node1.setLeft(node2).setRight(node3);
        node2.setLeft(node4).setRight(node5);
        node3.setLeft(node7).setRight(node6);

        return node1;
    }

    public static void main(String[] args) {
        Node root = prepareData();
        System.out.println(checkFoldable(root));
    }

    private static boolean checkFoldable(Node root) {
        if (root == null) {
            return true;
        }

        return checkFoldable(root.left, root.right);
    }

    private static boolean checkFoldable(Node root1, Node root2) {
        if (root1 == null && root2 == null) {
            return true;
        }

        if (root1 != null ^ root2 != null || root1.value != root2.value) {
            return false;
        }

        return checkFoldable(root1.left, root2.right) && checkFoldable(root1.right, root2.left);
    }

}

- igor.s.sokolov May 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<bits/stdc++.h>
using namespace std;
typedef struct Node
{
int data;
Node *left;
Node *right;
};
Node * Create(int data)
{
Node *xx=(Node *)malloc(sizeof(Node));
xx->data=data;
xx->left=NULL;
xx->right=NULL;
return xx;
}
bool mirrorrec(Node *root1,Node * root2)
{
if(root1==NULL && root2==NULL)
return true;
if(root1==NULL || root2==NULL)
return false;
if(root1->data!=root2->data)
return false;
return mirrorrec(root1->left,root2->right) && mirrorrec(root1->right,root2->left);
}
int main()
{
Node *root=Create(10);
root->left=Create(20);
root->right=Create(20);
root->left->left=Create(30);
root->left->right=Create(40);
root->right->left=Create(40);
root->right->right=Create(30);
//root->left->left->left=Create(8);
//root->left->left->right=Create(9);
if(mirrorrec(root,root))
{
cout<<"yes, mirror image is possible "<<endl;
}
else
{
cout<<"mirror image is not possible "<<endl;
}
return 0;
}

- undefined May 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<bits/stdc++.h>
using namespace std;
typedef struct Node
{
int data;
Node *left;
Node *right;
};
Node * Create(int data)
{
Node *xx=(Node *)malloc(sizeof(Node));
xx->data=data;
xx->left=NULL;
xx->right=NULL;
return xx;
}
bool mirrorrec(Node *root1,Node * root2)
{
if(root1==NULL && root2==NULL)
return true;
if(root1==NULL || root2==NULL)
return false;
if(root1->data!=root2->data)
return false;
return mirrorrec(root1->left,root2->right) && mirrorrec(root1->right,root2->left);
}
int main()
{
Node *root=Create(10);
root->left=Create(20);
root->right=Create(20);
root->left->left=Create(30);
root->left->right=Create(40);
root->right->left=Create(40);
root->right->right=Create(30);
//root->left->left->left=Create(8);
//root->left->left->right=Create(9);
if(mirrorrec(root,root))
{
cout<<"yes, mirror image is possible "<<endl;
}
else
{
cout<<"mirror image is not possible "<<endl;
}
return 0;
}

- undefined May 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

do a bfs on left and right

isFoldable( node ) {
     if ( node == null ) return true;
     node left = node.left;
     node right = node.right;

     queue1 = new queue();
     queue2 = new queue();

     if ( left != null ) queue1.add(left);
     if ( right != null ) queue2.add(right);

    
   
     while ( true ) {
         if ( queue1.isEmpty() && queue2.isEmpty() ) return true;
         if ( queue1.isEmpty() ) return false;
         if ( queue2.isEmpty() ) return false;

         left = queue1.poll();
     
         right = queue2.poll();

         if( left.left != null ) {
             if ( right.right == null ) return false;
             queue1.add(left.left);
             queue2.add(right.right);
         } 


         if( left.right != null ) {
             if ( right.left == null ) return false;
             queue1.add(left.right);
             queue2.add(right.left);
         }

     }
     return true;

}

- stephenpince July 31, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Approach
1. Check Left and right sub tree of the root recursively if they are identical.

bool IsFoldable(Tree t)
{ 
   return t !=null && recursiveSameTree(t.left, t.right);
}
bool recursiveSameTree(Tree  t1, Tree t2)
{
  if (t1 == null && t2 == null )
  {
     return true;
  }
  if (t1 == null || t2 == null )
  {
     return false;
  } 

  return recursiveSameTree(t1.left, t2.left) && recursiveSameTree(t1.right, t2.right) 
}

- pc May 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

it is asking if the tree is symmetric, not if the 2 subtrees are identical.

- SK May 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The function recursiveSameTree is checking if the two subtrees are similar , but since the question is asking for foldable tree, the subtrees should be mirror copies of each other.

- rushikesh90 May 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Generate the BFS queue of both sub trees.
The trick is that the BFS queue for the right sub tree is generated right-to-left, i.e., adding the right child before the left child and hence processing it first.
Add null children to the queue as well.
Compare the two.

bool is_foldable(node_t* n)
{
	if (nullptr == n) return true;
	std::list<node_t*> s_left, s_right;
	get_bfs(n->left, s_left, true);
	get_bfs(n->right, s_right, false);
	if (s_left.size() != s_right.size()) return false;
	auto li = s_left.begin();
	auto ri = s_right.begin();
	for (; li != s_left.end(); ++li, ++ri)
	{
		if (nullptr == *li && nullptr = *ri) continue;
		if (nullptr == *li || nullptr = *ri) return false;
		if (li->data != ri->data) return false;
	}
	return true;
}

void get_bfs(node_t* n, std::list<node_t*>& s_out, bool ltr)
{
	std::list<node_t*> s_in;
	s_in.push_back(n);
	while (!s_in.empty())
	{
		node_t* curr = s_in.front();
		s_in.pop_front();
		s_out.push_back(curr);
		if (nullptr != curr)
		{
			if (ltr)
			{
				s_in.push_back(curr->left);
				s_in.push_back(curr->right);
			}
			else
			{
				s_in.push_back(curr->right);
				s_in.push_back(curr->left);
			}
		}
	}	
}

- Omri.Bashari May 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 votes

The question is not asking for identical subtrees but foldable , so data of both subtrees can be different.

- rushikesh90 May 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

mirror image means value as well as nodes must match.

- jaip42 May 11, 2015 | Flag


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