VMWare Inc Interview Question
Software Engineer / DevelopersCountry: United States
Theoretically, 3 iterations, log2(8) = 3
Assume balls are numbered 1 ~ 8.
Iteration #1: weight (1, 2, 3) against (5, 6, 7), if they are same, then either 4 or 8 is bad, then we need another weight to find the bad one. If they are different, suppose (1, 2, 3) < (5, 6, 7) (the other case can the handled in the similar way).
Iteration #2: weight (1, 4, 8) against (5, 2, 3), three cases:
case 1: (1, 4, 8) == (5, 2, 3), then either 6 or 7 is bad
case 2: (1, 4, 8) > (5, 2, 3), then either 2 or 3 is bad
case 3: (1, 4, 8) < (5, 2, 3), then either 1 or 5 is bad
Iteration #3: we now have 6 normal balls and two candidate bad balls, simply compare a normal ball with one of candidate ball, the it is easy to find out the bad one.
I think 2 times weighing is sufficient to figure it out an odd coin. Total coins 8. Divide it into 3,3,2 groups.
Case 1.
Iteration 1) check 3 coins with another 3 coins. if both are same, then other 2 coins having an odd coin.
Iteration2) So weighing 2 coins should give you heavier / lighter coin.
Case2)
Iteration 1) check 3 coins with another 3 coins. if both are not same, then among this 2 group we need to pick one group which is either heavier or lighter.
other 2 coins are having the same weight.
Iteration2) take heavier one and among 3 take only coins. Check 2 coins. If they are same in weight, then 3rd one is the odd number. else weighing should give us a result of a heavier coin.
It can be done in 4 iteration:
1) Create 2 groups - 4 balls each, Say group A and B
2) Weight balls from group A in pairs (on one side put 2 balls and on the other side put 2 balls from group A). - First iteration
3) If the sides are equal the faulty ball is in group B otherwise in group A.
4) Take 2 balls from the group which contains proper balls and 2 balls from the group which contain faulty ball and weight then with each other. - Second iteration
5) If the sides are equal the faulty ball is in the remaining two balls from the faulty group,
If different the faulty ball is in the balls which we are weighting.
6) So we have a group of 2 balls which contain faulty ball, say C.
7) Take one proper ball and weight it with every ball from the group C to find faulty ball. - 2 weights.
Total 4 iterations.
It can be done in two iterations
1) group 3,3,2 weight 3 group if they are equal you left with 2 balls if not you left with 3 balls
2)Now you have either 3 balls or 2 left, if can be solved by using 1 weight
I have answered it based on "8 coins are given where all the coins have equal weight, except one." which means it is one odd either heavy or light
Another approach to do it in 4 iterations:
1) Create 4 groups - 2 balls each, Say group A, B, C and D.
2) compare weight of each group - 3 iterations
3) After that you know which group is odd-one-out. Lets say it is group D (or faulty group).
4) Now take 1 good ball from any of the good groups- A, B or C. Take any ball from D group.
if weight of the ball from group D == weight of the ball from good group
- the other ball from group D is the answer.
else
- the ball which you are holding of group D is the answer.
This strikes me a good for show interview question...
Divide the 8 balls into two groups of 4. Weigh the two groups, noting which group is heavier. Split the heavier group into two groups 2. If these weight the same, discard them and the fake ball is lighter than the rest and in the group of 4 balls we didn't weigh. If these groups are different discard the balls we didn't weigh; the fake is heavier and in the balls we did weigh.
Split the remaining 4 balls into 2 groups and weigh. If the fake is heavier, toss the lighter group. If the fake is lighter, discard the heavier. Continue this process until you are comparing just 2 balls. At this point you will know which is the fake. For 8 balls, this takes lg(8)+1=4 iterations. The nice thing about this algorithm is that is scales for number of balls. Every power of 2 more balls you are working with, takes 1 more iteration (assuming perfect powers of 2)
That said,
This being only 8 balls, we can use some probability to get better performance over all, while every once in a while paying a penalty. Break balls into four groups of 2 randomly. Pick a group of two at random and weigh the balls. If they are equal, discard the group and repeat. Once you find a group where the balls are different, pick a ball from the different group and then pick a ball from another group that you didn't just weight. If the balls you picked weigh the same, then ball you didn't pick from the different group is the fake. If they don't weight the same, the ball you picked from the different group is the fake.
In the worse case, this could take 5 iterations...so why mention it? Well with only 8 balls and four groups there is a 1/4 of me picking the different group right off the bat. It would only take one more iteration to find the fake ball for a total of 2 iterations. If I didn't find fake on my first try, there is a 1/3 chance of finding on it on my second try and thus finding the fake in 3 iterations. 1/2 chance of finding it on the third try and thus finding the fake in 4 iterations (the same as I would have before) ...So what this really come down to are what are the odds of me take MORE iterations to find the fake.
It is a divide anc conquer problem. Best and Worst case are the same: log2(N) . In this case N=3, so the answer as someone already mentionned is: 3
Total 3 comaprison
1. compare group 1 against group2
a. If equals then compare group3 against group1 [problematic coin is in group3 or group 4]
i. If equal then take first coin in group 4 against first member in group1[Problem is with the coin in group 4]
1. If they are equal problem is with second coin in group4
2. Else problem is with first coin in group4
ii. Else take first coin in group 3 and compare with first element in group 1[Problem is with the coin in group 3]
1. If they are equal problem is with second coin in group3
2. Else problem is with first coin in group3
b. Else compare group 1 against group3[problematic coin is in group1 or group 2]
i. If equal then take first coin in group 2 against first member in group1[Problem is with the coin in group 2]
1. If they are equal problem is with second coin in group2
2. Else problem is with first coin in group2
ii. Else take first coin in group 1 and compare with first element in group 3[Problem is with the coin in group 1]
1. If they are equal problem is with second coin in group1
2. Else problem is with first coin in group1
The idea is to eliminate the maximum number of coins at a time which 2/3 at a time.
{
#include<iostream>
#include<stdlib.h>
#include<math.h>
using namespace std;
int main()
{
float n;
cin>>n;
for(int i=1;i<100;i++)
{
if(pow(3.0,i)>n)
{
if(i==1)
n=1;
else
n=i;
break;
}
}
cout<<n<<endl;
return EXIT_SUCCESS;
}
}
Step 1: 3 3 2: Compare 3 and 3. It is either in 2 or in 3.
Lets assume 3:
Step 2: break 3: 1 1 1
compare two of them. if they are equal, the last one is the fake one. else out of those two
take 1 compare it with another one, if they both are equal then its the solution else the other one is the solution.
So at max 3 iterations.
We can find the different one in 3 comparations by following steps:
Divide these 8 coins into 4 groups
then
- uuuouou April 22, 2014