 Feature Articles
 CodeSOD
 Error'd
 Forums

Other Articles
 Random Article
 Other Series
 Alex's Soapbox
 Announcements
 Best of…
 Best of Email
 Best of the Sidebar
 Bring Your Own Code
 Coded Smorgasbord
 Mandatory Fun Day
 Off Topic
 Representative Line
 News Roundup
 Editor's Soapbox
 Software on the Rocks
 Souvenir Potpourri
 Sponsor Post
 Tales from the Interview
 The Daily WTF: Live
 Virtudyne
Admin
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.
Admin
Great article!
I never liked this idea of a brainteaser as a bullet point in an interview. I like brainteasers 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.
Admin
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.
Admin
The problem should be for an mbit integer, with arbitrary m. All the solutions given so far are O(m). n can be much smaller than m.
Admin
Each one says something different, that way all cases are covered ;)
Admin
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.
Admin
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:
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.
Admin
Wait, that was nonsense.
Instead, everybody passes ;)
Admin
Wait that was nonsense.
Everybody passes of course :D
Admin
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.
Admin
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.
Admin
Admin
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?
Admin
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).
Admin
That's not the bloody point. There is no fixed "you". Look at the scenarios table. Point out a flaw, please.
Admin
Pointing is a form of communication, none of which is allowed.
Admin
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 oneword 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 mathlike 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.
Admin
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?
Admin
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....
Admin
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?
Admin
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.
Admin
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?
Admin
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(wini) * P(i).
P(i) is 1/8 for all i, and P(wini) = .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%.
Admin
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.
Admin
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 :)
Admin
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
Admin
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 (20070515 16:50): Frickin gross btw :)
Admin
Admin
Admin
Admin
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.
Admin
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?)
Admin
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.
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)
Admin
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.
Admin
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.
Admin
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.
Admin
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.)
Admin
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 subset of three (lets call that TRUE). If the left side is heavier, it is in that subset (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!
Admin
Watch closely... you're about to get pwned.
Admin
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.
Admin
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.
Admin
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.
Admin
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.
Admin
CAPTCHA: darwin. Man, oh man :))
Admin
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.
CAPTCHA: sanitarium. Is there some advanced AI behind these? :)
Admin
Hmmm . . . not so good discussion. The odd quarter can be heavier or lighter.
Admin
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:
So it's 75%! Now please, stop your arguing! sniff
Admin
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.
Admin
Admin
Bicycle for blind people? That's easy  tandem bicycle! (I've seen several blind people driving those  of course not in blindpairs ;))