• Tom Woolf (unregistered) in reply to Grandpa
    Grandpa:
    Three players enter a room and a red or blue hat...

    What strategy would you use?

    Wear mirrored sunglasses.

  • RodeoBob (unregistered) in reply to JL
    JL:
    Anon:
    vt_mruhlin:
    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.....
    I have to interview somebody for a position later this week and I was thinking of using that one (not so sure now). You can actually do it quicker by splitting it into 3 groups. The 8 coin thing is deliberately misleading to make you think of splitting into 2 groups, but you should be able to do it with just two weighings if you split into three. Still, I'd give bonus points for using the term "binary sort".
    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.

    Oy. Some folks need it spelled out explicitly 8 coins. All visibily identical, but one heavier.

    First weighing: 3 coins versus 3 coins, with two held out. If the weighing is balanced, then the heavy coin must be one of the two held out. A second weighing shows us the heavy coin. If the weighing is NOT balanced, than the heavy coin must be one of three. Two are weighed, and the third is held out. The heavy coin will either be on the scale, or if the scale is balanced, the heavy coin was the one held out.

    Two trials, no fuss.

  • Ken (unregistered) in reply to Rodyland
    Rodyland:
    - You have a 3 litre jug and a 5 litre jug. How do you get exactly 4 litres into the 5 litre jug?
    Fill the 5-liter jug. Pour 3 into the 3-liter jug, leaving 2. Empty the 3-liter. Pour the remaining 2 into the 3 liter. Fill the 5 liter. Pour into the 3 liter until it is full. This will take 1 liter, as it previously held 2. You now have 4 remaining in the 5 liter jug.
    Why are manhole covers usually round?
    Constant diameter. The cover cannot fall in due to being placed incorrectly.
    You've got a chicken, a fox, and a bag of grain on one side of the river, and a boat that holds you and one of the chicken/fox/grain. If the fox is left alone with the chicken, he'll eat it. If the chicken is left alone with the grain, he'll eat it. How do you get all across the river so that nobody/nothing gets eaten.
    Take chicken (leaving fox+grain). Come back (leaving chicken). Take fox (leaving grain), come back with chicken (leaving fox). Take grain (leaving chicken). Come back (leaving fox+grain). Take chicken. Done.
    Hat problem - make the strategy be: The person who sees two other people with the same colour hat calls out the opposite colour. He's got a 3/4 chance in being right. There is a 1/4 chance that they are all the same colour, in which case they'll all call out the (wrong) opposite colour.
    Hmm... (Using "0" and "1" rather than "red" and "blue".) 000 -- Result: everyone yells "1" -- wrong 001 -- silent/silent/1 -- correct 010 -- silent/1/silent -- correct 011 -- 0/silent/silent -- correct 100 -- 1/silent/silent -- correct 101 -- silent/0/silent -- correct 110 -- silent/silent/0 -- correct 111 -- 0/0/0 -- incorrect

    Six correct, 2 incorrect. That's 75%, which is better than my 50% solution.

  • (cs)

    Yeah, I don't really see how problem-solving skills would apply to a career in programming.

    /sarcasm

    Take the problem of weighing the airplane. There is no correct and practical answer. But how would YOU approach it?

  • atari (unregistered) in reply to TimS
    TimS:
    If someone shouts out the answer immediately, and recites the answer, as memorized, from a book of problems, that's an immediate check in the "no" column for me.
    So, you disqualify people simply because you are too unoriginal to come up with a ridiculous brain teaser that the candidate has already heard? Wow am I so glad I don't work with you.
  • (cs)

    I confess that I have "How Would You Move Mt. Fuji" at home somewhere, and worked on a large number of the riddles.

    The "five pirates" riddle (google it) is still one of my favorite riddles ever, and the inmates and two switches is probably the second.

    I think that the benefit of these questions depends on the interviewee being indulgent enough to view the problem as the intended mathematical or algorithmic problem, and to form a precise answer. I say "indulgent" precisely because, obviously, it pisses off a lot of reasonable people who have decent answers outside the weird world where pirates and prisoners are collaborative mathematical geniuses.

    As I see it, the context of the problem is there mainly for entertainment; Instead of asking you to distribute loot among very clever pirates, how would you feel if an interviewer asked you to "Determine the maximum possible value of L1,1 for some values L1,1 to L1,5 where LA,1 to LA,5 = 100 for all A, and LM,N = 0 where M < N and LX,Y > LX-1,Y for half of all nonzero blah blah blah..." PIRATES, man, PIRATES!

  • (cs) in reply to Rodyland

    A: three litre jug B: 5 litre jug

    Fill A and pour into B; Fill A and pour into B what you can; Dump out B; Pour the remainder of A into B; Fill A and pour into B;

    So they don't fall in.

    This one is too long to type out

  • Anonymous (unregistered) in reply to Grandpa

    I interviewed for MS once and was asked a few of these questions. I probably failed miserably, but not because I am incapable of answering the questions. Answering these is just not in my frame of reference when I am interviewing. I prepare carefully for the subject of the job, and I guess I'm blindsided when concentrating on having a good interview and then suddenly thrown a question out of context. I think this would be the equivalent of walking over to a software engineer's cube and asking them the appropriate temperature at which meat can be assumed to be fully cooked. Why the hell would most engineers know that?

    I did, however, ask why the person was asking me the question. The response was, "I want to see how you think."

    Well....I have since come up with the exact answer I will give the next time (if ever...I doubt I'd ever apply at MS again) I am asked this question:

    If you are asking this question to see how I think, then there can be no right or wrong answer. Unless you have specific criteria in which you will give me some sort of "grade" by which to compare me to other candidates that are asked the same question, what you are really asking for is my opinion. In my opinion, a question that involves solving a puzzle is hardly relevant to providing a software solution to a non-arbitrary, real world business problem. But since you asked, here is what I think:

    1. Did the people that architected, approved the release of, and implemented that disaster called ActiveX prove that they were exceptional people by answering this type of question? Would you hire them now if you could see the future? If I let you watch me write an ActiveX control right now that pwnz0r3d your box, would you hire me?

    2. How about the people that came up with COM/COM+ as the future of cross platform development? I guess that little performance problem called marshaling that is done WITH EVERY SINGLE METHOD CALL sort of killed it, eh? Not to mention that it never actually went mainstream with those bogus cross platform problems.

    3. Microsoft Bob. Enough said.

    4. If this interview method lets you only choose brilliant people, why is it that so many security holes are found in your software that involve simple buffer overruns?

    5. Did the developers and QA people responsible for letting BizTalk 2004 out the door when it would crash when receiving a file larger than 2GB (or was it 3GB?) prove they were k-k00l, aw3s0m3, and l33t people by answering these questions?

    I could seriously find a lot more points I think. If your interviewer, imho, can't figure out if you're skilled from just asking you questions about relevant past experience or even questions relevant to the job position, they are the wrong interviewer.

  • JL (unregistered) in reply to RodeoBob
    RodeoBob:
    JL:
    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.
    Oy. Some folks need it spelled out explicitly 8 coins. All visibily identical, but one heavier.
    I agree both that you have given an optimal solution for the case where the odd coin is heavier and that some folks need it spelled out explicitly. :) The original problem as posted in this thread:
    Saladin:
    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?
    You are not given the fact that the quarter weighs more, so the split-into-three groups solution does not work.
  • AnonCoder (unregistered)

    Not a WTF in the least, we're really scraping the barrel now aren't we?

    Questions like these can be a useful way for an interviewer to guage how a potential employee thinks.

    It doesn't matter whether they get the brainteaser right or not, it's how they approach the problem and how they communicate to you what solutions they're considering and discarding and why.

    Someone who say there silently for 60 seconds and then gave the correct answer would get less credit from me than someone who talked coherently and briefly through several possible solutions and made a justifiable choice out of them.

    Think of it like an exam question with the little bit at the end that says "show your working".

    If I was interviewing this guy would have got the job based on his ability to recognise fucking stupid requirements and meet them without costing me much time or money or upsetting the customer.

  • Anon (unregistered) in reply to tchize
    How would you determine the weight of a Boeing 747?

    Google it--err, I mean Live Search it!

  • Milkshake (unregistered)
    (fox)(grain) -----(chicken)----->
    (fox)(grain) <------------------- (chicken)
         (grain) -------(fox)-------> (chicken)
         (grain) <----(chicken)------ (fox)
       (chicken) ------(grain)------> (fox)
       (chicken) <------------------- (fox)(grain)
                 -----(chicken)-----> (fox)(grain)
    
    
    After all that...
    
     (interview) -----(me)----->
    
  • Zlodo (unregistered) in reply to Grandpa

    That's pretty easy: just designate only one person who will guess his hat color. A random answer would already have 50% chance of winning. To bring it to 100, designate another person who will communicate the right answer to the guesser when lookng at him. It could be something as subtle as eye movement, or blinking if the hat is red or whatever. Good luck proving that the "no communication at all" rule have been broken then.

  • Jim (unregistered) in reply to JL
    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.

  • Vaibhav (unregistered) in reply to goochrules
    goochrules:
    Eggtastic:
    vt_mruhlin:
    Saladin:
    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.

    And yet the solution you cited is less than optimal. Does it make you a bad programmer that you did not recognize that? Probably not. It just means you never had someone goad you on asking if you can think of a better way. That is the reason these brain teasers are at best tangentially related to programming skill.

    Unless the interviewer is attempting to determine if you know a better sort than binary sort.

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

  • RIAA (unregistered) in reply to Grandpa

    RE: hat riddle

    Grandpa:
    What strategy would you use?

    Simple: make a mental note of everybody's toin coss result and correlate that to the color hat they are wearing. You now know what color hat you are wearing based on your coin toss.

  • Bezalel (unregistered) in reply to Grandpa
    Grandpa:
    Three players enter a room and a red or blue hat is placed on each person's head. The color of each hat is determined by a coin toss, with the outcome of one coin toss having no effect on the others. Each person can see the other players' hats but not his own.

    The first person that sees two hats of the same color should pass. At that point the other two participants will know that they are wearing the same color hats and will be able to guess correctly.

  • krisztian pinter (unregistered)

    "And that candidate will be the same person who designs their software."

    their software?? c'mon, it is MY software! it is on MY machine. I use it, not they! i use it every day! i'm quite sure this guy is the same who wrote the part in explorer for deleting files. as deleting a single file takes 5 seconds on my pc.

  • (cs) in reply to Anonymous
    Anonymous:
    I could seriously find a lot more points I think. If your interviewer, imho, can't figure out if you're skilled from just asking you questions about relevant past experience or even questions relevant to the job position, they are the wrong interviewer.

    The interviewer wants to find out if you require a 20 page document explaining every functional requirement for each method. Or can they say "Hey, go write BlahBlahMethod()." and you can basically figure out what they need.

  • smile (unregistered) in reply to Bezalel
    Bezalel:
    The first person that sees two hats of the same color should pass. At that point the other two participants will know that they are wearing the same color hats and will be able to guess correctly.
    You missed part of the problem:
    Grandpa:
    the players must simultaneously guess the color of their own hats or pass.
  • Talchas (unregistered) in reply to Anon

    For the hat thing: Assuming that you aren't allowed to communicate in any way (including pointing, jumping up and down, and so on) and that you can't see your own hat and so on, then the best you can do is have one person guess for 50/50. You have no matter what a 50/50 chance of guessing your hat color - the problem says you have a 50% chance of red, a 50% chance of blue, and learning about what others have does NOT tell you anything. All those who think otherwise have not learned probability.

  • Steve (unregistered)

    Answer: "The Aristocrats"

  • Drone (unregistered)

    Hat question:

    The problem explicitly states that no communication is allowed, however, it is possible to communicate in many non-standard ways. Depending on the attitude of the test-giver, it is possible to solve this with 100% success every time:

    1. People are entering a room, thus, they have to stand somewhere.
    2. The first two people should stand together.
    3. The third person, on entering the room, should look at the other two hats. If they are the same, he will stand with them. If they are different, he will stand apart.
    4. The two people standing together now have enough information to correctly infer the color of their own hat.

    Captcha: Yummy. Mmm, "Hats Of Meat".

  • (cs)
    Given an opaque box with three light bulbs inside and three switches outside, how would you determine which switch corresponded to which bulb if the box could be opened only once and only after all the switches were permanently set?

    That's the one that I've heard of. Took me a long time to get the answer and would never have thought of it in the span of an interview.

    Turn on switch A for a couple minutes. Turn A off then turn on switch B. Quickly open the box. The bulb that's on is switch B, the bulb that is off but is still warm to the touch from being lit is switch A, and the remaining bulb is switch C.

    Mind you, with LED and compact fluorescent bulbs becoming more popular because of the regulation on power usage for incandescents, this solution will quickly become invalid.

  • CynicalTyler (unregistered)

    I interviewed with a company that asked for a written response to "how do you move a mountain from one side of a town to another". (My answer, by the way: move the town.)

    This is a great question (especially if you have a while to think about it.) Not only did it give me a chance to show off elements of my personality that wouldn't normally come through in an interview, but it gave a question for which I knew there was no wrong answer and made me relax a bit. Now maybe there are some folks who don't like writing or creative thinking, but I wouldn't want to hire them anyway. Programming is all about being creative, and if you can't write a paragraph answer to a silly question, how are you going to write a spec sheet?

    So I would advise that when faced with these questions is to just relax and answer creatively, constructively, and in a way that showcases you. There worst thing you can do is stress about it because it "doesn't test" your programming aptitude.

  • (cs)

    Hats question.

    Before you go into the room, 3 of the people make a plan. Two of them will go into one corner of the room. If they have the same color hats, the third will join them. Then both of them will know what color their hat is.

    Everyone else just sits down.

  • I can so relate... (unregistered)

    Actual questions I got at an interview (not with MS):

    • Why is the sky blue?
    • How would you estimate the weight of Earth?
    • How many people are there in the world?

    I was told the point of these questions was to see how comfortable I am to admit that I don't know the answer. The only problem is the situation -- when I'm at an interview, I feel like I have to give an answer. In normal work I'd have no problem admitting I don't know, or I'd just go look it up. You can't use the interview to see how someone will act in a typical work environment. There are certain expectations and pressures at an interview that simply aren't there when you actually hire a person.

  • (cs) in reply to NotanEnglishMajor

    The number of people who don't have the reading comprehension to handle the riddles here is utterly appalling.

  • Giedrius (unregistered) in reply to AnonCoder
    AnonCoder:
    Someone who say there silently for 60 seconds and then gave the correct answer would get less credit from me than someone who talked coherently and briefly through several possible solutions and made a justifiable choice out of them.

    If you state that you expect loud thinking not correct answer - then, yes I agree with you. Otherwise, you have a problem. There is a lot of different level of recruiters. Some of them are smart enough to figure out that the thinking is important, some of them think that the answer is. How, should I know what recruiter is expecting in such situation?

    I would put in another way. Recruiter should be able to communicate what he is expecting, not just state the problem and hope that you got the right way to answer it.

    Lately, I had both types of recruiters. I still have a problem when deciding which way to go. This not only applies to teasers, some questions even from programming are ambiguous.

  • SomeCoder (unregistered) in reply to CynicalTyler
    CynicalTyler:
    So I would advise that when faced with these questions is to just relax and answer creatively, constructively, and in a way that showcases you. There worst thing you can do is stress about it because it "doesn't test" your programming aptitude.

    That's pretty good advice. The only thing I'd say to this is that I'm not stressing because it doesn't test my programming aptitude (which it clearly does not). I'm stressing because I'm not great at solving brain teasers.

    I interviewed (over the phone) at a place that did brain teasers. The main thing that the interviewer stressed was that he didn't care if I got the right answer but rather he wanted to see how I worked it out. I required a few hints from him on the answers but in the end, he said I did pretty well.

    If you're going to use brain teasers, that's the way to do it. However, I still think they shouldn't be used at all.

  • Grumpy Young Man (unregistered) in reply to Anonymous

    "If you are asking this question to see how I think, then there can be no right or wrong answer."

    That's the wrong answer here at my shop, at M$, or anywhere else.

    Getting the right solution is just for bonus points. If you can demonstrate that you have conceptualized the problem and have some idea as to how to attack it that will lead you to the right answer, you've passed the test. I'm mystified how people who claim to be qualified programmers could fail to be able to do something that simple, let alone balk at attempting it.

  • Someone (unregistered) in reply to Zlodo
    Zlodo:
    That's pretty easy: just designate only one person who will guess his hat color. A random answer would already have 50% chance of winning. To bring it to 100, designate another person who will communicate the right answer to the guesser when lookng at him. It could be something as subtle as eye movement, or blinking if the hat is red or whatever. Good luck proving that the "no communication at all" rule have been broken then.
    Bezalel:
    The first person that sees two hats of the same color should pass. At that point the other two participants will know that they are wearing the same color hats and will be able to guess correctly.

    Read the problem. They must answer simultaneously.

  • P Riva (unregistered)

    Is it just me or is WTF loosing the grip with it?

    It's several months since I've started reading it daily, but it seems to me you're trying to grow a bit too much struggling to get the content...

    Do one thing, do it well and do another one when you're ready to do it, otherwise you'll mess up everything.

    Not only Microsoft but oogle as well is famous for using puzzles in the recruitment process, so maybe it's useful, you know we're talking the two major software companies in the global market!

    And, by the way, if so many comments are about puzzles does it mean only bad programmers do read the daily WTF .... mmmmh should start thinking if I have to keep reading it!

  • Shadowman (unregistered) in reply to zip
    zip:
    The number of people who don't have the reading comprehension to handle the riddles here is utterly appalling.

    As is the number of people who take internet forum postings so seriously.

  • fist-poster (unregistered) in reply to JL

    Concerning the 8 coins.

    If you don't know if one is heavier or lighter, how is binary search going to work? You weigh 4+4. One side is heavier. Is it because the heavier side has the heavy coin or is it because the lighter side has the light coin?

  • Konstantin Surkov (unregistered)

    Actually, Microsoft doesn't ask brainteasers on the interviews. Wall Street companies do.

    That is besides the completely moronic idea that the people who can solve brainteasers are less capable to be software developers than people who don't.

  • Jim (unregistered) in reply to Talchas
    Talchas:
    For the hat thing: Assuming that you aren't allowed to communicate in any way (including pointing, jumping up and down, and so on) and that you can't see your own hat and so on, then the best you can do is have one person guess for 50/50. You have no matter what a 50/50 chance of guessing your hat color - the problem says you have a 50% chance of red, a 50% chance of blue, and learning about what others have does NOT tell you anything. All those who think otherwise have not learned probability.

    Agreed. Everyone who has been saying that you have a 75% chance of winning is incorrect. In fact, what people are calculating is that, on average, 75% of the hat outcomes will be two same colour, one different. Once the three hats have been picked, there is still only a 50% chance that you will guess your hat correctly because of the coin toss. The optimal solution is still "two people pass, one person guesses", but everyone has been calculating the win probability incorrectly.

  • Anonymous Coward (unregistered)

    Three women want to [redacted] with you, but you only have two condoms. How do have safe [redacted] with all three?

    This was an actual interview question!

    CAPTCHA: bathe - which is NOT the answer above.

  • Jim (unregistered) in reply to fist-poster
    fist-poster:
    Concerning the 8 coins.

    If you don't know if one is heavier or lighter, how is binary search going to work? You weigh 4+4. One side is heavier. Is it because the heavier side has the heavy coin or is it because the lighter side has the light coin?

    It requires an extra weighing.

    1. Split into two groups of 4 coins.
    2. Weigh both groups, find which is lighter.
    3. Split the lighter group into 2 groups of 2 coins and weigh them. a) If the two groups are equal, the odd coin is heavier. Go back to the original group of 4 and binary search that group for the heavier coin. b) If the two groups are unequal, the odd coin is lighter. Keep up the binary search on the lighter group of 4.
  • jmcwade (unregistered)

    why call boeing when you have google?

    empty weight for a 747-100 is 358100 lbs, and the 747-400 weighs in empty at 399000 lbs

  • Dan (unregistered) in reply to Ken

    [quote user="Ken][quote]Hat problem - make the strategy be: The person who sees two other people with the same colour hat calls out the opposite colour. He's got a 3/4 chance in being right. There is a 1/4 chance that they are all the same colour, in which case they'll all call out the (wrong) opposite colour.[/quote] Hmm... (Using "0" and "1" rather than "red" and "blue".) 000 -- Result: everyone yells "1" -- wrong 001 -- silent/silent/1 -- correct 010 -- silent/1/silent -- correct 011 -- 0/silent/silent -- correct 100 -- 1/silent/silent -- correct 101 -- silent/0/silent -- correct 110 -- silent/silent/0 -- correct 111 -- 0/0/0 -- incorrect

    Six correct, 2 incorrect. That's 75%, which is better than my 50% solution.[/quote]

    Solution...as stated earlier...say what is to your left actual -- said -- result 000 -- 000 -- all correct 001 -- 100 -- middle correct 010 -- 001 -- first correct 011 -- 101 -- last correct 100 -- 010 -- last correct 101 -- 110 -- first correct 110 -- 011 -- middle correct 111 -- 111 -- all correct

    In all cases at least one person is right. 100% of the time you win!!

    captha: onomatopoeia

  • tryphiodorus (unregistered) in reply to Vaibhav
    Vaibhav:
    goochrules:
    Eggtastic:
    vt_mruhlin:
    Saladin:
    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.

    And yet the solution you cited is less than optimal. Does it make you a bad programmer that you did not recognize that? Probably not. It just means you never had someone goad you on asking if you can think of a better way. That is the reason these brain teasers are at best tangentially related to programming skill.

    Unless the interviewer is attempting to determine if you know a better sort than binary sort.

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

    Ternary search can get the final result with exactly three weighings.

    To start, you have 16 possibilities (each of the 8 coins could be either heavier or lighter). Weigh 3 coins on either side, with two left out.

    If the batches of three coins are unequal, you have six possibilities (3 possibly heavier; three possibly lighter). If we call these H_1, H_2, H_3, L_1, L_2, and L_3, weigh H_1 and L_1 against H_2 and L_2. If H_1 L_1 > H_2 L_2, weigh H_1 against a known correct coin (for example, one of the two coins left out of the original weighing). If heavier, H_1 is heavy; if equal L_2 is light. Similarly, if H_1 L_1 < H_2 L_2, weigh H_2 against a known correct coin. Either H_2 is heavy, or they are equal, in which case L_1 is light. Finally, if H_1 L_1 = H_2 L_2, weigh H_3 against a known correct coin; either it is heavy or L_3 is light.

    If the original batches of three coins equal, you have four (2 coins, either heavier or lighter). You have two weighings left (only one used), so weigh each against a known correct coin.

    The key in each case is to make certain that the number of possibilities remaining, no matter what the result of your current weighing, is equal to no more than 3^(number of weighings to use).

  • Konstantin Surkov (unregistered) in reply to Adam Z
    Adam Z:
    Everyone should guess the same color. Statistically, at least one hat would be that color in a group of 3 or more.
    Good. I was worried this thread would end without any WTF whatsoever.
  • Ken (unregistered) in reply to Talchas
    Talchas:
    For the hat thing: Assuming that you aren't allowed to communicate in any way (including pointing, jumping up and down, and so on) and that you can't see your own hat and so on, then the best you can do is have one person guess for 50/50. You have no matter what a 50/50 chance of guessing your hat color - the problem says you have a 50% chance of red, a 50% chance of blue, and learning about what others have does NOT tell you anything. All those who think otherwise have not learned probability.
    Yes, if the question were "guess your hat color", the result is a 50-50 chance. However, re-read the posts regarding the 75% chance answer. In those cases, half the time you won't even give an answer. By making that change, you have shifted from "what is your color" at 50-50, to the group's collective "what is your color, should you wish to venture a guess" to a 75% chance of being correct.

    It's like the "Let's Make a Deal" problem, where you have a 2/3 probability of winning by switching. However, that problem only works if Monty truly picks a door at random, in which case 1/3 of the time he exposes the real prize. In "real life", Monty skewed the odds by knowing ahead of time which is the correct door.

  • Jim (unregistered) in reply to Dan
    Dan:
    In all cases at least one person is right. 100% of the time you win!!

    If one person is wrong then everyone loses. Your solution has a 1/8 chance of winning.

  • Anon (unregistered) in reply to Jim
    Jim:
    Talchas:
    For the hat thing: Assuming that you aren't allowed to communicate in any way (including pointing, jumping up and down, and so on) and that you can't see your own hat and so on, then the best you can do is have one person guess for 50/50. You have no matter what a 50/50 chance of guessing your hat color - the problem says you have a 50% chance of red, a 50% chance of blue, and learning about what others have does NOT tell you anything. All those who think otherwise have not learned probability.

    Agreed. Everyone who has been saying that you have a 75% chance of winning is incorrect. In fact, what people are calculating is that, on average, 75% of the hat outcomes will be two same colour, one different. Once the three hats have been picked, there is still only a 50% chance that you will guess your hat correctly because of the coin toss. The optimal solution is still "two people pass, one person guesses", but everyone has been calculating the win probability incorrectly.

    Disagree. You're both wrong, and you'll probably never understand why.

  • (cs) in reply to Jim
    Jim:
    Talchas:
    For the hat thing: Assuming that you aren't allowed to communicate in any way (including pointing, jumping up and down, and so on) and that you can't see your own hat and so on, then the best you can do is have one person guess for 50/50. You have no matter what a 50/50 chance of guessing your hat color - the problem says you have a 50% chance of red, a 50% chance of blue, and learning about what others have does NOT tell you anything. All those who think otherwise have not learned probability.

    Agreed. Everyone who has been saying that you have a 75% chance of winning is incorrect. In fact, what people are calculating is that, on average, 75% of the hat outcomes will be two same colour, one different. Once the three hats have been picked, there is still only a 50% chance that you will guess your hat correctly because of the coin toss. The optimal solution is still "two people pass, one person guesses", but everyone has been calculating the win probability incorrectly.

    Or more succinctly put: The hat colors of the other two people have absolutely no bearing on your hat's color.

    This thread has given me a lot of good retorts for when such an interview question is fielded. It's not about figuring out the question, but figuring out why they're asking the question.

  • jwray (unregistered) in reply to Grandpa
    Grandpa:
    Three players enter a room and a red or blue hat is placed on each person's head. The color of each hat is determined by a coin toss, with the outcome of one coin toss having no effect on the others. Each person can see the other players' hats but not his own.

    It's pretty obvious that all strategies are equally effective here, because the only information a player gets before guessing is independent of his own hat color.

  • Anonymous Coward (unregistered) in reply to Jim
    Jim:
    Talchas:
    For the hat thing: Assuming that you aren't allowed to communicate in any way (including pointing, jumping up and down, and so on) and that you can't see your own hat and so on, then the best you can do is have one person guess for 50/50. You have no matter what a 50/50 chance of guessing your hat color - the problem says you have a 50% chance of red, a 50% chance of blue, and learning about what others have does NOT tell you anything. All those who think otherwise have not learned probability.

    Agreed. Everyone who has been saying that you have a 75% chance of winning is incorrect. In fact, what people are calculating is that, on average, 75% of the hat outcomes will be two same colour, one different. Once the three hats have been picked, there is still only a 50% chance that you will guess your hat correctly because of the coin toss. The optimal solution is still "two people pass, one person guesses", but everyone has been calculating the win probability incorrectly.

    I think we've discovered the WTF right here.

  • Ken (unregistered) in reply to Dan
    Dan:
    Solution...as stated earlier...say what is to your left actual -- said -- result 000 -- 000 -- all correct 001 -- 100 -- middle correct 010 -- 001 -- first correct 011 -- 101 -- last correct 100 -- 010 -- last correct 101 -- 110 -- first correct 110 -- 011 -- middle correct 111 -- 111 -- all correct

    In all cases at least one person is right. 100% of the time you win!!

    Re-read the specs.

    In 75% of the cases, at least one person is wrong. You lose 75% of the time!

Leave a comment on “Job Interview 2.0: Now With Riddles!”

Log In or post as a guest

Replying to comment #:

« Return to Article