Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
If it's a bst then there must be one unique path between any two of nodes. the complexity of searching in BST is log(n) .
void Bst::Path(int &i_source , int &i_destination ){ // give two node value for searching path
node *temp=FindBreak( root , i_source , i_destination );
if( temp->i_value == i_source && temp->i_value == i_destination ){
std::cout<<temp->i_value<<std::endl;
}
Push( temp , i_source );
Push(temp , i_destination);
PrintMap();
}
node *Bst::FindBreak( node *temp, int &i_source , int &i_destination ){ // find the breaking node after which source & destination nodes became ( left , righ ) of break point node
//node *temp=root;
while ( temp!=NULL ){
int i_change=0;
while ( temp->i_value >i_source & temp->i_value>i_destination ){
std::cout<<"left\n";
temp=temp->l_child;
i_change=1;
}
while( temp->i_value <i_source & temp->i_value<i_destination ){
std::cout<<"Right\n";
temp=temp->r_child;
i_change=1;
}
//std::cout<<temp->i_value<<std::endl;
if ( i_change == 0 ) return temp;
FindBreak ( temp , i_source , i_destination);
}
}
void Bst::PrintMap(){
std::cout<<"The path is -------- \n";
for ( Track::iterator ii=m_track.begin() ; ii!=m_track.end() ; ii ++ )
std::cout<<ii->first<<"-->";
std::cout<<"END"<<std::endl;
}
void Bst::Push ( node *temp , int &i_search ){
while( temp!=NULL ){
m_track[ temp->i_value ]=temp->i_value;
if( temp->i_value == i_search )
return ;
else {
m_track[ temp->i_value ]=temp->i_value;
if ( temp->i_value > i_search ) temp=temp->l_child;
else temp=temp->r_child;
}
}
return ;
}
Can you please explain the algorithm what exactly you are doing and also the code for it in C if possible.
The idea here is to find the lowest common ancestor of the given nodes and then print the path from first given node to second given node through the LCA.
The code is
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string.h>
using namespace std;
struct node {
int data;
struct node *left;
struct node *right;
};
void printPath(int num,struct node *LCA) {
if(num==LCA->data) {
cout<<LCA->data<<" ";
return;
}
struct node *temp=LCA;
if(num<LCA->data)
LCA=LCA->left;
else
LCA=LCA->right;
printPath(num,LCA);
cout<<temp->data<<" ";
}
void findMaxPath(int num1,int num2,struct node *root) {
struct node *num1LCA=root;
struct node *num2LCA=root;
struct node *LCA=root;
while(num1LCA==num2LCA) {
if(num1 < num1LCA->data)
num1LCA=num1LCA->left;
else
num1LCA=num1LCA->right;
if(num2<num2LCA->data)
num2LCA=num2LCA->left;
else
num2LCA=num2LCA->right;
if(num1LCA==num2LCA)
LCA=num1LCA;
}
cout<<"Path from node1 to root\n";
printPath(num1,LCA);
cout<<"\nAnother path starting from node 2 to root\n";
printPath(num2,LCA);
return;
}
// FUNCTION TO INSERT NODES IN THE BINARY TREE
void insertNode(struct node **root,int data) {
// CREATES THE ROOT NODE
if(*root==NULL) {
(*root)=(struct node*)malloc(sizeof(struct node));
(*root)->data=data;
(*root)->left=NULL;
(*root)->right=NULL;
return;
}
// FOR CREATION OF OTHER NODES
if(data < (*root)->data) {
insertNode((&(*root)->left),data);
}
else {
insertNode((&(*root)->right),data);
}
return;
}
// DRIVER FUNCTION
int main() {
struct node *root=NULL;
// TAKES THE INPUT FOR INSERTION
do {
int data;
scanf("%d",&data);
if(data!=-1) {
insertNode(&root,data);
}
else {
break;
}
}while(1);
findMaxPath(10,14,root);
return 0;
}
// (x, y)
int maxPath(TreeNode* root, int x, int y)
{
if (root == NULL) return INT_MAX; // not found;
if (root->data == x) return 1 + distance(root->right, y);
else if (root->data == y) return 1 + distance(root->left, x);
else if (root->data < x) return maxPath(root->right, x , y);
else if (root->data > y) return maxPath(root->left, x, y);
else return 2 + distance(root->left, x) + distance(root->right, y);
}
int distance(TreeNode* root, int key)
{
if (root == NULL) return INT_MAX ; // not found;
else if (root->val == key) return 0;
else if (key > root->right) return 1 + distance(root->right, key);
else return 1 + distance(root->left, key);
}
int maxPath(int a, int b){
return maxPath(BST.root,a, b);
}
int maxPath(BST node,int a, int b){
if(a<node.val && b<node.val)
return maxPath(node.left,a, b);
else if(a>node.val && b>node.val)
return maxPath(node.right,a, b);
return height1(node,a)+height1(node,b);
}
int height1(BST node, int a){
if(node.val == a)
return 0;
if(node.val<a)
return 1+height1(node.right,a);
return 1+height1(node.left,a);
}
distance from node1 to common ancestor + distance from node2 to common ancestor
- algos July 11, 2013