techinterview

Classic Weighing

techinterview:

this is a classic problem which i have heard many times before. this is the “harder” of the two problems, since in this one, you do not know if the invalid item weighs more or less than the others.

solving it is only half the battle. writing up a solution that anyone including your grandma could understand, is very hard.

problem: the evil king from before sends his own assassin to take care of the evil queen who tried to poison him. of course, her trusty guards catch the assassin before any harm is done. the queen notices that the assassin is quite handsome and doesn’t really want to punish him by death. she decides to test his wisdom.

the queen gives the assassin 12 pills which are all completely identical in shape, smell, texture, size, except 1 pill has a different weight. the queen gives the man a balance and tells him that all the pills are deadly poison except for the pill of a different weight. the assassin can make three weighings and then must swallow the pill of his choice. if he lives, he will be sent back to the bad king’s kingdom. if he dies, well, thats what you get for being an assassin.

only one pill is not poison and it is the pill which has a different weight. the assassin does not know if it weighs more or less than the other pills. how can he save his skin?

Read More