Microsoft Interview Question for Software Engineer / Developers


Team: Windows Live
Country: United States
Interview Type: In-Person




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

To be very specific as @numbus said, All door numbers which are perfect squares will be closed.
And rest of the doors will remain open, The reason is, There is always a pair of devisors.

EG : take number 12.

2*6
6*2

3*4
4*3

12*1
1*12

- Vijay Rajanna January 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

great, only perfect squares have odd number of pair of devisors

- nim January 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

numbers with odd number of factors would change state. The rest would remain in the same state as the initial state.

- smffap March 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

great view dear....
nic

- shreyans June 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yeah This is correct...

- Raju B July 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
9
of 9 vote

This problem is designed to seem overwhelming. You don’t have time to draw a diagram of 100 lockers and count 100 passes through them. Even if you did, solving the problem that way wouldn’t illustrate any skill or intuition, so there must be some trick that can be used to determine how many doors will be open. You just have to figure out what that trick is.

It’s unlikely that you’re going to be able to intuit the solution to this problem by just staring at it. What can you do? Although it’s not practical to solve the entire problem by brute force, solving a few lockers in this manner is reasonable. Perhaps you’ll notice some patterns you can apply to the larger problem.

Start by choosing an arbitrary locker, 12, and determining whether it will end open or closed. On which passes will you toggle locker 12? Obviously on the first pass, when you toggle every locker, and on the twelfth pass when you start with 12. You don’t need to consider any pass after 12 because those will all start farther down the hall. This leaves passes 2 through 11. You can count these out: 2, 4, 6, 8, 10, 12 (you toggle on pass 2); 3, 6, 9, 12 (on 3); 4, 8, 12 (on 4); 5, 10, 15 (not on 5); 6, 12 (on 6); 7, 14 (not on 7), and so on. Somewhere in the middle of this process, you will probably notice that you toggle locker 12 only when the number of the pass you’re on is a factor of 12. If you think about this, it makes sense: When counting by n, you hit 12 only when some integer number of n’s add to 12, which is another way of saying that n is a factor of 12. Though it seems simple in retrospect, this probably wasn’t obvious before you worked out an example.

The factors of 12 are 1, 2, 3, 4, 6, and 12. Correspondingly, the operations on the locker door are open, close, open, close, open, close. So locker 12 will end closed. The solution seems to have something to do with factors. Primes are numbers with unique factor properties. Perhaps it would be instructive to investigate a prime numbered locker. You might select 17 as a representative prime. The factors are 1 and 17, so the operations are open, close. It ends closed just like 12. Apparently primes are not necessarily different from nonprimes for the purposes of this problem.

What generalizations can you make about whether a locker ends open or closed? All lockers start closed and alternate between being open and closed. So lockers are closed after the second, fourth, sixth, and so on, times they are toggled - in other words, if a locker is toggled an even number of times, then it ends closed; otherwise, it ends open. You know that a locker is toggled once for every factor of the locker number, so you can say that a locker ends open only if it has an odd number of factors.

The task has now been reduced to finding how many numbers between 1 and 100 have an odd number of factors. The two you’ve examined (and most others, if you try a few more examples) have even numbers of factors. Why is that? If a number i is a factor of n, what does that mean? It means that i times some other number j is equal to n. Of course, because multiplication is commutative (i × j = j × i), that means that j is a factor of n, too, so the number of factors is usually even because factors tend to come in pairs. If you can find the numbers that have unpaired factors, you will know which lockers will be open. Multiplication is a binary operation, so two numbers will always be involved, but what if they are both the same number (that is, i = j)? In that case, a single number would effectively form both halves of the pair and there would be an odd number of factors. When this is the case, i × i = n. Therefore, n would have to be a perfect square. Try a perfect square to check this solution. For example, for 16, the factors are 1, 2, 4, 8, 16; operations are open, close, open, close, open - as expected, it ends open.

Based on this reasoning, you can conclude that only lockers with numbers that are perfect squares end open. The perfect squares between 1 and 100 (inclusive) are 1, 4, 9, 16, 25, 36, 49, 64, 81, and 100. So 10 lockers would remain open.

Similarly, for the general case of k lockers, the number of open lockers is the number of perfect squares between 1 and k, inclusive. How can you best count these? The perfect squares themselves are inconvenient to count because they’re unevenly spaced. However, the square roots of the perfect squares greater than zero are the positive integers. These are very easy to count: The last number in the list of square roots gives the number of items in each list. For example, the square roots of 1, 4, 9, 16, and 25 are 1, 2, 3, 4, and 5; the last number in the list of square roots is the square root of the largest perfect square and is equal to the number of perfect squares. You need to find the square root of the largest perfect square less than or equal to k.

This task is trivial when k is a perfect square, but most of the time it won’t be. In these cases, the square root of k will be a noninteger. If you round this square root down to the nearest integer, then its square is the largest perfect square less than k-just what you were looking for. The operation of rounding to the largest integer less than or equal to a given number is often called floor. Thus, in the general case of k lockers, there will be floor(sqrt(k)) lockers remaining open.

