Microsoft Interview Question
Country: United States
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)
Take this case in view... if the nuts get finished at some point, we cant find the biggest bolt then....
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).
-> 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.
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
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
}
Here is the approach:
- havefun December 12, 20121) 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.