## Monday 12 November 2012

## Solution of 100 door puzzle....microsoft interview puzzle

**Solution:**

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.

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.

## Solution of 2 Egg Problem: Google Interview Puzzle

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

## Village of demons & sleeping man puzzle....tricky puzzle

**Question:**

given a village with demons and a sleeping man, The man is always sleeping ,never wakes up. Now a demon can eat the sleeping man , but after that

he will fall asleep , any demon can eat another sleeping demon.

If demons are very smart and would always choose to stay alive than to eat the man and risk their lives.

so if initially there are 65 demons and 1 sleeping man .. what would happen in the village ??

he will fall asleep , any demon can eat another sleeping demon.

If demons are very smart and would always choose to stay alive than to eat the man and risk their lives.

so if initially there are 65 demons and 1 sleeping man .. what would happen in the village ??

## Find bad apples from boxes in 1 attempt...!!!

**Question:**

There are 10 boxes of apples. Each apple in the boxes weights 1 pound, except that one of the boxes contains bad apples, which weights 0.9 pound each. You are given a digital weight (not a scale), and you can take apples out of the boxes. what is the minimum time of weighs to find out which box has bad apples?

**Solution:**

it's simple:

take 1 apple from box 1, 2 apples from box 2 ... 10 apples from box 10

take 1 apple from box 1, 2 apples from box 2 ... 10 apples from box 10

## Move block in matrix

**Question:**

Given a m*n matrix and a person is sitting in (0,0) box, and he has to go to the (m-1,n-1) box of the matrix .And the person can only go to right or down box from its current box position . We need to find out the number of ways he can reach from start to destination box .

## 100 prisoner`s hat problem..

**Question:**

There are 100 prisoners , and a officer of them . Now the officer gave the command to the prisoner that next day they will be going to wear a hat which they will not be know its colour . But its colour will be either Red or Blue . And he says that all the prisoner will be standing in a line .

And then the officer will start asking the color of the prisoner one by one from the back . whichever prisoner says the wrong color of his hat ,gets shoot .So now we have to find out wat strategy should the prisoners should apply to safe maximum prisoners .

## 17 min bridge crossing puzzle

**Puzzle:**

There are four people who want to cross a bridge; they all begin on the same side. You have 17 minutes to get them all across to the other side. It is night, and they have one flashlight. A maximum of two people can cross the bridge at one time. Any party that crosses, either one or two people, must have the flashlight with them.

The flashlight must be walked back and forth; it cannot be thrown, for example. Person 1 takes 1 minute to cross the bridge, person 2 takes 2 minutes, person 3 takes 5 minutes, and person 4 takes 10 minutes. A pair must walk together at the rate of the slower person’s pace. For example, if person 1 and person 4 walk across first, 10 minutes have elapsed when they get to the other side of the bridge. If person 4 returns the flashlight, a total of 20 minutes have passed and you have failed the mission.

## What are your weaknesses? (HR interview)

**TRAPS**

**:**Beware - this is an eliminator question, designed to shorten the candidate list. Any admission of a weakness or fault will earn you an “A” for honesty, but an “F” for the interview.

**PASSABLE ANSWER:**

Disguise a strength as a weakness.

__Example__:*“I sometimes push my people too hard. I like to work with a sense of urgency and everyone is not always on the same wavelength.”*

__Drawback:__*This strategy is better than admitting a flaw, but it's so widely used, it is transparent to any experienced interviewer.*

## What are your greatest strengths? (HR interview)

**TRAPS:**This question seems like a softball lob, but be prepared. You don't want to come across as egotistical or arrogant. Neither is this a time to be humble.

**BEST ANSWER:**You know that your key strategy is to first uncover your interviewer's greatest wants and needs before you answer questions. And from Question 1, you know how to do this.

## Tell me about yourself (HR interview)

**TRAPS**

**:**Beware, about 80% of all interviews begin with this “innocent” question. Many candidates, unprepared for the question, skewer themselves by rambling, recapping their life story, delving into ancient work history or personal matters.

**BEST ANSWER:**

Start with the present and tell why you are well qualified for the position. Remember that the key to all successful interviewing is to match your qualifications to what the interviewer is looking for. In other words

*you must sell what the buyer is buying. This is the single most important strategy in job hunting.*## 9 card puzzle

**Question:**

9 cards are there. u have to arrange them in a 3*3 matrix.

cards are of 4 colors.they are red,yellow,blue,green.

conditions for arrangement: one red card must be in first row

or second row.2 green cards should be in 3rd column.Yellow

cards must be in the 3 corners only. Two blue cards must be in

the 2nd row. Atleast one green card in each row.

## 100 door puzzle....microsoft interview puzzle

**Question:**

Lets say you have a room with 100 doors in it. Initially, all of these doors are open. You have 100 people that will be entering the room. The 1st person toggles every door, 2nd person toggles every other door, 3rd toggles every 3rd door, ... , nth person toggles every nth door. How would you determine the state of all 100 doors after all 100 people have entered the room?

## 1000 barrels Puzzle

**Question:**

