Amazon Interview Question for SDE-2s


Team: Kindle
Country: India
Interview Type: Written Test




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

public boolean isMirrored(TreeNode t){
		if(t!=null) return isMirrored(t.left,t.right);
		return false;
}
	public boolean isMirrored(TreeNode a, TreeNode b){
		if(a==null && b==null) return true;
		if(a==null ^ b==null) return false;
		if(a.data==b.data){
		return isMirrored(a.left,b.right) && isMirrored(a.right,b.left);
	}
}
/*class TreeNode{
	int data;
	TreeNode left;
	TreeNode right;
}*/

- dmi March 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

1. Do level order traversing.
2. if(root==null) return;
else
for each level in the tree
a. maintain a queue. (like BFS)
b. Insert using add(element);
c. for a given level compare first() and count-1() until q.size() for that level., if needed elements can be moved to an auxiliary memory and compared.
d. during pop() operation, the child nodes has to be inserted in the queue.

- DuttaJ March 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The side doesn't let me to paste my dotnetfiddle link here, but you can still check it out, the id is /nchavf.

// C# code:
using System;
using System.Collections.Generic;


namespace PracticeProgrammingPack
{

    public partial class Program
    {
		// This method first creates the list of left child nodes by visting them in a VLR fashion,
		// Then, creates the list of right child nodes by visting them in a VRL fashion (mirrored),
		// Finally compares the 2 above lists to see if they're equal.
		// The algorithm runs in O(n)
        private static bool IsMirroredBinaryTree(BinaryTree<int> tree)
        {
            if (tree == null || tree.Root == null)
            {
                return false;
            }

            List<int> leftChildren = new List<int>();
            List<int> rightChildren = new List<int>();

            TraverseLeftVLR(tree.Root.LeftChild, leftChildren);
            TraverseRightVRL(tree.Root.RightChild, rightChildren);

            if (leftChildren.Count != rightChildren.Count)
            {
                return false;
            }

            for (int i = 0; i < leftChildren.Count; i++)
            {
                if (leftChildren[i] != rightChildren[i])
                {
                    return false;
                }
            }

            return true;
        }

        // a depth first traverse, in a Visit-Right-Left fashion 
        private static void TraverseRightVRL(BinaryTreeNode<int> node, List<int> rightChildren)
        {
            if (node == null)
            {
                return;
            }

            rightChildren.Add(node.Value);
            TraverseRightVRL(node.RightChild, rightChildren);
            TraverseRightVRL(node.LeftChild, rightChildren);
        }

        // a depth first traverse, in a Visit-Left-Right fashion 
        private static void TraverseLeftVLR(BinaryTreeNode<int> node, List<int> leftChildren)
        {
            if (node == null)
            {
                return;
            }

            leftChildren.Add(node.Value);
            TraverseLeftVLR(node.LeftChild, leftChildren);
            TraverseLeftVLR(node.RightChild, leftChildren);
        }

        public static void Main()
        {
			// Pardon me for this stupid initialization, but I didn't want to spend time developing a perfect BinaryTree data structure
            BinaryTreeNode<int> n1 = new BinaryTreeNode<int> { Value = 60 };
            BinaryTreeNode<int> n2 = new BinaryTreeNode<int> { Value = 30 };
            BinaryTreeNode<int> n3 = new BinaryTreeNode<int> { Value = 30 };
            BinaryTreeNode<int> n4 = new BinaryTreeNode<int> { Value = 20 };
            BinaryTreeNode<int> n5 = new BinaryTreeNode<int> { Value = 50 };
            BinaryTreeNode<int> n6 = new BinaryTreeNode<int> { Value = 50 };
            BinaryTreeNode<int> n7 = new BinaryTreeNode<int> { Value = 20 };
            BinaryTreeNode<int> n8 = new BinaryTreeNode<int> { Value = 15 };
            BinaryTreeNode<int> n9 = new BinaryTreeNode<int> { Value = 15 };

            BinaryTree<int> tree = new BinaryTree<int>();
            tree.Root = n1;
            tree.Root.LeftChild = n2;
            tree.Root.RightChild = n3;
            tree.Root.LeftChild.LeftChild = n4;
            tree.Root.LeftChild.RightChild = n5;
            tree.Root.LeftChild.RightChild.LeftChild = n8;
            tree.Root.RightChild.LeftChild = n6;
            tree.Root.RightChild.LeftChild.RightChild = n9;
            tree.Root.RightChild.RightChild = n7;

            Console.WriteLine(IsMirroredBinaryTree(tree));
        }
    }

    public class BinaryTreeNode<T>
    {
        public T Value { get; set; }
        public BinaryTreeNode<T> LeftChild { get; set; }
        public BinaryTreeNode<T> RightChild { get; set; }
    }

    public class BinaryTree<T>
    {
        public BinaryTreeNode<T> Root { get; set; }
    }
}

- sminfo March 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your concept is correct, except for the fact that you also need to add "NULL" or any number representing null to the list of children. This is because if you don't add "NULL" then the order of the children will not be proper. For e.g

60
				     /       \	
				30	       30
				   \		/
				    50      50

this will give you "its a mirror" whereas it is "not a mirror".

- deepansh March 12, 2017 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static bool AreTreesMirrored(TreeNode n1, TreeNode n2)
{
if (n1 == null && n2 == null)
{
return true;
}

if (n1 == null || n2 == null)
{
return false;
}

return n1.Value == n2.Value &&
AreTreesMirrored(n1.Left, n2.Right) &&
AreTreesMirrored(n1.Right, n2.Left);

}

