• (cs) in reply to Undefined Reference
Undefined Reference:
bramster:
Jim:
vt_mruhlin:
This only works in the case where you know if the odd coin is lighter or heavier. If you check the post above, it could be either, in which case splitting into three groups does not help you: if the one of the weighed groups is heavier, it does not tell you which of the two has the odd coin, so you may need to do more weighing (2-4 weighings total). So in this instance, binary search is the optimal solution.

If you don't know if the odd coin is heavier or lighter, the binary search will have exactly the same problem as the ternary solution. I haven't worked through the worst case scenarios, but in both cases it should be significantly more than 4 weighings.

Minimum two weighings, Maximum 5

Nope, Min 2, Max 3.

{0,1,2} < {3,4,5} => {0,3} < {1,4} => {0} < {3} => (0, lighter) {0} = {3} => (4, heavier) {0,3} > {1,4} => {0} < {3} => (3, heavier) {0} = {3} => (1, lighter) {0,3} = {1,4} => {0} < {5} => (5, heavier) {0} = {5} => (2, lighter) {0,1,2} > {3,4,5} => {0,3} > {1,4} => {0} > {3} => (0, heavier) {0} = {3} => (4, lighter) {0,3} < {1,4} => {0} > {3} => (3, lighter) {0} = {3} => (1, heavier) {0,3} = {1,4} => {0} > {5} => (5, lighter) {0} = {5} => (2, heavier) {0,1,2} = {3,4,5} => {6} < {7} => {6} < {8} => (6, lighter) {6} = {8} => (7, heavier) {6} > {7} => {6} > {8} => (6, heavier) {6} = {8} => (7, lighter) {6} = {7} => (8, UNKNOWN)

I get Min=2, Max=4, Avg=3.25

Separate the coins into three groups, one group with 2 coins, and two groups with 3 coins.

Lucky situation (2 comparisons): Weigh the 2 groups of 3 coins. If they are the the same, then you know that the odd coin is one of the coins in the group of 2. Pick one of those and compare it's weight to any of the coins from the groups of 3. If the weight is equal, the coin that you didn't pick from the group of 2 is the odd coin. If the weight is unequal the coin you picked is the odd coin.

Unlucky situation (3 comparisons): Weigh the 2 groups of 3 coins. If they are different, discard the coins in the group of 2, and then separate the two groups of 3 coins into 3 groups of 2 coins. Compare the weight of 2 groups of 2. If they are the same weight, then you know that the odd coin is in the other group of 2. Pick one of those coins and weigh it against any normal coin. If the weights are the same, then coin that you didn't pick is the odd one. If the weights are different, then you picked the odd coin.

Really unlucky situation #1 (4 comparisons): Weigh the 2 groups of 3 coins. If they are different, discard the coins in the group of 2, and then separate the two groups of 3 coins into 3 groups of 2 coins. Compare the weight of 2 groups of 2. If they have different weights, then pick one of the two groups and compare the weights of the 2 coins in that group. If they weigh the same, you know the odd coin is in the other group of 2. Pick one of those coins and compare it's weight to one of the 6 known normal coins. If the weights are equal, then the coin you didn't pick is the odd coin. If the weights are different, then the coin you picked is the odd one.

Really unlucky situation #2 (4 comparisons): Weigh the 2 groups of 3 coins. If they are different, discard the coins in the group of 2, and then separate the two groups of 3 coins into 3 groups of 2 coins. Compare the weight of 2 groups of 2. If they have different weights, then pick one of the two groups and compare the weights of the 2 coins in that group. If they have different weights, you know the odd coin is in the group of 2 that you picked. Pick one of those coins and compare it's weight to one of the 6 known normal coins. If the weights are equal, then the coin you didn't pick is the odd coin. If the weights are different, then the coin you picked is the odd one.

The binary search method, as explained earlier, can find the odd coin in 3 comparisons every time.

If I am wrong, please call me on it.

• (cs)

Great article!

I never liked this idea of a brain-teaser as a bullet point in an interview. I like brain-teasers but this practice attempts to solve a difficult problem (whether or not you should hire someone) by masking it with a simple (almost binary) question that the interviewer has to solve and not you. Because of this you don't fully have to make the decision so you're not fully responsible if it's the wrong one.

