Brainstorm

## 2. more brainstorm questions

### stupid prime number problem.

http://www.tekpool.com/?p=18

### numbers

#### general

• A number is divisible by 2 if its last digit is 0, 2, 4, 6 or 8.
• A number is divisible by 3 if the sum of its digits is divisible by 3.
• A number is divisible by 4 if the number formed by its last two digits is divisible by 4.
• A number is divisible by 5 if its last digit is 0 or 5.
• A number is divisible by 6 if it is divisible by 2 AND it is divisible by 3.
• A number is divisible by 8 if the number formed by its last three digits is divisible by 8.
• A number is divisible by 9 if the sum of its digits is divisible by 9.
• A number is divisible by 10 if its last digit is 0.

#### locks

Suppose you are in a hallway lined with 100 closed lockers. You begin by opening all 100 lockers. Next, you close every second locker. Then you go to every third locker and close it if it is open or open it if it is closed (call this toggling the locker). You continue toggling every nth locker on pass number n. After your hundredth
pass of the hallway, in which you toggle only locker number 100, how many lockers are open?

Answer : 1, 4,9,16,25,36,49,64,81,100= 10 opens.

In a hall with k lockers, how many lockers remain open after pass k?
Thus, in the general case of k lockers, there will be floor(sqrt(k)) lockers remaining open.

#### factors

How many zeros are there at the end of 100! (factorial)?

Answer: each pair of 2 and 5 will generate a 0, however, the frequency of 2 will out number the frequency of
5

number of factors of 5 in 100 = [100/5] + [100/5^2] + [100/5^3] + … = 20 + 4 + 0 + … = 24
number of factors of 2 in 100 = [100/2] + [100/2^2] + [100/2^3] + … = 50 + 25 + 0 + … = 97

The smaller of the two is 24, so the highest power of 10 dividing 100

### three lights

Q: You are standing in a hallway next to three light switches, all of which are off. Each switch operates a different incandescent light-bulb in the room at the end of the hall. You cannot see the lights from where the switches are. Determine which light corresponds to each switch. You may go into the room with the lights only once.

A: You can determine which switch goes with each bulb by turning the first switch on, and the second and third off. After ten minutes, turn the first switch off, leave the second off, and turn the third on. When you go into the room, the hot dark bulb corresponds to the first switch, the cold dark bulb to the second, and the lit bulb to the third.

### drop eggs from building

http://www.jokelibrary.net/education/m_files/m4s-eggs.html

### marbles

You have eight marbles and a two-pan balance. All the marbles weigh the same, except for one, which is heavier than all the others. The marbles are otherwise indistinguishable. You may make
no assumptions about how much heavier the heavy marble is. What is the minimum number of weighings needed to be certain of identifying the heavy marble?

Answer: you can identity up to 3n marbles in max n measures. ceiling(log3(m)).

if you don't know it is either heavier or lighter. you can identify up to (3n-3)/2 balls in max n measures. ceiling(log3(2m+3)).

### balls

you have 20 blue balls and 14 red balls in a bag. you put your hand in and remove 2 at a time. if they're of the same color, you add a blue ball to the bag. if they're of different colors, you add a red ball to the bag. (assume you have a big supply of blue & red balls for this purpose. note: when you take the two balls out, you don't put them back in, so the number of balls in the bag keeps decreasing). what will be the color of the last ball left in the bag?

once you tackle that, what if there are 20 blue balls and 13 red balls to start with?

A:You always take off Red Balls two by two !

here is why you take off Red Balls 2 by 2 :
- If you take off 1 RED and 1 BLUE, in fact you will take off 1 BLUE
- If you take off 2 RED, in fact you will take off 2 RED (and add 1 BLUE)
- If you take off 2 BLUE, in fact you will take off 1 BLUE

So if you start with 14 Red Balls, you cannot have one single Red ball at the end.

… so the last ball is blue.

But if you start with 13 Red Balls, as you take them off 2 by 2 (at one moment or the other you'll do it !) you will arrive at a moment when you have 1 red ball in the bag. But as you can only take off Red Balls 2 by 2 (Did I already say that ?!) you'll remove the last Blue Balls, one by one……

So the last ball will be red…

### estimation

#### gas station

"How many gas stations are there in the United States?

Taking the gas station problem as an example, your calculation might go like this:

1)It takes me about 6 minutes to fill up my car. I go to the gas station about once a week, and there are usually two other cars there. If I assume this is average for Americans, each gas station services about 30 cars an hour.

2)Suppose a gas station were open 12 hours a day, 7 days a week. That would be 84 hours a week. In reality, a gas station is probably open more than 12 hours a day, so I'll say the average gas station is open 100 hours a week. That means it services 3,000 cars a week.(100hours * 30 cars/hr)

