Amazon Microsoft Interview Question Software Engineer / Developers
0of 0 votesimplement ur own malloc() function, and free(), in C
Country: United States
This is quite open ended and implementing that is not possible in an interview.
More likely, you are asking us to do you homework. So here goes...
void * my_malloc(size_t bytes) {
return malloc(bytes);
}
void my_free(void *ptr) {
free(ptr);
}
Yes, homework.
See this other question: id = 14581754
Same person, same question and different company.
Stupid mofos, I added this ques on 2 companies becoz the company in which it was asked wasnt listed here
Moreover as a programmer u shud know the concepts
Whosoever did this bullshit solution thinks he is the greatest programmer in world and begging him to do our homework r we poor ppl
I am ur baap bc, m in Delhi college of engineering, just google it...nincompoop
This was my answer.
I wanted to use B-Tree but was asked to write the code for it in an hour so I backed out and used balanced trees intsted.
Its does defragmentation to some level but that needs improvement.
It did took me around 4 hours to write this :)
# include<stdio.h>
# include<malloc.h>
# define F 0
# define T 1
struct MEM_NODE{
int start;
int len;
};
struct NODE
{
char Info;
int Flag;
struct MEM_NODE *mem_Info;
struct NODE *Left_Child;
struct NODE *Right_Child;
};
/*
Memory Manager
*/
struct MEM_MANAGER {
struct LIST *alloc_list;
struct NODE *used_list;
int H; //Height of Balanced Binary tree
};
/*
Link List
*/
struct LIST{
struct MEM_NODE *mem_Info;
struct LIST *next;
};
struct LIST * insert_alloc(struct MEM_NODE *, struct LIST *);
struct LIST * insert_alloc_defragment(struct MEM_NODE *, struct LIST *);
struct LIST * delete_alloc(struct LIST *, struct MEM_NODE *);
struct LIST *alloc_memnode_defragment(int, int, struct LIST *);
void print_alloc_list(struct LIST *);
int malloc_new(int, struct MEM_MANAGER *);
void free_new(int, struct MEM_MANAGER *);
struct NODE *Binary_Tree (char , struct MEM_NODE *, struct NODE *, int *);
void Output(struct NODE *, int );
struct NODE *Balance_Right_Heavy(struct NODE *, int *);
struct NODE *Balance_Left_Heavy(struct NODE *, int *);
struct NODE *DELETE(struct NODE *, struct NODE *, int *, struct MEM_NODE *);
struct NODE *Delete_Element(struct NODE *, int , int *, struct MEM_NODE *);
/* Function to insert an element into tree */
struct NODE * Binary_Tree (char Info, struct MEM_NODE *mem_Info, struct NODE *Parent, int *H)
{
struct NODE *Node1;
struct NODE *Node2;
if(!Parent)
{
Parent = (struct NODE *) malloc(sizeof(struct NODE));
Parent->Info = Info;
Parent->mem_Info = mem_Info;
Parent->Left_Child = NULL;
Parent->Right_Child = NULL;
Parent->Flag = 0;
*H = T;
return (Parent);
}
if(Info < Parent->Info)
{
Parent->Left_Child = Binary_Tree(Info, mem_Info, Parent->Left_Child, H);
if(*H)
/* Left branch has grown higher */
{
switch(Parent->Flag)
{
case 1: /* Right heavy */
Parent->Flag = 0;
*H = F;
break;
case 0: /* Balanced tree */
Parent->Flag = -1;
break;
case -1: /* Left heavy */
Node1 = Parent->Left_Child;
if(Node1->Flag == -1)
{
printf("\n Left to Left Rotation\n");
Parent->Left_Child= Node1->Right_Child;
Node1->Right_Child = Parent;
Parent->Flag = 0;
Parent = Node1;
}
else
{
printf("\n Left to right rotation\n");
Node2 = Node1->Right_Child;
Node1->Right_Child = Node2->Left_Child;
Node2->Left_Child = Node1;
Parent->Left_Child = Node2->Right_Child;
Node2->Right_Child = Parent;
if(Node2->Flag == -1)
Parent->Flag = 1;
else
Parent->Flag = 0;
if(Node2->Flag == 1)
Node1->Flag = -1;
else
Node1->Flag = 0;
Parent = Node2;
}
Parent->Flag = 0;
*H = F;
}
}
}
if(Info > Parent->Info)
{
Parent->Right_Child = Binary_Tree(Info, mem_Info, Parent->Right_Child, H);
if(*H)
/* Right branch has grown higher */
{
switch(Parent->Flag)
{
case -1: /* Left heavy */
Parent->Flag = 0;
*H = F;
break;
case 0: /* Balanced tree */
Parent->Flag = 1;
break;
case 1: /* Right heavy */
Node1 = Parent->Right_Child;
if(Node1->Flag == 1)
{
printf("\n Right to Right Rotation\n");
Parent->Right_Child= Node1->Left_Child;
Node1->Left_Child = Parent;
Parent->Flag = 0;
Parent = Node1;
}
else
{
printf("\n Right to Left Rotation\n");
Node2 = Node1->Left_Child;
Node1->Left_Child = Node2->Right_Child;
Node2->Right_Child = Node1;
Parent->Right_Child = Node2->Left_Child;
Node2->Left_Child = Parent;
if(Node2->Flag == 1)
Parent->Flag = -1;
else
Parent->Flag = 0;
if(Node2->Flag == -1)
Node1->Flag = 1;
else
Node1->Flag = 0;
Parent = Node2;
}
Parent->Flag = 0;
*H = F;
}
}
}
return(Parent);
}
/* Output function */
void Output(struct NODE *Tree,int Level)
{
int i;
if (Tree)
{
Output(Tree->Right_Child, Level+1);
printf("\n");
for (i = 0; i < Level; i++)
printf(" ");
printf("(%d, %d)", Tree->mem_Info->start, Tree->mem_Info->start + Tree->mem_Info->len - 1);
Output(Tree->Left_Child, Level+1);
}
}
/* Balancing Right Heavy */
struct NODE * Balance_Right_Heavy(struct NODE *Parent, int *H)
{
struct NODE *Node1, *Node2;
switch(Parent->Flag)
{
case -1:
Parent->Flag = 0;
break;
case 0:
Parent->Flag = 1;
*H= F;
break;
case 1: /* Rebalance */
Node1 = Parent->Right_Child;
if(Node1->Flag >= 0)
{
printf("\n Right to Right Rotation\n");
Parent->Right_Child= Node1->Left_Child;
Node1->Left_Child = Parent;
if(Node1->Flag == 0)
{
Parent->Flag = 1;
Node1->Flag = -1;
*H = F;
}
else
{
Parent->Flag = Node1->Flag = 0;
}
Parent = Node1;
}
else
{
printf("\n Right to Left Rotation\n");
Node2 = Node1->Left_Child;
Node1->Left_Child = Node2->Right_Child;
Node2->Right_Child = Node1;
Parent->Right_Child = Node2->Left_Child;
Node2->Left_Child = Parent;
if(Node2->Flag == 1)
Parent->Flag = -1;
else
Parent->Flag = 0;
if(Node2->Flag == -1)
Node1->Flag = 1;
else
Node1->Flag = 0;
Parent = Node2;
Node2->Flag = 0;
}
}
return(Parent);
}
/* Balancing Left Heavy */
struct NODE * Balance_Left_Heavy(struct NODE *Parent, int *H)
{
struct NODE *Node1, *Node2;
switch(Parent->Flag)
{
case 1:
Parent->Flag = 0;
break;
case 0:
Parent->Flag = -1;
*H= F;
break;
case -1: /* Rebalance */
Node1 = Parent->Left_Child;
if(Node1->Flag <= 0)
{
printf("\n Left to Left Rotation\n");
Parent->Left_Child= Node1->Right_Child;
Node1->Right_Child = Parent;
if(Node1->Flag == 0)
{
Parent->Flag = -1;
Node1->Flag = 1;
*H = F;
}
else
{
Parent->Flag = Node1->Flag = 0;
}
Parent = Node1;
}
else
{
printf("\n Left to Right Rotation\n");
Node2 = Node1->Right_Child;
Node1->Right_Child = Node2->Left_Child;
Node2->Left_Child = Node1;
Parent->Left_Child = Node2->Right_Child;
Node2->Right_Child = Parent;
if(Node2->Flag == -1)
Parent->Flag = 1;
else
Parent->Flag = 0;
if(Node2->Flag == 1)
Node1->Flag = -1;
else
Node1->Flag = 0;
Parent = Node2;
Node2->Flag = 0;
}
}
return(Parent);
}
/* Replace the node at which key is found with last right key of a left child */
struct NODE * DELETE(struct NODE *R, struct NODE *Temp, int *H, struct MEM_NODE *mem)
{
struct NODE *Dnode = R;
if( R->Right_Child != NULL)
{
R->Right_Child = DELETE(R->Right_Child, Temp, H, mem);
if(*H)
R = Balance_Left_Heavy(R, H);
}
else
{
Dnode = R;
mem->start = Dnode->mem_Info->start;
mem->len = Dnode->mem_Info->len;
Temp->Info = R->Info;
R = R->Left_Child;
free(Dnode);
*H = T;
}
return(R);
}
/* Delete the key element from the tree */
struct NODE * Delete_Element(struct NODE *Parent, int Info, int *H, struct MEM_NODE *mem)
{
struct NODE *Temp;
if(!Parent)
{
return(Parent);
}
else
{
if (Info < Parent->Info )
{
Parent->Left_Child = Delete_Element(Parent->Left_Child, Info, H, mem);
if(*H)
Parent = Balance_Right_Heavy(Parent, H);
}
else
if(Info > Parent->Info)
{
Parent->Right_Child = Delete_Element(Parent->Right_Child, Info, H, mem);
if(*H)
Parent = Balance_Left_Heavy(Parent, H);
}
else
{
Temp= Parent;
if(Temp->Right_Child == NULL)
{
Parent = Temp->Left_Child;
*H = T;
mem->start = Temp->mem_Info->start;
mem->len = Temp->mem_Info->len;
free(Temp);
}
else
if(Temp->Left_Child == NULL)
{
Parent = Temp->Right_Child;
*H = T;
mem->start = Temp->mem_Info->start;
mem->len = Temp->mem_Info->len;
}
else
{
Temp->Left_Child = DELETE(Temp->Left_Child, Temp, H, mem);
if(*H)
Parent = Balance_Right_Heavy(Parent, H);
}
}
}
return(Parent);
}
struct LIST * insert_alloc(struct MEM_NODE *mem_Info, struct LIST *root)
{
struct LIST *curr = NULL;
struct LIST *new_node = NULL;
new_node = (LIST *) malloc(sizeof(struct LIST));
new_node->next = NULL;
new_node->mem_Info = mem_Info;
if (root == NULL)
{
root = new_node;
return root;
}
if (root->mem_Info->start > mem_Info->start)
{
new_node->next = root;
root = new_node;
return root;
}
curr = root;
while(curr->next != NULL)
{
if(curr->next->mem_Info->start > mem_Info->start)
{
new_node->next = curr->next;
curr->next = new_node;
return root;
}
curr = curr->next;
}
curr->next = new_node;
return root;
}
struct LIST * insert_alloc_defragment(struct MEM_NODE *mem_Info, struct LIST *root)
{
struct LIST *curr = NULL;
struct LIST *new_node = NULL;
new_node = (LIST *) malloc(sizeof(struct LIST));
new_node->next = NULL;
new_node->mem_Info = mem_Info;
if (root == NULL)
{
root = new_node;
return root;
}
if (root->mem_Info->start > mem_Info->start)
{
// Merge Nodes if necessery
if(root->mem_Info->start == mem_Info->start + mem_Info->len) {
mem_Info->len = mem_Info->len + root->mem_Info->len;
free(root->mem_Info);
free(new_node);
root->mem_Info = mem_Info;
}
else {
new_node->next = root;
root = new_node;
}
return root;
}
curr = root;
while(curr->next != NULL)
{
if(curr->next->mem_Info->start > mem_Info->start)
{
// Merge Nodes if necessery
if(curr->next->mem_Info->start == mem_Info->start + mem_Info->len) {
mem_Info->len = mem_Info->len + curr->mem_Info->len;
free(curr->next->mem_Info);
free(new_node);
curr->next->mem_Info = mem_Info;
}
else {
new_node->next = curr->next;
curr->next = new_node;
}
return root;
}
curr = curr->next;
}
// Merge Nodes if necessery
if(curr->mem_Info->start + curr->mem_Info->len == new_node->mem_Info->start){
new_node->mem_Info->start = curr->mem_Info->start;
new_node->mem_Info->len = curr->mem_Info->len + new_node->mem_Info->len;
free(curr->mem_Info);
curr->mem_Info = new_node->mem_Info;
free(new_node);
}
else {
curr->next = new_node;
}
return root;
}
struct LIST * delete_alloc(struct LIST *root, struct MEM_NODE *mem_Info){
LIST *curr = root;
if(curr->mem_Info == mem_Info) {
root=curr->next;
free(curr);
return root;
}
while(curr->next != NULL) {
if(curr->next->mem_Info == mem_Info) {
free(curr->next);
curr->next = curr->next->next;
break;
}
curr = curr->next;
}
return root;
}
/*struct LIST *alloc_memnode(int start, int len, struct LIST *root){
struct MEM_NODE *new_node=NULL;
new_node = (struct MEM_NODE *)malloc(sizeof(struct MEM_NODE));
new_node->start = start;
new_node->len = len;
return insert_alloc(new_node, root);
}*/
// this one also defreagments the memory manager
struct LIST *alloc_memnode_defragment(int start, int len, struct LIST *root){
struct MEM_NODE *new_node=NULL;
new_node = (struct MEM_NODE *)malloc(sizeof(struct MEM_NODE));
new_node->start = start;
new_node->len = len;
return insert_alloc_defragment(new_node, root);
}
void print_alloc_list(struct LIST *root){
LIST *curr = root;
printf("\n Showing List");
while(curr) {
printf(" - node(%d to %d )", curr->mem_Info->start, curr->mem_Info->start + curr->mem_Info->len -1);
curr = curr->next;
}
printf("\n");
}
int malloc_new(int size, struct MEM_MANAGER *mem_manager){
int start = -1;
LIST *curr = mem_manager->alloc_list;
MEM_NODE *mem=NULL;
int done = 0;
if(curr == NULL) {
printf("\nError : No memory Attached");
return -1;
}
while(curr) {
if(size == curr->mem_Info->len) {
mem = curr->mem_Info;
mem_manager->alloc_list = delete_alloc(mem_manager->alloc_list, curr->mem_Info);
//insert meminfo to NODE
mem_manager->used_list = Binary_Tree(mem->start, mem, mem_manager->used_list, &mem_manager->H);
done = 1;
break;
}
if(size < curr->mem_Info->len) {
mem = (struct MEM_NODE *)malloc(sizeof(struct MEM_NODE));
mem->start = curr->mem_Info->start;
mem->len = size;
curr->mem_Info->start = curr->mem_Info->start + size;
curr->mem_Info->len = curr->mem_Info->len - size;
mem_manager->used_list = Binary_Tree(mem->start, mem, mem_manager->used_list, &mem_manager->H);
done = 1;
break;
}
curr = curr->next;
}
if(done == 0){
printf("\nError : Memory not available!!");
start = -1;
}
else {
start = mem->start;
}
return start;
}
void free_new(int start, struct MEM_MANAGER *mem_manager) {
struct MEM_NODE *new_node=NULL;
new_node = (struct MEM_NODE *)malloc(sizeof(struct MEM_NODE));
new_node->start = -1;
new_node->len = -1;
mem_manager->used_list = Delete_Element(mem_manager->used_list, start, &mem_manager->H, new_node);
if(new_node->start != start) {
printf("\nError : Allocated Node not found for addreess %d",start);
}
else {
mem_manager->alloc_list = insert_alloc(new_node, mem_manager->alloc_list);
}
}
// allocate 30 mb and delete it
void case1(struct MEM_MANAGER *mem_manager) {
int ret_pt;
printf("Case1 : Objective -> allocate 30 memory and free it.");
ret_pt = malloc_new(30, mem_manager);
printf("\nCase1 : Allocated 30 memory and ptr returned = %d", ret_pt);
free_new(ret_pt, mem_manager);
printf("\nCase1 : freed 30 memory and from ptr = %d", ret_pt);
printf("\nCase1 Ended\n");
}
// Try to allcate too much memory . which does not exist
void case2(struct MEM_MANAGER *mem_manager) {
int ret_pt;
printf("\nCase2 : Allocated 500 memory while we only have 70 free. Error should Appear");
ret_pt = malloc_new(500, mem_manager);
printf("\nCase2 Ended\n");
}
// Trying to free non existent Pointer
void case3(struct MEM_MANAGER *mem_manager) {
printf("\nCase3 : freed non available memory and from ptr = %d. Error should Appear", 530);
free_new(530, mem_manager);
printf("\nCase3 Ended\n");
}
int main(){
struct MEM_MANAGER *mem_manager = NULL;
// Seting initial memory to 100
int initial_memory = 100;
int ret_pt = -2;
// Initialize memory manager
mem_manager = (struct MEM_MANAGER *)malloc(sizeof(struct MEM_MANAGER));
mem_manager->alloc_list = NULL;
mem_manager->used_list = NULL;
mem_manager->alloc_list = alloc_memnode_defragment(1,initial_memory, mem_manager->alloc_list);
print_alloc_list(mem_manager->alloc_list);
case1(mem_manager);
case2(mem_manager);
case3(mem_manager);
return 0;
}
Same guy, same question, two different companies.
- Anonymous September 03, 2012Stop posting your homework.