## Amazon Interview Question for SDE-2s

• 3

Country: United States
Interview Type: In-Person

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

Assuming there aren't duplicate values or the two integers provided don't repeat,

Carry out a DFS over the tree, and
- when you find the one of the two values, store the stack.
- continue the DFS search
- when you find the next value, store the stack.
- terminate the search.
- Reverse the two stacks
- keep popping both the stacks until both of them have identical nodes.
- stop when the nodes in the stack differ.

The recent most popped node or nil is the answer.

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

``````// ZoomBA uLanguage. Simple.
paths = [ '', '' ]
def find_paths( key1, key2,  node , path  ){
if ( !empty(path.0) && !empty(path.1) ) return
if ( node == null ) {
if ( path #\$ key1 ){ paths.0 = path }
if ( path #\$ key2 ){ paths.1 = path }
return
}
find_paths ( node.left, path + '/' + node.key )
find_paths ( node.right, path + '/' + node.key )
}
// find paths
find_paths( key1, key2, root, '' )
// split and now match
paths.0 = paths.0.split('/')
paths.1 = paths.1.split('/')
#(s,l) = minmax ( paths ) :: { #|\$.left| < #|\$.right| }
inx = index ( [ #|s|-1:-1 ] ) :: {
paths[0][\$.item] != paths[1][\$.item]
}
println( s[0][inx] )``````

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

Supposing the two integer values are not repeated:

``````private int num1, num2;
private Integer ancestor;

public int leastCommonAncestor(Node root, int num1, int num2){
this.num1 = num1;
this.num2 = num2;

leastCommonAncestor(root);

return ancestor;

}

private Integer leastCommonAncestor(Node node){
if(node == null)
return null;

//Check if the ancestor is behind this node
Integer left = leastCommonAncestor(node.left);
if(ancestor != null)
return null;
Integer right = leastCommonAncestor(node.left);
if(ancestor != null)
return null;

//Chech if the ancestor is this node
if(left != null && right != null){
ancestor = node.val;
return  null;
}

//Check if the ancestor is this node, being also one of the numbers
boolean isNum = (node.val == num1) || (node.val == num2);

if((left != null || right != null) && isNum))
ancestor = node.val;
return null;
}

//Return the num
if(left != null)
return left;
if(right != null)
return right;

if(isNum)
return node.val;

return null;

}``````

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

``````import java.util.LinkedList;
public class LCA{

public class Node {
int info;
Node left;
Node right;

public Node(int info) {
this.info = info;
}
}

Node lca;
Node root;

public void build() {
root = new Node(1);
Node two = new Node(2);
Node three = new Node(3);
root.left = two;
root.right = three;

Node four = new Node(4);
Node five = new Node(5);
Node six = new Node(6);
Node seven = new Node(7);

two.left = four;
two.right = five;
three.left = six;
three.right = seven;

four.left = new Node(9);
five.right = new Node(10);

seven.right = new Node(11);
}

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

if(root.info == n1 || root.info == n2) {
return 1;
}

int l = lca(root.left, n1, n2);
int r = lca(root.right, n1, n2);

if(l == 1 && r == 1) {
this.lca = root;
return 2;
}

return l+r;
}

public void bfs() {
doBfs(q);
}

public void doBfs(LinkedList<Node> q) {
int len = q.size();

if(len == 0) {
return;
}

for(int i=0;i<len;i++) {
Node t = q.removeFirst();
System.out.println(t.info + " ");
if(t.left != null) {
}

if(t.right != null) {
}
}

System.out.println();
doBfs(q);
}

public static void main(String []args){
LCA test = new LCA();
test.build();
test.bfs();
test.lca(test.root, 5,4);
System.out.println(test.lca.info);
}``````

}

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

This is an Objective-C solution using recursion

``````-(TreeNode *)getLowestCommonAncestor:(TreeNode *)root andNode1:(TreeNode *)n1 andNode2:(TreeNode *)n2{

if(root == nil){
return nil;
}

if(root == n1 || root == n2){
return root;
}

TreeNode *leftNode = [self getLowestCommonAncestor:root.left andNode1:n1 andNode2:n2];

TreeNode *rigthNode = [self getLowestCommonAncestor:root.rigth andNode1:n1 andNode2:n2];

if(leftNode != nil && rigthNode != nil){

return root;
}
else if(leftNode == nil && rigthNode == nil){

return nil;
}

return leftNode != nil ? leftNode : rigthNode;

}``````

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

