Microsoft Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
@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.
@ashot madatyan please tell how could one generalize and conclude the no of initial groups into vich prob shud be subdivided
???
thnx in advance
@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
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!!!
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.
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;
}
ANSWER:: 2
- krishnakanth June 23, 2012divide 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.]