GOOGLE INTERVIEW QUESTION 1(USA)
Q.) can you efficiently implement three stacks in a single array, such that no stack overflows until there is no space left in the entire array space.
SOLUTION--
METHOD:
1. Make the first stack from position zero(arr[0]).
2. Make the second stack using from last position (position=size of array -1) .
3. Now there is the problem how we can make second stack using one array . Lets take we start the stack2 from position= size of arr/2+1, now only we have to manage the stack2 according to the empty space in array, such that move the stack2 forward with increasing its top2 position by 1 and bottom2 by 1 or move the stack backward with decreasing the top2 by 1 and bottom2 by 1.
try it happy CODING ...
-----------------------------------------------------------------------------------------------------------
#include
#define MAX 20
int top1=-1,top2=MAX/2,top3=MAX,bottom2=MAX/2+1,flag=0;
int arr[MAX];
void arrange_stack2_forward()
{
int i;
for(i=top2;i>=bottom2;i--)
{
arr[i+1]=arr[i];
}
top2=top2+1;
bottom2=bottom2+1;
}
void arrange_stack2_backward()
{
int i;
for(i=bottom2;i<=top2;i++)
{
arr[i-1]=arr[i];
}
bottom2=bottom2-1;
top2=top2-1;
}
void push_stack1(int item)
{
if(top1+1==bottom2&&top2==top3-1){
printf("arey is full\n");
flag=1;
}
else if(top1+1==bottom2&&top2!=top3-1){
arrange_stack2_forward();
top1=top1+1;
arr[top1]=item;
}
else
{
top1=top1+1;
arr[top1]=item;
}
}
void pop_stack1()
{
if(top1==-1)
printf("stack1 is empty\n");
else{
int poped_item=arr[top1];
top1=top1-1;
printf("poped item=%d\n",poped_item);
}
}
void display_stack1()
{
int i;
if(top1==-1)
printf("stack1 is empty\n");
else{
printf("STACK1 DISPLAY\n");
for(i=top1;i>=0;i--)
{
printf("%d ",arr[i]);
}
printf("\n");
}
}
void push_stack2(int item)
{
if(top2+1==top3&&bottom2==top1+1){
printf("array is full\n");
flag=1;
}
else if(top2+1==top3&&bottom2!=top1+1){
arrange_stack2_backward();
top2=top2+1;
arr[top2]=item;
}
else{
top2=top2+1;
arr[top2]=item;
}
}
void pop_stack2()
{
if(bottom2==top2+1)
printf("stack2 is empty\n");
else{
int poped_item=arr[top2];
top2=top2-1;
printf("poped item=%d\n",poped_item);
}
}
void display_stack2()
{
int i;
if(bottom2==top2+1)
printf("stack2 is empty\n");
else{
printf("DISPLAY STACK2\n");
for(i=top2;i>=bottom2;i--)
{
printf("%d ",arr[i]);
printf("\n");
}
}
}
void push_stack3(int item)
{
printf("bottom2=%d,top2=%d\n",bottom2,top2);
if(top3-1==top2&&bottom2==top1+1)
{
printf("array is full\n");
}
else if(top3-1==top2&&bottom2!=top1+1)
{
arrange_stack2_backward();
top3=top3-1;
arr[top3]=item;
}
else{
top3=top3-1;
arr[top3]=item;
}
}
void pop_stack3()
{
if(top3==MAX)
printf("stack3 is empty\n");
else{
int poped_item=arr[top3];
top3=top3+1;
printf("poped item=%d\n",poped_item);
}
}
void display_stack3()
{
int i;
if(top3==MAX)
printf("stack3 is empty\n");
else{
printf("DISPLAY STACK3\n");
for(i=MAX-1;i>=top3;i--)
printf("%d ",arr[i]);
printf("\n");
}
}
int main()
{
int item,choice,pop_item;
printf("enter choice\n");
printf("1. push on stack1\n");
printf("2. pop on stack1\n");
printf("3. display stack1\n");
printf("4. push on stack2\n");
printf("5. pop on stack2\n");
printf("6. display stack2\n");
printf("7. push on stack3\n");
printf("8. pop on stack3\n");
printf("9. display stack3\n");
printf("10. QUIT\n");
printf("enter choice=");
scanf("%d",&choice);
do
{
switch(choice)
{
case 1: printf("enter item=");
scanf("%d",&item);
push_stack1(item);
break;
case 2: pop_stack1();
break;
case 3: display_stack1();
break;
case 4: printf("enter item=");
scanf("%d",&item);
push_stack2(item);
break;
case 5: pop_stack2();
break;
case 6: display_stack2();
break;
case 7: printf("enter item=");
scanf("%d",&item);
push_stack3(item);
break;
case 8: pop_stack3();
break;
case 9: display_stack3();
break;
}
printf("enter choice=");
scanf("%d",&choice);
}while(choice!=10);
return 0;
}
if you fing any bug related to code plzz post in comment thanks!!
2 comments:
top2<bottom2..
how will the first function work??
didn't get ur question.
top2<bottom2 is the condition which resuls ,empty the stack2.
Post a Comment