3) There's somewhere upwards of 250 million people in the United States. Not everyone has a car, so say there are 100 million cars on the road. If every car goes to the gas station once a week, like mine does,

4) as each station sees 3,000 cars a week, there would have to be about 33,000 gas stations in the United States. = 100 million cars/week / 3000 cars/week/gas station

### how to test it is a power of 2 of a number

isPow2 = x && !( (x-1) & x );

Algorithm:
If x is a power of two, it doesn't have any bits in common with x-1, since it
consists of a single bit on. Any positive power of two is a single bit, using
binary integer representation.

This means that we test if x-1 and x doesn't share bits with the and operator.

Of course, if x is zero (not a power of two) this doesn't hold, so we add an
explicit test for zero with xx && expression.

Negative powers of two (0.5, 0.25, 0.125, etc) could share this same property
in a suitable fraction representation. 0.5 would be 0.1, 0.250 would be 0.01,
0.125 would be 0.001 etc.
http://www.velocityreviews.com/forums/t315506-test-whether-a-number-is-a-power-of-2.html

### pirates problem.

five pirates have 100 gold coins. they have to divide up the loot. in order of seniority (suppose pirate 5 is most senior, pirate 1 is least senior), the most senior pirate proposes a distribution of the loot. they vote and if at least 50% accept the proposal, the loot is divided as proposed. otherwise the most senior pirate is executed, and they start over again with the next senior pirate. what solution does the most senior pirate propose? assume they are very intelligent and extremely greedy (and that they would prefer not to die).

(to be clear on what 50% means, 3 pirates must vote for the proposal when there are 5 for it to pass. 2 if there are 4. 2 if there are 3. etc… )

solution: most of the time i get people who give answers like "the most senior pirate takes half and divides the rest up among the least senior pirates." um, you missed the whole point to begin with. sorry.

any answer without a specific logic behind it is invalid. if i ask you why pirate 5 gave x coins to pirate 1, please don't say "because he's nice".

now for the real solution. pirate 5 being the most senior knows that he needs to get 2 other people to vote for his solution in order for him not to be executed. so who can he get to vote for him, and why would they choose to vote for him? if you start thinking that pirate 4 will never vote for him, because he would rather have 5 die and then be in charge and take it all for himself, you are on the right track. but it gets more complicated.

lets consider if there were only 1 pirate. obviously he would take it all for himself and no one would complain.

if there were 2 pirates, pirate 2 being the most senior, he would just vote for himself and that would be 50% of the vote, so he's obviously going to keep all the money for himself.

if there were 3 pirates, pirate 3 has to convince at least one other person to join in his plan. so who can he convince and how? here is the leap that needs to be made to solve this problem. pirate 3 realizes that if his plan is not adopted he will be executed and they will be left with 2 pirates. he already knows what happens when there are 2 pirates as we just figured out. pirate 2 takes all the money himself and gives nothing to pirate 1. so pirate 3 proposes that he will take 99 gold coins and give 1 coin to pirate 1. pirate 1 says, well, 1 is better than none, and since i know if i don't vote for pirate 3, i get nothing, i should vote for this plan.

now we know what happens when there are 3 pirates. so what happens with 4? well pirate 4 has to convince 1 other person to join in his plan. he knows if he walks the plank then pirate 3 will get 99 coins and pirate 1 will get 1 coin. pirate 4 could propose giving pirate 1 two coins, and surely pirate 1 would vote for him, since 2 is better than 1. but as greedy as he is, pirate 4 would rather not part with 2 whole coins. he realizes that if he gets executed, then pirate 3's scenario happens and pirate 2 gets the shaft in that scenario (he gets zero coins). so pirate 4 proposes that he will give 1 coin to pirate 2, and pirate 2 seeing that 1 is better than 0 will obviously vote for this plan.

