Amazon Interview Question for SDE-2s


Country: India




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

boolean distance(Node root, Integer height, int n1, int n2) {
                
                if(null == root || n1 == n2) {
                        height = 0;
                        return false;
                }
                
                if(root.data == n1 || root.data == n2) {
                        height = 0;
                        return true;
                }
                
                Integer leftHeight = 0, rightHeight = 0;
                boolean left = distance(root.left, leftHeight, n1, n2);
                boolean right = distance(root.right, rightHeight, n1, n2);
                
                if(left && right) {
                        System.out.println("Diameter "+leftHeight+rightHeight+1);
                        return true;
                } else if(left || right) {
                        height = (left ? leftHeight+1 : 0);
                        height = (right ? rightHeight +1 : 0);
                        return true;
                } 
                
                return false;
        }

- Kapil July 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Distance between two nodes in a binary tree = distance between root and node 1 + distance between root and node 2 - 2 * distance between root and lowest common ancestor of the two nodes.

- sid July 31, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

same as lca

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

1) if NULL || NULL : return 0
2) if node1 == node2 :return 0
3) Check subtree of every single node BFS, maybe node located in subtree
4) Nodes located on different sides of root and use bfs(root->left) + bfs(root->right)

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

Or
find lowestCommonAcessor

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

he he he

- Anonymous July 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class BinTreeDistance {
	private static class Node {

		private int data; 
		Node left = null;
		Node right = null;

		public static class DataCount {
			public int cnt = 0;
		}
		public Node (int level, DataCount dataCnt) {
			if (level != 0) {
				this.left  = new Node(level - 1, dataCnt);
				this.data = ++dataCnt.cnt;
				this.right = new Node(level - 1, dataCnt);
			}
			else
				this.data = ++dataCnt.cnt;
		}
	}

	private Node tree = new Node(5, new Node.DataCount());

	private int nodeDistance(Node root, int data) {
		int x = -1;
		if (root == null) {
			return -1;
		}
		if (root.data == data || (x = nodeDistance(root.left, data)) > -1 || (x = nodeDistance(root.right, data)) > -1) {
			return x + 1;
		}
		return -1;
	}

	private Node nodeLca(Node root, int left, int right) {
		if (root == null) {
			return null;
		}
		if (root.data == left || root.data == right)
			return root;
		Node lNode = nodeLca(root.left, left, right);
		Node rNode = nodeLca(root.right, left, right);

		if (lNode != null && rNode != null)
			return root;
		
		if (lNode != null)
			return lNode;
		
		if (rNode != null)
			return rNode;

		return null;
	}

	private int bstNodeDistance(Node root, int data) {
		int x = -1;
		if (root == null) {
			return -1;
		}
		if (root.data == data)
			return x +1;
		
		if (root.data > data && (x = bstNodeDistance(root.left, data)) > -1){
			return x + 1;
		}
		if (root.data < data && (x = bstNodeDistance(root.right, data)) > -1) {
			return x + 1;
		}
		return -1;
	}

	private Node bstNodeLca(Node root, int left, int right) {
		if (root == null) {
			return null;
		}
		if (root.data > left && root.data > right)
			return bstNodeLca(root.left, left, right);
		
		if (root.data < left && root.data < right)
			return bstNodeLca(root.right, left, right);
			
		return root;

	}
	
	public static void main(String[] args) {
		BinTreeDistance btd = new BinTreeDistance();
		//btd.tree.printTree();
		
		Node nLca = btd.bstNodeLca(btd.tree, 4, 45);
		int ld = btd.bstNodeDistance(nLca, 4);
		int rd = btd.bstNodeDistance(nLca, 45);
		
		System.out.println();
		System.out.println(ld + rd );
		
		nLca = btd.nodeLca(btd.tree, 4, 45);
		ld = btd.nodeDistance(nLca, 4);
		rd = btd.nodeDistance(nLca, 45);
		
		System.out.println(ld + rd );
		
	}

}

