- Feature Articles
- CodeSOD
- Error'd
-
Forums
-
Other Articles
- Random Article
- 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
Admin
People continuing to attack brainteasers: You are at most attacking dumb interviewers who apply them wrong. As others have noted, it's the thought process that's interesting. Bad interviewers will continue to be bad interviewers, counting off TLA's and buzzwords.
Also, I can't believe that people are still ignoring the "no communication" bit. That means "no communication," including order of passes and everything. For what it's worth, my comment about your hat being independent is correct, though the 50/50 solution is wrong as noted. As someone else hinted with the reference to Marilyn, this is the Monty Hall Problem in disguise; while your personal chance of your hat is still 50/50, "the guy who sees two hats the same color" is in fact dependent on some variables.
Via Google:
A pirate ship captures a treasure of 1000 golden coins. The treasure has to be split among the 5 pirates: 1, 2, 3, 4, and 5 in order of rank. The pirates have the following important characteristics: infinitely smart, bloodthirsty, greedy. Starting with pirate 5 they can make a proposal how to split up the treasure. This proposal can either be accepted or the pirate is thrown overboard. A proposal is accepted if and only if a majority of the pirates agrees on it. What proposal should pirate 5 make?
This is one of those backwards induction game theory problems, right? Here's a gander at it.
The 1 pirate case is easy. 1000 doubloons for me. The 2 pirate case is also easy. 1 gets all 1K for free if he vetoes the proposal, so 2 will offer 1 all 1000 gold coins in hopes that 1 spares his life.
3 pirates case: 1 will get all the treasure otherwise, so he's impossible to payoff and will always vote against. Luckily, 2 is really easy to bribe, since he gets nothing in the above case. 2:1 3:999
4 pirates case: Now 1 is on the outs, expecting nothing if it comes to 3 pirates. 2 isn't expecting much either, so they can be bribed. 1:1 2:2 4:997
5 pirates case: Assuming the above solution will pass for sure, getting three votes for 5's offer would involve 1:2 3:1 5:997 This is a better deal for 1 and 3 than the 4 pirate case, so it should pass.
Admin
What you are saying is absolutely true, but does not prove the 75% strategy to be wrong. A single person has no information to determine his own hat color, but the strategy relies on the fact that the information being provided (the other hats) is used to determine who should be speaking!
Admin
Great, so if you ask a riddle I've already heard, then I'm DQed. Why don't you, instead of a stupid riddle, ask something more open ended, like how to build an exchange clone, what's important, and what tradeoffs you'd make in the design?
Admin
That is suboptimal. You can eliminate two thirds of the quarters in each weighing, so you only need to use the scale twice.
Admin
Minimum two weighings, Maximum 5
Admin
This reminds me of one very painful interview. The interviewer asked me a brainteaser. It was one I already knew, but he messed up a couple of the details, resulting in a puzzle with no possible solution. I thought it was a trick and tried to be clever by mathematically proving there was no solution. Needless to say, I wasn't offered the position.
Admin
split the coins into 2 groups. 1: weigh one group (2+2). if the scales balance the odd duck is in the other group 2: repeat for the group with the odd coin you now have 2 coins, one of which is odd 3: weigh one of those coins against the known good coins. if the scales balance, it's the other one.
Admin
Take the heavier group and split it 2/2. If they weigh the same, then it's a lighter coin in the other four. (Two more weighings -- total 4.) If they are different, then it's a heavy coin in the heavier half currently on the scale. (One more weighing -- total 3.)
Admin
Shooting the fox is definitely more efficient.
Admin
That doesn't tell you the weight of a specific plane (who knows what they have in there). The answer is obvious (and it doesn't involve building a barge, Alex). You measure the air pressure in the tires and the contact area with the tarmac. Problem solved with essentially no cost. Do I get the job?
Admin
Admin
There's a solution to the coin problem that requires exactly three weighings, always. (No best case or worst case options) It works because the number of coins here was a power of two.
Set half (4 coins) aside. Weigh the others 2 against 2. If they balance, the odd coin is is the 4 you set aside. If they don't the odd coin is in the 4 you weighed.
Repeat the process with the 4 coins you know to contain a bad one. Set half (2 coins) aside. Weigh the others 1 against 1. If they balance, the odd coin is one of the 2 you set aside. If they don't, the odd coin is in the 2 you weighed.
Now you have 2 coins and you know one of them is bad. Set one aside and weigh the other against one of the six good coins. If they balance, the odd coin is the one you set aside. If they don't balance, the odd coin is the one you weighed.
Admin
Ah, but do you even know the initial settings of the switches? That is, are they labeled "on/off"? Could some of them be mounted backwards? They could all be switched in the same direction while the bulbs have different states. (Let's assume there is a one-to-one relationship of switch to bulb, although the original phrasing leaves some weasel room.)
As a corollary to your solution, if all the bulbs are initially on, you find the cool bulb and the unlit-but-warm bulb and it still holds.
Here's the "sneaky solutions"...
Admin
Bingo. You can't do better than 50%.
Admin
Here's another... I don't remember where I heard it:
Given a random 32-bit integer, write some code that will count the number of set bits (i.e., 1's) in O(n) time, where n is the number of set bits. Use your favorite language that has bit-wise operators.
Admin
For those that continue to think the hat problem is only 50%, please shed your grade-school probability knowledge, study the Monty Hall problem, then rethink your answer.
Admin
How about, put 3 and 3 on the balance, keeping 2 aside. If it balances then just compare the 2. Otherwise take the heavy side (3 coins) and compare two, same thing, if they balance it's the odd one out, else you know it's the heavier one. Just 2 weighings, not 3.
Admin
Admin
Admin
They're arguing semantics because no one said whether the "odd coin out" was heavier or lighter than the others.
Admin
There are three options though. Blue, red, and pass. If you were forced to say blue or red, then you would be correct. As it stands, you are not.
Admin
That works, strangely.
Admin
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.
Admin
However, Monty has knowledge about the locations of the prizes, and will never reveal the "wrong" box accidentally, leaving you with the original 1/3 chance of having the good prize, and you should switch.
Admin
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%
Admin
Do the employees at this company face this problem a lot? If so, sign me up! :-)
But to answer the question: Technically you only need one condom. That way it's safe for you, anyway.
Admin
int f(uint32_t n) { int count = 0; while (n) { n = n & (n-1); ++count; } return count; }
I got the bit count one in an interview, and none of them had seen this solution before!
Of course, the constant-time solution to this problem (for 32 bits) is even better...
Admin
count = 0; for(i = 0; i < 32; i++) { count += (integer >> 1) & 1; }
Constant time, and therefore O(n). Remember, since the size of the integer is constant, so is the running time.
Admin
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)
Admin
In the problem of 8 quarters, when you don't know whether the odd one out is heavier or lighter, starting with a 4v4 weighing doesn't give you any information. You could put half the quarters off of the scale, and half the remaining quarters on each side of the scale. If the scale is balanced, you eliminate the ones on the scale. Otherwise, you eliminate the ones off the scale. 3 weighings.
Admin
"O(n) time, where n is the number of set bits."
Yours may be constant time, but it's not O(n).
Admin
guess which color correctly?
Admin
Fill both jugs.
Tip both jugs so half of the water pours out from each (waterline from corner to corner). Pour the 3 litre jug into the 5 litre jug (1.5 + 2.5 = 4).
This assuming the jugs are not some odd shape, which you can quickly determine visually.
Admin
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.
Admin
You're actually calculating the probability that a coin flipped three times will be heads every time (or tails every time).
First flip doesn't matter. Then you have a 50% chance twice.
1.00 * .5 * .5 = .25
So you have a 25% chance of three consecutive heads (or three consecutive tails).
You have a 75% chance of success if the three people follow the rules:
Admin
Sigh
Look, no one's saying that if the two hats you see are the same color, yours has a 75% chance of having the other color.
But if everyone who sees two hats of the same color guesses that they have the opposite color, and everyone who sees two different color hats abstains from guessing, then this strategy will work for 75% of the 8 possible hat combinations. If you don't believe it, write down the 8 combinations, figure out who guesses what color for each combo, and you'll notice that the only time when this strategy fails is when all three hats are the same color, which is 2 of the 8 cases.
Admin
And it's pretty obvious you don't understand what you're saying. Proof by example: strategy of "no one guess." Fails 100% of the time. Run some sims if you don't understand probabilities. Pre-agreeing that one person should guess randomly gets you 50% wins.
Having everyone stand silent if they see two different colors, and guess the opposite if they see two identical colors gets 75%. The eight possibilities are each equally probable. You do only get information about the other hats, but that's enough to eliminate many of the possible answers. Part of the key is that the information about the other hats determines whether or not you make a guess at all, like dynamically choosing who is making the guess.
Admin
Yeah, I have been asked that one before. It would be OK if they have come up with that one themselves. If you are going to ask these questions. At the very least put some efforts into preparing the questions and come up with an original one. Not one you copied off from the web or from a riddle book! So now each time before I go to an interview, I have to read up on the riddle books as well?!
Admin
Manhole covers aren't round (at least not in the UK). Over 90% are either square or a rectangle made up out of two triangles. Why? To stop people stealing them by rolling them away. Where in the world has round manholes?
Admin
It's the opposite in the USA. They make them round so sewer workers can move them easier (and so they can't fall in the hole as mentioned earlier). The covers weigh a ton so i couldn't imagine it would be a very popular theft item.
Admin
Take the Chicken Over, return and take the fox over. Upon returning for the Grain, take the chicken back over. Take the grain. Return for the chicken.
It's not that hard.
Admin
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.
Admin
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.
Admin
Yes. You have a 50% chance of answering correctly any time you choose to answer.
Now what is the probability that you choose to answer.
Further, when you are going to answer incorrectly, what is the probability that your group following this strategy would have otherwise gotten it correct.
Basically, you arrange so that all people answer incorrectly simultaneously. But when someone would answer correctly, he is the only person to attempt an answer.
Admin
You're looking at it in the perspective of one event in time and therefore you are calculating the probability of the wrong thing.
There are 8 combinations of hats that the three of you can be wearing. Assume red=0 and blue=1 (since R's and B's look a lot alike).
000 Everyone guesses 1 and gets it wrong 001 The two 0's say nothing. 1 says 1 and is correct. 010 The two 0's say nothing. 1 says 1 and is correct. 100 The two 0's say nothing. 1 says 1 and is correct. 110 The two 1's say nothing. 0 says 0 and is correct. 101 The two 1's say nothing. 0 says 0 and is correct. 011 The two 1's say nothing. 0 says 0 and is correct. 111 Everyone guesses 0 and gets it wrong
Now follow the previously agreed upon rules:
This only fails when you have 000 or 111 (in which case it fails spectacularly because you all guess AND you all guess wrong).
Admin
Yes,
whenever you choose to answer, the prob = 0.5 that you are correct.
If all 3 answer then the prob is 0.875 that someone guesses wrong and you all lose.
If 2 answer (doesn't matter which) prob is 0.75 that you lose.
If 1 answers (dones't matter which one) prob is 0.5
If 0 answer , prob is 1.0 that you lose
Admin
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."
Admin
That's not what matters. Everybody's stuck on what one particular person does. That's not what matters. What matters is what all three people do together.
Look at all the scenarios. Persons A, B, C, given hats 1 or 0. Strategy of anybody who sees two identical hats calling out the opposite, and everybody else stays silent. Here are the possible hat assignments,
A B C 0 0 0 Everybody says 1, loss. 0 0 1 C says 1, win. 0 1 0 B says 1, win. 0 1 1 A says 0, win. 1 0 0 A says 1, win. 1 0 1 B says 0, win. 1 1 0 C says 0, win. 1 1 1 Everybody says 0, loss.
Admin
It is frightening how many people can't read or comprehend the problem definition. What's worse is that many of those brush off "puzzle on an interview" as useless while it clearly shows that at the very least those questions test your comprehension abilities. Now, there will always be stupid interviewers who will expect you to know or figure out the right answer completely missing the point of the exercise. Oh well, perhaps you don't want to work with those people anyway. I've been asked those questions and I asked them myself and I can tell you, you can find out a lot about someone by the way he handles the challenge. A typical question I used was "How many trips a tooth fairy makes per night". Here are some answers I got:
Guess which answer is more likely to land a job for a candidate... I'm not saying that one is "righter" than the others, it just I wouldn't want to work alongside someone who when presented with a nontrivial problem dismisses it outright, just pulls a guess out of his a$$ or goes on the offensive because the question is "not related to the position he's interviewing for".
CAPTCHA: craaazy - how appropriate :)