## Microsoft Interview Question Software Engineer / Developers

• 0

There are 9 identical Maples out of which 1 is heavy. find that maple.

Country: India
Interview Type: In-Person

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

divide the whole in to three sets. each set again containing 3 maples.

now weigh two of the three sets using common balance. [ FIRST WEIGHING. ]

This will tell us the set in which the heavier maple is in. Hence, we are just left with 3 maples.

now, weigh the two maples on a balance with the third one aside. this will tell us the heavier one. [ SECOND WEIGHING.]

Comment hidden because of low score. Click to expand.
0

``This question seems to be Kid's stuff``

Comment hidden because of low score. Click to expand.
0

@saurabh
OK, this seems really to be a kid's stuff. What will you answer when you are asked why do you devide into three groups , etc. How would you describe the algorithm, if you are given not 9 marbles, but say 120, or some other number of them? This is the main point in posing this types of problems - to find out how the person thinks about attacking the problem, and how he/she would scale his solution and generalize the algorithm.

Comment hidden because of low score. Click to expand.
0

@ashot madatyan please tell how could one generalize and conclude the no of initial groups into vich prob shud be subdivided
???

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

@codinglearner
From the point of view of information retrieved by weighing the marbles, each weighing may yield us
three different results: the left pan is heavier, the right pan is heavier and the pans are in balance.
If we weigh two equal-sized groups of marbles, we are not using the complete information about the weighing - the case when the pans are in balance.
In that case (splitting into two equal-sized groups), we lose 1/3 of the information that comes from weighing.
This is why we need to maximize the use of information coming from weighing result, i.e. what part
of the marbles can be safely skipped as having no bad (heavier or lighter) marble.
So, to maximize the information usage, we will need to divide our marbles into three possibly equal-sized groups.
As soon as we weight the first two equal-sized groups and have the result, we can safely eliminate 2/3 of the total count
of marbles. We proceed with this logic until we are left with a single marble.
The task of repeatedly dividing by 3 eventually leads us to the formula
C = log3(N), where
N - the total count of marbles
C - the count of weighings required to identify the bad (heavier or lighter) marble

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

Here's my solution

``````#include <iostream>

using namespace std;

int unmberoftrails(unsigned int numberofcoins)
{
if(numberofcoins)
{
if(numberofcoins>3)
{
if(numberofcoins%3) // not divisible by 3
{
if(numberofcoins%2) // not divisible by 2
{
return 1 + unmberoftrails(numberofcoins-1);
}
else    //divisible by 2
{
return 1 + unmberoftrails(numberofcoins/2);
}
}
else    //divisible by 3
{
return 1 + unmberoftrails(numberofcoins/3);
}
}
else    // 1 ,2 ,3 shall take only 1
{
return 1;
}
}
return 0;
}

int main()
{
unsigned int noc = 0;
cout << "\n Entern number of coins => ";cin>>noc;
cout<<"\n Number of trails needed = "<<unmberoftrails(noc)<<"\n";
return 0;
}``````

Please let me know if there is a problem!!!

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

This is similar to the fake coin problem. Can be solved in logn time complexity. We just need to weight by breaking the collection into three sub-collections at a time.

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

I dare believe they are "marbles" not "maples" :)
Anyway, this is a known problem and the heavier one can be identified in just two weighings (I also believe the fact that you are given a scale is also missing from the problem statement :)).vDivide those marbles into 3 groups, each conating 3 marbles:
Weigh the group 1 and 2. If they are in balance, then the heavier one is in the third group - weigh any 2 of the remaining marbles in the third group, if they are in balance, then the third one is the guy. Similarly do for the case, when the first weighing identified the heavier group. Anyway, the total count of weighings is 2.

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

{and}... because at the compile time three braces is not necessary we can use only start brace and by convention we have to use other end braces ....

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

Any tried coding this up for n marbles.

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

Any tried coding this up for n marbles.

Comment hidden because of low score. Click to expand.
0

Here is C++ solution for this without using extra space and is O(log n ) in complexity..

``````#include<iostream>
#include <math.h>

using namespace std;

int getSum(int a[],int start,int size){

int sum =0;

for(int i=start;i<start+size;++i)
sum+=a[i];

return sum;

}

int findHeaviest(int a[],int start,int n){

if(start<0) return -1;

if(n==1) return start;
if(n==2){
if(a[start]>a[start+1]) return start;
return start+1;
}

int size;

if(n%3==0) size =n/3;
else size=n/3+1;

int LSum=getSum(a,start,size);
int RSum=getSum(a,start+size,size);

if(LSum==RSum) return findHeaviest(a,start+2*size,n-2*size);

if(LSum>RSum) return findHeaviest(a,start,size);

return findHeaviest(a,start+size,size);

}

int main(){

cout<<"Find Heaviest Element"<<endl;
int a[]={1,1,1,1,1,1,1,2,1};
int b[]={1,1,1,1,1,1,1,2,1,1,1,1,1};
int c[]={1,1,1,2,1,1,1,1};

cout<<"Heaviest index"<<findHeaviest(a,0,9)+1<<endl;

cout<<"Heaviest index"<<findHeaviest(b,0,13)+1<<endl;

cout<<"Heaviest index"<<findHeaviest(c,0,8)+1<<endl;

return 0;
}``````

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

try "find defective maple out of 9 maples"
note: defective cn be either heavier or lighter

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

The solution for number of time the balls needs to be balanced is

``logN``

with logbase as 3 .....

Name:

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

### Books

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

### 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.