a common objection is that pirate 2 is not guaranteed to vote for this plan since he might hope for the case when there are only 2 pirates and then he gets all the booty. but that is why i said that the pirates are extremely intelligent. pirate 2 realizes that pirate 3 is smart enough to make the optimal proposal, so he realizes that there will never be 2 pirates left, because 3 doesn't want to die and we just showed that 3 has a winning proposal.

so lets sum up at this point

Pirate 1 2 3 4 5
5. ? ? ? ? ?
4. 0 1 0 99 -
3. 1 0 99 - -
2. 0 100 - - -
1.100

once you see the pattern it becomes very clear. you have to realize that when a pirate's plan does not succeed then that means you are in the same situation with one less pirate.
1. pirate 1 needs 0 other people to vote for him. so he votes for himself and takes all the money. 2. pirate 2 needs 0 other people to vote for him. so he votes for himself and takes all the money. pirate 1 gets 0. 3. pirate 3 needs 1 other person to vote for him. he gives 1 coin to pirate 1 for his vote - if we are reduced to 2 pirates, pirate 1 gets 0 so pirate 1 knows 1 is better than none. pirate 3 takes 99. pirate 2 gets 0. 4. pirate 4 needs 1 other person to vote for him. he gives 1 coin to pirate 2 - if we reduce to 3 pirates, pirate 2 gets 0 so pirate 2 knows 1 is better than none. pirate 4 takes 99. pirate 3 gets 0. pirate 1 gets 0. 5. pirate 5 needs 2 other people to vote for him. its clear now that the 2 people he needs to convince are the 2 who get shafted in the 4 pirate scenario - pirate 3 and pirate 1. so he can give them each 1 coin (which is better than 0 - what they would get otherwise) and keep 98 for himself.

Pirate 1 2 3 4 5
5. 1 0 1 0 98

what happens if there are 15 pirates? pirate 15 needs 7 other people to vote for him, so he recruits pirates 13,11,9,7,5,3, and 1 with 1 coin each and keeps 93 coins himself. those pirates will all vote for him because they know that they get 0 coins if he dies and pirate 14 is in charge.

hope you enjoyed this one. its my favorite interview question of all. it really allows the candidate to ask a lot of interesting questions and its really amazing when they reach the solution all by themselves (as all fogcreek employees have done so far).

http://www.techinterview.org/Puzzles/fog0000000072.html

#### 25 horses

There are 25 horses and you need to figure out the three fastest horses by placing them into races. Assume there is no tie in the speed. There are five tracks so for each race, you can place five horses and figure out the relative rank among those five horses but you don't have the exact finishing time, i.e. there is no direct comparison between results from two different races. What's the minimum number of races you need to arrange in order to figure out the three fastest horses?

A是最快的，不用比了，DE are out，也不用比了

C2 不需要拿出来比较，因为B1 已经排在C1的前面。

so total is 7.

#### fuse

You are given two fuses and a lighter. When lit, each fuse takes exactly one hour to burn from one end to the other. The fuses do not burn at a constant rate, though, and they are not identical. In other words, you may make no assumptions about the relationship
between the length of a section of fuse and the time it has taken or will take to burn. Two equal lengths of fuse will not necessarily
take the same time to burn. Using only the fuses and the lighter, measure a period of exactly 45 minutes.

1)If you light both ends of the 1st fuse, the flames will burn toward each other until they meet and extinguish each other after exactly 30 minutes.

2)If you light one end of the second fuse at the same moment you light both ends of the first, then you'll be left with 30 minutes of fuse on the second fuse when the first fuse is gone.