While I'm all for the idea of asking unexpected random questions just to get a feel for their personality, this is too specific now that everyone is doing it, people can prepare for this and even expect it.

• (cs) in reply to unknown
unknown:
*Sigh* (I can do that too)

there are 2 possible groups of people.

A) Those that can see the others have hats of the same colour B) those that can see that the others have hats of different colours.

You are telling me that, even though the colour of your hat is randomly chosen, that these groups have different properties and that A can make a more informed decision?

You are wrong. The events are inependent. It does not matter what you see.

You and others are missing the point. It matters not how your hat was chosen, given three hats, each with a 50% chance that they will be one color or another, what is the chance that they will all three be the same color? All three being the same color will only happen 25% of the time. So if you see two of the same color your best option is saying the opposite. It isn't a guaranteed win, but the oods show saying the opposite is best.

• KM (unregistered) in reply to Anonymous
Anonymous:
Big O notation expresses an upper bound to the running time. So yes, any program that is O(1) is also O(n). What you're talking about is capital theta notation, which specifies a tight bound rather than an upper bound.

The problem should be for an m-bit integer, with arbitrary m. All the solutions given so far are O(m). n can be much smaller than m.

• Ahnfelt (unregistered) in reply to Grandpa

Each one says something different, that way all cases are covered ;-)

• (cs) in reply to tchize
tchize:
Interview for a human ressource:

You ask a teaser to a candidate, he give you a better answer that what is in you list of accepted answer. He did great at rest of interview. Probably the best candidate of today, but you still have 2 candidates to interview. You don't comment on his answer, the interview is nearly over. However, the candidate says it's now or never. When he quit the room, if there is no contract for him, he will never come back here. He also says he won't wait for more than 10 minutes, it's enough to make an offer. What do you do?

A) You start to negociate term end ensure him he will be accepted with a very good salary

B) You ask him to wait while you get to the boss for a contract. During this time you try to quickly test 2 remaining candidates

C) You let him go, there are still 2 other candidates

I let him go, because who is he to give ultimatums to me, when I am the one with the money he needs to make a living? I may have to wait, but a guy asking me for a job and then telling me it's "now or never" wouldn't really fit in with my team.

• Undefined Reference (unregistered) in reply to unknown

Following the rules stated:

Each individual has a 50% chance of answering (seeing two hats the same color) in any game. So each individual will correctly answer in 25% of the games, wrong in 25% of the games, and not at all in 50% of the games.

The rules ensure two things:

1. That all contestants will answer their 25% wrong in the same cases (all the same color hat).
2. If an individual answers correctly, no others guess.

Thus each player's 25% correct is independent from others while their error guesses are all the same.

So 25% P1 is right, 25% P2 is right, 25% P3 is right, and 25% all are wrong.

• Ahnfelt (unregistered) in reply to Ahnfelt

Wait, that was nonsense.

• Ahnfelt (unregistered) in reply to Ahnfelt

Wait that was nonsense.

Everybody passes of course :D

• DW (unregistered) in reply to Vaibhav
goochrules:
For this question, if you also have to tell in the end if the odd coin is heavier or lighter, my solutions gives 2 as the best case, and 4 weighings in the worst case. It won't take more than 4 to find the odd coin and also know whether it was lighter or heavier. I dont think I used either Binary or Ternary...

If you use Ternary and remember the previous weighing results you can do it in three always. 3^3 is 27, and you only have 16 possible choices.

The first time I saw this sort of problem I wasted a lot of time saying 'measure group a against group b, now two coins from group a against group b if the first measurement was less than the second...'

But you can actually do this sort of thing with three predetermined weighings. Nine of the results will either be duplicates or impossible.

• Matthew (unregistered)

I didn't see a serious answer to the two condoms, three women question. Here's my attempt:

Put on condom A, then condom B over the top of it. Have sex with woman 1. Remove condom B, turn it inside out and replace. Have sex with woman 2. Remove condom B and have sex with woman 3.

NB: this is definitely against the manufacturer's recommended guidelines.

• Sgt. Preston (unregistered) in reply to Tarwn
Tarwn:
Hat Problem: Why is everyone guessing, thats silly.

