Microsoft Interview Question : Polar Bear

One of the most asked and well known microsoft interview question is that of the walking bear.The question is still asked because a lot of people have either not heard of it or most of them don't know the correct solution yet.

If a bear walks one mile south, turns left and walks one mile to the east and then turns left again and walks one mile north and arrives at its original position, what is the color of the bear.

Well,from the very framing of the question it is evident that we r talking about the poles,and all polar bears are white.You can also very well argue that any bear or man walking the same path will reach the same starting position if he is at north
pole.The question can also be extended and that's what we are interested in.

The question is how many such points exists on the surface of the globe.
Well,whats your answer,is it one or infinity

Microsoft Puzzle : Coins on the Table

This is not one of the classic Microsoft puzzle. I recently heard from a friend. I am listing the problem below.

There is a table on which a number of coins are placed. You also know that there are as many coins with Head up as many coins with Tail up. Now you have to divide the coins (number of coins is even) into two equal piles such that number of coins with Heads up and Tails up in either piles be the same. The catch is you are blind folded and you cannot determine the sides (for sure) if you are blinded

Solution to the Shopkeeper Problem

I don't think I need to post the solution as Christophe has already solved all of them in no time.

Problem 1: One Side Only (Simple)

This is simply the numbers 2^0,2^1,2^2 ….. that is 1,2,4,8,16 ……….
So for making 1000 kg we need up to
1, 2, 4, 8, 16, 32, 64, 128, 512.

Problem 2: Both Sides (Medium)

For this answer is 3^0,3^1,3^2 …. That is 1,3,9,27,81,243,729

Problem 3: Incremental (Hard)

This is exactly a problem solved by Gray code.

Gray codes are named after the Frank Gray who patented their use for shaft encoders in 1953
A Gray code represents each number in the sequence of integers {0...2^N-1} as a binary string of length N in an order such that adjacent integers have Gray code representations that differ in only one bit position. Marching through the integer sequence therefore requires flipping just one bit at a time.

Example (N=3): The binary coding of {0...7} is {000, 001, 010, 011,
100, 101, 110, 111}, while one Gray coding is {000, 001, 011, 010,
110, 111, 101, 100}.

For this answer we need as many blocks as per Solution to Problem 1.
For easy understanding let me describe the case where the packets range from 1 to 7 which can be easily extended to 1 - 125 range.
Now if we want to make packets of all weights from 1 to & we will do the following

001 We measure 1kg,using 1kg block.
011 We measure 3kg by placing 2 kg block also
010 We remove 1kg block and measure 2 kg.
110 We add 4kg weight and measure 6kg weight …
………….

Now we can see answer to our problem is Gray code of 7 bits. Now our range is 1 to 125 and not 1 to 127.This can be solved by using appropriate Gray code making the following numbers falling to the end of the sequence you are starting with
1111 110
1111 111

Job Interview Puzzle: 3 Classic Weighing puzzles :Simple Medium and Hard

In this post I want to describe about a series of puzzles called weighing puzzles. These puzzle vary in hardness from simple to extremely mathematical involving either expertise in some fields or extreme ingenuity. Either you know it or you figure out it using extreme intelligence. So here is the chance for some people to burn your grey cells.

I am putting forward three puzzles with varying range of hardness. Sometimes you may feel the hardest one is very easy for you have already come across the theory, but I still made it the hardest for the people who will be solving it with out knowing the theory behind it, giving them an option to figure out a small part in evolution of computational history.

There is a shopkeeper who wants to weigh things who has a common balance. He must be in a position to weigh things of all possible integral weighing units from 1 to a given maximum sum. The question will be either about how many weights you will need or how will you weigh.

Problem 1: One Side Only (Simple Interview Question for Phone Screening usually)

In this version of the problem shopkeeper can only place the weights in one side of the common balance. For example if shopkeeper has weights 1 and 3 then he can measure 1,3 and 4 only. Now the question is how many minimum weights and name the weights you will need to measure all weights from 1 to 1000. This is a fairly simple problem and very easy to prove also.

Problem 2: Both Sides (Medium:5 to 10 mins onsite interview question)

This is same as the first problem with the condition of placing weights on only side of the common balance being removed. You can place weights on both side and you need to measure all weights between 1 and 1000.For example if you have weights 1 and 3,now you can measure 1,3 and 4 like earlier case, and also you can measure 2,by placing 3 on one side and 1 on the side which contain the substance to be weighed. So question again is how many minimum weights and of what denominations you need to measure all weights from 1kg to 1000kg.

Problem 3: Incremental (Hard)

