VMWare Inc Interview Question for Software Engineer / Developers


Country: United States




Comment hidden because of low score. Click to expand.
3
of 3 vote

We can find the different one in 3 comparations by following steps:
Divide these 8 coins into 4 groups

group[1] = [1,2]
group[2] = [3,4]
group[3] = [5,6]
group[4] = [7,8]

then

COMPARE group[1] with group[2]
if group[1] has the same weight with group[2]
	//now we know [1,2,3,4] are good
	COMPARE group[1] with group[3]
	if group[1] has the same weight with group[3]
		//now we know [1,2,3,4,5,6] are good
		COMPARE 1 with 7
		if 1 has same weight with 7, then 8 is fake
		else 7 is fake
	else
		//now we know the fake one is in [5,6] and whether if it's heavier or lighter!!!
		if group[1] is heavier than group[3]//the fake one is lighter
			COMPARE 6 with 7, the lighter one is fake
		else//the fake one is heavier
			COMPARE 6 with 7, the heavier one is fake
else
	//now we know [5,6,7,8] are good
	if group[1] is heavier than group[2]
		COMPARE group[1] with group[3]
		if group[1] has the same weight with group[3]
			//now we know the fake one is in [3,4] and the fake one is lighter
			COMPARE 3 with 4, the lighter is fake
		else//now we know the fake one is in [1,2] and the fake one is heavier
			COMPARE 1 with 2, the heavier is fake
	else
		COMPARE group[1] with group[3]
		if group[1] has the same weight with group[3]
			//now we know the fake one is in [3,4] and the fake one is heavier
			COMPARE 3 with 4, the heavier is fake
		else//now we know the fake one is in [1,2] and the fake one is lighter
			COMPARE 1 with 2, the lighter is fake

- uuuouou April 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Beautiful solution!

Dividing balls into 4 groups is really helpful.
Trying to infer the type of fake ball (heavier or lighter) along the way is also an essential trick.

- ninhnnsoc April 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

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.

- Yuan May 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 3 vote

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.

- Anonymous November 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- hulkthedestroyer April 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

in the 7th point u have considered 2 iterations i think 1 iteration is enough. If we weigh one ball from faulty pair with proper ball, if they are equal then other ball is faulty ball if they are not equal then considered ball is faulty

- madridista April 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- malatesh April 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

It could be done in this way if you know whether the ball is heavier or lighter. Here you know only that the one ball is faulty.

- hulkthedestroyer April 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous April 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You wrote "ls if not you left with 3 balls", which 3 balls? How do you know whether to choose heavier or lighter group?

- hulkthedestroyer April 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Pawan Kishor Singh April 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Huh? What iterations? Using a two pan balance? Spring loaded weighing scale? Other means?

At least give the whole problem...

- Anonymous April 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Anonymous April 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Sofianito May 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is a divide and conquer problem. Worst case is: log2(N) . In this case N=8, so the answer as someone already mentionned is: 3

The best case is 2

- Sofianito May 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous September 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

}

- Vishal October 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Akki March 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Peoples are saying to break in 3,3,2.
Suppose if 1st 3 coin and other 3 coins don't wight the same, how would you decide which 3 coins to pick for next iteration.
So correct answer is 3 iteration, with split 2,2,2,2.

- Sanjit November 07, 2020 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More