There are only two color hats. In the initial strategy session have everyone agree to point at red hats.

Everyone then gets a random hat, hands are raised to point only at members wearing red hats, everyone knows the color they are wearing (either they are being pointed at or they aren't), no guessing required.

This of course assumes that one of the members isn't a complete jackass willing to pass up on his/her portion of \$3 million just to see the reactions of the other two members.

"No communication of any sort is allowed, except for an initial strategy session before the game begins." I would call pointing communicating.

• unknown (unregistered) in reply to KattMan

Okay,

what is instead of 3 people/hats, we have 1000000.

You stand there and see that EVERYBODY elses hat is blue.

Would you risk 10000 to win 100 that your hat is red?

• (cs) in reply to YourMoFoFriend
YourMoFoFriend:
A typical question I used was "How many trips a tooth fairy makes per night". Here are some answers I got: - without a pause: "3000" - "there is no tooth fairy" - a refusal to answer a "stupid question unrelated to the position" - an attempt to estimate number of teeth lost per night by kids based on population of countries that do believe in tooth fairy

3000 is hilarious. I hope you continued the interview and he/she sat there wondering what the hell they were thinking.

Personally, if they said "there is no tooth fairy" I would prompt them for more info (ok... if there WAS a tooth fairy).

• KM (unregistered) in reply to unknown
unknown:
Okay,

what is instead of 3 people/hats, we have 1000000.

You stand there and see that EVERYBODY elses hat is blue.

Would you risk 10000 to win 100 that your hat is red?

That's not the bloody point. There is no fixed "you". Look at the scenarios table. Point out a flaw, please.

Tarwn:
Everyone then gets a random hat, hands are raised to point only at members wearing red hats, everyone knows the color they are wearing (either they are being pointed at or they aren't), no guessing required.

Pointing is a form of communication, none of which is allowed.

• OldContractor (unregistered) in reply to Giedrius
Giedrius:
The problem that I have with these interviews is that you newer know what are you expected to say. Once I had the question with the coins in the interview. Naturally, I first thought of binary search. Then I thought that this is an interview and it should not be so easy. So I thought harder and got the right answer (I would call that being lucky, not smart). So, I have never mentioned the idea about binary-search. Still, I do not know if I should have mentioned it or not.

Sometimes I feel as it is a game of trying to guess what you are expected to say, not what the real answer is.

Giedrius - you shouldn't feel like that. You should instead SAY that and continue saying your entire thought process.

I've often said, "Well, my first thought is binary search, but I suspect that there's a better way," which is exactly what you're thinking. So you get credit for binary search AND being a good communicator while still buying yourself time for a better solution. You also show how you are thinking about the solution. Anyone who expects an interviewee to give a correct one-word answer to a question wouldn't be very good to work for.

I've both had and given these types of interviews and they can be very useful with two caveats: 1) it cannot be a trick question and 2) the interviewer must be looking for the right things.

For no. 1), trick questions test nothing but your luck. The question should have several solutions some of which are more optimal than others. The question should involve not overly complex math-like reasoning (the interview is how long?!?) and maybe drawing some simple diagrams.

And for no. 2), the interviewer should be looking at how the candidate listens to a problem's description, asks follow up questions on anything that they don't understand, and communicates their process of solving the problem.

I've been known to deliberately (and accidentally) leave out important information just to make sure the candidate asks for it. I also try to help and lead the candidate to the answer without giving it to them - the idea being to simulate us working together.

Finally, it's best if both interviewers and interviewees remember that we're all humans and not assume that the other person is this monster who is waiting for you to trip up and then they'll eat you.

Who knows? We just might have to start working with each other.

• (cs) in reply to Matthew
Matthew:
I didn't see a serious answer to the two condoms, three women question. Here's my attempt:

Put on condom A, then condom B over the top of it. Have sex with woman 1. Remove condom B, turn it inside out and replace. Have sex with woman 2. Remove condom B and have sex with woman 3.

NB: this is definitely against the manufacturer's recommended guidelines.

You almost got it

Put on A and B, have sex with 1. Remove B, have sex with 2. Turn B inside out, have sex with 3.