3)You can light the other end (the one that isn't already burning) of this second fuse as soon as the first goes out. The two flames burning on the 30-minute length of fuse will extinguish each other after exactly 15 minutes, giving you a total of 30 + 15 = 45 minutes.

#### There is a room In the room are 50 coins 18 of them are showing tails The rest are showing heads.

In the dark without being able to tell which way up the coins are Sort then in to two groups With the same amount of heads showing in each group.

answer: if you want the heads to be the same, then take 32 coins(since we have 32 heads) and flip them over.

Here's the algebraic proof that the solution of grabbing 32 coins and flipping them works.

Let's call our pile of 18 Pile I
Let's call our pile of 32 Pile II

Let a be the number of heads in Pile I
Let b be the number of tails in Pile I
Let x be the number of heads in Pile II
Let y be the number of tails in Pile II

Therefore,

eq1: a + b = 18 (From Pile I)
eq2: x + y = 32 (From Pile II)
eq3: a + x = 32 (From the total number of heads)
eq4: b + y = 18 (From the total number of tails)

Combining eq2 & eq3 we see that,
y - a = 0 —> y = a

Therefore the number of heads in Pile I is the same as the number of tails in Pile II

Now, we flip all 32 coins in Pile II. So all the heads become tails and vice-versa. So now we have y heads and x tails in pile II.

Since a = y, we see that the number of heads in both piles I & II is equal!

#### cubes

Imagine a cubic array made up of a 3×3×3 arrangement of smaller cubes: The cubic array
is three cubes wide, three cubes high, and three cubes deep. It may help to picture a
Rubik’s Cube, as shown in Figure 13-3.
n3 – (n – 2)3
i dimension ni – (n – 2)i

#### Camel issue

A camel must travel 1000 miles across a desert to the nearest city. She has 3000 bananas but can only carry 1000 at a time. For every mile she walks, she needs to eat a banana. What is the maximum number of bananas she can transport to the city?

Solution Description:

Suppose the camel does this:

1. Pick up 1000 bananas.
2. Carry them one mile into the desert, eating 1 on the way.
3. coming back 1 mile and eating 1 banana;
4. pick up 1000 bananas and carry one mile into the desert , eating 1 banana;
5. coming back 1 mile and eating 1 banana;
6. pick up 1000 bananas and carry one mile into the desert , eating 1 banana;

At the end of this, there will be 2995 bananas, which are 999 miles from the city. The camel will also be 999 miles from the city.

Solution:

Camel will need 5 bananas to transfer all the bananas 1 mile away…
5 as for 1st 1000 he'll go n come back then for another 1000 he'll go n come back but for last 1000 he'll only go as nothing will be left behind…

For second mile too it'll take 5 bananas…

Now it'll require 5 bananas per mile for total banana count > 2000
and for banana count <= 2000 it'll eat 3 bananas…

and for <= 1000 it'll eat 1 banana….

so 1st 1000 bananas will be finished in 1000/5 = 200 Miles
next 1000 in 1000/3 = 334 Miles…

finally he'll have 1000 bananas and 466 miles to go…

At B camel will have 534 bananas

#### one checkerboard consists of 8x8 squares, how many rectangules (including

squares) can be counted on this board?

(1+2+…+8)^2

#### arrange the numbers 1 to 8 in the grid below such that adjacent numbers are not in adjacent boxes (horizontally, vertically, or diagonally).

___
| 1 |
=============
| 6 | 4 | 3 |
=============
| 2 | 7 | 5 |
=============
| 8 |
=====

the arrangement above, for example, is wrong because 3 & 4, 4 & 5, 6 & 7, and 7 & 8 are adjacent.

The key (as I see it) is putting the 1 & 8 in the centre spots - which is required, because those spots both border all but one of the other spots, and 1 & 8 are the only numbers that are only adjacent to one number.

From there, the 2 & 7 are forced, then you have your choice of the next number, which then forces the rest. Really, though there are only two valid solutions, and they are mirror images of each other.
___
| 7 |
=============
| 4 | 1 | 3 |
=============
| 6 | 8 | 5 |
=============
| 2 |
=====

#### Every man in a village of 100 married couples has cheated on his wife. Every wife in the village instantly knows when a man other than her husband has cheated, but does not know when her own husband has. The village has a law that does not allow for adultery. Any wife who can prove that her husband is unfaithful must kill him that very day. The women of the village would never disobey this law. One day, the queen of the village visits and announces that at least one husband has been unfaithful. What happens?

Here's another way to explain how the Queen's statement adds new information. Before the Queen speaks:

Woman 1 thinks that there may only be 99 cheating men (since Woman 1 does not know whether Man 1 is cheating).

