Microsoft Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
{{
int FindAdjacentOns(int** matrix, int rows, int cols)
{
int groupCount = 0;
for (int i=0; i< rows ; i++)
{
for(int j=0; j< cols ; j++)
{
if(matrix[i][j] == 1)
{
groupCount ++;
CheckAdjacent( matrix, i, j)
}
}
}
return groupCount;
}
void CheckAdjacent(int** matrix, int i, int j, int rows, int cols)
{
if (matrix != null && matrix[i][j] == 0)
{
return;
}
matrix[i][j] = 0;
if (i > 0)
{
CheckAdjacent(matrix, i - 1, j, rows, cols);
}
if (j > 0)
{
CheckAdjacent(matrix, i - 1, j, rows, cols);
}
if (i < rows - 1)
{
CheckAdjacent(matrix, i + 1, j, rows, cols);
}
if (j < cols - 1)
{
CheckAdjacent(matrix, i, j + 1, rows, cols);
}
}
}}
I think Anonymous algorithm will not work.
This is the problem. Initial state of the seat arrangement is given below
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
When two person book a ticket, allocation will be end/middle of the row
0 0 0 1 1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
Now another 2 more person are booking a ticket. Allocate a seat in the right side or left side
0 0 0 1 1 0 1 1
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
Suppose if three of tem request a ticket second time. Seating allocation will be like this with some privacy
0 0 0 1 1 0 0 0
0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
Hope now problem statement is clear.
One solution where theater is matrix of seat objects.
Class Theater{
Seat[][] matrix;
int[] classes;
public Theater(int rows, int cols){
matrix=new Seat[rows][cols];
classes=new int[rows];
//gold, platinum or premium class rows to be declared here
for(int i=0; i<rows; i++)
for(int j=0; j<cols; j++)
matrix[i][j]=new Seat();
}
public bookSeat(int r, int c){
if(!matrix[r][c].booked){
matrix[r][c].seatLock.lock();
matrix[r][c].booked=true;
matrix[r][c].seatLock.unlock();
}
}
public boolean[][] listSeats(){
boolean[][] view=new boolean[matrix.length][matrix[0].length];
for(int i=0; i<matrix.length; i++){
for(int j=0; j<matrix[0].length; j++){
if(matrix[i][j].booked || seatLock.locked())
view[i][j]=false;
}
}
}
public price(int r){
return pricePerClass[r];
}
public getSeatPrice(int r, int c){
return price(r);
}
}
Class Seat{
boolean booked;
Lock seatLock;
public Seat(){
this.booked=false;
this.seatLock=new Lock();
}
}
Still show title and show timings to be mentioned ...
Data structure :
I would like to use hasmap and bucket :-
Each row would be given a name a1,a2...an
create hasmap -> stores key = row name value = seats left
Create bucket : a1 -> 1,2,3,4....n
Whenever have to reserve seat go in hashmap see how many seats left starting from a1 to an. If enough seats available got to a1 bucket : divide the array into two parts left and right row. Start assigning seats if adjacent then ok else go to next least nu,ber available in hashmap.
Follow same above procedure.
We can represent a "Row" as a data structure that contain row number and current seat number and has a method book(int num). Then the theater has a LinkedList of 2*|Row| each of which represent "Half Row". The first element is the Left (or right) Row follow by the other half. Then the the N-1 row... All Row elements behave very similar except the Left Row booking by decreament the current seat number by num while the Right Row do the opposite. Given below is the data structure.
How to divide the row you may ask. If the number of seats is Odd then the middle seat is blank. If it is even, either Left or Right Row would be 1 seat lessor. Given above Data Structure and a LinkedList<Row> of size 2*|Row|. When the first person comes, it will reserve the Last Row at the Middle and the seat next to him is also mark empty. When num greater than the availability, then move to the next half row element. Doing so take O(|Row|) complexity.
- Anonymous November 06, 2011