Your solution mixes 1 and 3 due to transfer. Remember they all have to be clean with no transfer.

There was another type of comdom question I ran into.

2 Guys. 2 Girls. 2 Condoms. How can each guy have sex with each girl safely?

• (cs) in reply to Jim

Wow, just wow.

The number of people with a flawed understanding of probability is truly outstanding.

It's been explained, demonstrated, and explained again, and yet still....

• Quizzle (unregistered) in reply to vt_mruhlin

How can you be sure that the odd coin out is lighter than all of the others. Could it not be the case that the odd coin is heavier than the others?

• (cs) in reply to KM
KM:
unknown:
Okay,

what is instead of 3 people/hats, we have 1000000.

You stand there and see that EVERYBODY elses hat is blue.

Would you risk 10000 to win 100 that your hat is red?

That's not the bloody point. There is no fixed "you". Look at the scenarios table. Point out a flaw, please.

That exactly is the point. If you were the one seeing that all other hats are the same color, you should be the one to answer and say the opposite. It matters not the number of hats, whether 3 or 3000000.

• Mark (unregistered)

Well I'm not sure if there is much point in posting a comment given the number, but I seriously had an interview (for a job I most definitely didn't get). I was asked "Using nothing but your own reasoning estimate the number of barber shops in the united states." I asked what the point of the question was. They responded with "To see how your reasoning is". So I got up to the white board made some guesses and calculations against known statistics in the US (all taking about 20 seconds) and guessed there where about 35,000 barber shops in the US.

So anybody know what the point of that stupid question was?

• obediah (unregistered) in reply to unknown
unknown:
Poochner:

So you are standing there and you see 2 red hats on the other guys. You know that - it is a priori information now.

You also know that your hat was chosen randomly. Are you telling me that there is a 75% chance that your hat is blue?

P(Your Hat == Blue | Other Hats == Red) is 0.5

This is because the two events are independent.

Wikipedia has failed you.

The strategy isn't obvious, but it's simple once you try to understand it.

There are 8 possible combinations, all equally likely. The naive solution (have one person guess), gives you a 50% chance of winning for any combination. Your overall chance of winning can be determined by:

sum over all situations i, P(win|i) * P(i).

P(i) is 1/8 for all i, and P(win|i) = .5 for all i, so the chance of winning is 50%.

In the other strategery, you have a 100% chance of winning 6 of the combinations, and a 0% chance of winning the other 2.

P(i) is still 1/8 for all i so you get

1.00 * 1/8 + 1.00 * 1/8 + 1.00 * 1/8 + 1.00 * 1/8 + 1.00 * 1/8 + 1.00 * 1/8 + 0.00 * 1/8 + 0.00 * 1/8 = 6/8

So the chance of winning is 75%.

• DW (unregistered) in reply to DW

Actually to expand on the fixed weighing comment I made above.

Imagine the coins are numbered 1 thru 8. You weigh each time:

1 2 3 vs 4 5 6 1 2 5 vs 3 4 7 1 6 8 vs 2 3 7

if 1 is odd, all three weighings will be the same, heavier or lighter. If 2 is odd, the first two will be the same and the third will switch. If 3 is odd, the last two will be opposite the first. If 4 is odd, the first two willb e the same, but the last will be balanced If 5 is odd, The first two will be opposite, but the last will be balanced If 6 is odd, the first and last will be opposite, but the middle will be balanced. If 7 is odd, the first will be balanced and the last two will be the same If 8 is odd, the first two will be balanced, but the last will be heavier or lighter.

Based on this, you can also figure out whether the coin is heavier or lighter than the rest.

• gvo (unregistered) in reply to vt_mruhlin

you don't know which bunch to discard since you don't know whether the fake quarter is heavier or lighter. gotta do better than that :)

• unknown (unregistered) in reply to KM

Well KM,

These are the scenarios where A has a 0 hat

0 0 0 0 0 1 0 1 0 0 1 1

These are two instances where he sees hats of the same colour. If he chooses the opposite he wins 1 time, out of the 2

• (cs) in reply to KattMan
KattMan:
2 Guys. 2 Girls. 2 Condoms. How can each guy have sex with each girl safely?