public void leastCommonPa(Node root, int n1, int n2){
HashMap<Integer, Integer> pa = new HashMap<>();
ArrayList<Node> queue = new ArrayList<>();
while(!queue.isEmpty()){
Node temp = queue.remove(0);
if(temp.left != null){
pa.put(temp.left.value, temp.value);
}
if(temp.right != null){
pa.put(temp.right.value, temp.value);
}
}
while(pa.get(n1) != pa.get(n2)){
System.out.println(pa.get(n1)+" "+pa.get(n2));
if(n1 == root.value || n2 == root.value)
break;
n1 = pa.get(n1);
n2 = pa.get(n2);
}
if(n1 == root.value || n2 == root.value)
System.out.println(root.value);
else
System.out.println(pa.get(n1));
}

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

``````using System.Collections.Generic;

public class Test
{
static int lca = Int32.MinValue;
class Node
{
public Node(int value, Node left, Node right)
{
Left = left;
Right = right;
Value = value;
}

public readonly Node Left;
public readonly Node Right;
public readonly int Value;
}
public static void Main()
{
// your code goes here
var root = new Node(1, new Node(2, new Node(4, null, null), new Node(5, null, null)),
new Node(3, new Node(6, null, null), new Node(7, null, null)));
var itemsFound = Find (root , 6, 7);
if(itemsFound == 2)
{
Console.Write(string.Format("LCA : {0}", lca));
}
else
{
Console.Write("NO LCA");
}

}

private static int Find(Node root, int val1, int val2)
{
if(root == null) return 0;
if(root.Value == val1 || root.Value == val2)
{
return 1;
}

int result  = Find(root.Left, val1, val2) + Find(root.Right, val1, val2);
if(result == 2 && lca == Int32.MinValue)
{
lca = root.Value;
}
return result;
}
}``````

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

``````public TreeNode getCommonAnchedtor(TreeNode n1, TreeNode n2){
if (n1 == null || n2 == null || n1.parent == null || n2.parent == null) return null;
boolean leftNode = true;
if (n1.parent.right == n1) leftNode = false;

TreeNode p = n1.parent;
while (p.parent != null){
if (leftNode) if (includedIn(p.parent.right,n2)) return p.parent;
else if (includedIn(p.parent.left,n2)) return p.parent;
p = p.parent;
}

return null;
}

public boolean includedIn(TreeNode n, TreeNode nSearch){
if (n.left != null && includedIn(n.left,nSearch)) return true;
if (n.right != null && includedIn(n.right,nSearch)) return true;
if (n == nSearch) return true;
return false;
}``````

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

Least common ancestor node will have the value within <a, b> range.
If its value is below this range, the common ancestor is in the right
sub-tree. If it is above the range - look in the left sub-tree.

``````Node* FindCommonAncestor(Node* n, int a, int b)
{
if (a > b)
{
int tmp = a;
a = b;
b = a;
}
while (n != 0)
{
if (n->val < a)
n = n->right;
else if (n->val > b)
n = n->left;
else
break;
}
return n;
}``````

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

This can be achieved in a single pass, without actually searching for the element.
We will use a simple property of a binary tree. At a particular node all elements at left will be smaller than the node and all elements at right will be bigger than the node. So this node will be LCA fo all combination of any node from left subtree and right subtree.
if both the values are less then traverse left if both values are greater then traverse right.
The solution proposed above is good but misses the case whe one of the two nodes is the LCA , so fixing the code

``````Node* FindCommonAncestor(Node* n, int a, int b)
{
if (a > b)
{
int tmp = a;
a = b;
b = a;
}
while (n != 0)
{
if (n->val == a)
break;
if (n->val < a)
n = n->right;
else if (n->val > b)
n = n->left;
else
break;
}
return n;
}``````

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

``````public BinaryTree F(BinaryTree root, int v1, int v2) {
if (root == null)
return null;
if (root.data == v1 || root.data == v2)
return root;

var lr = F(root.left, v1, v2);
var rr = F(root.right, v1, v2);

if (lr != null && rr != null &&
(lr.data == v1 || lr.data == v2) &&
(rr.data == v1 || rr.data == v2) &&
lr.data != rr.data)
return root;
if (lr != null)
return lr;
else
return rr;``````

}

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

``````public static BinaryTree F(BinaryTree root, int v1, int v2) {
if (root == null)
return null;
if (root.data == v1 || root.data == v2)
return root;

var lr = F(root.left, v1, v2);
var rr = F(root.right, v1, v2);

if (lr != null && rr != null &&
(lr.data == v1 || lr.data == v2) &&
(rr.data == v1 || rr.data == v2) &&
lr.data != rr.data)
return root;
if (lr != null)
return lr;
else
return rr;
}``````

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.

### 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.