Microsoft Interview Question
Software Engineer / DevelopersTeam: Bing
Country: India
Interview Type: In-Person
Hi,
Can you please explain more about the question like, what do the numbers 4, (3,1) , (2,2) indicate?
Thanks in advance
/*
* BusSeat.cpp
*
* Created on: Dec 10, 2012
* Author: Kevin Li
*/
#include <cstdio>
#include <iostream>
using namespace std;
//This is the available seats in each row
int seatRow[10]={3,1,2,2,1,1,2,1,2,1};
bool flag=false;
//check if there is enough seat n for the request
bool seatsAvailable(int n)
{
for(int i =0; i< 10; i++)
{
if(seatRow[i]>=n)
{
seatRow[i]-=n;
return true;
}
}
return false;
}
int getSeat(int total,int n)
{
//check if request seat number available
if(seatsAvailable(n))
{
cout<<"get seat number"<<n<<endl;
if(total>n)
{
//if there is still more seat needed, search them
getSeat(total-n,total-n);
}
return 0;
}
else
{
int seat =getSeat(total,n-1);
}
return 0;
}
This should work,although doing lot more than required.
#include <stdio.h>
#include <stdlib.h>
const int R=10;
const int C=6;
int gettotal(int *seats,int size)
{
int i,sum=0;
for(i=0;i<size;i++)
sum+=seats[i];
return sum;
}
main()
{
int seats[R];
int i,num,start,end,j,max=0,index=-1,available;
char c;
for(i=0;i<R;i++)
seats[i]=C;
do
{
printf("No. of tickets:\n");
scanf("%d",&num);
for(i=0;i<R;i++)
{
available=gettotal(seats,R);
if(num>available)
{
printf("\n#####Only %d seats available#####\n",available);
break;
}
if(seats[i]>=num)
{
start=C-seats[i]+1;
end=start+num-1;
printf("\t%d seats allotted at row %d seat %d-%d.\n",num,i,start,end);
seats[i]=seats[i]-num;
for(j=0;j<R;j++)
printf("%d ",seats[j]);
printf("\n");
break;
}
else
{
if(seats[i]>max)
{
max=seats[i];
index=i;
}
if(i==R-1)
{
start=C-seats[index]+1;
end=start+max-1;
printf("\t..%d seats allotted at row %d seat %d-%d.\n",max,index,start,end);
seats[index]=seats[index]-max;
num=num-max;
for(j=0;j<R;j++)
printf("%d ",seats[j]);
printf("\n");
i=-1;
max=0,index=-1;
}
}
}
// for(j=0;j<R;j++)
// printf("%d ",seats[j]);
if(gettotal(seats,R)==0)
{
printf("\nNO MORE ALLOCATION POSSIBLE.. QUITTING\n");
break;
}
printf("\nCONTINUE?y[n]: ");
c=getchar();
c=getchar();
}while(c!='n');
}
We can convert this to a bin packing problem which can be solved using a Max Winner tree. Complexity is O(log n).
- isandesh7 January 28, 2013