CareerCup

I will ask interviewer more questions about whats in the bottle. The reason is if bottle contents are something which can be individually selected, then this can be solved in a single weighting as follows:

Lets say after asking questions, We have more information that bottle contains pills. Every pill is of 10grams each except in one of the bottle which has 9 grams pills. Also say the bottles are marked 1, 2, 3, 4 and out of that bottle 3 has contents with less weight.

So I will pick up 1 pill from bottle 1, 2 pills from bottle 2, 3 pills from bottle 3 and 4 pills from bottle 4.

So I have total of 1 + 2+ 3+4 pills = 10 pills

Their ideal weight should have been 10 pills of 10 gm each = 100 grams

Now since bottle 3 is defective, total weight of the pills would come out to be 97 grams.

That will tell us that its less by 3 grams so its 3rd bottle which is defective. If the weight would have been less by 4 grams, then the 4th bottle would have been at fault.

Programs for the same shouldnt be hard to write.

Saurabh

requires 2 weighs

Pick 2 bottles at random. Weigh, if unequal then you are in luck, you now know exactly which one is defective, with probability of 0.58333
if equal, choose 1 of remaining bottles, probability of you picking the right bottle : 0.5

Best of Luck :)

require 2 weights...

What If, If I put bottles one by one on the weighting machine and keep checking the weights, every time when we put bottle of same weight the total weight will be multiple of weight of one bottle but as soon as we put less weight bottle it will be less than that, and thus we come to know which bottle is less heavy, not sure It might be a very bad idea ;)

put two bottles at one side and remaining bottles at other side of the weighing machine, which side has less weight, choose which one from that side.

public class test2 {

	public static void main(String[] args) {
		int[] a = {3,3,3,1};
		int compare = 0;
		int preResultIndex1 = 0;
		int finalValue1 = 0;
		int preResultIndex2 = 0;
		int finalValue2 = 0;
		
		for(int i=0; i<a.length;i++){
			if(i ==0)
				compare = a[i];
			else if(i == 1){
				if(compare != a[i]){
					preResultIndex1 = 0;
					preResultIndex2 = 1;
					finalValue1 = compare;
					finalValue2 = a[i];
				}
			}else if(i == 2){
				compare = a[i-1];
				if(compare != a[i]){
					if(preResultIndex2 != 0){
						if(finalValue1 == a[i]){
							System.out.println("found:" + preResultIndex2);
							break;							
						}else{
							System.out.println("found:" + preResultIndex1);
							break;
						}
					}else{
						preResultIndex1 = i-1;
						preResultIndex2 = i;
						finalValue1 = compare;
						finalValue2 = a[i];
					}
				}else{
					if(preResultIndex2 != 0){
						if(finalValue1 == a[i]){
							System.out.println("found:" + preResultIndex2);
							break;							
						}else{
							System.out.println("found:" + preResultIndex1);
							break;
						}
					}
					
				}
			}else if(i == 3){
				compare = a[i-1];
				if(compare != a[i]){
					if(preResultIndex2 != 0){
						if(finalValue1 == a[i]){
							System.out.println("found:" + preResultIndex2);
							break;							
						}else{
							System.out.println("found:" + preResultIndex1);
							break;
						}
					}else{
						if(preResultIndex2 != 0){
							if(finalValue1 == a[i]){
								System.out.println("found:" + preResultIndex2);
								break;							
							}else{
								System.out.println("found:" + preResultIndex1);
								break;
							}
						}else{
							System.out.println("found:"+i);
						}
					}
				}
			}
				
		}
	}
}

God know how with only 1 measurement ! But what we can do is keep all of the four bottles on the weighing machine... Note the total weight, and pseudo individual weights (total weight / 4..).. remove one bottle, now note down the weight of the removed bottle (total weight - weight of 3 bottles), if it is less than the pseudo individual weight then this is the bottle which is odd man out. If the removed bottle's weight is greater than pseudo individual weight then this bottle is one among the 3 bottles which weigh same. Now you know the actual weight of the true bottle. keep removing the bottles until you find a bottle which is not same as weight of the true bottle.

I think we need to design a 3-WAY comparison scale... LOL

I think u r correct we need to justify why it can't be done in one shot and go for 4 4 way weighing machine.

Bottles are 1, 2, 3, 4. L = Left pan of scale, R = Right pan of scale

Step 1:

L(1), R(2) - if pan weights are not equal, we have found the bottle that weighs less
If pan weights are equal, do Step 2.

Step 2:

L(1, 3), R(2,4) - this step will tell us which of the two bottles - 3/4 is of lesser weight.

All bottles have been weighed just once and we know which bottle weighs less.

How about using four different weighing machines and keep all the bottles on it at the same time, the one which weighs less is defective.. in one single weigh...may not be cost effective though but worth a try.

not likely to be done...

Get 3 sticks of wood and mark the middle. Find some rope and time one rope to the end of the first stick (stick 1) to the middle of one of the other sticks (stick 2), repeat the process on the other end of stick 1 (to stick 3). Tie the bottles to the ends of stick 2 and 3, hang the contraption from the middle of stick 1 and you will have a double balance.

There are two possible scenarios, the bottle is defective because it either weights less than the others or it weights more than the others. In either case you will find which one is defective by looking at the balance of stick 2 and 3.

We can't do it in a single weigh but if there are 8 bottles and 1 bottle weigh different than the other 7, then we can find it in 2 weighs.
1) Divide the 8 bottles in a group of 3,3,2
2) weigh group of 3 and 3, if the weight is equal then the bottle is present in the other group of 2 and we can determine in one more step.
3) if the bottle is present in one of the group in 3, then choose 2 bottles at random from this group weigh them if the weight is equal, the defected bottle is the other one which we left else we have found the bottle in group of two.

We can find defective bottle in only one weight:
1. Put 2 bottle at one side and remaining 2 at another side of weight machine.
2. One side will heavy and another side will be less.(due to one of them have less weight)
3. Remove one and one bottle form both side.(one from left and one from right side of weight machine)
4. If remaining bottle on weight machine are equal.
5. Removed bottle form less weight side will be defective.
6. Else remaining bottle on weight machine will show the defective bottle.