Woman 1 thinks that Woman 2 may think that there are only 98 cheating men (since Woman 1 does not know whether Man 1 is cheating, and Woman 1 knows that Woman 2 does not know that Man 2 is cheating).

If you can see why this second statement is true, then you should be able to realize that we can continue the line of reasoning that got from the first statement to the second (even though the statements become increasingly convoluted). Thus, Woman 1 thinks that Woman 2 may think that Woman 3 may think that there are only 97 cheating men (since Woman 1 does not know whether Man 1 is cheating, Woman 1 knows that Woman 2 does not know that Man 2 is cheating, and Woman 1 knows that Woman 2 knows that Woman 3 does not know that Man 3 is cheating).

… And so on, until we include all 100 women in the knowledge nesting and realize that: Woman 1 thinks that Woman 2 may think that Woman 3 may think that Woman 4 may think that … Woman 99 may think that Woman 100 may think that there are 0 cheating men.

After the Queen speaks, this last statement is no longer true. It is now common knowledge that at least 1 man is cheating, which means that Woman 1 knows that Woman 2 knows that … Woman 99 knows that Woman 100 knows that there is at least 1 cheating man. That is a new piece of information that Woman 1 has because of the Queen's statement (and every other woman has learned something equivalent).

The induction argument shows why this convoluted-seeming piece of knowledge actually matters.

The reasoning for 100 people is analogous to a smaller number, so let's keep it simple. With 2 couples we have:

Day 1: Queen gives the starting point. Woman 1 reasons: "there is at least 1 cheater and the other woman's husband is a cheater. If mine is faithful, she will realize the truth and kill her husband". Woman 2 thinks the same. Nothing happens.

Day 2: Nobody died the day before. Woman 1 thinks "the other woman must have know my husband to be a cheater (otherwise she would have killed hers). Therefore my husband is a cheater." Every man is killed.

With 3 couples:

Day 1: Queen gives the starting point. Woman 1 reasons: "there is at least 1 cheater and the other women's husbands are both cheaters. If mine is faithful, it will take one day for them to kill their respective husbands (see 2 couple-scenario)". Woman 2 and 3 think the same. Nothing happens.

Day 2: Woman 1 knows: "today women 2 and 3 will kill their husbands if mine is faithful (see 2 couple-scenario)". Women 2 and 3 each thinks the same. Nothing happens.

Day 3: Nobody died. Each woman realizes that can only happen if her husband too was a cheater. Every man is killed.

With 100 couples it takes 100 days. That is: from the 1st to the 99th day *no one* dies, on the 100th day, every man dies.

Again, there was no new information, only a starting point.
http://www.marginalrevolution.com/marginalrevolution/2007/09/job-interview-q.html
http://www.math.temple.edu/~paulos/parable.html

++++There is a group of devotees for a saint and they attend a meeting everyday. The saint makes a mark on heads of few devotees and says that if they found that their head has a marking, they shud not come for the next day's meeting. Each devotee can see others head, but not his own. They cannot communicate with each other. All the devotees attend the meeting for 5 days, on the 6th day, people having the markings over their head do not attend the meeting, while the other continue. How many markings did the saint make?

Make all asumptions needed for this kind of puzzles.

If you assume that the saint made at least one mark then you can prove the following statement using mathematical induction:

"If the saint made n marks then n disciples will fail to attend the meeting on the (n + 1)st day."

http://discuss.techinterview.org/default.asp?interview.11.433044.7

#### You have an empty room, and a group of people waiting outside the room. At each step, you may either get one person into the room, or get one out. Can you make subsequent steps, so that every possible combination of people is achieved exactly once?

http://the-technical-interview.blogspot.com/2007/02/you-have-empty-room-and-group-of-people.html

We can think of each person as 1 bit that is 0 if the person is outside and 1 if the person is inside. The problem now is how to generate all n bit combinations by modifying just one bit. We use mathematical induction to prove that there is a solution for any arbitrary n number of bits, n>0: Starting with n=1, there is one person, and the solution is obvious. For n=2, we have 00 01 11 10 Assume we have a solution for n=k. For n=k+1, we keep the most significant bit 0 and concatenate the n=k solution, then we change the MSB to 1 and concatenate the n=k solution in reverse order. Example: n=3. We know the n=2 solution (00, 01, 11, 10). We obtain 000, 001, 010, 011 and then 111, 110, 101, 100. By using mathematical induction, it means that we have a solution for any n>0

