Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: Phone Interview
You didnt handle the case if key is equal to lowest OR key is equal to highest. This should come after the AND you are doing and if it is true you MUST return P.
One more thing for this code to work you MUST first traverse the whole BST and make sure that the input given does exist in the tree. Of course you can also ask your interviewer if the input is guaranteed to be in the tree.
//pass root as p , lowest and highest values in the given numbers m.
// i am assuming that all the given m numbers are present in the tree
int least_c_a(node *p,int lowest,int highest)
{
if((p->key>=lowest)&&(p->key<=highest))
return p->key;
else if(p->key<lowest)
least_c_a(p->rchild,lowest,highest);
else if(p->key>lowest)
least_c_a(p->lchild,lowest,highest);
}
*correction I think the last else if statement should be:
else if(p->key > highest)
least_c_a(p->lchild, lowest, highest);
i think do it is as:
in each recursive call
1.check that if T==null return no any lca ;)
2.loop from i=1 to m and check for all vaues if any value equal to T->info return T->info.
3.initialize r=0,l=0;
4.loop again from i=1 to m if any value is less than the T->info then l=1 else r=1
5.after loop check if both l==1 and r==1 return T->info
6. if (r&& l==0) return the recusrive call of func passing T->right
7else return the recursive call of func passing T->left
//this is for two elements only;
#include<iostream>
#include<string.h>
using namespace std;
struct node
{
node *l,*r;int data;
}*root;
void show(node *);node *insert(node *,int );int n;
void search(node *,node *,int ,int);
void search(node *sr,node *sr1,int d,int e)
{
node *p;p=sr;node *p1;p1=sr1;
while(sr!=NULL && sr1!=NULL)
{
if(sr->data==d || sr1->data==e)
{
cout<<"found\n";cout<<endl<<p->data<<" "<<p1->data<<endl;break;
}
p=sr;p1=sr1;cout<<endl<<p->data<<" "<<p1->data<<endl;
if(p->data!=p1->data) break;
if(sr->data>d) sr=sr->l;
else sr=sr->r;
if(sr1->data>e) sr1=sr1->l;
else sr1=sr1->r;
}
sr=root;node *g;g=sr;cout<<endl<<p->data<<endl;
while(sr!=NULL)
{
if(sr->data==p->data) {cout<<"again found\n";cout<<endl<<g->data<<endl;return;}
g=sr;
if(sr->data>p->data) sr=sr->l;
else sr=sr->r;
}
}
node *insert(node *sr,int a)
{
if(sr==NULL)
{
sr=new node;sr->data=a;sr->l=sr->r=NULL;return sr;
}
else if(sr->data<a)
sr->r=insert(sr->r,a);
else if(sr->data>a)
sr->l=insert(sr->l,a);
else return sr;
}
void show(node *sr)
{
if(sr!=NULL)
{
show(sr->l);cout<<sr->data<<" ";show(sr->r);
}}
int main()
{
root=NULL;int num;cout<<"enter how many\n";cin>>n;
cout<<"enter which one\n";
for(int i=0;i<n;i++)
{
cin>>num;root=insert(root,num);
}
cout<<endl;show(root);cout<<endl;int x,y;cout<<"enter the 1st searched element\n";
cin>>x;cout<<"enter the 2nd searche element\n";cin>>y;search(root,root,x,y);
return 0;
}
//this is for two elements only;
#include<iostream>
#include<string.h>
using namespace std;
struct node
{
node *l,*r;int data;
}*root;
void show(node *);node *insert(node *,int );int n;
void search(node *,node *,int ,int);
void search(node *sr,node *sr1,int d,int e)
{
node *p;p=sr;node *p1;p1=sr1;
while(sr!=NULL && sr1!=NULL)
{
if(sr->data==d || sr1->data==e)
{
cout<<"found\n";cout<<endl<<p->data<<" "<<p1->data<<endl;break;
}
p=sr;p1=sr1;cout<<endl<<p->data<<" "<<p1->data<<endl;
if(p->data!=p1->data) break;
if(sr->data>d) sr=sr->l;
else sr=sr->r;
if(sr1->data>e) sr1=sr1->l;
else sr1=sr1->r;
}
sr=root;node *g;g=sr;cout<<endl<<p->data<<endl;
while(sr!=NULL)
{
if(sr->data==p->data) {cout<<"again found\n";cout<<endl<<g->data<<endl;return;}
g=sr;
if(sr->data>p->data) sr=sr->l;
else sr=sr->r;
}
}
node *insert(node *sr,int a)
{
if(sr==NULL)
{
sr=new node;sr->data=a;sr->l=sr->r=NULL;return sr;
}
else if(sr->data<a)
sr->r=insert(sr->r,a);
else if(sr->data>a)
sr->l=insert(sr->l,a);
else return sr;
}
void show(node *sr)
{
if(sr!=NULL)
{
show(sr->l);cout<<sr->data<<" ";show(sr->r);
}}
int main()
{
root=NULL;int num;cout<<"enter how many\n";cin>>n;
cout<<"enter which one\n";
for(int i=0;i<n;i++)
{
cin>>num;root=insert(root,num);
}
cout<<endl;show(root);cout<<endl;int x,y;cout<<"enter the 1st searched element\n";
cin>>x;cout<<"enter the 2nd searche element\n";cin>>y;search(root,root,x,y);
return 0;
}
//this is for two elements only;
#include<iostream>
#include<string.h>
using namespace std;
struct node
{
node *l,*r;int data;
}*root;
void show(node *);node *insert(node *,int );int n;
void search(node *,node *,int ,int);
void search(node *sr,node *sr1,int d,int e)
{
node *p;p=sr;node *p1;p1=sr1;
while(sr!=NULL && sr1!=NULL)
{
if(sr->data==d || sr1->data==e)
{
cout<<"found\n";cout<<endl<<p->data<<" "<<p1->data<<endl;break;
}
p=sr;p1=sr1;cout<<endl<<p->data<<" "<<p1->data<<endl;
if(p->data!=p1->data) break;
if(sr->data>d) sr=sr->l;
else sr=sr->r;
if(sr1->data>e) sr1=sr1->l;
else sr1=sr1->r;
}
sr=root;node *g;g=sr;cout<<endl<<p->data<<endl;
while(sr!=NULL)
{
if(sr->data==p->data) {cout<<"again found\n";cout<<endl<<g->data<<endl;return;}
g=sr;
if(sr->data>p->data) sr=sr->l;
else sr=sr->r;
}
}
node *insert(node *sr,int a)
{
if(sr==NULL)
{
sr=new node;sr->data=a;sr->l=sr->r=NULL;return sr;
}
else if(sr->data<a)
sr->r=insert(sr->r,a);
else if(sr->data>a)
sr->l=insert(sr->l,a);
else return sr;
}
void show(node *sr)
{
if(sr!=NULL)
{
show(sr->l);cout<<sr->data<<" ";show(sr->r);
}}
int main()
{
root=NULL;int num;cout<<"enter how many\n";cin>>n;
cout<<"enter which one\n";
for(int i=0;i<n;i++)
{
cin>>num;root=insert(root,num);
}
cout<<endl;show(root);cout<<endl;int x,y;cout<<"enter the 1st searched element\n";
cin>>x;cout<<"enter the 2nd searche element\n";cin>>y;search(root,root,x,y);
return 0;
}
As it is a binary search tree , find the least and largest of all m numbers and find their LCA .
- Anonymous January 22, 2012