Amazon Interview Question
SDE1sCountry: India
Interview Type: In-Person
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
struct node
{
struct node*left;
struct node*right;
int key;
static int maxheight;
};
int node::maxheight =0;
struct node * insert(struct node*root,int key,int height=0)
{
if(root == NULL)
{
if(height>node::maxheight) node::maxheight=height;
struct node * temp=new node;
temp->key = key;
temp->left=temp->right=NULL;
return temp;
}
if(key > root->key)
{
root->right = insert(root->right,key,height+1);
}
else if(key < root->key)
{
root->left = insert(root->left,key,height+1);
}
}
void printTree(struct node*root, int level=0, int maxheight=node::maxheight)
{
if(root==NULL) return;
printTree(root->left,level+1);
for(int i=maxheight-level;i>=0;i--) cout<<" ";
cout<<root->key<<endl;
if(root->key<10) cout<<" "<<endl;
printTree(root->right,level+1);
/*for(int i=maxheight-level;i>=0;i--) cout<<" ";
cout<<root->key<<endl;
if(root->key<10) cout<<" "<<endl; */
}
struct node * best_fit_memory(struct node* root,int input_block_size,struct node* best_fit=0)
{
if(root)
{
if(root->key > input_block_size && ((best_fit && best_fit->key > root->key)||!best_fit))
best_fit = root;
}
else
{
return best_fit;
}
if(input_block_size > root->key)
{
best_fit = best_fit_memory(root->right, input_block_size,best_fit);
}
else if(input_block_size < root->key)
{
best_fit = best_fit_memory(root->left, input_block_size,best_fit);
}
else
{
best_fit = root;
//return root;
}
return best_fit;
}
int main()
{
struct node*root=NULL;
root = insert(root,8);
printTree(root);
cout<<"------------------------------------------------------------------------------"<<endl;
root = insert(root,7);
printTree(root);
cout<<"------------------------------------------------------------------------------"<<endl;
root = insert(root,10);
printTree(root);
cout<<"------------------------------------------------------------------------------"<<endl;
root = insert(root,9);
printTree(root);
cout<<"------------------------------------------------------------------------------"<<endl;
root = insert(root,5);
printTree(root);
cout<<"------------------------------------------------------------------------------"<<endl;
struct node* result_best_fit = best_fit_memory(root,6);
cout<<"for input "<<6<<"resultbest fit = "<<result_best_fit->key<<endl;
}
- Breathes_In_Binary June 06, 2019