This is an altogether different one in the same scenario. You have to make 125 packets of sugar with first one weighing 1 kg, second 2 kg, third 3 kg etc ...and 125th one weighing 125kg.You can only use one pan of the common balance for measurement for weighing sugar, the other pan had to be used for weights i.e. weights should be used for each weighing.
It has come into notice that moving weights into and out of the pan of the balance takes time and this time depends on the number on the number of weights that are moved. For example - If we need to measure 4 kg using weights 1 and 3 only, it will take twice as much time needed to measure 1 kg. Lets say we want to make sugar packets of weights 1,3,4 using weights 1 and 3 only. For this first we measure 1 kg, with 1 unit of time, we place 3 kg along with 1 kg and measure 4kg with again 1 unit of time, and finally we move 1kg out of pan to measure 3kg in 1 unit of time. So in 3 units of time we could measure 1,3 and 4kg using weights 1 and 3 only.

Now you have to make sugar packets of all weights from 1 to 125 in minimum time, in other words in minimum movement of weights. The question here is to find out the minimum number of weighs needed and the weight of each the weights used and the strategy to be followed for the creation of 125 packets of sugar.


Please post your solutions as comments.Solution will be posted soon in the blog.If any where its obfuscated or simple wrong pls feel free to correct.

Solution to the 13 Balls Problem

Solution for 12 Ball Problem

NOTE : N represents a normal ball

Name the 12 balls as A1,A2,A3,A4,B1,B2,B3,B4 C1,C2,C3 and C4.We will weigh A's on one side and B's on the other side.
A1 A2 A3 A4 <---> B1 B2 B3 B4
If Both weighed same then the odd ball is among C's.
We have to find the odd ball among 4 balls using 2 weightings.For that we balance

C1 C2 with C3 N.

Now if C1 C2 equals C3 N then C4 is the odd one.

Now suppose C1 C2 is heavier than C3 N then we compare
C1 C3 to N N
Now if C1 C3 equals to N N the C2 is the odd ball.
If C1 C3 is lighter than N N, then C3 is the odd ball.
If C1 C3 is heavier than N N then C1 is the odd ball.


Coming to the situation where the first weighing resulted in unequal balance.Lets assume A's are heavier than B's.
ie .

A1 A2 A3 A4 > B1 B2 B3 B4

Now we compare

A1 A2 B1 B2 to N N N B4.


if A1 A2 B1 B2 > N N N B4

The odd ball is among A1 A2 or B4 and we also know that A1 A2 > B4 N.To find out the odd ball among A1 A2 and B4 we do compare

A1 B4 to N N .

if A1 B4 > N N then
A1 is the odd ball
if A1 B4 < b4 =" N" b2 =" N"> N B3 which we have already shown how to solve.


Solution for 13 ball problem is easy if we could solve 12 ball problem.For that lets assume we have an extra ball C5.Now if A's and B's dont weigh same we have all the steps already calculated.

Now if A's and B's weigh same then the odd one is among C's.

Now we compare

C1 C2 to C3 N.

If C1 C2 = C3 N then we can find out the odd ball from C4 and C5 by comparing it with any normal ball.
Else if C1 C2 > C3 N then we compare

C1 C3 to N N.
If C1 C3 > N N then C1 is the odd ball
If C1 C3 = N N then C2 is the odd ball
If C1 C3 < N N then C3 is the odd ball

13 Balls problem : One of the Hardest Interview Questions

One of the most classic puzzles involving balls is figuring out the odd one out using common balance.There are many levels of puzzles based on the same concept for different levels of interviews - Simple ones for phone interviews to the most gruelling 1 hour hard work needing hard ones.

Problem space
The general problem is you will be given n balls and one of them is either heavier or lighter and you are asked to find out the minimum number of weighings using a common balance required to find out the odd one out.

Example 1:8 Balls,Odd ball being heavier

This is the simplest question among the lot and is often used during phone screenings.The question is to find out the minimum number of weighings required to spot the odd heavier ball among 8 identically looking balls using a common balance.Answer is 2 and the solution is given in the next paragraph.

For simplicity let us name the balls as A1,A2,A3,B1,B2,B3,C1 and C2.We weigh with A's on one side and B's on the other side of the balance.If both sides are equal this means the heavier odd ball is among C1 and C2.We can figure out the heavier ball with one more weighing.If A's are heavier than B's then the heavier odd ball is among A's.Now we balance A1 and A2.If both are same then A3 is the odd ball or else the heavier one of A1 and A2 .Thus, we can find out the heavier ball using only 2 weighings.



Example 2:8 Balls,Odd ball can be either heavier or lighter than the rest.

This is a little trickier to solve.Let us name the 8 balls as A1,A2,A3,B1,B2,B3,C1 and C2.Now weigh with A1,A2,A3 on one side and B1,B2,B3 on the other side.If both weigh equal then the odd ball is among C1 and C2.Now we know that A's and B's are all normal ones we can weigh C1 with A1 and check whether C1 weighs the same as the normal ball.In this way, we can figure out in one weigh which of C1 and C2 is odd.Now if A's weighed more than B's then we know for sure C's are normal ones.Now lets assume A's heavier than B's and we still don't know whether the odd is among A's or B's.

We know
A1 A2 A3 < B1 B2 B3