Guy 1 puts on condom A then B. Does Girl 1. He gives condom B to Guy 2 who then does Girl 1. Guy 1 does Girl 2 then gives condom A to Guy 2.
He puts it on over his (condom B) and does Girl 2.

Addendum (2007-05-15 16:50): Frickin gross btw :)

• KM (unregistered) in reply to unknown
unknown:
Well KM,

These are the scenarios where A has a 0 hat

0 0 0 0 0 1 0 1 0 0 1 1

These are two instances where he sees hats of the same colour. If he chooses the opposite he wins 1 time, out of the 2

We don't care about A. We don't care about B. We don't care about C. We care about their action in toto. Setting A as the person who has a 0 hat is restricting the sample space.

• KM (unregistered) in reply to KattMan
KattMan:
KM:
unknown:
Okay,

what is instead of 3 people/hats, we have 1000000.

You stand there and see that EVERYBODY elses hat is blue.

Would you risk 10000 to win 100 that your hat is red?

That's not the bloody point. There is no fixed "you". Look at the scenarios table. Point out a flaw, please.

That exactly is the point. If you were the one seeing that all other hats are the same color, you should be the one to answer and say the opposite. It matters not the number of hats, whether 3 or 3000000.

I agree. "unknown" is the one who disagrees.

• (cs) in reply to unknown
unknown:
Well KM,

These are the scenarios where A has a 0 hat

0 0 0 0 0 1 0 1 0 0 1 1

These are two instances where he sees hats of the same colour. If he chooses the opposite he wins 1 time, out of the 2

If he sees two hats of differeing colors he doesn't choose. Look at your chart and the person seeing two of the same color is the one that should answer. In your list, that wins 3 out of four times. A 75% chance of success, always. This conversation about hats is done, if you still don't get it, you never will.

• (cs) in reply to unknown
unknown:
Well KM,

These are the scenarios where A has a 0 hat

0 0 0 0 0 1 0 1 0 0 1 1

These are two instances where he sees hats of the same colour. If he chooses the opposite he wins 1 time, out of the 2

0 0 0 Lose 0 0 1 Unknown by itself, but will win under the given rules 0 1 0 Unknown by itself, but will win under the given rules 0 1 1 Win

75% chance again.

• Jen Larkin (unregistered) in reply to Grandpa

One of the many reasons that no one should ever listen to Joel on Software-- he thinks this is a really great interview technique and we should all use it. Because it shows our ability to think under pressure and shows the interviewer our thought process. BWAHAHAHAHAHAHA! He's such a smarmy little jerk.

I know someone who encountered this who simply got up and walked out, then when the company called back he told them that they clearly were not interested in hiring someone competent. I keep waiting for someone to ask me one of these questions; I've been preparing....

captcha: scooter (what I should leave such an inteview on?)

• Noviota (unregistered) in reply to Grandpa

All enter the room and prepare to sit down. If you see two hats of the same colour stand instead.

If you are standing, guess the opposite colour of the two sitting, or the same colour as everyone standing.

If you are sitting, guess the opposite colour of the one standing, and the same as the other one sitting.

```Hat Colour			Position
1	2	3		1	2	3
Blue	Blue	Blue		Stand	Stand	Stand
Blue	Blue	Red		Sit	Sit	Stand
Blue	Red	Blue		Sit	Stand	Sit
Blue	Red	Red		Stand	Sit	Sit
Red	Blue	Blue		Stand	Sit	Sit
Red	Blue	Red		Sit	Stand	Sit
Red	Red	Blue		Sit	Sit	Stand
Red	Red	Red		Stand	Stand	Stand
```

Yes, one could argue, it is communication of a sort, but not directly, or provable. Everything we do can be classed as communication of a sort. Minute differences in the way we stand, smiling or frowning. It is all down to making it unnoticeable to the judge. (Yes it is cheating a bit)

• jwray (unregistered) in reply to unknown
unknown:
Hat problem:

People are saying that you can get a 75% chance by guessing the opposite colour IFF the hats you see are the same colour.

Whilst it is true that there is a 75% chance that any 3 hats will have that kind of distribution, you are missing conditional probability rules;

given that the other 2 hats you see are the same colour, the probability that your hat is the opposite colour is only 50%