The key to solving this problem is trying strategies to solve parts of the problem even when it isn’t clear how these parts will contribute to the overall solution. Although some attempts, such as the investigation of prime numbered lockers, may not be fruitful, others are likely to lead to greater insight about how to attack the problem, such as the strategy of calculating the result for a single locker. Even in the worst case, where none of the things you try lead you closer to the final solution, you show the interviewer that you aren’t intimidated by difficult problems with no clear solution and that you are willing to keep trying different approaches until you find one that works.

- Anil January 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

your way of explaining is really good.Good explaination

- Anonymous February 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

thanks for such a lucid description of the problem. :)

- Abhay February 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 4 vote

1 4 9 16 25 36 49 64 81 100 remain closed

- Anonymous January 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Doors with " Even Number of Factors " remains opened.
and Doors with " ODD " number of factors remains closed.

- Vijay Rajanna January 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

sqrt(N) door would be closed
because when we make factor of perfect squares it have odd numbers of factor
for eg:
N=15
1*15
3*5
5*3
15*1
even factors
for 19
19*1
1*19
even factors
28
1*28
2*14
4*7
7*4
14*2
28*1
even factor
no let the case of perfect square
16
1*16
2*8
4*4
8*2
16*1
odd factors so only the perfect square door would not be doggle remain in same state other all chnge its state....

- Anonymous January 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

sqrt(N) door would be closed
because when we make factor of perfect squares it have odd numbers of factor
for eg:
N=15
1*15
3*5
5*3
15*1
even factors
for 19
19*1
1*19
even factors
28
1*28
2*14
4*7
7*4
14*2
28*1
even factor
no let the case of perfect square
16
1*16
2*8
4*4
8*2
16*1
odd factors so only the perfect square door would not be doggle remain in same state other all chnge its state....

- dabbcomputers January 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//run the doorStatus for each door (doorNum - 1 to 100).
//Assumption is that function countFactors (int) is returning the number of factors of inpteger

doorStatus(int doorNum) {
if (doorNum > 1)
numberOfFactors = countFactors (doorNum-1);
else
numberOfFactors = numOfDoors;

cout <<"Door "<<doorNum<<"is "<<(doorStatus(numberOfFactors) == true ? "open":"close");
}

bool doorStatus (int numberOfFactors) {
if (numberOfFactors % 2) {
return false;
}
return true; //door is open

- Himanshu January 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Perfect squares will be closed, i.e. 1,4,9,16,25,36,etc will be closed (because these numbers have even number of devisors and hence even number of toggles will make the final state as intial state).
Note:- Considering the initial state after the 1st toggled all the doors.

- Niranjan January 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

hey, but i tried it out with a 12 lockers.. here assuming all lockers to be initially closed, the final configuration comes out to be in this way,
open, close close open close close close close open close close open
and this series must continue.. so i don't think your logic on all those perfect squares etc. wont work fine with this... Please correct me if am wrong..
So, in case of 100 lockers, the above series repeats..

- Chandana January 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Certain numbers that have odd number of factors will be CLOSED and every number with even number of factors will be OPEN. For every prime square that is less than 100, the door will be closed. The first door will also be closed. The rest of the doors will be open.

So, doors numbered 2^0 , 2^2 , 2^4 , 2^6 , 2^2 * 3^2 , 3^2 , 3^4 , 2^2*5^2 , 5^2 , 7^2 will be closed; i.e doors 1 , 4 , 9 , 16 , 25 , 36 , 49 , 64 and 81 and 100. Rest of the doors will be open

- Ani April 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

only the numbers which are perfect squares will be open,all other doors will be closed.since the square numbered doors have odd number of factors

- sreejadas.jucse June 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class dolapsorusu {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int s=0;
boolean[] doors = new boolean[101];
for (int i = 1; i <= 100; i++) {
for (int j = i; j <= 100; j++) {{
if(j % i == 0) doors[j] = !doors[j];

} }
}
for (int i = 1; i <= 100; i++) {
System.out.printf("Door %d: %s%n", i, doors[i] ? "opened" : "closed");
}
for(int i=1;i<=100;i++){
if(doors[i]==true){
s=s+1;
}
}
System.out.println("\n"+s+"doors is open ");


}
}

- facebook.com/honestrockk August 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

the answer is every even door is open and odd door is closed.
The solution goes this way: Each person can toggle a door which is a multiple of their number. that is first person can toggle all doors. second person can toggle only doors that are multiples of 2 and so on. If this process continues, it shows that nth door will be toggled n times. So even number doors will be toggled even number of times, so they remained open and odd numbered doors will be toggled odd number of times which keeps them closed.

- krishna chaitanya January 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

All Doors are open
1. User 1 closes all doors
2. Hence all prime nos will open the doors
3. All perfect squares will close the doors
4. 6 - 2 would open, 3 would close and 6 would open is again
5.8 - 2 would open, 4 would close and 8 would open again
6. 10 - 2 would open, 5 would close and 10 would open
7. 12 - 2 would open, 3 would close, 4 - 0, 6 - C, 12 - O
8. 15- 3-O,5-C,15-O
9. 30- 2-O,3-C,5-O,10-C,30-O
10.42-2-O,3-C,7-O,21-C,42-O

- tester January 17, 2012 | Flag


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