Bloomberg LP Interview Question
Financial Software DevelopersCountry: United States
Interview Type: Phone Interview
struct Node
{
int val;
Node * left;
Node * right;
}
Node * findNode (Node * root, int val)
{
if (root == NULL) return root;
if (root->val == val) return root;
Node * result = 0;
if (root->left != NULL)
{
result = findNode (root->left, val);
if (result != 0) return result;
}
if (root->right!=NULL)
{
result = findNode(root->right,val);
if (result != 0) return result;
}
return result;
}
#include<stdio.h>
#include<stdlib.h>
#include<process.h>
typedef struct tree
{
int data;
struct tree*lptr;
struct tree*rptr;
}tree;
tree*create()
{
tree*root,*t1,*temp,*prev;
int val;
char ch;
root=NULL;
printf("enter choice");
fflush(stdin);
scanf("%c",&ch);
do
{
if(ch=='y')
{
t1=(tree*)malloc(sizeof(tree));
printf("enter value");
scanf("%d",&val);
t1->data=val;
t1->lptr=NULL;
t1->rptr=NULL;
if(root==NULL)
{
root=t1;
temp=root;
}
else
{ temp=root;
while(temp!=NULL)
{
if(val<temp->data)
{
prev=temp;
temp=temp->lptr;
}
else if(val>temp->data)
{
prev=temp;
temp=temp->rptr;
}
else
{
printf("duplicate data is not allowed");
}
}
if(val<prev->data)
prev->lptr=t1;
else
prev->rptr=t1;
}
printf("do u want to have more nodes");
fflush(stdin);
scanf("%c",&ch);
}
}while(ch=='y');
return(root);
}
tree* search(tree*root,int data)
{
if(data==root->data)
return(root);
else if(data<root->data)
return search(root->lptr,data);
else if(data>root->data)
return search(root->rptr,data);
else
return NULL;
}
int main()
{
tree*root,*temp;
int data,y;
root=create();
printf("enter data u want to search");
scanf("%d",&data);
temp=search(root,data);
if(temp==NULL)
printf("not found");
else
printf("found");
}
struct Node
{
int val;
Node * left;
Node * right;
}
Node *findNode(Node *rootPtr, int data)
{
if(rootPtr == NULL) return rootPtr;
if(rootPtr->data == data) return rootPtr;
if(rootPtr->data > data)
return findNode(rootPtr->left, data);
if(rootPtr->data < data)
return findNode(rootPtr->right, data);
}
O( log n) complexity (assuming balanced), O(1) memory:
- zortlord July 14, 2015