## Amazon Interview Question for Software Engineer / Developers

Country: India
Interview Type: In-Person

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

dff

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

You mean BFF? Yes, once tree in UNORDERED then it worth considering the tree as directed (we can traverse it only downwards) graph.

Complexity is linear from the amount of tree nodes.

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

``````struct node{
int data;
struct node* left;
struct node* right;
};

struct node* leastCommonAncestor(struct node* root,struct node* p,struct node* q){

if(root==NULL){
return NULL;  //If no root  leastCommonAncestor is NULL.
}

if(root==p || root==q){
return root; // Check if the current root is equal to any of the desired node.
}else{
struct node* l=leastCommonAncestor(root->left, p, q); // Find LCA in left of the tree
struct node* r=leastCommonAncestor(root->right, p, q); // Find LCA in right of the tree

if(l!=NULL && r!=NULL){
return root;
}else if(l!=NULL && r==NULL){
return l;
}else if(l==NULL && r!=NULL){
return r;
}else{
return NULL;
}
}
}``````

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

http://bestinterviewsquestions.blogspot.in/2013/02/find-least-common-ancestorlca.html

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

This algorithm only finds if two nodes have a LCA, it doesn't return the node which is LCA

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

``````private static void leastCommonAncestor(final TreeNode root, TreeNode n1, TreeNode n2) {
Stack<TreeNode> leftPath = getPath(root, n1);
Stack<TreeNode> rightPath = getPath(root, n2);
while (!leftPath.isEmpty() && !rightPath.isEmpty()) {
int lca = 0;
if ((lca = leftPath.pop().value) == rightPath.pop().value) {
System.out.println(lca);
}
}
}

private static Stack<TreeNode> getPath(TreeNode root, TreeNode n) {
HashMap<TreeNode, Object> visitedMap = new HashMap<>();
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
visitedMap.put(root, null);
while (!stack.isEmpty()) {
TreeNode t = stack.peek();
if (t.value == n.value) {
return stack;
} else if (t.left != null && !visitedMap.containsKey(t.left)) {
visitedMap.put(t.left, null);
stack.push(t.left);
} else if (t.right != null && !visitedMap.containsKey(t.right)) {
visitedMap.put(t.right, null);
stack.push(t.right);
} else {
stack.pop();
}
}
return stack;``````

}

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

Corner case missing .. Question hasn't mentioned it is a binary tree.. Infact the question Says its an UNORDERED tree. So a Child may hv 5 children and another hv only 1... your code fails here

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

struct TreeNode {
TreeNode(int in_value = 0) : parent(0), left(0), right(0), value(in_value)
{
}

TreeNode *parent;
TreeNode *left;
TreeNode *right;
int value;
};

int GetNodeLevel(TreeNode *node)
{
int level = 0;

if ( node ) {
TreeNode *parentNode = node->parent;
while(parentNode) {
++level;
parentNode = parentNode->parent;
}
}

return level;
}

TreeNode* GetLeastCommonAncestor(TreeNode *node1, TreeNode *node2)
{
if ( node1 && node2 ) {
int n1level = GetNodeLevel(node1);
int n2level = GetNodeLevel(node2);

while( n1level!=n2level ) {
if ( n1level>n2level) {
--n1level;
node1 = node1->parent;
}
else {
--n2level;
node2 = node2->parent;
}
}

while ( node1 && node2 && node1!=node2 ) {
node1 = node1->parent;
node2 = node2->parent;
}
}

return (node1 && node1==node2) ? node1 : 0;
}

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

Its Not a Binary tree

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

It doesn't matter. The same approach can be applied to any tree.

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

find node2 in the sub-tree of node1's parent, parent's parent recursively

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

``````public int LCA(int value1,int value2){
Node node1 = find(value1);
Node node2 = find(value2);
int depth1 = depth(value1);
int depth2 = depth(value2);
if(depth1>depth2)
{
while(depth1>depth2)
{
node1 = node1.getParent();
depth1--;
}
}else if(depth2>depth1)
{
while(depth2>depth1)
{
node2 = node2.getParent();
depth2--;
}
}
while(node1 != null|| node2!= null){
if( node1 == node2)
break;
node1 = node1.getParent();
node2 = node2.getParent();

}

return node1.getValue();
}``````

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

A single node can have multiple children.

The idea is to find two paths from the root to the two nodes separately and then find the least common nodes from the two lists.
One possible downside is that we go through the nodes twice for each query node we consider.
However, the space and time [O(number of nodes) both for time and space] complexity remains the same.

Feel free to point out any flaws. :-)

``````import java.util.ArrayList;
import java.util.List;
import java.util.Iterator;

class Node {
Node children[];
int value;
}

// The recursive method
private boolean findTrail(Node curr, Node node, List trail){
if(curr == node ){
return true;
}

boolean found = false;
for(Node child : curr.children){
found = findTrail(child, node, trail);
if(found){
return true;
}
}
return false;
}
//.................

// Method using the recursive method.
public Node findLeastComAns(Node root, Node A, Node B){
if(root == null || A == null || B == null){
return null;
}

List list1 = new ArrayList();
List list2 = new ArrayList();

boolean found = findTrail(root, A, list1);
if(!found){
return null;
}
found = findTrail(root, B, list2);
if(!found){
return null;
}

Iterator<Node> itr1 = list1.listIterator();
Iterator<Node> itr2 = list2.listIterator();
Node common;
Node least = null;
while(itr1.hasNext()&&itr2.hasNext()){
common = itr1.next();
if(common == itr2.next()){
if(least == null){
least = common;
}
else if(least.value > common.value){
least = common;
}
}
}
return least;
}``````

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

pseudo-code:

int traverse(node n) {
if(n is either of the given nodes) {
return 1;
}
if (n is leaf node) {
return 0;
}
else {
value = 0;
foreach (node m : children of n) {
value += traverse(m);
if (value>1) {
node n is the least parent;
exit; // r return 0 if you cannot exit

}

}
}

}

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

algo:

1# find path to both of the nodes from root lets say pPath and qPath.
2# compare paths till the both start getting on different way. the previous node where the are departing will be least common ancestor.

Note: space complexity will be high but as i know time complexity will be maximum O(n+n+n) i.e. O(n)

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.