Fortinet Interview Question
Software Engineer / DevelopersCountry: Canada
Interview Type: Written Test
void CreateBSTAsennd(int s, int e)
{
if(e-s==0)
{
AddNode(n[e]);
}
else if(e-s==1)
{
AddNode(n[s]);
AddNode(n[e]);
}
else
{
AddNode(n[(s+e)/2]);
CreateBSTAsennd(s,s+(e-s)/2-1);
CreateBSTAsennd(s+(e-s)/2+1,e);
}
}
also create a bstree with it , it is balanced
typedef struct bst {
int data;
struct bst * lc;
struct bst * rc;
} *bstree,*bstnode;
void AddNode(int e)
{
static bstree root=NULL;
bstnode q,f;
bstnode p =(bstnode)malloc(sizeof(struct bst));
if(p==NULL) return;
memset(p,0,sizeof(struct bst));
if(root==NULL) {root=p; return;}
q=root;
while(q)
{
f=q;
if(q->data>p->data)q=q->lc;
else q=q->rc;
}
if(f->data>p->data)
{
f->lc=p;
}
else
{
f->rc=p;
}
}
public static void main(String arg[]){
int arr[]={1,3,5,9,10};
int size = arr.length-1;
int index = size /2;
int startIndex = 0;
int endIndex = arr.length;
int givenNumber = 1;
while( true ){
index = (startIndex+endIndex)/2;
if( givenNumber == arr[index] ){
System.out.println( "found here: "+ index);
break;
}
else if( givenNumber<arr[index] ){
if( endIndex == index )
break;
endIndex = index;
}
else{
if( startIndex == index)
break;
startIndex = index;
}
}
}
- Aashish June 23, 2012