## Search This Blog

### Simple Simple Google Interview Puzzle

Simple Simple Google Interview Puzzle - 7 September

The puzzle is if the 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 names the weights you will need to measure all weights from 1 to 1000.

1. Total 12 weight of 1, 2, 2, 5, 10, 10, 20, 50, 100, 200, 200, 500.

2. minimum weight required: 2 (weight 1 and weight 3 only)

3. 1, 2, 4, 8, 16, 32, 64, 128, 256, 512. Takes ten.

4. Ceiling(log2(1000)) = 10

This problem can be seen more abstractly as trying to encode any integer between 1 and 1000 in the fewest bits possible. (Integers corresponding to the integer weights, and bits corresponding to unique weights).

As such, you need at least the lowest integer greater than the base 2 log of the number of unique weights, which is ten. Constructing an example shows that 10 is also the upper bound. (i.e. 1, 2, 4, 8, 16, 32, 64, 128, 256, 512)

5. Has any one considered that you can add weights on the opposite side as well?

6. thats puzzle coming soon

7. i understand the solution but an anyone explain to me why we took 2 as a base ....plz

8. what is d solution??

9. There is a link after every puzzle

click on that link to get soln

10. You can think of it this way in if you take the 1,2,4,8,16 numbering system then each time you are only choosing a new number only when all other combination of the already present number is exhausted.
example:-
after 1, 2
3 is not chosen.4 is only chosen because both all combination of the possible numbers is done.
similary 8 is chosen only when all other combination of three numbers(1,2,4) is done(which is 3c0+3c1+3c2+3c3 = 8(0-7)).
So by induction we can prove that this is the best way

11. 1,3,9,27,81,243,729 only seven wt want

12. using these 7 weights we cant measure 2,5,6,7 and so on... therefore taking base as two is the right approach!

13. This is simply the numbers 2^0,2^1,2^2 ... that is 1,2,4,8,16... So for making 1000 kg we need up to 1, 2, 4, 8, 16, 32, 64, 128, and 512

14. The answer for the number of ights is : 7

but the anser of weights is not unique:

1, 3, 9, 27, 81, 243, 636

1, 3, 9, 27, 81, 243, 637

1, 3, 9, 27, 81, 243, 638

1, 3, 9, 27, 81, 243, 639

................

................

1, 3, 9, 27, 81, 243, 729

15. guys provided answer is looks wrong

for ex: 1, 2, 4, 8, 16, 32, 64, 128, and 512 with this numbers

you can't count: 27 (by placing one sided only)

i guess correct ans: arithmetic progression from 1 to 45

1. off course 1+2+8+16

16. 1,1,2,5,10,10,20,50,100,100,200,500