## Cisco Systems Interview Question

SDE-2s**Team:**Video processing capabilities

**Country:**India

**Interview Type:**In-Person

@algos

Good one.

I think step 2 can be modified a bit to reduce the number of overall comparisons. .

Once the first matching bolt is placed in its correct position, take a 2nd nut at random and compare it with the first matching bolt. Based on the result, match the nut with bolts in either smaller group or bigger group.

Take a 3rd nut at random and based on the comparisons with the first and second matching bolts, compare it with bolts in the appropriate sub groups. Continue this until all nuts are matched.

This obviates the need to compare a matching bolt with all of the remaining nuts to divide them into sub groups. The nuts themselves don't seem to be required to divide into subgroups.

+1. This is a classic problem invented by G.J.E. Rawlins. The key point is that the solution is a "randomized" quicksort, where the nuts and bolts are picked randomly and therefore expected running time is Big-Theta(n log n). Randomness element in the solution is important, I think that's why @D,tox'mi's points are important, otherwise just like quicksort, this solution performs O(n^2) worst case, so +1 for D,tox'mi's comment too.

@algos

Stop up-voting yourself, you shameless fellow. I saw the following notification on 'What's Going On' section, when you were up-voting yourself.

>> algos up-voted algos's comment: answer for this question ...

Hey, your solution ultimately replies on the fact that for any nut there is a bolt that matches it, but I think this assumption is not true for all the bolts, at least since N is not M. You could get around this by using a random algorithm which keeps looping until one bolt is found such that it has a matching nut, but then what if only 1/10 of the nuts have matching bolts? So 9/10 of the times your step 2) which relies on the *existence* of a match is very inefficient.

@Ananimus: stop this non-sense talk, and contribute for better discussion... just go and check self voting is disabled and that will not count for voting...

@Ayahuasca: in 2nd point compare matching bolt with all other nuts, does not means that every time it compare all n elements for each recursive call.. we will be applying recursion in each sub group, so only that subgroup exists during that run so it will compare with all elements in that subgroup only.

We don;t know sizes.. Only compare function is present. He asked me the question with sizes initially, so once i answered, he changed the question to compare function..which will return -1.0,1

Assuming the problem is as written, the answer is no. Consider the following edge case: there are big bolts and small nuts, except right in the middle there is one match (a medium bolt and and medium nut). Then the compare function always returns +1, except for that one match, where it returns 0. So basically we get no information from the compare function, except when we get lucky. It takes potentially O(mn) time to find that match.

o(nlogn) solution

```
/*
Developed By :Suman Roy
Email : email.suman.roy@gmail.com
*/
#include<iostream>
using namespace std;
int i_length;
void Print(int *a , int *b){
for( int i=0 ;i<i_length ;i ++)
std::cout<<a[i];
std::cout<<std::endl;
for ( int i=0 ; i<i_length ; i++ )
std::cout<<b[i];
}
int Break( int *array , int i_start , int i_end ,int i_pivot){
int i=i_start - 1;
int temp;
while ( i_start != i_end ){
if ( array [ i_start ] == i_pivot ){
temp=array[ i_start ];
array [ i_start]=array [ i_end ];
array[ i_end ]=temp;
}
if ( array [ i_start ] < i_pivot ) {
temp=array [ i_start ];
array [ i_start ]=array [ ++i ];
array [ i ]=temp;
}
i_start ++;
}
temp=array [ ++ i ];
array[i] = array [ i_end ];
array [i_end]=temp;
return i;
}
int count=0;
void Quicksort( int *array , int i_start , int i_end , int *b){
while ( i_start < i_end ){
int k=Break( array , i_start , i_end ,b[i_start]);
Break( b , i_start , i_end , array[k] );
count ++;
Quicksort( array , i_start , k-1 , b );
Quicksort( array , k+1 , i_end, b);
return ;
}
return ;
}
int main(){
int b[]={0,9,1,6,7,4};
int a[]={4,7,1,6,0,9};
i_length=6;
Quicksort( a, 0 , i_length-1 , b);
Pr int( a , b );
}
```

Output

```
suman@suman-laptop:/media/D/coding/algo/search$ ./a.out
014679
014679
```

From "The Algorithm Design Manual":

Stop and Think: Nuts and Bolts

Problem: The nuts and bolts problem is defined as follows. You are given a collection of n bolts of different widths, and n corresponding nuts. You can test whether a given nut and bolt fit together, from which you learn whether the nut is too large, too small, or an exact match for the bolt. The differences in size between pairs of nuts or bolts are too small to see by eye, so you cannot compare the sizes of two nuts or two bolts directly. You are to match each bolt to each nut.

Give an O(n2) algorithm to solve the nuts and bolts problem. Then give a randomized O(n log n) expected time algorithm for the same problem.

Solution: The brute force algorithm for matching nuts and bolts starts with the first bolt and compares it to each nut until we find a match. In the worst case, this will require n comparisons. Repeating this for each successive bolt on all remaining nuts yields a quadratic-comparison algorithm.

What if we pick a random bolt and try it? On average, we would expect to get about halfway through the set of nuts before we found the match, so this randomized algorithm would do half the work as the worst case. That counts as some kind of improvement, although not an asymptotic one.

Randomized quicksort achieves the desired expected-case running time, so a natural idea is to emulate it on the nuts and bolts problem. Indeed, sorting both the nuts and bolts by size would yield a matching, since the ith largest nut must match the ith largest bolt.

The fundamental step in quicksort is partitioning elements around a pivot. Can we partition nuts and bolts around a randomly selected bolt b? Certainly we can partition the nuts into those of size less than b and greater than b. But decomposing the problem into two halves requires partitioning the bolts as well, and we cannot compare bolt against bolt. But once we find the matching nut to b we can use it to partition the bolts accordingly. In 2n − 2 comparisons, we partition the nuts and bolts, and the remaining analysis follows directly from randomized quicksort.

What is interesting about this problem is that no simple deterministic algorithm for nut and bolt sorting is known. It illustrates how randomization makes the bad case go away, leaving behind a simple and beautiful algorithm.

￼￼

answer for this question is variation of QUICK SORT.

- algos July 14, 2013lets there are n bolts and n nuts, you can compare nut with bolt and can tell whether bolt is smaller, bigger or equal to nut.

1. lets take a random nut and compare with all bolts. after this exercise you will get one match that will fit with nut, one group of bolts those are bigger than nut and another group which is smaller than nut.

2. now compare the matching bolt with all other nuts in the same group, here also we get two groups.. one is bigger group and another is smaller group

3. finally we get one nut-bolt match and one group of nuts and bolts those are smaller than the match nut-bolt and another group of nuts and bolts those are bigger than the match nut-bolt combination

4. now apply recursion on both smaller and bigger groups... do this till all matches found

5. finally we get nut-bolt match combinations and also those are sorted.

time complexity is O(n log n).