Microsoft Interview Question Software Engineer / Developers


Country: India
Interview Type: In-Person


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

ANSWER:: 2

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

- krishnakanth on June 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This question seems to be Kid's stuff

- saurabh on June 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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 on June 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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 on June 26, 2012 | Flag
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

- ashot madatyan on November 16, 2012 | Flag
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!!!

- aashutosh.mishra on November 13, 2012 | Flag Reply
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.

- Pavan Dittakavi on June 23, 2012 | Flag Reply
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.

- ashot madatyan on June 23, 2012 | Flag Reply
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 ....

- debasish2deb on June 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Any tried coding this up for n marbles.

- AA on July 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Any tried coding this up for n marbles.

- AA on July 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- AA on August 06, 2012 | Flag
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

- prakhar on July 30, 2012 | Flag Reply
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 .....

- vasa.v03 on February 06, 2013 | Flag Reply


Add a Comment
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.

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