Microsoft Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

public abstract class ROW{
int row_num;
int curr_seat;
public abstract boolean isAvailable(int num);
public abstract void book(int num);
}
	
public class LeftRow extends ROW{
@Override
public boolean isAvailable(int num){return (curr_seat - num > 0);}
		
@Override
public void book(int num) {curr_seat -= num -1;} 
}
public class RightRow extends ROW{
@Override
public boolean isAvailable(int num){return (curr_seat + num < LastRow);}
		
@Override
public void book(int num) {curr_seat += num +1;} 
}

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 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{
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);
}
}
}}

- Anonymous November 05, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can you explain by providing an example? What do you mean by saying "we have to provide empty space between the existing audience" ?

- numa November 05, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- nmarasu November 05, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Seating allocation will be like this with some privacy?
what does this mean??

- nr November 05, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

While allocating a seat, we should give a space between each group.

- JobHunter November 05, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

In the above solutions, finally there will be lots of spaces inbetween which cannot be booked by anyone. I think one should point this out to the interviewer which suggests that you can infact recognize a poor design

- Anonymous December 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 ...

- spiderman July 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Chaz September 30, 2012 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More