posted
"I got asked something similar to the "10 bomb" and "12 bomb" riddles in a recent job interview."
I also got presented with a brain teaser in a recent job interview.
I think it'd be much better to ask people to find a suitable algorithm for solving a problem than to come up with a narrowly defined solution to a deliberately tricky problem. These things are great for making people think hard and exercise their brains, but don't map very well to real world problems, in my opinion.
(Imagine: you're tasked with designing efficient manufacturing processes. As a precondition of any solution, are you going to decide that you can only weigh items within a batch 3 times? Or you're writing a program: should we say that you get 15 lines of code for your function, or just let you write one that works?)
Perhaps I'm just bitter that I failed my test.
Out of curiosity, Nighthawk, what was the job?
Posts: 4287 | Registered: Mar 2005
| IP: Logged |
posted
Senior software development position at a major pharmaceutical company in Miami.
Honestly, for a position such as this they don't care of you get the answer right or wrong; they care about how you come to the conclusion. First they asked what was the minimum amount of weighings and I told them "three" almost instantly, but they wanted to know how I came to that conclusion in vivid detail. It's meant to display deductive reasoning, not memorization.
On a related note, I was asked by Yahn Bernier at Valve Software something similar to a riddle, but designed to analyze algorithmic ability: you have a deck of cards and five cards drawn from it. Systematically and programmatically (not through code, but through design), how would you determine whether you have a straight or not. This puzzle involves defining the deck, the cards and the method to scan for the yes/no result, and those methods could be either really optimized or horribly impractical. For example, I came up with 23 different solutions, perhaps 20 of which I would never dream of implementing.
I've heard of numerous companies, especially programming shops, doing similar things. Microsoft was infamous at one point for asking questions like that in their upper tier job interviews. They would ask questions like, put simply, "how would you test an elevator?" and expect you to write or speak a virtual thesis of a response.
Posts: 3486 | Registered: Sep 2002
| IP: Logged |
When I solved this I started with the hypothesis that you have to have narrowed it down to three bombs in the first two weighings and you have to know whether those bombs are heavy or light. Then the problem comes down to how you eliminate 9 bombs in the first two weighings.
Prior to the final weighing you always end up with 9 good bombs, 2 potentially heavy bombs and 1 potentially light bomb (or vice versa). I solved this by putting the one of the light bombs and one of the heavy bombs on the right side of the scale and two good bombs on the left side. If the right side rises, the light bomb is bad. If is falls, the heavy bomb is bad. I'm not sure if that solution is more elegant or just more complicated than putting the two light or two heavy bombs on opposite sides of the scale.
My current problem involves determining the maximum starting number that you can solve with only 3 weighings. I know it can be done with 13 easily (at least its easy after you've done the solution for 12).
For 13 bombs you start of by dividing the bombs into three groups of 4, 4 and 5. The two groups of four go on the scale if they are unequal, you proceed as in the 12 bomb problem. i.e you put one heavy bomb and 2 light bombs aside. You put two heavy bombs and one light bomb on one side of the scale and one heavy, one light and one good on the other side of the scale.
If the first 2 sets of 4 bombs have equal weight. You put 2 of the remaining five on one side of the scale and one of the remaining five plus 1 good bomb on the right side. If they are unequal you have 2 heavy and 1 light bomb and you solve it in M3. If they are equal, you weigh one of the remaining 2 bombs against one of the good bombs in M3.
So now I need to figure out if it can be done with more than 13 bombs.
Posts: 12591 | Registered: Jan 2000
| IP: Logged |
posted
With 13, it's possible to determine which one's the dud, but not always possible to determine whether it's lighter or heavier. The only way I've seen to solve the 14 bomb problem is by adding another known good bomb to the equation, leaving 15 bombs, with one dud and one known good one.
Posts: 1594 | Registered: Apr 2006
| IP: Logged |