Microsoft Interview Question


Country: United States




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

Here is the approach:

1) Take a Bolt B.
2) Take a Nut N.
3) while(more nuts && B >= N) {
Throw away this nut & take next Nut N;
}
if(no more nuts)
Print B.
4) while(N > B){
Throw away this Bolt and get next Bolt B;
}
go to Step 3.

Complexity: O(B + N).
Assumption: There is only one Bolt which is > all nuts.

- havefun December 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Buddy... Pls ReCalculate the Complexity..
Its hell not O(B+N).

FYI.. U missed to calculate the gotoStep 3 part.. which may run for again O(B) or O(N)..

Making it total of O(B2) or O(N2)

- hprem991 December 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Take this case in view... if the nuts get finished at some point, we cant find the biggest bolt then....

- ML December 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

Hold on guys,

@ML, didn't see the assumption? Only one Bolt is > all the nuts. So In this case if all the nuts are exhausted then the present Bolt is the biggest of all. Further, if there are more then one bolt that is bigger then all nuts, I am sure you don't have an answer of finding the biggest bolt.

@hprem91, it's heaven O(B+N) lol..(this is worst case, avg case might be less than that).......here is the reason why, you won't run either step 3/4 for O(B)/O(N) times...as you are throwing away the nuts/bolts once they fail the condition. Worst case can happen only when the Biggest Bolt you are taking out is the last Bolt in the bag. This takes O(B + N).

- havefun December 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

perfect! works great and complexity is correct.

- karthik December 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The solution is correct.

- Code January 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

The correct assumption is: there must be One and only one bolt larger than any nut; otherwise, the problem cannot be solved.

For instance, there is no solution for this:
B: 1, 3, 2
N: 5

- Nut Bolt January 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

-> Problem is we have two unsorted array, both array contains same and equal number of elements .
-> We have to find the maximum element from array 1st.
-> Here condition is you can not do any comparision within same array.

Algorithm:

Step 1: Pick a element from array1.

Step 2: And compare it with element of array2 till we get the larger or equal number.

Step 3: If found larger element in step 2 then start comparision with array1 till get equal or larger number and repeat step2.
else return the equal number found in step 2.

- Anonymous December 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, it is looking similar problem as mentioned by you.

- Anonymous December 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This looks good!!!

- Gajanan Rudrawar December 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How can u say both arrays have same elements (in regard to this problem) ?

- WeAreBack January 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

0.1) Assumption: We have empty spare bags to use (or memory)
0.2) Assumption: No two bolts should be bigger than biggest nut
0.3) Extra Assumption (not MUST): No two nuts should be bigger than biggest bolt
1) We can not sort bags as we can't compare the two bolts and two nuts
2) But there is a math law here: Nut1 < Bolt1 and Bolt1 < Nut2 implies Nut1 < Nut2. We can divide any bag into two portions with a reference of a other bag item.
2.1) Have two spare bags, namely lowBag and highBag
3) Take a nut (randomly), for every bolt
3.1) compare the bolt with nut. If bolt < nut, put it in lowBag; otherwise put it in high bag
3.2) Now we have emptied the original bolt bag and have two new bolt bags
3.3) If highBag has at least one item, throw away the lowBag items
3.4) If highBag is empty, nut is greater than all bolts - throw away the nut
3.5) Now we have only one bag
4) Repeat step (3) and sub-steps with a new nut
5) After finishing all nuts with steps (3) and (4), we will have highBag with few items
5.1) With assumption (0.1) - highBag should contain only one item (biggest bolt)
5.2) With assumption (0.2) - the first nut to be thrown away in step (3.4) is biggest nut

If no. of bolts is b and no. of nuts is n - The time complexity is O(n * b * log(b))

Thanks,
Laxmi

- Laxmi Narsimha Rao Oruganti December 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@havefun.. its a neat solution..

- truelies December 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bolt getBigBolt(Bolts, Nuts) {
type op = NUT;
if (bold.empty())
  return null;
bolt = Bolts.get(); //get a bolt from the bag;
nut = null;
while(!Nuts.empty() || !Bolts.empty()) 
{
  if(op == NUT) 
 {
   if (Nuts.empty()) break;
   tempNut = Nuts.get();
   if (tempNut >= bolt) //continue until bigger nut than the current bold is found
    {
      nut = tempNut;
      op = BOLT; // switch picking bolt
     }
  }
  else // op == BOLT
   {
       if (Bolts.empty() break;
       tempBolt = Bolts.get();
       if(tempBolt >= nut)  
       {
          bolt = tempBolt;
          op = NUT; // switch picking nut
        }
   }
 }
 return bolt
}

- JollyJumper January 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@havefun's solution is correct I think.

- Kevin March 02, 2013 | 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