Now we compare
A1 B2 B3 to B1 C1 C2 .
Now if the A1 B2 B3 is heavier than B1 C1 C2 Then it means the odd ball is among A1 and B1.If A1 B2 B3 is lighter than B1 C1 C2 then the odd ball is among B2 and B3.If A1 B2 B3 equal to B1 C1 C2 then odd ball is among A2 and A3.So we have zeroed down to 2 balls.Now its very easy as we can compare any of the normal ball with one of the 2 balls.So answer is 3,ie in 3 weighings we can find out the odd ball.

Problem

You are given 13 balls.The odd ball may be either heavier or lighter.Find out the odd ball in 3 weightings.(There is an equally difficult smaller version of the puzzle involving 12 balls also but because both require the same solution technique i am leaving that problem) Hint: I have already given the hint for this question.This mammoth looking task only requires the techniques already discussed in the page.If you have not read all the steps mentioned above i request you to please go through the above solutions carefully.


Solution will be posted soon ....
Pls post your solution as comment ...
Waiting for a trickier smarter solution ....

Google Interview Puzzle : 2 Egg Problem

My intention here is not to trouble Google interviewers. I was just collecting some classic puzzles and found this one and a small Google search showed me that this is a Google interview puzzle to my pleasant surprise. But many of the answers I found were either wrong or totally twisted. I am making no surety of the answer I give and I am open to your remarks or suggestion or corrections.

The Standard Problem in simple writing goes like this:

* You are given 2 eggs.
* You have access to a 100-storey building.
* Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical.
* You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking.
* Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process



If you are one of the people who likes to solve a puzzle before seeing the answer you must quit the blog now and come back later for checking the answer.


Now that this is a Google interview question I am taking the normal "Interview-Style" of solving a problem. Simply saying thinking aloud through the solution from worst to the best correcting the flows optimizing the solution or taking the 5-minute hard thinking acting pause to a problem, which you know already and just want to make your interviewer think that you are a challenge lover.

Solution

Drop the first egg from 50.If it breaks you can try the same approach for a 50-storey building (1 to 49) and try it from 25th floor. If it did not break try at 75th floor. And use linear search with the remaining portion of storey we need to test. For example if the first egg breaks at 50 we need to try all possibilities from 1 to 49.

Now this looks a feasible solution. In computer student's jargon do a binary search with first egg and linear search with the second one. Best case is log (100) and worst is 50.


Now the optimal solution for the problem is that you figure out that you will eventually end up with a linear search because you have no way of deciding the highest floor with only one egg (If you broke one egg and you have to find the answer among 10 all you can do is start from the lowest to the highest and the worst is the total number of floors). So the whole question grinds up to how to make use of the first egg to reduce the linear testing of the egg.


(For strict computer science students, well this problem can be solved using binary search on the number of drops needed to find the highest floor.)

Now let x be the answer we want, the number of drops required.

So if the first egg breaks maximum we can have x-1 drops and so we must always put the first egg from height x. So we have determined that for a given x we must drop the first ball from x height. And now if the first drop of the first egg doesn’t breaks we can have x-2 drops for the second egg if the first egg breaks in the second drop.

Taking an example, lets say 16 is my answer. That I need 16 drops to find out the answer. Lets see whether we can find out the height in 16 drops. First we drop from height 16,and if it breaks we try all floors from 1 to 15.If the egg don’t break then we have left 15 drops, so we will drop it from 16+15+1 =32nd floor. The reason being if it breaks at 32nd floor we can try all the floors from 17 to 31 in 14 drops (total of 16 drops). Now if it did not break then we have left 13 drops. and we can figure out whether we can find out whether we can figure out the floor in 16 drops.

Lets take the case with 16 as the answer

1 + 15 16 if breaks at 16 checks from 1 to 15 in 15 drops
1 + 14 31 if breaks at 31 checks from 17 to 30 in 14 drops
1 + 13 45 .....
1 + 12 58
1 + 11 70
1 + 10 81
1 + 9 91
1 + 8 100 We can easily do in the end as we have enough drops to accomplish the task


Now finding out the optimal one we can see that we could have done it in either 15 or 14 drops only but how can we find the optimal one. From the above table we can see that the optimal one will be needing 0 linear trials in the last step.

So we could write it as

(1+p) + (1+(p-1))+ (1+(p-2)) + .........+ (1+0) >= 100.

Let 1+p=q which is the answer we are looking for

q (q+1)/2 >=100

Solving for 100 you get q=14.
So the answer is: 14
Drop first orb from floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100... (i.e. move up 14 then 13, then 12 floors, etc) until it breaks (or doesn't at 100).

Please feel free to correct or post any comment on the solution or the answer.

Links I found useful

OR/MS Games: 4. The Joy of Egg-Dropping in Braunschweig and Hong Kong

Puzzle from Techinterview.org

http://blog.taragana.com/index.php/archive/google-and-the-puzzle-of-dropping-eggs/