A king is about to give a party in 24 hours. For the party they have arranged drinks which will be served through 1000 barrels. Out of jealousy , some one near to king has poisoned one of the barrels. The poison is so strong that even a drop can kill a person. But results are not immediate. A person may die from 13 to 20 hrs. Now king has a duty of finding that barrel. He has 24 hours with him. And he has unlimited prisoners on which the drinks can be tested. Find out the maximum prisoners he would need to find out that barrel.

## count the number of students in a classroom in quickest way

**Question:**

How will you count the number of students in a classroom in quickest possible manner.

**Solution:**

Ask the class to stand up and make pairs, if one student is left out write '1' else write 0. tell the left out student to sit down and ask one person in each group to sit down. Repeat the process and append '1' or '0' to your number, until no student is left standing. You will get the binary representation of the number of students in reverse order.

## Find shortest path in an array

**Question:**

Given a character array. Find if there exists a path from O to X. Here is an example

. . . . . . .

. . . . . . .

w . . . . . .

w .w.w..

. . . . O . .

. . w. . . .

. . . X . . .

. . . . . . .

w . . . . . .

w .w.w..

. . . . O . .

. . w. . . .

. . . X . . .

**Solution:**

This can be solved by Simple Depth First Search using Recursion..

// 8 Adjacent points

int dx[]={+0,+0,+1,-1,+1,+1,-1,-1};

int dy[]={+1,-1,+0,+0,+1,-1,+1,-1};bool visited[50][50];

string grid[50];

int m=50,n=50;

bool dfs(int x,int y){

if(grid[x][y]=='X')return 1;

## 3black and 2 white cap tricky puzzle

**Question:**

3 black caps and 2 white caps

randomly 3 caps are chosen and A,B,C are made to wear

they are standing in que and A can see B nC , B can only see C and C cant see anyone

A is asked which cap are you wearing? Ans from A was he dont knw

B was asked which cap is he wearing? B answered I dont know

But when asked C , he gave the correct answer

The question was...which color cap was C wearing?

## Red Marbles and Blue Marbles puzzle...goggle puzzle

**Problem:**

## Flying bird from trains puzzle(Bumblebee)

**Question:**

Two trains enter a tunnel 200 miles long (yeah, its a big tunnel) travelling at 100 mph at the same time from opposite directions. as soon as they enter the tunnel a supersonic bee flying at 1000 mph starts from one train and heads toward the other one.

as soon as it reaches the other one it turns around and heads back toward the first, going back and forth between the trains until the trains collide in a fiery explosion in the middle of the tunnel (the bee survives). how far did the bee travel?

## Coins on the Table : Microsoft Puzzle

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

**Question:**

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

POST YOUR OPINION IF YOU HAVE BETTER SOLUTION

## Shopkeeper Problem with Solution

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

## Daughters’ Ages

**Question:**

Two MIT math grads bump into each other at Fairway on the upper west side. They haven’t seen each other in over 20 years.

**THE FIRST GRAD SAYS TO THE SECOND**: “how have you been?”

**SECOND**: “great! i got married and i have three daughters now”

**FIRST**: “really? how old are they?”

**SECOND**: “well, the product of their ages is 72, and the sum of their ages is the same as the number on that building over there..”

**FIRST**: “right, ok.. oh wait.. hmm, i still don’t know”

**SECOND**: “oh sorry, the oldest one just started to play the piano”

**FIRST**: “wonderful! my oldest is the same age!”

## 100 Doors in a Row...microsoft puzzle

**Question:**

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?

### Solution:

For example, after the first pass every door is open. on the second pass you only visit the even doors (2,4,6,8…) so now the even doors are closed and the odd ones are opened. the third time through you will close door 3 (opened from the first pass), open door 6 (closed from the second pass), etc..

## 13 Balls problem : One of Hardest Interview Questions

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.

## Door Toggling Puzzle Or 100 Doors Puzzle

**Question:**

This is a very common interview puzzle. The problem is very simple if you understand it. So the point to note is, do not arrive at the solution so "fast”, if you are asked this puzzle in an interview and if you are not planning to show any acquaintance with this puzzle.

Problem goes like this :

There are N doors in a row numbered from 1 to N. Initially all are closed.

Then you make N passes by the N doors. In pass 1 you toggle the all the doors (1,2,3,4....)starting from the first door. In the second pass you toggle every second door(2,4,6,8,...). In the third pass you toggle all third doors(3,6,9...).Similarly you make N passes.

## Polar Bear : Microsoft Interview Question

**Question:**

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.

## 3 Classic Weighing puzzles :Simple Medium and Hard (Google puzzle)

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.

## 100 Doors Puzzle Or Door Toggling Puzzle

**Question:**

This is a very common interview puzzle. The problem is very simple if you understand it. So the point to note is, do not arrive at the solution so "fast”, if you are asked this puzzle in an interview and if you are not planning to show any acquaintance with this puzzle.

Problem goes like this :

There are N doors in a row numbered from 1 to N. Initially all are closed.

Then you make N passes by the N doors. In pass 1 you toggle the all the doors (1,2,3,4....)starting from the first door. In the second pass you toggle every second door(2,4,6,8,...). In the third pass you toggle all third doors(3,6,9...).Similarly you make N passes.

## 2 Egg Problem: Google Interview Puzzle

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.

**Question:**

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