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.

For Solution : Click Here

16 comments:

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

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

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

    ReplyDelete
  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)

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

    ReplyDelete
  6. thats puzzle coming soon

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

    ReplyDelete
  8. what is d solution??

    ReplyDelete
  9. There is a link after every puzzle
    For Solution : Click Here.

    click on that link to get soln

    ReplyDelete
  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

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

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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete