Hey guys, Johnny here again, and in a much better frame of mind than my last post :-)
Had an interview yesterday, which I thought went really well, and I've just heard back that they thought exactly the same. So there may finally be some progress for me. The job sounds awesome - but I won't jinx it by raving on about it any more here. There'll be plenty of time for that later, touch wood.
Anyway, as sometimes happens when you're applying for jobs with techie-companies, they wanted me to complete a little test of my programming abilities and logical thinking. I had 60 minutes, and there were four questions, two of which were programmy-type ones, the other two logical ones.
I was really eager to impress these guys with my elite programming skills <cough>bullsh!t<cough> so I spent rather too much time on the first two questions, giving myself only 15 minutes to do the others. I guess my time-management skills are not so elite...
Anyway, reproduced below are the two questions:
3. I have balancing scales and 7 balls. One ball is heavier than all the rest. How do I determine the heaviest ball with only 3 possible weighing attempts?
4. On the shelf you have 10 identical bottles of identical pills (let's say there are 100 pills in each bottle). However, one of these 10 bottles contains cheap knockoff pills. The only way to differentiate fake pills from real pills is the weight - while real pills weigh 1g each, the knockoff pills are only 0.9g. You have one digital scale that shows the exact weight (down to the mg) of whatever is weighed.
How can you tell which bottle contains fake pills with just ONE weighing?
Thinking-caps on. Answers next blog-post!
Thursday 15 February 2007
A bit of a brain-melter
Subscribe to:
Post Comments (Atom)
4 comments:
Isn't the first one really easy? In fact, unless I'm misunderstanding the explanation (likely! It *is* 1:30am!) you only need two weigh-ins don't you?
Make two groups of three balls, so there is one left over. Weigh the two groups of balls. If they're even then the leftover ball is the heaviest. If one side is heavier discard the leftover and the three balls from the lighter side.
Now weigh two of the heavier side balls against each other (with one 'new' leftover). If they're even it's the remaining leftover otherwise it's the heavier one.
The second one is a little harder I think but seems pretty easy too (if I've gotten it right...).
For each bottle, take out the number of pills that identify that bottle (ie one pill from bottle one, two pills from bottle two through to 10 pills from bottle 10). Place those pills on the scale. The weight difference compared to the total weight if all pills were real will identify the dodgey bottle.
For example, if all bottles contained real pills the weight would be 55g. If we found that the weight was actually 54.7g we know that bottle three contains the knock-offs.
For bonus points the math equation would look something like:
a = t - (rb - kb)
where
a = actual weight (54.7g)
t = expected total weight (55g)
r = real weight of pill (1g)
k = knock-off weight of pill (0.9g)
b = bottle number
solve for b:
b = (t - a) / (r - k)
[You could actually remove any number of pills from the bottles as long as that number was unique but taking the "bottle number of pills" out makes it a little easier to do the math. :) ]
How did I do?
Matt, you've hit it on the head! Don't come to the UK in the next week please, I need this job! :-)
I had exactly the same problem in Q3, it only took 2 weighings as far as I could tell and I was certain I had somehow tragically misunderstood. But we're right, if the heavy ball H is say 2kg, and the others are all 1kg. Apparently the wording is a little open to interpretation, and if you read it a different way, it takes 3 weighings.
And yep, your answer to Q4 is perfect, even down to the formula to find the dodgy pill bottle. I was really sweating on that one, I had about 5 minutes left when the key point (that you can differentiate the bottles by the quantity of their contents) came to me.
Full marks Matty, plus bonus points for being first to answer and another for it being 1:30am!
Nice Answer.
How about this for the second one though. Put all the bottles on the scales. Then remove them one at a time. Still only one weighing!!!
Genial post and this post helped me alot in my college assignement. Thanks you for your information.
Post a Comment