Gluster Interview Question
Applications DevelopersCountry: India
Interview Type: Written Test
so, ultimate solution is 4.. we have to give best solution for worst case in problem solving..
hmm .. ya i think 4 is solution .. i tried a lot to bring the worst case to 3 but no result ..
We can get the answer in 4 steps.
Procedure:
Take 3 balls at a time.
Say, the balls are BBBBBBB'B'
Take 3 balls at a time, which could be
a)BBB BBB equal
b)BBB' BBB' equal
c)BB'B' BBB unequal
d)BBB' BBB unequal
Then try two balls from the 3's selected.
Then compare the two balls in each beam from step 1.
This on comparison with the 2 balls left from the first step will give you the required answer.
Just try the steps ,analyse each result and eureka...
Can anyone find any better solutions than the following?
A B C D E F G H
1. WEIGH ABC with DEF (W1)
2. Case ABC == DEF
Case 1: ABCDEF are light. GH are the two heavy ones.
Case 2: One of ABC is heavy. One of DEF is heavy. GH are both light.
WEIGH AB with GH (W2)
2.1. AB = GH, then GH are both light, C is BallOne. WEIGH 2 of DEF to find BallTwo. (W3)
2.2. AB < GH, then GH are both heavy - BallOne and BallTwo. (DONE WITH 2 WEIGHINGS)
2.3. AB > GH, then GH are both light. C is light. One of AB is heavy. One of DEF is heavy. WEIGH A with B to find BallOne (W3). WEIGH two of DEF to find BallTwo (W4).
OR WEIGH A with B (W2)
2.1. A >B then A is BallOne, and GH are both out. WEIGH two of DEF to find BallTwo (W3).
2.2. A == B then we know both AB are light. WEIGH CD with GH (W3):
2.2.1. CD == GH is not possible.
2.2.2. CD < GH then GH are the 2 heavy ones.
2.2.3. CD > GH then C is BallOne. WEIGH D with E (W4), if D > E, D is BallTwo; if D=E, F is BallTow; if D < E, E is BallTwo.
3. Case ABC > DEF:
We now know 1-2 of ABC are heavy, 0-1 of GH is heavy.
WEIGH G with H (W2)
3.1. G > H then G is BallOne. WEIGH two of ABC (W3), if equal the 3rd is BallTwo, if not the heavier is BallTwo.
3.2. G == H then both GH are light. WEIGH two of ABC (W3), if equal they are both heavy, if not the heavier is BallOne and the third is BallTwo.
The problem statement doesn't say that the two heavier balls weigh the same. I don't think anyone's taken that into account.
I get a worst case of 7 steps:
1) Set 4 balls aside, split the other 4 into pairs & put them on the scale
Cond 1: scale balances
Two possibilities:
1) they're all light balls
2) the heavier balls weigh the same & one is in each pair
To find out which possibility is correct:
1) Put each ball from one of the pairs on the scale
Scale balances - all 4 are light balls. Set them aside
& repeat above on the other 4 balls. Total steps = 2
Scale unbalances - you've found one of the heavier balls
Repeat the procedure on the other pair to identify the other heavier ball
You're done. Total steps = 3
Cond 2: scale unbalances
Three possibilities:
1) One of the heavier balls is in the heavier pair
2) Both of the heavier balls are in the heavier pair
3) One of the heavier balls is heavier than the other and they are in different pairs
To find out which possibility is correct:
1) Put each ball from the lighter pair on the scale
possibilities:
1) both are light
2) one is light, one is heavy
If scale balances - both are light & poss 3 is eliminated
- put one identified light & one ball from the heavier pair on the scale:
balances - poss 1 is occurring, the other ball f/ the heavier pair is identified heavy
unbalances - the heavier ball on the scale is identified heavy
You now know the make-up of the 1st 4 balls: either all light, 1 heavy 3 light, or 2 heavy 2 light
Worst case is they're all light:
Retrieve the 4 balls set aside.
1) Put 2 of those balls on the scale against 2 known light balls
Scale balances: all 4 balls are light, the other two balls in the second set of 4 are heavy. You're done.
Scale unbalances: one or both balls on the heavy end are heavy
- put one identified light ball on the scale against one from the heavier pair.
balances - the other ball of the heavier pair is identified heavy
unbalances - the heavier ball on the scale is identified heavy
- repeat the above to find out if the second ball of the heavier set is light or heavy. If found heavy,
you're done
If found light;
2) Put an identified light ball on the scale against one of the balls that hasn't been weighed yet:
Scale balances - the last ball is the 2nd heavy ball
Scale unbalances - the ball being weighed is the last heavy ball
All balls identified.
Min # steps: 4
Max # steps: 7
I hope I never get something this bad in an interview!
divide the 8 balls in 3 groups
- mAn1Ac September 06, 2012say .. group A => 3 balls
group B=> 3 balls
group C =>2 balls
put group a and b on balance ..
case 1) A = B .. implies either both a and b have the one heavy ball or group c have both the balls
so choose any two balls from any one of the group ie. A or B (suppose i chose group A) and weigh them against group C ..
if (the balance balances)
{
that means the third ball of group A is heavier one and the other heavy ball is in group B .. so to get it choose any two balls from group B and weigh them against each other ..
if (they are equal)
{that means its the third ball of group B..}
else
{its the one which is giving more weight on balance ..}
}
else if (the side with group C on it is heavier)
{ both the balls of group C are heavy balls .. the required balls ..
THIS IS THE BEST CASE }
else // side with group A's balls is heavier
{
this means one of the two balls are heavier .. (THIS IS THE WORST CASE)
now weigh both balls against each other u will get one heavy ball ..
for next heavy ball take any two balls from group B and weigh them .. if they are equal then its the third ball otherwise which ever is heavier ...
}
Case 2) side with A is heavier ..this means either one heavy ball is in A and another in C or both are in A ...now take 2 balls from A and weigh them against group C
if(balance balances)
{
this means each side has one heavy ball .. now in each of these groups weigh one ball against another to get the heavy balls .. THIS IS ALSO WORST CASE
}
else if(side with C on it is heavier)
{
weigh the balls of C against each other .. if equal means these are the two required balls .. if not then u will get one heavy ball and the other heavy ball is the third ball of group A ..
}
else
{
weigh the two balls of group A .. if equal then they are the required ones .. if not then u will get one heavy ball and the other heavy ball is the third ball of group A...
}
Case 3) side with B is heavier .. same as case (2) ..
FINALLY,
for BEST CASE => 2 comparisions
for AVERAGE CASE => 3 comparisions
for WORST CASE => 4 comparisions ..