Amazon Interview Question for Software Engineer / Developers






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

can you elaborate with an example ?

- Anonymous January 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Approach I could think of:

1) Find Mirror of the Given Tree
2) Now traverse both the trees in order and store traversal in a string
3) Say you get traversal string str1 and st2
4) If str1 is reverse of str2 then the tree is valid mirror, else otherwise

- Anonymous January 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What I think is doing two way BFS to traversal left subtree and right subtree simultaneously.

Once the child nodes of two poped nodes from queues are not opposite, then return false.

So, the run time would O(n)

- Anonymous January 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Does this Q mean that tree is bilateral? if yes.

bool BilateralTree(node* root)
{
	if(root == null)
		return false;

	return isTreeBilateral(&root, &root);
}


bool isTreeBilateral(node *root, node *root1)
{
	if(!root && !root1)
		return true;

	if((!root && root1) || (root && !root1))
		return false;

	return isTreeBilateral(root->left, root1->right) && isTreeBilateral(root->right, root1->left);

}

- Anonymous January 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Does you last call actually is
isTreeBilateral(root->left, root1->right) && isTreeBilateral(root->right, root1->left);

or (rather it should be)
isTreeBilateral(root->left, root1->left) && isTreeBilateral(root->right, root1->right);

or I have misunderstood the question?

- left or right January 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is the description of the question that sucks..... the example cannot show whether we check left-left & right-right or left-right & right-left.....

- Zhen January 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think the original one:
isTreeBilateral(root->left, root1->right) && isTreeBilateral(root->right, root1->left) is more likely valid.

Cuz we suppose the "mirror" stands for the left of the left should be opposite the right of the right. root refers to left and root1 refers to right.

Am I right? This code sounds good but I am not pretty sure....I'd better run it this evening to make sure...

- XO January 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

If the Tree is represented by string, we can do a simple check.

1. find beginning pos(close) of left tree --> f
2. find ending pos(close) of right tree ---> r
3. while( str[f] != '(' or ',' or ')' ) f++;
4. while( str[r] != '(' or ',' or ')' ) r--;
5. if( str[f] == '(" && str[r] == ')' ) {f++,r--};
6. else if( str[f] == ')' && str[r] == '(' ) {f++,r--};
7. else if( str[f] == str[r] == ',' ) {f++,r--};
8. else return false;
9. if( f >= r ) return true;
10. if( f < r ) goto 3;

- Zhen January 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool checkMirror(Node * root)
{
if(root->left != null && root->right != null)
{
if(root->left = root->right) {
return ( checkMirror(root->left) && checkMirror(root->right) )
}
else {
return false;
}

}
else if(root->left = null && root->right = null)
{
return true;
}
else
return false;
}

- Anonymous January 23, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ ^ u cant check whether left tree then right tree "AND" them to get result cos try this case a root,root left(l),root right(r),l right,r left wud return false by ur code....An approach wud be to do inorder traversal to flatten the tree (with place holders even for null pointers)and to check the string for palindrome

- Anonymous January 23, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think the above answer is right

- DDDDDDD February 07, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1)Take two pointers to "root" of the tree say temp1,temp2;

2)Now first pointer "temp1" traverses tree in "preorder" and "temp2" in "postorder"..
till they reach the "root"(No need of complete preorder and postorder traversals)..

3)temp1 and temp2 at each and every node they visit check that either both are NULLs or both are NOTNULL..

i.e either if((temp1==NULL&&temp2==NULL)||(temp1!=NULL&&temp2!=NULL))
if the above condition fails tree is "not image" else "YES"

- keshav January 23, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you give a simple example??
Bicuz in step2, you said to do preorder traverse till temp1 reach the root, doesn't preorder traverse start from the root??

got confused here. Thanks.

- Anonymous January 24, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>

// DS for tree node
struct tnode {
    int data;
    struct tnode *left, *right;
};

// tree
typedef struct {
    struct tnode *root;
} Tree;

// create a new node
struct tnode *newNode(int data, struct tnode *l, struct tnode *r) {
    struct tnode *node = (struct tnode *) malloc(sizeof(struct tnode));
    node->data = data;
    node->left = l;
    node->right = r;
    return node;
}

// utility function - builds a mirrored tree
// comment any node for non-mirror
Tree* buildTree() {
    Tree *t = (Tree *) malloc(sizeof(Tree));
    t->root = newNode(1, NULL, NULL);
    t->root->left = newNode(2, NULL, NULL);
    t->root->left->left = newNode(3, NULL, NULL);
    t->root->left->right = newNode(4, NULL, NULL);
    t->root->right = newNode(5, NULL, NULL);
    t->root->right->left = newNode(6, NULL, NULL);
    t->root->right->right = newNode(7, NULL, NULL);
    return t;
}

// Compare if left and right subtrees are mirrors
int isMirror(struct tnode *t1, struct tnode *t2) {
    if(t1==NULL || t2==NULL)
        return t1==t2;
    return isMirror(t1->left, t2->left) && isMirror(t1->right, t2->right);
}

int main() {
    Tree *t = buildTree();
    printf("%s\n", isMirror(t->root->left, t->root->right) ? "Mirror" : "Non-Mirror");
    
    return 0;
}

- Anil January 24, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Should the parameters of isMirror to be (t1->left, t2->right) && (t1->right, t2->left)??

- Anonymous January 24, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

are we supposed to write executable code for the phone interview

- Anonymous January 24, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

at Google they usually ask you to code in right in shared Google doc so that interviewer can actually see everything you type immediately. Many companies do that now, not just Google.

- Anonymous January 26, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

(A (B (C,D), E( F,G)))
1. remove root and outer parenthesis, we get B (C,D), E( F,G)
2. locate length/2 to see if it's a ',', return false if not
3. use 2 pointers starts at each parts, ->B and ->E
4. pass if both pointing to characters(need not to be the same) or '(' or ')' or ',', else return false
5. if first got length/2 and second got end, return true
complexity is O(n)

- sunb0w January 25, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple java code:

public static boolean isMirror(BinaryTree tree1, BinaryTree tree2){
boolean isMirror=false;
if(tree1.getRoot()==null&&tree2.getRoot()==null) return true;
if(tree1.getRoot()==null||tree2.getRoot()==null) return false;

if(!tree1.getRoot().equals(tree2.getRoot())) return false;

isMirror=checkMirror(tree1.getRoot(),tree2.getRoot());

return isMirror;
}

private static boolean checkMirror(Node root1, Node root2) {
boolean isMirror=true;
if(root1.left!=null&&!root1.left.equals(root2.right)) return false;
if(root1.right!=null&&!root1.right.equals(root2.left)) return false;

if(root1.left!=null) isMirror=isMirror&&checkMirrorroot1.left,root2.right);
if(root1.right!=null) isMirror=isMirror&&checkMirror(root1.right,root2.left);

return isMirror;
}

- Ankit January 31, 2011 | 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