- vzyarko July 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

n xz jfmnlkmlke ckemlkemdlkdm

- sid July 31, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

An improved version of Kapil's answer. In their code, it is missed the case when n1 is subnode of n2

package com.careercup.ruslanbes.distance;

public class Main {
    protected static int distance;

    public static int distance(Node root, int n1, int n2) {
        distance = 0;
        if (n1 == n2) {
            return 0;
        }

        findNodes(root, n1, n2);
        return distance;
    }

    protected static int findNodes(Node root, int n1, int n2) {
        if (root == null) {
            return 0;
        }

        boolean isHere = root.data == n1 || root.data == n2;
        int inLeft = findNodes(root.left, n1, n2);
        int inRight = findNodes(root.right, n1, n2);

        if (inLeft > 0 && inRight > 0) {
            distance = inLeft + inRight;
            return 0;
        } else if (inLeft > 0) {
            if (isHere) {
                distance = inLeft;
                return 0;
            }
            return inLeft+1;
        } else if (inRight > 0) {
            if (isHere) {
                distance = inRight;
                return 0;
            }
            return inRight+1;
        } else if (isHere) {
            return 1;
        }
        return 0;
    }
}

Test Set:

package com.careercup.ruslanbes.distance;

import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;

class MainTest {


    @Test
    void distance1() {
        Node root = new Node(0);
        root.putLeft(101);
        root.putRight(100);

        assertEquals(2, Main.distance(root,100, 101));
        assertEquals(2, Main.distance(root,101, 100));
        assertEquals(1, Main.distance(root,0, 100));
        assertEquals(1, Main.distance(root,0, 101));
    }

    @Test
    void distance2() {
        Node root = new Node(0);
        Node left = root.putLeft(3);
        left.putLeft(4)
                .putLeft(100);
        left.putRight(5);

        root.putRight(6)
                .putRight(101);
        assertEquals(5, Main.distance(root,100, 101));
        assertEquals(3, Main.distance(root,100, 5));
        assertEquals(3, Main.distance(root,101, 3));
        assertEquals(4, Main.distance(root,101, 4));
        assertEquals(3, Main.distance(root,100, 0));
    }

}

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

public class Distance
{
public int distance;
public bool xExists;
public bool yExists;

public Distance(int d, bool bx, bool by)
{
this.distance = d;
this.xExists = bx;
this.yExists = by;
}
}

public Distance FindRootDistance(TreeNode root, int x, int y)
{
if (root == null)
return new Distance(0, false, false);
if (x == y)
return new Distance(0, true, true);

Distance LeftDistance = FindRootDistance(root.left, x, y);
Distance RightDistance = FindRootDistance(root.right, x, y);

if ((LeftDistance.xExists && RightDistance.yExists) || (LeftDistance.xExists && RightDistance.yExists))
return new Distance(LeftDistance.distance + RightDistance.distance, true, true);
else if (LeftDistance.xExists && LeftDistance.yExists)
return LeftDistance;
else if (RightDistance.xExists && LeftDistance.yExists)
return RightDistance;
else if (LeftDistance.xExists && root.val == y)
{
LeftDistance.yExists = true;
return LeftDistance;
}
else if (LeftDistance.yExists && root.val == x)
{
LeftDistance.xExists = true;
return LeftDistance;
}
else if (RightDistance.xExists && root.val == y)
{
RightDistance.yExists = true;
return RightDistance;
}
else if (RightDistance.yExists && root.val == x)
{
RightDistance.xExists = true;
return RightDistance;
}
else if (LeftDistance.xExists || LeftDistance.yExists)
{
LeftDistance.distance += 1;
return LeftDistance;
}
else if (RightDistance.xExists || RightDistance.yExists)
{
RightDistance.distance += 1;
return RightDistance;
}
else if (root.val == x)
return new Distance(1, true, false);
else if (root.val == y)
return new Distance(1, false, true);
else
{
return new Distance(0, false, false);
}
}

