Interview Question

Senior Software Engineer Interview Bedford, MA

1 different weight object out of 8, how to find with least

  measurement.
Answer

Interview Answer

2 Answers

0

weight 3 objects against 3 objects ...

Interview Candidate on Mar 25, 2009
0

This tests that you understand a decision tree, and the notion of a binary sort. Divide the group in to 4 x 4. It is known in this example that an odd weight exists so there is no need to measure those, it will be unbalanced. Chose one group randomly and divide into 2 x 2. Measure these against each other. If they balance reject this entire group of 4 and use the other group of 4 and repeat. If they don't balance chose one group of the 2 x 2 randomly and divide into 1 x 1... At most 3 measurements because 2**3 = 8

Furd on May 29, 2009

Add Answers or Comments

To comment on this, Sign In or Sign Up.