public static bool IsTreeMirrored(TreeNode n)
{
bool ret = false;
if (n != null)
{
ret = AreTreesMirrored(n.Left, n.Right);
}
return ret;
}

- FA1987 March 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

easy to understand

#include<bits/stdc++.h>
using namespace std;
struct node{
int data;
node *left,*right;
};
bool is_mirror(node *first_tree,node *second_tree)
{
if(first_tree==NULL && second_tree ==NULL)
return true;
if(first_tree== NULL || second_tree==NULL)
return false;
return (first_tree->data == second_tree->data) &&
 	is_mirror(first_tree->left,second_tree->right) && 
	is_mirror(first_tree->right ,second_tree->left);

}
node *newnode(int d)
{
node * temp=new node;
temp->data=d;
temp->left=NULL;
temp->right=NULL;
return temp;
}
int main()
{
node *first_tree = newnode(1);
first_tree->left = newnode(2);
first_tree->right = newnode(3);
first_tree->left->left = newnode(4);
first_tree->left->right = newnode(5);
first_tree->right->left = newnode(6);
first_tree->right->right = newnode(3);

node *second_tree = newnode(1);
second_tree->left = newnode(3);
second_tree->right = newnode(2);
second_tree->left->left = newnode(7);
second_tree->left->right = newnode(6);
second_tree->right->left = newnode(5);
second_tree->right->right = newnode(4);

is_mirror(first_tree,second_tree)?cout<<"yes"<<endl:cout<<"no"<<endl;
}

- rahul_kumar March 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private boolean isMirroredTree(Node tree) {
		if(tree == null) {
			return false;
		}
		Queue queue = new Queue();

		if(tree.left != null) {
			if(tree.right == null)
				return false;
			queue.push(tree.left);
		}
		if(tree.right != null) {
			if(tree.left == null)
				return false;
			queue.push(tree.right);
		}
		
		return isMirroredQueue(queue, 1);
	}
	
	private boolean isMirroredQueue(Queue queue, int level) {
		if(queue.isEmpty()) {
			return true;
		}
		
		if(queue.size() != Math.power(2, level)) {
			return false;
		}
		
		Queue temp = new Queue();
		for(int i=0; i<(Math.power(2, level)/2); i++) {
			int item = queue.pop();
			temp.push(item);
			
			if(item.left != null) {
				if(item.right == null)
					return false;
				queue.push(item.left);
			}
			if(item.right != null) {
				if(item.left == null)
					return false;
				queue.push(item.right);
			}
		}
		
		for(int i= Math.power(2, level)/2; i<Math.power(2, level); i++) {
			int item = temp.pop();
			if(queue.pop() != item)
				return false;
				
			if(item.left != null) {
				if(item.right == null)
					return false;
				queue.push(item.left);
			}
			if(item.right != null) {
				if(item.left == null)
					return false;
				queue.push(item.right);
			}
		}
		
		return isMirroredQueue(queue, i++);
	}

- S March 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private boolean isMirroredTree(Node tree) {
		if(tree == null) {
			return false;
		}
		Queue queue = new Queue();

		if(tree.left != null) {
			if(tree.right == null)
				return false;
			queue.push(tree.left);
		}
		if(tree.right != null) {
			if(tree.left == null)
				return false;
			queue.push(tree.right);
		}
		
		return isMirroredQueue(queue, 1);
	}
	
	private boolean isMirroredQueue(Queue queue, int level) {
		if(queue.isEmpty()) {
			return true;
		}
		
		if(queue.size() != Math.power(2, level)) {
			return false;
		}
		
		Queue temp = new Queue();
		for(int i=0; i<(Math.power(2, level)/2); i++) {
			int item = queue.pop();
			temp.push(item);
			
			if(item.left != null) {
				if(item.right == null)
					return false;
				queue.push(item.left);
			}
			if(item.right != null) {
				if(item.left == null)
					return false;
				queue.push(item.right);
			}
		}
		
		for(int i= Math.power(2, level)/2; i<Math.power(2, level); i++) {
			int item = temp.pop();
			if(queue.pop() != item)
				return false;
				
			if(item.left != null) {
				if(item.right == null)
					return false;
				queue.push(item.left);
			}
			if(item.right != null) {
				if(item.left == null)
					return false;
				queue.push(item.right);
			}
		}
		
		return isMirroredQueue(queue, i++);
	}

- Suren March 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Using DFS:

bool isMirrored(Node root) {
	Queue<int> mirrorQ;
	isMirroredPush(root.left, mirrorQ);

	return isMirrored(root.right, mirrorQ);
}

void isMirroredPush(Node root, Queue<int> mirrorQ) {
	if (root == null) {
		mirrorQ.enqueue(-1);
		return;
	}

	mirrorQ.enqueue(root.value);
	isMirroredPush(root.left, mirrorQ);
	isMIrroredPush(root.right, mirrorQ);
}

bool isMirrored(Node root, Queue<int> mirrorQ) {
	if (mirrorQ.size() == 0) {
		return false;
	}

	int val = mirrorQ.dequeue();
	if (root == null) {
		return val == -1;
	}

	if (root.value != val) {
		return false;
	}

	return isMirrored(root.right, mirrorQ) && isMirrored(root.left, mirrorQ);
}

- ajawaid191 April 14, 2017 | 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