#### You are in the dark, and on the floor there are six shoes of three colors, and a heap of twenty-four socks, black and brown. How many socks and shoes must you take into the light to be certain that you have a matching pair of socks and a matching pair of shoes?

Solution:
Three socks and four shoes would guarantee that you would have a matching pair of each. Since there are only two colors of socks, it doesn't matter how many are in the heap, as long as you take at least three, you are certain to have two of the same. As for the shoes, you must pick four, because selecting only three could result in one shoe in each of the three colors!

#### If 75 men can complete a piece of work in 20 days. How much longer will it take to complete the work by 50 men?

30 days.
Explanation:
With the 75 men case:
One day work = 1 / 20
One man’s one day work = 1 / ( 20 * 75)
Now with the 50 men case:
No. Of workers = 50
One day work = 50 * 1 / ( 20 * 75)

The total number of days required to complete the work = (75 * 20) / 50 = 30 days.

#### hat

Three folks A,B and C walk into a room. On the way in, an unbiased coin is tossed for each player, deciding that player's hat color, either red or blue.Each player can see the hat colors of the other two players, but cannot see her own hat color. After inspecting each other's hat colors, each player decides on a response, one of: "I have a red hat", "I had a blue hat", or "I pass". The responses are recorded, but the responses are not shared until every player has recorded his/her response. The team wins if at least one player responds with a color and every color response correctly describes the hat color of the player making the response.In other words, the team loses if either everyone responds with "I pass" or someone responds with a wrong color.

What strategy should they should use to maximize the team's chance of winning?

Lets talk in terms in of probability.

If a player sees two different colors, he should pass. If a player sees the same color on the other two players, he should respond with the opposite color. That way, the team can only lose if all players have the same color, which is 2 in 8 cases, or 1/4. So the team wins in 3/4 cases.

#### computing

Puzzle: If a hen and a half lay an egg and a half in a day and a half then how many hens will it take to lay six eggs in six days?

Answer: A simple one…right? Only 1.5 hens will be needed in this case.

Since, 1.5 eggs in 1.5 days require 1.5 hens
=> 1 egg in 1.5 days will require 1.5/1.5 = 1 hen
=> 1 egg in 1 day will require 1 * 1.5 = 1.5 hens
=> 6 eggs in 1 day will require 1.5 * 6 hens
=> 6 eggs in 6 days will require 1.5 * 6 / 6 = 1.5 hens

uzzle: If the probability of observing a car on a highway in 20 minutes time is 609/625 then what is the probability of observing a car in 5 minutes time on the same highway (considering all the factors involved to be uniform)?

Solution: Probability of seeing a car in 20 minutes = 609/625
=> Probability of not seeing a car in 20 minutes = 1 - 609/625 = 16/625
=> (Probability of not seeing a car in 5 minutes)^4 = 16/625
=> Probability of not seeing a car in 5 minutes = (16/625)^(1/4)
=> Probability of not seeing a car in 5 minutes = 2/5

Hence, the Probability of seeing a car in 5 minutes = 1 - 2/5 = 3/5

#### more hats

here are 3 folks A,B and C sitting in a room, each wearing a hat. C is blind and others can see and they can hear each other. They can sit any way they want (order is not important). The hats can be either black or white, but _only constraint_ is that all 3 hats can not be white. First I asked A what color he is wearing, he says he doesnt have any idea, then he shuts up forever. Then I ask B, he says he doesnt have any idea, then he also shuts up forever. I go to C and ask him the same question, any idea what C will say and why?

Assuming the folks are intelligent and honest and know the other folks to be intelligent and honest, (which the question does not allow us to assume)

If A sees two white hats, he would conclude he had a black hat. But since A says "I don't know", then B and C both conclude that B and C cannot both have white hats.

If B sees a white hat on C, he would then conclude that his hat is black because he knows that B and C do not both have white hats. But since B says "I don't know" then, then C concludes that he has a black hat.