Oracle Interview Question Software Engineer / Developers
Country: India
xy xy xy ab...... how can u neglect the result of xy xy as they all are identical...... we cant differentiate b\w them
xy xy xy ab 4steps
so suppose result is x<y
x x x a
xx xa 2steps
xx equal neglect it check only xa pairs result is ans
total 6steps
1. compare xxx to yyy
suppose yyy is heavier than xxx
so x <y
2. compare a to b
suppose a<b so
3. compare a to x
if a is light then answer is a
if x is light then answer is x
vice-versa for y
in last possibility if we get ' x' as a result from xy
and 'a' from xa,'b' from yb
so nw fr comparison we have x x a b and i make pair of xa and xb
how it can be done 6 steps then?
@rahul you're right, OP's approach cannot resolve xy xy xy ab. I would propose the following:
If all 4 groups' results are not equal, then we have
1) xy xy xy ab or 2) xa yb xy xy
Now, put the lighter balls from the first and the second group to the LHS of the scale, and put the lighter balls from the first and the second group to the RHS of the scale (that is, we have 2 balls for each side), then we have 3 possibilities:
1) min(x,y) + min(x,y) vs. min(x,y) + min(a,b)
2) min(x,a) + min(y,b) vs. min(x,y) + min(x,y)
3) min(x,a) + min(x,y) vs. min(y,b) + min(x,y)
It is not hard to show that the lightest ball must be in the lighter side, which has two balls. Compare those two balls and choose the lighter one. If they're equal, then choosing either one is fine.
Consider case 1) for example, i.e., min(x,y) + min(x,y) vs. min(x,y) + min(a,b), if the LHS is lighter, then that implies min(x,y) < min(a,b). Now let's compare the two balls on the LHS, i.e., min(x,y), min(x,y), and they turn out to be equal. Now we can pick either one and return.
@rahul I agree with you the xa yb xy xy case cannot be resolved in 6 steps following the OP's approach.
Let me propose something else. If all four groups turn out to be not equal, then we have:
(1) xy xy xy ab or (2) xa yb xy xy
Next, let us throw away the heavier ball from each group, then we have 4 balls remaining and they could be:
(1) min(x,y) min(x,y) min(x,y) min(a,b)
or
(2) min(x,a) min(y,b) min(x,y) min(x,y)
Now split the 4 balls into two groups (with 2 balls per group) and compare. There are three possibilities:
(i) min(x,y) + min(x,y) vs. min(x,y) + min(a,b)
(ii) min(x,a) + min(y,b) vs. min(x,y) + min(x,y)
(iii) min(x,a) + min(x,y) vs. min(y,b) + min(x,y)
It is not hard to show that the lightest ball (our target) must be on the lighter side of the scale. We can resolve the two candidates by using one comparison.
For example, if we had (i) min(x,y) + min(x,y) vs. min(x,y) + min(a,b) in the previous step, and the LHS is lighter. That implies min(x,y) < min(a,b). Now we compare the two balls min(x,y) and min(x,y) from the LHS, and they turn out to be equal, so we return either one as our result.
i think it can be done is 5 steps:
1.make 4 group of 2 each.
2. compare 1st group with the 2nd. you come 2 now about the lighter group.
3. compare any one coin from first group with one from second. you get lighest of the 4.
4. repeat for 3rd and 4th group.
5. compare the two lighter ones to get the lightest.
your solution seems correct if the weight balance is provided if suppose wighing machine is provided than this wont work. Kindly comment
in this kind of questions, u are supposed to solve them using weighing balance only. coz the results are based on the relative weight of one compared to other. if chcking for absolute weights, u ll be needing as many no. of comparisons as the no of coins.
@Ashish
you wanna say that there is two type of weights!
7 have same weights and other one does not have!
But what is a,b,x,y have different weightings! correct me if i misunderstood :)
x x x y y y a b
possible pairs
xx xy yy ab 5
xa xb xy yy 6
xy xy xy ab 6
xa yb yy xx 5
xa yb xy xy 6
ans can be obtain in 6steps max in any case, by eliminating pair with same weight because if threre is same wait then it must be pair from 3 unit, so if we reject it then also one uni is remain
this problem will be solved by divide and conquer we dont need 7 comparisons. Dive 8 /2 = 4 sets compute the lesser on each subsets. now we will get 4/2 = 2 sets again lesser of 2 will be the smallest one.
e.g. set{3,3,3,4,4,4,2,1}
divide in to four 33, 34, 44,21 lesser of these 4 sets
3,3,4,1 create 2 sets 33, 41 lesser of these
3,1 make a set compare we will get 1 as the smallest we need only 3 comparisons. Let me know if we have a better approach.
Thanks
Bala
I think this is the worst solution. Maybe someone can build up on this(?)
1)Take any random coin and weigh each of the other coins against this one. Arrange all coins with respect to this coin on a table (i.e heavier ones to the right, and lighter ones to the left of the coin. If weights are equal, then stack them over the base coin). Now since you know which coin you used to compare with the others, you can remove all those coins and any coin heavier than that coin from the picture (remove from your table and throw them away).
Now repeat the same process taking the coin which is relatively just lighter than your previous common coin used for comparison. Eventually, you should get just 2 coins of which one will be the "lightest" of them all.
Am I wrong? This may be a bad method, but makes no assumptions whatsoever. Also, it is guaranteed to find you the absolute lightest coin in the mixture of coins.
Thanks and any feedback is appreciated!
a small change to Ashish 5 steps,
In the third step, compare the two elements with each other in the ligther group and the element which is ligther will be the ligther element among 4 elements(of two groups)
eg say gropA -elements wt 10,8 and Gropu B wtv12,6.Now Group A> Group B..so Group B is ligther and if compare 12 and 6..obviously 6 is least elemet among four elemrnts(10,8,12,6). Plz let me if i my understanding is wrong
the combinations are:
com 1:xy xy xy ab all 4 groups distinct none off them have element with equal wt.
com 2:
ax bx xy yy
ay by xy xx these 2 combination, 1 group will have equal element
com3:
ax by xx yy
ay bx xx yy
ab xy xx yy these 3 combinations have 2 groups with equal elements
in com1 after 4 weighings btw group members you will have either x x x a or yyyb or xxxb or yyya. now again group into groups of 2 and weigh. you will find that 1 group has elemnts of same weight and other have elements of diff wts.lighter in group with diff weight is the lightest.(total 6 weighings)
in com 2: after initial 4 weighings to determine the combination.neglect the group with equal members from competition as those members are already in other groups.no weigh 1st group against 2 group and 3 group.that is 6 weighings now you know the lightest group and the lightest member of them(initial comparison).
in com3 : neglect the 2 groups with equal members as these weights will be in the other groups as well.weigh the lighter members of the other two groups and lightest of them is the lightest of all coins.so you have answer in 5 weighs.
in any combination max number of weighings is 6 except com3 then it is 5
Good explanations where already given further up. Still for me
it is always easier to understand a concept when I can related
it somehow to the 'real world'
Think of a sports event where always the weakest wins
and moves up to the next round of comparisons. That
would require 7 'matches' to find the winner. Since there
are two sets of three, equals/'ties' can be eliminated
since there is still a third coin 'in the game' with the
same weight that would win in case it was the lightest.
c
c <-- 7 --> c
c <--5--> c c <--6--> c
c<-1->c c<-2->c c<-3->c c<-4->c
There is only a limited number of combinations
possible:
- two ties on either side of the tree (left or right)
in the first round.
-
- <----------> WINNER
----------- c <--5--> c
TIE TIE
x<-1->x y<-2->y a<-3->x b<-4->y
- one tie on each side of the tree in the first round
WINNER
c <--- 5 ---> c
- <----> c - <-----> c
TIE TIE
x<-1->x a<-2->x y<-3->y b<-4->y
- only one tie or second one in case x (or y) is
the lightest
WINNER
c <--- 6 ---> c
c <--5--> c c <-----> -
TIE
x<-1->a x<-2->b x<-3->y y<-4->y
- one tie in the second round
-
TIE <----------> WINNER
c <--5--> c c <--6--> c
x<-1->y x<-2->y x<-3->a y<-4->b
Hope it helps.
4 cases..
suppose there are 8 coins with weight( 1,2,3,3,3,4,4,4) divide them randomly into sets of four like(1,2)(3,3)(3,4)(4,4) now compare these sets will get two sets (2 comparisons) .
again compare the least two (1 more comparison) now compare the last set (last comparison).
(1,2)(3,4)--->>(1,2)-->>1
The problem does not say that we need to compare in sets of two. So here is the algo
1) Divide 8 coins in 2 sets. In 1 weigh get 4 lighter coins.
2) Divide 4 coins in two sets. In 1 weighs you will get 2 lighter coins.
3) In last 1 weigh you will get the lightest coin.
Total 3 Weighs
its not like, all weigh the same except the one.
how can you assure that the light set you get on one first weighing will have the lightest coin.
3 steps:
compare x units and y units coin eliminate the one with higher weight
then compare the remaining coin(either x or y) with a units coin and eliminate the one with higher weight
finally compare the remaining coin(either x or y or a) with b units coin and eliminate the one with higher weight..........!!!!!!!!!!!
I was wondering, it could be done in 3 steps.
Groups {XXX,YYY,A,B}
Step 1: Weight between XXX and YYY. Find the least weight in it. Namely, X
Step 2: Weight between A and B. Find the least weight among them, Namely, A
Step 3: The least weight would be among X and A. We can try one more time, and it seems we are done. :)
Correct ans is 6step
- Ajit Deshmukh August 30, 2012Assume weights
x x x y y y a b
possible pairs
xx xy yy ab -> xx yy reject as equal, now compare result of ab & xy ->steps=5
xa xb xy yy -> reject pair yy, compare result of pair xa & xb then compare it with reult of xy ->step=6
xy xy xy ab 6-> reult of xy&xy wil be same so reject pair ->steps=6
xa yb yy xx -> same as first-> steps=5
xa yb xy xy -> steps=6
ans can be obtain in 6steps max in any case, by eliminating pair with same weight because if threre is same wait then it must be pair from 3 unit, so if we reject it then also one unit is remain of tht weight