Amazon Interview Question


Country: India




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

class Tree {

    public static Boolean makeLeafAsNewRoot(Node node, Node leaf){
        if (node == null)
            return false;
        if (node == leaf)
            return true;
        Node newParent;
        if (makeLeafAsNewRoot(node.left, leaf)){
            newParent = node.left;
            node.left = null;
        }
        else if (makeLeafAsNewRoot(node.right, leaf)){
            newParent = node.right;
            node.right = null;
        }
        else{
            return false;
        }
        if (newParent.left == null)
            newParent.left = node;
        else
            newParent.right = node;
        return true;
    }
}

class Node {

    public Node(Node left , Node right){
        this.left = left;
        this.right = right;
    }

    Node left;
    Node right;
}

- GK June 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Forgot to say : have to start this algo from the current root.

- GK June 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This does not work. Can you show the first call. I don't see any mechanism by which the original root's value will get switched to the new root. Your newParent's Parent, does not see newParent, as its child

- cluser721 June 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can't take of my previous comment, but I just overlooked an assignment. It works fine!!

- cluser721 June 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This won't change the root.

- NJC August 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

public boolean dropTree(Node root,Node leafNode){
		
		if(root.getNodeValue().equals(leafNode.getNodeValue())){
			return true;
		}
		boolean isLeafNode = dropTree(root.getLeftNode(), leafNode);
		if(isLeafNode){
			dropLeftTree(root.getLeftNode(),root);
			return isLeafNode;
		}
		isLeafNode = dropTree(root.getRightNode(), leafNode);
		if(isLeafNode){
			dropRightTree(root.getRightNode(),root);
			return isLeafNode;
		}
		return false;
	}
	
	
	private void dropLeftTree(Node leftNode, Node root) {
		leftNode.setRightNode(root);
		root.setLeftNode(root.getRightNode());
		root.setRightNode(null);
	}

	private void dropRightTree(Node rightNode, Node root) {
		rightNode.setLeftNode(root);
		root.setRightNode(root.getLeftNode());
		root.setLeftNode(null);
		
	}

- Vishal June 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I have the same solution! :)

- byteattack June 20, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can you describe what you mean by "fall down" ?

- addy June 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Previous, you have pointers points from the root to the leaf. Now you make the left as the root, then you have to reverse some of the pointers, right? It is the meaning of "fall down"

- ravio June 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

// Take a non-trivial example
//       25
//  12      34
// 1   3   4    5


// if 3 is chosen The answer should be since the links wont change.
//      3
//        12
//       1   25
//              34
//            4   5 
// 3's parent's parent becomes right child of 3's parent and this continues up untill root is reached and then stops.

public class BinaryTree<T>{
    Node<T> root;
    private Class Node<T>{
        Node<T> left;
        Node<T> right;
    }
    
    public BinaryTree<T> tiltUsingLeafNode(BinaryTree<T> tree, T leafNode){
          Node<T> parent = findParent(leafNode);
          
          return reverseParentRelationShip(root, parent);
    }    

}

The solution would be easier if there is a redundant parent link in each node along with left and right links.

- Sandeep June 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Iam making tree structure in such a way where a Node has child as well as parent node associated with it.

reverseNode(Node node , Node initialLeafNode)
{
if(node.getChild() ==null)
{
return;
}
Node currentParent = node.getParent();
if(currentParent!=initialLeafNode)
{
node.setChild(currentParent);
}
currentNode.removeChild(node);
reverseTree(currentParent);
}

- Dhruv June 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my solution:

class TreeNode {
Object data;
TreeNode right;
TreeNode left;

TreeNode(Object data){
this.data = data;
}
}

boolean balance(TreeNode root, TreeNode holdingNode){
if(root.data == holdingNode.data){
return true;
}
if(root.left != null){
boolean dfsBalance = balance(root.left,holdingNode);
if(dfsBalance){
TreeNode left = root.left.right;
root.left.right = root;
root.left = left;
return true;
}
}
if(root.right != null){
boolean dfsBalance = balance(root.right,holdingNode);
if(dfsBalance){
TreeNode right = root.right.left;
root.right.left = root;
root.right = right;
return true;
}
}
return false;
}

- NaN June 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

No need to balance, and no need to keep "Object data" for each node. You can compare two nodes just with == , because in case of objects Java compares links, nor values.

- GK June 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

a
/ \
b c
/ \ / \
d e f g


let's assume holding node: b
in this case the output will be:
b
/ \
d a
/ \
e c
/ \
f g

- NaN June 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Read the task more carefully. It's written that you are holding the leaf node. b is not a leaf node.

- GK June 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

check splay tree..

- Anonymous June 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

- {{{ }}} June 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public Node hangFromALeaf(Node start, Node leaf) {
    if (null == start || null == leaf) {
        return null;
    }
    if (null == leaf.left && start == leaf && null == leaf.right) {
        return leaf;
    }
    Node left = hangFromALeaf(start.left, leaf);
    if (null != left) {
        left.left = start;
        start.right = start.left;
	start.left = null;
        return left;
    }
    Node right = handFromALeaf(start.right, leaf);
    if (null != right) {
        right.right = start;
        start.left = start.right;
	start.right = null;
        return right;
    }
    return null;
}

if leaf comes from the left
we assign its parent to its left,
its parent's right will get the parent's left node (mirroring) and parent's

if leaf comes from right
we do the opposite,

propagate this logic till the root node, at the root node, we just switch the root's left with right (or vice versa depending on the location of the leaf) and we are done.

worst case nlog(n) to go down the tree logn to come up so i guess O(n) = nLog(n)

- byteattack June 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

a
/ \
b c
/ \ / \
d e f g


let's assume holding node: c
in this case the output will be:
c
/ \
a g
/ \
b f
/ \
d e

- NaN June 08, 2014 | 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