- Anonymous February 01, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Distance
{
public int distance;
public bool xExists;
public bool yExists;

public Distance(int d, bool bx, bool by)
{
this.distance = d;
this.xExists = bx;
this.yExists = by;
}
}

public Distance FindRootDistance(TreeNode root, int x, int y)
{
if (root == null)
return new Distance(0, false, false);
if (x == y)
return new Distance(0, true, true);

Distance LeftDistance = FindRootDistance(root.left, x, y);
Distance RightDistance = FindRootDistance(root.right, x, y);

if ((LeftDistance.xExists && RightDistance.yExists) || (LeftDistance.xExists && RightDistance.yExists))
return new Distance(LeftDistance.distance + RightDistance.distance, true, true);
else if (LeftDistance.xExists && LeftDistance.yExists)
return LeftDistance;
else if (RightDistance.xExists && LeftDistance.yExists)
return RightDistance;
else if (LeftDistance.xExists && root.val == y)
{
LeftDistance.yExists = true;
return LeftDistance;
}
else if (LeftDistance.yExists && root.val == x)
{
LeftDistance.xExists = true;
return LeftDistance;
}
else if (RightDistance.xExists && root.val == y)
{
RightDistance.yExists = true;
return RightDistance;
}
else if (RightDistance.yExists && root.val == x)
{
RightDistance.xExists = true;
return RightDistance;
}
else if (LeftDistance.xExists || LeftDistance.yExists)
{
LeftDistance.distance += 1;
return LeftDistance;
}
else if (RightDistance.xExists || RightDistance.yExists)
{
RightDistance.distance += 1;
return RightDistance;
}
else if (root.val == x)
return new Distance(1, true, false);
else if (root.val == y)
return new Distance(1, false, true);
else
{
return new Distance(0, false, false);
}
}

- Havva February 01, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Distance
        {
            public int distance;
            public bool xExists;
            public bool yExists;

            public Distance(int d, bool bx, bool by)
            {
                this.distance = d;
                this.xExists = bx;
                this.yExists = by;
            }
        }

        public Distance FindRootDistance(TreeNode root, int x, int y)
        {
            if (root == null)
                return new Distance(0, false, false);
            if (x == y)
                return new Distance(0, true, true);

            Distance LeftDistance = FindRootDistance(root.left, x, y);
            Distance RightDistance = FindRootDistance(root.right, x, y);

            if ((LeftDistance.xExists && RightDistance.yExists) || (LeftDistance.xExists && RightDistance.yExists))
                return new Distance(LeftDistance.distance + RightDistance.distance, true, true);
            else if (LeftDistance.xExists && LeftDistance.yExists)
                return LeftDistance;
            else if (RightDistance.xExists && LeftDistance.yExists)
                return RightDistance;
            else if (LeftDistance.xExists && root.val == y)
            {
                LeftDistance.yExists = true;
                return LeftDistance;
            }
            else if (LeftDistance.yExists && root.val == x)
            {
                LeftDistance.xExists = true;
                return LeftDistance;
            }
            else if (RightDistance.xExists && root.val == y)
            {
                RightDistance.yExists = true;
                return RightDistance;
            }
            else if (RightDistance.yExists && root.val == x)
            {
                RightDistance.xExists = true;
                return RightDistance;
            }
            else if (LeftDistance.xExists || LeftDistance.yExists)
            {
                LeftDistance.distance += 1;
                return LeftDistance;
            }
            else if (RightDistance.xExists || RightDistance.yExists)
            {
                RightDistance.distance += 1;
                return RightDistance;
            }
            else if (root.val == x)
                return new Distance(1, true, false);
            else if (root.val == y)
                return new Distance(1, false, true);
            else
            {
                return new Distance(0, false, false);
            }

}

- Havva February 01, 2020 | 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