The bunching of wrong answers is what explains this apparent paradox. In two cases, all three people are wrong. In the other six cases, one person is right and the others pass. So even though the probability that you have a red hat given that the other two have blue hats is still 50%, this strategy wins 75% of the time.

• (cs) in reply to akatherder
akatherder:
KattMan:
2 Guys. 2 Girls. 2 Condoms. How can each guy have sex with each girl safely?

Guy 1 puts on condom A then B. Does Girl 1. He gives condom B to Guy 2 who then does Girl 1. Guy 1 does Girl 2 then gives condom A to Guy 2.
He puts it on over his (condom B) and does Girl 2.

And you have proven yourself as a person I could party with while having limited funds and an overstock of girls!

Now about working, I'm not so sure. Can you code yourself out of a wet paper bag?

Of course this is just a "Towers of Hanoi" modification which is a logic problem in itself usually taught to beginner programmers. If you can solve this, you should be able to code. THAT is the reason for these types of logic problems. Now for the How many trips does a tooth fairy make, that is for a statistician, not a programmer.

• Chaz (unregistered) in reply to Grandpa

For those of you saying that you can look at the other hats and use statistics to find your own hat's color... the line "with the outcome of one coin toss having no effect on the others." means that the events are independent. Thus, despite how it may seem, there is no greater or lesser chance of your hat being a color based on the color of their hats. As far as I can tell, the feedback of the other hats is useless and you're just as well off with one person guessing randomly. There may be tricky wording somewhere in the question, however.

• (cs) in reply to Fuz

Very nice... so simple...

The solution I came up with was a bit more obfuscated & relies on two's complement representation (although I think this is pretty close to the standard answer):

int f(uint32_t n) { int count = 0; while (n) { n = n & (n ^ -n); ++count; } return count; }

(The same as yours except for the "n = ..." line.)

• Zmee (unregistered) in reply to vt_mruhlin
vt_mruhlin:
Quick. Given eight quarters -- one weighing more or less than the rest -- and a balance scale, if you were faced with the task of figuring out which was the odd coin out using the fewest weighings possible, what would you do?

Obviously, I pocket the quarters and leave this stupid interview, giving me enough change to buy a Coke and pay the highway toll on the way to my next (hopefully better) job interview.

I actually saw a good discussion of this one, and how that particular example can be used to guage programming skills. Correct solution was to do a binary sort on on. Put 4 coins on each side of the scale, discard the lighter half, weigh the remaining 4, then weigh the remaining two.....

Course the person who answers that correctly probably just heard it before. Nobody thinks about weighing quarters that fast.

Ironically, this is actually best solved with TRUE/FALSE/FILE_NOT_FOUND. In particular, you put three quarters on either side of the scale leaving 2 off. If the right side is heavier, it is now in that sub-set of three (lets call that TRUE). If the left side is heavier, it is in that sub-set (lets call that FALSE). If, however, the two sides of the scale are equal, then one of the two quarters that are off the scale is the delinquent (FILE_NOT_FOUND). Answering this question correctly (ie only 2 measures) might be something that would disqualify a candidate.

PS - I guess that makes me disqualified to be a programmer - doh!

• Patrick McCormick (unregistered) in reply to strictnein
strictnein:
Patrick McCormick:
You people, who think that one person should make a 50% guess at the hat color, fail at probability (or learned it from Marilyn vos Savant). The correct strategy is for each person who sees the others wearing the same color hat to guess the opposite color, and for those that see one of each hat on the other heads to pass. This has more than a 50% chance of getting a winning condition.

I love all these people who think this is an obvious answer. This thing has been floating around the Internet for a little while now, most recently showing up on Digg. Nice try with your smug little "oh I'm so smart" attitude. Better luck next time.

Watch closely... you're about to get pwned.

