Amazon Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
Step1: has to be 'find the lowest common ancestor'
Step2: Find the number of hops to reach each node from lowest common ancestor, by doing binary search individually on nodes. and then add both numbers of hops.
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
//Defining Node
struct node{
int data;
struct node *left;
struct node *right;
};
//Function to insert a node in a BST
struct node* insert(struct node* node, int data)
{
if(node == NULL)
{
struct node* newnode = (struct node*) malloc (sizeof(struct node));
newnode->data = data;
newnode->left = NULL;
newnode->right = NULL;
node = newnode;
}
else
{
if(data <= node->data)
{
node->left = insert(node->left, data);
}
else
{
node->right = insert(node->right, data);
}
}
return (node);
}
//Finding common ancestor
struct node* commonancestor(struct node* root, int node1, int node2)
{
if(root == NULL) return NULL;
if(root->data < node1 && root->data < node2)
{
return commonancestor(root->right, node1, node2);
}
else if(root->data > node1 && root->data > node2)
{
return commonancestor(root->left, node1, node2);
}
else
{
return root;
}
}
//Distance between two given nodes
void distance(struct node* root, int node1, int node2)
{
if(root == NULL) return;
struct node* leftpath = root;
struct node* rightpath = root;
int countleft = 0, countright = 0;
while(leftpath != NULL)
{
if(leftpath->data > node1)
{
leftpath = leftpath->left;
countleft++;
}
else if(leftpath->data < node1)
{
leftpath = leftpath->right;
countleft++;
}
else
{
break;
}
}
while(rightpath != NULL)
{
if(rightpath->data > node2)
{
rightpath = rightpath->left;
countright++;
}
else if(rightpath->data < node2)
{
rightpath = rightpath->right;
countright++;
}
else
{
break;
}
}
printf("Shortest path between %d and %d is : %d", node1, node2, countleft+countright);
}
//Driver Function
int main(void)
{
struct node* root = NULL;
struct node* common = NULL;
root = insert(root, 9);
root = insert(root, 6);
root = insert(root, 15);
root = insert(root, 8);
root = insert(root, 4);
root = insert(root, 5);
root = insert(root, 1);
root = insert(root, 7);
root = insert(root, 13);
root = insert(root, 17);
root = insert(root, 11);
root = insert(root, 14);
root = insert(root, 19);
common = commonancestor(root, 2,9);
distance(common, 2, 9);
getch();
}
Traverse the BST in following way starting from ROOT:
If node->value lies between the two numbers given, then node is the least common ancestor
If node->value > both the numbers, then node=node->left.
If node->value <both the numbers, then node=node->right
Once the common ancestor is found, find the path to both the nodes from this ancestor node creating two linked lists and then finally joining them.
class Node
{
int item;
Node left;
Node right;
Node(int item , Node left, Node right )
{
this.item=item;
this.left=left;
this.right=right;
}
}
public class Finding_distance_in_a_BST {
public static void main(String[] args) {
Node root=new Node(5,null,null);
root.left=new Node(3,null,null);
root.right=new Node(8, null,null);
root.left.left=new Node(2,null,null);
root.left.right=new Node(4,null,null);
root.right.left=new Node(7,null,null);
root.right.right=new Node(9,null,null);
System.out.println( Tree.distance_between_node(root, root.left, root.right.left));
}
}
class Tree
{
static int depth(Node root,Node x)
{
if(root==null)
return -1;
if(x.item==root.item)
return 0;
else if(x.item<root.item)
{
return depth(root.left,x)+1;
}
else
return depth(root.right,x)+1;
}
static int distance_between_node(Node root,Node left,Node right)
{int distance;
if(left==right)
return 0;
else
if(left==root)
return depth(root,right);
else
if(right==root)
return depth(root,left);
Node greater=left.item>right.item?left:right;
Node smaller=left.item<right.item?left:right;
if(root.item>smaller.item&&root.item<greater.item)
{
distance=depth(root,left)+depth(root,right);
return distance;
}
else
return depth(root,smaller)-depth(root,greater);
}
}
The program take 0(h) where h is the height of the BST.
int Distance(node *tree, int data)
{
// Keep in mind this is bst
if(tree == null) return -infinity;
if(tree->data == data) return 1;
if(tree->data > data)
{
return(1+Distance(tree->left,data));
}
else
{
return(1+Distance(tree->right,data));
}
}
int ShortestDistanceBetweenNodes(node *tree, node *node1, node *node2)
{
if(tree == null) return -1;
else if (node1 == null || node2 == null) return -1;
else if (node1->data == node2->data) return 0;
int min = Min(node1->data, node2->data);
int max = Max(node1->data, node2->data);
if(node->data > max)
{
return(ShortestDistanceBetweenNodes(node->left, node1, node2));
}
else if (node->data < min)
{
return(ShortestDistanceBetweenNodes(node->right, node1, node2));
}
else
{
if(node->data == min)
{
return(Distance(node->right,max));
}
else if (node->data == max)
{
return(Distance(node->left, min));
}
else
{
return(Distance(node->left,min) + Distance(node->right,max));
}
}
}
int dis(node *n, int a){
int c = 0;
while (n){
if (n->value == a){
return c;
}else if (n->value > a){
n = n->left;
} else {
n = n->right;
}
++c;
}
return -0xffff;
}
int shortestdistance(node *n, int a, int b){
if (NULL == n){
return -1;
} else if (a == b) {
return 0;
} else if (n->value > a && n->value > b){
return shortestdistance(n->left, a, b);
} else if (n->value < a && n->value < b){
return shortestdistance(n->right, a, b);
}
return dis(n, a) + dis(n, b);
}
You can write a post-order traversal algo such that when a node is traversed, all parents will be in the stack.
For each node inserted, insert a flag also. This flag will be initially zero.
When the first node to be found is traversed, set StackLengthWhenFirstNodeIsFound to length of stack.
Continue traversing but now for all nodes pushed into the stack, set the flag as 1 not a 0.
When the second node to be found is traversed, stop traversing. find path length as:
pathlength = StackLengthWhenFirstNodeIsFound;
pathlength -= stack.NumberofNodesWithFlagSetTo(0);
pathlength += stack.NumberofNodesWithFlagSetTo(1);
f1, f2 // nodes to be found
p = root;
visited = NULL;
bool found = false;
int StackLengthWhenFirstNodeIsFound = -1;
NODE* foundFirst = NULL;
int pathlength;
do
{
while( p != NULL )
{
if( p == f1 )
f1 = NULL;
if( StackLengthWhenFirstNodeIsFound == -1 )
StackLengthWhenFirstNodeIsFound = stack.length();
foundFirst = p1;
if( p == f2 )
// do the same for f2
if( StackLengthWhenFirstNodeIsFound != -1 && p != foundFirst )
found = true;
break;
stack.push(p,StackLengthWhenFirstNodeIsFound==-1?0:1);
p=p->left;
}
if( found )
pathlength = StackLengthWhenFirstNodeIsFound;
pathlength -= stack.NumberofNodesWithFlagSetTo(0);
pathlength += stack.NumberofNodesWithFlagSetTo(1);
return pathlength;
while( !empty.stack )
{
temp = stack.top();
if( temp->right == NULL || visited == temp->right )
visit(temp);
visited = temp;
stack.pop();
else
p = p->right;
break;
}
}while( p != NULL || !stack.empty() );
treeNode* LowestCommonAncestor(treeNode *node,int val1,int val2)
{
if(!node)
return NULL ;
else if((val1<(node->data))&& (val2>(node->data)))
{
return node;
}
else if((val1>(node->data))&& (val2>(node->data)))
{
return(LowestCommonAncestor(node->right,val1,val2));
}
else if((val1<(node->data))&& (val2<(node->data)))
{
return (LowestCommonAncestor(node->left,val1,val2));
}
}
int hightCount(treeNode *node,int val)
{
int count;
if((!node)||(val==(node->data)))
return 0;
else if(val<(node->data))
{
count=(hightCount(node->left,val))+1;
}
else if(val>(node->data))
{
count=(hightCount(node->right,val))+1;
}
return count;
}
int findShortestLength(treeNode *node,int val1,int val2)
{
int leftLength=0,rightLength=0;
treeNode *LCA=LowestCommonAncestor(node,val1,val2);
leftLength=hightCount(LCA->left,val1)+1;
rightLength=hightCount(LCA->right,val2)+1;
return (leftLength+rightLength);
}
Here val1<va2 and
[1].treeNode* LowestCommonAncestor(treeNode *node,int val1,int val2);
[2]int hightCount(treeNode *node,int val);
[3]int findShortestLength(treeNode *node,int val1,int val2);
here we find the lowest common Ancestor and the find the hight of the left child found and then hight of right child found.After that we sum the hights.
Accept list of numbers as input from user. Accept the values to calculate the distance between. Then create BST. Find path from root to node1 and root to node2. Find the LCA by comparing the paths. Add the difference between the LCA and length of each path to calculate distance. Returns -1 if one of the values is missing in the tree
(function(){
let values = prompt("Enter unique integers for bin tree");
let nodes = prompt("Enter nodes to calculate distance");
let rootNode = createTree(values);
alert(inOrder(rootNode,""));
let nodeArr = nodes.split(",");
var p1 = getPath(rootNode,parseInt(nodeArr[0]),"");
var p2 = getPath(rootNode,parseInt(nodeArr[1]),"");
if(p1[0]==-1 || p2[0] == -1){
alert(-1);
return;
}
alert(p1+" "+p2);
let exit = false;i=0,dist=0;
while(exit==false){
if(p1[i]!=p2[i]){
dist=(p1.length-i)+(p2.length-i);
exit=true;
}else if(i==p1.length-1){
dist = (p2.length-1)-i;
exit=true;
}else if(i==p2.length-1){
dist = (p1.length-1)-i;
exit=true;
}
i++;
}
alert(dist);
function inOrder(currNode,path){
if(currNode==null)
return path;
path=inOrder(currNode.left,path);
path+=currNode.val+",";
path=inOrder(currNode.right,path);
return path;
}
function getPath(currRoot,theVal,path){
if(!currRoot || currRoot==null)
return [-1];
if(!path)
path=[];
path.push(currRoot.val);
if(currRoot.val == theVal)
return path;
else if(currRoot.val > theVal)
return getPath(currRoot.left,theVal,path);
else
return getPath(currRoot.right,theVal,path);
}
function createTree(values){
var vals = values.split(",");
let rootNode;
vals.forEach(function(v) {
v = parseInt(v);
if(!rootNode)
rootNode = {left:null,right:null,val:v};
else
insertNode(rootNode,{left:null,right:null,val:v});
}, this);
return rootNode;
}
function insertNode(currRoot,currNode){
if(currRoot.val>currNode.val){
if(currRoot.left==null)
currRoot.left=currNode;
else
insertNode(currRoot.left,currNode);
}else{
if(currRoot.right==null)
currRoot.right=currNode;
else
insertNode(currRoot.right,currNode);
}
}
})();
Accept list of numbers as input from user. Accept the values to calculate the distance between. Then create BST. Find path from root to node1 and root to node2. Find the LCA by comparing the paths. Add the difference between the LCA and length of each path to calculate distance. Returns -1 if one of the values is missing in the tree
(function(){
let values = prompt("Enter unique integers for bin tree");
let nodes = prompt("Enter nodes to calculate distance");
let rootNode = createTree(values);
alert(inOrder(rootNode,""));
let nodeArr = nodes.split(",");
var p1 = getPath(rootNode,parseInt(nodeArr[0]),"");
var p2 = getPath(rootNode,parseInt(nodeArr[1]),"");
if(p1[0]==-1 || p2[0] == -1){
alert(-1);
return;
}
alert(p1+" "+p2);
let exit = false;i=0,dist=0;
while(exit==false){
if(p1[i]!=p2[i]){
dist=(p1.length-i)+(p2.length-i);
exit=true;
}else if(i==p1.length-1){
dist = (p2.length-1)-i;
exit=true;
}else if(i==p2.length-1){
dist = (p1.length-1)-i;
exit=true;
}
i++;
}
alert(dist);
function inOrder(currNode,path){
if(currNode==null)
return path;
path=inOrder(currNode.left,path);
path+=currNode.val+",";
path=inOrder(currNode.right,path);
return path;
}
function getPath(currRoot,theVal,path){
if(!currRoot || currRoot==null)
return [-1];
if(!path)
path=[];
path.push(currRoot.val);
if(currRoot.val == theVal)
return path;
else if(currRoot.val > theVal)
return getPath(currRoot.left,theVal,path);
else
return getPath(currRoot.right,theVal,path);
}
function createTree(values){
var vals = values.split(",");
let rootNode;
vals.forEach(function(v) {
v = parseInt(v);
if(!rootNode)
rootNode = {left:null,right:null,val:v};
else
insertNode(rootNode,{left:null,right:null,val:v});
}, this);
return rootNode;
}
function insertNode(currRoot,currNode){
if(currRoot.val>currNode.val){
if(currRoot.left==null)
currRoot.left=currNode;
else
insertNode(currRoot.left,currNode);
}else{
if(currRoot.right==null)
currRoot.right=currNode;
else
insertNode(currRoot.right,currNode);
}
}
})();
1. Find the common ancestor.
- Anonymous February 16, 20122. From the common ancestor, find the path of each element.