Amazon Interview Question Software Engineer / Developers

  • amazon-interview-questions
    0
    of 0 votes
    15
    Answers

    Two trees are given. Write a function to check if both of these trees are isotropic. Isotropic trees are those, when flipping few of the child nodes of a tree make both the trees equal. For e.g
    .......1......
    ...2.......3.
    .........4...5

    ......1.......
    ...3.......2..
    .4....5.......

    both of these are isotropic. If we flip the node with value 2 and 3 in the second tree then both trees will be equal.

    - upgrade.server on June 22, 2012 in India Report Duplicate | Flag
    Amazon Software Engineer / Developer Algorithm

Country: India


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

bool isotropic(root *t1,root *t2)
{
	if(t1==Null&&t2==NULL)
	return true;
	
	if(t1==Null||t2==nULL)
	return false;
	
	if(t1->data!=t2->data)
	return false;

	if(t1->left==t2->left)
	{
		return isotropic(t1->left,t2->left)&&(t1->right,t2->right);
	}
	else if(t1->left==t2->right)
	{
		return isotropic(t1->left,t2->right)&&(t1->right,t2->left);
	}
	else
	return false;
}

- guneesh on June 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

clear and precise but lot of extra memory will be used. call stack though you are not using explicitly but your program do, but liked the solution had a similar approach but explicitly using stack.

- murlikrishna.b on July 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

t1->left.Data==t2->left.Data

and else if(t1->left.Data==t2->right.Data)

- murlikrishna.b on July 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Assuming your code is in C, please elaborate on how pointer comparison works. For instance

t1->left == t2->left

. I guess you meant to do

t1->left->data == t2->left->data

. But in that case we would have to first check if

t1->left and t2->left

are not null.

- guessWho on July 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
4
of 4 vote

I may or may not be understanding the definition of 'isotropic' correctly, but if I understand correctly, I think two trees will be isotropic iff each node has the same parent in one tree as in the other tree. So we'd just have to check that every node has the same parent. As we read through a tree we could simply record in an array the parent node of each value (or in a HashMap depending on how the info is given) and then read through the second tree and check that the info matches up.

- eugene.yarovoi on June 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Eugene,

Your analysis will hold true as long as there is no duplicate data in the tree. Since this is a binary tree, hence duplicates might exist, and they will exist with different parents.

@upgrade_server
Can you please tell if there is any restriction of data in the question?

- Learner on June 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I got the impression nodes would actually be labeled 1 through N. I admit the question was unclear.

- eugene.yarovoi on June 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

isIsotropic(root1,root2)
{
	if(!root1 && !root2)
		return true;
	if(!root1 || !root2)
		return false;
	return root1->data==root2->data && ( (isIsotropic(root1->left,root2->left) && isIsotropic(root1->right,root2->right)) || (isIsotropic(root1->left,root2->right) && isIsotropic(root1->right,root2->left)) )
}

- Aashish on June 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Like

- jiangok2006 on June 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This looks correct !

- Rohit Kumar on November 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

If there are no repeated nodes and nodes in the tree has a link to the parent the Eugene solution is just perfect (+1 from me).
Still if the tree has no link to the parent or the tree can have repeated nodes we have to traverse all the possible combinations. Here is the java code for that

public boolean isIsotropicBT(TreeNode t1, TreeNode t2) {
  boolean result = false;
  if (t1 ==null && t2 == null)
   result = true;
  else if (t1 != null && t2 != null && t1.data == t2.data) {
   result = isIsotropicBT(t1.left, t2.left) && isIsotropicBT(t1.right, t2.right);
   result |= isIsotropicBT(t1.left, t2.right) && isIsotropicBT(t1.right, t2.left);
  } 
 
  return result;
 }

- GKalchev on June 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Consider each tree as logically composed of

unordered list of leaf nodes + subtree without leaf nodes.

If both properties are identical, then trees are isotropic.

Would need additional space equal to the number of leaf nodes.

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

/ignore ;) Isotropic needs to be defined more accurately

- ViX on July 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

If the nodes are comparable(have some ordering property)

then we can use 'ViX' traversal where we visit child nodes in ascending/descending order.

Isotropic trees should result in identical nodes at each step.

(This is if I finally understand isotropic trees))

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

ViX traversal for

0
|
___
| |
A B

would be OAB if A>B and OBA if B>A

- ViX on July 03, 2012 | Flag


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