Friday, December 15, 2006

Job Interview Puzzle: 3 Classic Weighing puzzles :Simple Medium and Hard



In this post I want to describe about a series of puzzles called weighing puzzles. These puzzle vary in hardness from simple to extremely mathematical involving either expertise in some fields or extreme ingenuity. Either you know it or you figure out it using extreme intelligence. So here is the chance for some people to burn your grey cells.

I am putting forward three puzzles with varying range of hardness. Sometimes you may feel the hardest one is very easy for you have already come across the theory, but I still made it the hardest for the people who will be solving it with out knowing the theory behind it, giving them an option to figure out a small part in evolution of computational history.

There is a shopkeeper who wants to weigh things who has a common balance. He must be in a position to weigh things of all possible integral weighing units from 1 to a given maximum sum. The question will be either about how many weights you will need or how will you weigh.

Problem 1: One Side Only (Simple Interview Question for Phone Screening usually)

In this version of the problem shopkeeper can only place the weights in one side of the common balance. For example if shopkeeper has weights 1 and 3 then he can measure 1,3 and 4 only. Now the question is how many minimum weights and name the weights you will need to measure all weights from 1 to 1000. This is a fairly simple problem and very easy to prove also.


Problem 2: Both Sides (Medium:5 to 10 mins onsite interview question)

This is same as the first problem with the condition of placing weights on only side of the common balance being removed. You can place weights on both side and you need to measure all weights between 1 and 1000.For example if you have weights 1 and 3,now you can measure 1,3 and 4 like earlier case, and also you can measure 2,by placing 3 on one side and 1 on the side which contain the substance to be weighed. So question again is how many minimum weights and of what denominations you need to measure all weights from 1kg to 1000kg.

Problem 3: Incremental (Hard)
This is an altogether different one in the same scenario. You have to make 125 packets of sugar with first one weighing 1 kg, second 2 kg, third 3 kg etc ...and 125th one weighing 125kg.You can only use one pan of the common balance for measurement for weighing sugar, the other pan had to be used for weights i.e. weights should be used for each weighing.
It has come into notice that moving weights into and out of the pan of the balance takes time and this time depends on the number on the number of weights that are moved. For example - If we need to measure 4 kg using weights 1 and 3 only, it will take twice as much time needed to measure 1 kg. Lets say we want to make sugar packets of weights 1,3,4 using weights 1 and 3 only. For this first we measure 1 kg, with 1 unit of time, we place 3 kg along with 1 kg and measure 4kg with again 1 unit of time, and finally we move 1kg out of pan to measure 3kg in 1 unit of time. So in 3 units of time we could measure 1,3 and 4kg using weights 1 and 3 only.

Now you have to make sugar packets of all weights from 1 to 125 in minimum time, in other words in minimum movement of weights. The question here is to find out the minimum number of weighs needed and the weight of each the weights used and the strategy to be followed for the creation of 125 packets of sugar.


Please post your solutions as comments.Solution will be posted soon in the blog.If any where its obfuscated or simple wrong pls feel free to correct.

23 comments:

Ricky Clarkson said...

"For example if shopkeeper has weights 1 and 3 then he can measure 1,3 and 4 only."

Surely he can measure 2.

Assuming he can't, I'd say 1, 2, 4, 8, 16, 32, 64, 128, 256, 512 are the required weights.

Christophe (vincenz) said...

Well I do not think the questions are that difficult.

In the first case, the poster is correct, it is simply the weights: 1, 2, 4, 8, 16, 32, 64, 128, 512

In the second case, we need to get subtractive logic involved as well. A quick analysis reveals that this means that we need to work in base 3 instead of 2 cause we only have three options. And for getting up to 1000 we then need the weights: map (3^) [0..6] meaning 7 weights.

In the third case it's also not so very difficult,. For some reason it reminds me of gray numbers, although in this case the bit encoding is fixed (the weights). The principle is the same, basically you want to minimize bitflips. So the maximum weight was 125, so we need 7 weights: map (2^) [0..6]. All that is required now is to traverse the space of all bits (except for the numbers 126 and 127 on, though if we include those number that's just two weight changes more cause each number can be arrived to by one weight change)
so that at each step we only flip one bit.

raganwald said...

With respect to the medium problem, if the unknown object has a whole number weight (1, 2, 3 ... but not 3.14 or 1.618), you do not need a one, the lightest weight should be a two.

As christophe points out, you can then work base 3 so the sequence goes { 2, 6, 18, ... } and not { 1, 3, 9, ... }

Dhananjay said...

excellent answers ....Christophe (vincenz)... :-) !!

Rishi said...

for medium ....it is 1,3,7,23,69,207,415,831.

This goes in a pattern like prev_num*2 + 1

Rishi said...

sorry it is sum of prev nums

MAWIA said...

i dont think roganwald solution is correct.how can some body weight for ,1 kg,3kg for expample with the denomanation of {2,6,18,...}....

Vitriol said...

I'm not computer guy, so let me talk ppure high school maths.

Basically its sum of geometric progession with first term=1 and common ratio=2.
a,ar,ar2,ar3....ar9=No of terms:10

So, sum of first 10 terms is
1023

I.e n=10

SO 10 weights are required

Yogesh said...

Rishi's solution is looking quite ok...

winnie_krithi said...

so is the final answer 125?

shiras said...

The third one has 2 pans.. one for measuring sugar and other for weights. first use the 1kg weight to measure one kg sugar. Now use this sugar and a 3 kg on the weigh pan to measure 2 kg and so on....

The sequence is 1,3,9,27,81.... this will end up the process in min time.

Mohd Shahid said...

For easy solution is 1,2,4,8,16,32,64,128,256,512 and medium answer is 1,3,8,16,32,64,256,512

Interview Puzzles said...
This comment has been removed by the author.
Interview Puzzles said...

Check interview puzzles for more puzzle with answers like this.

mahesh said...

For Hard problem.. the solution is 1,3,9,27,81 and we will measure in a sequence ..i.e., 1,(3-1),3,3+1,.....

I think this might be the best solution

neeraj/iitr said...

for medium, the solution could be 1,3,12,33,99,297,891

hemant_finding my way said...

Hi,
For the first question..
Can you prove/disprove that the set
(1,2,4,8,16,32,64,128,256 and 512) is the only sets of 10 weights that can be used to weigh all the weights from 1 to 1000 kg?

kanhaiya sharma said...

Great Blog with very good posts .Can you please tell me that how much time you take to create this wonderful blog,although i am new on internet but your work is very good and i appreciate your work.
Aptitude test

Ashish Lahoti said...

I have been asked the same question in one of the interview - How many minimum weighs required to measure weight from 1 to 60 kg?

If use one side balance (1,2,4,8,16,32 = 6 weighs)
If use both side balance
(1,3,9,27,81 = 5 weighs)

sWebDev said...

http://iamsoftwareengineer.blogspot.com Check out software aspirants

Ashutosh Mukherjee said...

explain the third one without using gray coding scheme

Christopher Oliver said...

I'm not a genius but bear with me.
Is this correct for 3?

1x1KG weight.
Measure 1KG bag
Move 1KG bag to other side
Measure 2KG bag
Remove 1KG bag
Move 2KG bag to other side
Measure 3KG bag
Following this process till you reach 125

A loop
measure N bag against N-1 bag + 1KG weight
Remove N-1 bag and replace with N bag
Repeat until N = 125

Vibhor said...

Good collection of puzzles.