```def A_BAJILLION = 10000     // eh; close enough

def List createHats() {
def hats = []
3.times {
def chance = Math.random()
hats.add( chance < 0.5 ? 1 : 0 )   // red = 1; blue = 0
}
hats
}

def boolean performStoopidStrategy( List hats ) {
def guess = ( Math.random() < 0.5 ? 1 : 0 );
return guess == hats[0]
}

def boolean performSmartStrategy( List hats ) {
def hatTotal = hats[0] + hats[1] + hats[2]    // 3 = all red; 0 = all blue; other = mix
return ( hatTotal != 3 ) && ( hatTotal != 0 )
}

def count = 0
A_BAJILLION.times {
if ( performStoopidStrategy( createHats() ) ) {
count++
}
}
stoopidPercent = count / A_BAJILLION

count = 0
A_BAJILLION.times {
if ( performSmartStrategy( createHats() ) ) {
count++
}
}
smartPercent = count / A_BAJILLION

println( "The stupid strategy was correct \$stoopidPercent of the time." );
println( "The smart strategy was correct \$smartPercent of the time." );

def strictneinIsATool = ( smartPercent > stoopidPercent );
assert( strictneinIsATool )   // always unit test kids
```
• Eggtastic (unregistered) in reply to Robot
Robot:
We use brainteasers in our interviews as a way to see how the interviewee thinks and reacts to not being able to figure it out. The wrong answer is "brainteasers suck, i give up."

The problem is that everyone with two brain cells knows that is why you asked the brainteaser. If someone knows the answer, they can just make a show of working it out according to any one of the detailed scripts available in every single bookstore. They make it look like they are clever because they were able to regurgitate the right answer in the right way. Sure, if someone just blurts out the answer, you know your test failed, but only an idiot would do that.

The real problem with these brain teasers is that there is no way for the interviewer to probe deeper. There is no depth to probe once someone figures out the right answer and there is no way to tell whether they really figured it themselves.

• (cs) in reply to Chaz
Chaz:
For those of you saying that you can look at the other hats and use statistics to find your own hat's color... the line "with the outcome of one coin toss having no effect on the others." means that the events are independent. Thus, despite how it may seem, there is no greater or lesser chance of your hat being a color based on the color of their hats. As far as I can tell, the feedback of the other hats is useless and you're just as well off with one person guessing randomly. There may be tricky wording somewhere in the question, however.

We already agreed that the probability discussion was over but I recommend you read up the thread. Specifically the chart which shows the 8 possible scenarios.

• onomatopoeia (unregistered) in reply to UncleMidriff

For the 8 coins. One weighing more then the others.

You seperate the coins into 3 groups. 2 groups of three and 1 group of 2.

For the first weighing. Place the 2 groups of three on the scale and the group of two to the side.

If the 2 groups of three are equal then put the 2 groups of three to the side and you split and weigh the group of two coins which have not been weighed yet and that will give you the heavier coin on the second weighing.

Else If 1 of the 2 groups of three are heavier. Then you remove all the coins except that group. You place one coin on each side of the scale and leave one coin off. Then on this weighing, the second. If the coins on the scale are equal its the one from the group of three you put on the side. otherwise its one that weighs more on the scale.

So if done correctly will result in no more or less then 2 weighings.

• (cs) in reply to Chaz
Chaz:
For those of you saying that you can look at the other hats and use statistics to find your own hat's color... the line "with the outcome of one coin toss having no effect on the others." means that the events are independent. Thus, despite how it may seem, there is no greater or lesser chance of your hat being a color based on the color of their hats. As far as I can tell, the feedback of the other hats is useless and you're just as well off with one person guessing randomly. There may be tricky wording somewhere in the question, however.

There is no trick in the wording.

Answer this question: What are the odds that all randomly picked hats will be the same color?

The answer is 1:4 or 25% of the time all three will be the same color. The other 75% of the time, you will have 2 of one color and 1 of another. So if you see two people with the same color hat, you should be the one to answer with the opposite color.

• YourMoFoFriend (unregistered) in reply to Jen Larkin
Jen Larkin:
I know someone who encountered this who simply got up and walked out, then when the company called back he told them that they clearly were not interested in hiring someone competent. I keep waiting for someone to ask me one of these questions; I've been preparing....
But did the "walk outie" show his competence or his "jerkness"? I've worked in enough small startups to know that one WILL encounter an unexpected problem that has nothing to do with ones particular job description, and that one WILL have to solve it. Walking out is not an option. Do you want to hire someone that did walk out on an interview? :)

