Microsoft Interview Questions 1

Question:

Find the defective ball out of 8 ballsYou have 8 balls. One of them is defective and weighs less than others. You have a balance to measure balls against each other. In 2 weightings how do you find the defective one?

Answer
1.Picks 3 balls on the left and 3 balls on the right, if they are balanced, pick the other 2 balls to measure.

2. If 3 left balls is lesser weights in the first step, pick two out of three to be measured again, if they are balanced, you know the last ball is the defective one. Easy! Right?


Question:

CRAZY GUY ON THE AIRPLANE
A line of 100 airline passengers is waiting to board a plane. they each hold a ticket to one of the 100 seats on that flight. (for convenience, let's say that the nth passenger in line has a ticket for the seat number n.)
Unfortunately, the first person in line is crazy, and will ignore the seat number on their ticket, picking a random seat to occupy. all of the other passengers are quite normal, and will go to their proper seat unless it is already occupied. if it is occupied, they will then find a free seat to sit in, at random.
What is the probability that the last (100th) person to board the plane will sit in their proper seat (#100)?

First Way of Doing It:
Let P(i) = probability that the ith person after the crazy guy loses their seat. What we want to know is P(99).
P(1) = 1/100 (the crazy guy picks seat 1). Notice that it is not 1/99 - the crazy guy could pick his own seat since he selects purely by random.
P(2) = 1/100 (crazy guy picks his seat) + P(1)*1/99 (crazy guy picks the first guy's seat, and the first guy picks the second guy's seat).
Following this sequence, we get the following recursive relationship:
P(n) = P(n-1)(1/(101-n))
If we start to work this relationship out, we get a surprising answer:
P(1) = 1/100
P(2) = 1/99
P(3) = 1/98
and, more generally,
P(n) = 1/(101-n) ( for n<100)
Thus, P(99) = 1/(101-99) = 1/2
Second Way of Doing It:
Let's start simply with 2 people. There a only 2 possible permutations (2x1) which are;
1 2
2 1
person 2 sits in his seat 1 out of the 2 possible combinations or 1/2.
Now 3 people. There are a total of 6 permutations (3x2x1) however 2 are not possible in this scenario as each person will sit in their seat if it is available. Therefore, apart from position 1, you cannot have a higher number in a particular position number. The impossible combinations I have marked with **
1 2 3
1 3 2 **
2 1 3
3 1 2
2 3 1 **
3 2 1
person 3 sits in his seat 2 out of the 4 possible combinations 2/4 = 1/2.
Now 4 people. There are a total of 24 permutations (4x3x2x1) and in this case there are 16 combinations that are not possible (marked **)
1 2 3 4
1 2 4 3 **
1 3 2 4 **
1 3 4 2 **
1 4 2 3 **
1 4 3 2 **
2 1 3 4
2 1 4 3 **
3 1 2 4
3 1 4 2 **
4 1 2 3
4 1 3 2
2 3 1 4 **
2 4 1 3 **
3 2 1 4
3 4 1 2 **
4 2 1 3
4 3 1 2 **
2 3 4 1 **
2 4 3 1 **
3 2 4 1 **
3 4 2 1 **
4 2 3 1
4 3 2 1 **
person 4 sits in his seat 4 out of the 8 possible combinations 4/8 = 1/2.


Question:
100 DOORS IN A ROW

You have 100 doors in a row that are all initially closed. you make 100 passes by the doors starting with the first door every time. the first time through you visit every door and toggle the door (if the door is closed, you open it, if its open, you close it). the second time you only visit every 2nd door (door #2, #4, #6). the third time, every 3rd door (door #3, #6, #9), etc, until you only visit the 100th door.
Question: what state are the doors in after the last pass? which are open which are closed?
• The state of the door depends on the number of times it will be visited as follows:
if the number of times it is visited is even - the door will end up closed
otherwise - the door will end up open
• The number of times each door is visited is directly related to the number of dividers the number (door number) has (including 1 and itself).
• For example, every prime number door will be visited twice, and hence ends up closed
• Now, for every divisor of a number there must exist another divisor - that other devisor is the result of dividing with the first divisor! So, divisors for a number come in pairs... except for... when the number is a square of a divisor.
• If the number is a square of a divisor, then it means it has one divisor - the square root - that does not have a pair. Dividing the number by it's square root yields the square root itself, and not a new divisor.
• hence numbers that have an integer square root have an odd number of divisors, while numbers that do not have an integer square root do not.
• Therefore only 1,4,9,16,25,36,49,64,81,100 will be opened! and you don't need to write a computer program to solve this (which was certainly not the purpose of the question in an interview setting)