Senior Applications Developer Interview
There are 10 stacks of 10 coins each. 9 of the stacks contain coins that weigh 1g each. The other stack contains coins of 2g each. The coins look the same. We have a scale that we can get a measurement of grams from, not a balance. We can use the scale exactly once to weigh anything here from a single coin to all of them. How can we determine which stack is the 2g coins?
Weigh these together: 10 coins from stack 1, 9 from stack 2, etc ending with 1 from stack 10. The weight of these will tell you which stack has the 2g coins. Ex: if it's 1st stack: 65g, 2nd: 64g, 10th: 54g
A more eloquent answer would be: Weigh together 1 coin from stack 1, 2 coins from stack2, 3 coins from stack 3, etc. Subtract 55 from that total weight to get the number of the stack with the 2g coins.
Jatin Rai on
Binary sort 1. Use single coin (I'd drop my stacks *s*) from each stack. Mark them by stack. 2. Place 5 each on both scales; note lower scale. 3. Place 2 coins on each scale, keep one aside; note scale. 4. If scales are at same level the coin NOT on the scale indicates the stack with heavier coins. Done. 5. If one scale is lower place 1 coin on each scale, note lower, identify stack. Done.
Doug Dodge on