CAPTCHA: darwin. Man, oh man :))

• YourMoFoFriend (unregistered) in reply to KattMan
KattMan:
And you have proven yourself as a person I could party with while having limited funds and an overstock of girls!

Now about working, I'm not so sure. Can you code yourself out of a wet paper bag?

Of course this is just a "Towers of Hanoi" modification which is a logic problem in itself usually taught to beginner programmers. If you can solve this, you should be able to code. THAT is the reason for these types of logic problems. Now for the How many trips does a tooth fairy make, that is for a statistician, not a programmer.

You're missing the point. In fact you are missing two points. First, this is not meant to test your puzzle solving abilities, though if you can +1 to you. Second, your programming abilities are just a part of your qualification. You can be a genius with C++, but if you're a jerk that can't work with people in my team - I don't want you.

• ronj (unregistered) in reply to vt_mruhlin

Hmmm . . . not so good discussion. The odd quarter can be heavier or lighter.

• (cs)

Hopefully nobody did this while I was writing, but I threw together a C program to simulate this. I tried to make it as close to what real life would be as possible (each "player" making a guess, then checking the accuracy).

I threw this together while nobody was looking, so please check the accuracy.

Here's the output: Attempts: 100000, Wins: 75119 -- 75.12%

And here's the code:

```#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv)
{
int i;
int a, b, c;
int a_guess, b_guess, c_guess;
int attempts = 0;
int wins = 0;

for(i = 0; i < 100000; i++)
{
attempts++;

a = (rand() % 2);
b = (rand() % 2);
c = (rand() % 2);

/* a's turn to guess. */
if(b == c)
a_guess = (b == 0 ? 1 : 0);
else
a_guess = -1;

/* b's turn to guess. */
if(a == c)
b_guess = (a == 0 ? 1 : 0);
else
b_guess = -1;

/* a's turn to guess. */
if(a == b)
c_guess = (a == 0 ? 1 : 0);
else
c_guess = -1;

if(a_guess == -1 && b_guess == -1 && c_guess == -1)
{
/* Nobody guessed. */
}
else if((a_guess == a || a_guess == -1) && (b_guess == b || b_guess == -1) && (c_guess == c || c_guess == -1))
{
wins++;
}

printf("Attempts: %5d, Wins: %5d -- %2.2f%\n", attempts, wins, ((double)wins / attempts) * 100);
}

return 0;
}
```

• M.G. (unregistered) in reply to onomatopoeia
onomatopoeia:
For the 8 coins. One weighing more then the others.

You seperate the coins into 3 groups. 2 groups of three and 1 group of 2.

For the first weighing. Place the 2 groups of three on the scale and the group of two to the side.

If the 2 groups of three are equal then put the 2 groups of three to the side and you split and weigh the group of two coins which have not been weighed yet and that will give you the heavier coin on the second weighing.

Else If 1 of the 2 groups of three are heavier. Then you remove all the coins except that group. You place one coin on each side of the scale and leave one coin off. Then on this weighing, the second. If the coins on the scale are equal its the one from the group of three you put on the side. otherwise its one that weighs more on the scale.

So if done correctly will result in no more or less then 2 weighings.

Except the problem didn't state that the odd coin weighs more. It said it weighs more or less than the others.

Between people missing that and the people missing the "no communications" part of the hat question, I am almost dumbfounded at the lack of reading comprehension around here.

Speaking of the hat problem: There is a large number of people who don't understand the 75% win strategy for the hat problem even after its been spelled out to them... I just hope I don't work with any of them. It reminds me of the people who can't accept that .99999999... (repeats forever) is exactly equal to 1. They refuse to accept it even though it can be proved rigorously with simple algebra, with the infinite sum of the geometric sequence rule, and with calculus.

• (cs) in reply to XML Hater
XML Hater:
Did M\$ start doing this after Google had their "IQ Test" job applications? Or was M\$ actually an innovator? ;-)
I don't know when M\$ started doing this. But Microsoft has been asking logic oriented question in interviews since before Google existed as a company.
• Abraxis (unregistered)

Bicycle for blind people? That's easy - tandem bicycle! (I've seen several blind people driving those - of course not in blind-pairs ;-))