• 0

Country: India
Interview Type: In-Person

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

1. Randomly choose a nut and partition the bolts ( smaller bolt than the nut | matched bolt | larger bolt than the nut)
2. Use the matched bolt at step 1 to partition the nuts (smaller nuts than the bolt | matched nut | larger nut than the bolt)
Recursively partition each subset.
Concept(same as quick-sort) compiled for people who just want the solution right here without the need to google for it. However this is average case (or randomized) nlogn solution. worst case is still n^2.

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

quick sort

google search "Matching Nuts and Bolts Problem"

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

For this problem, you would need to sort the bolts and nuts by their size. This is an O(n log n) operation. With both of them sorted, you will then have a case where bolts[i] = nuts[i] and you are matched.

The above assumes that there is exactly one match for each element. If this is not true, then you would need to sort one of the sets and then binary search for a result one element at a time from the other set.

Comment hidden because of low score. Click to expand.
0

API can compare a nut and bolt and return which is smaller / bigger. you can't compare two bolts or two nuts

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

Quicksort

``````quickSort :: (a -> b -> Ordering) -> [a] -> [b] -> [(a, b)]
quickSort _ [] [] = []
quickSort f l l' = quickSort f leftL leftL' ++ [match] ++ quickSort f rightL rightL'
where
selB = head \$ filter ((EQ ==) . f choice) l'
match = (choice, selB)
choice = l !! ind
ind = length l `div` 2
leftL = filter ((LT ==) . flip f selB) l
leftL' = filter ((LT ==) . f choice) l'
rightL = filter ((GT ==) . flip f selB) l
rightL' = filter ((GT ==) . f choice) l'``````

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

Same algorithm with C++ code.

``````#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>
#include <cassert>

using namespace std;

auto sort_bolts_and_nuts = [](vector<int>& bolts, vector<int>& nuts) {
if (bolts.size() != nuts.size()) {
return false;
}

auto partition = [](vector<int>& data, int left, int right, int pivot) {
int pivot_idx = -1;
int i = left;
while (i <= right) {
if (pivot_idx < 0 && data[i] == pivot) {
swap(data[i], data[right]);
pivot_idx = right;
continue;
}
if (data[i] < pivot) {
swap(data[left++], data[i]);
}
++i;
}
return pivot_idx >= 0 ? swap(data[left], data[pivot_idx]), left : -1;
};

function<bool(int, int)> impl = [&](int left, int right) {
if (left > right) {
return true;
}
if (left == right) {
return bolts[left] == nuts[left];
}

auto mid = left + (right - left) / 2;
auto r = partition(nuts, left, right, bolts[mid]);
if (r < 0) {
return false;
}
if (r != partition(bolts, left, right, nuts[r])) {
return false;
}
if (!impl(left, r - 1)) {
return false;
}
return impl(r + 1, right);
};
return impl(0, bolts.size() - 1);
};

ostream& operator<<(ostream& os, const vector<int>& data) {
for (auto d : data) {
os << d << " ";
}
return os;
}

int main() {
vector<int> bolts = { 8, 4, 3, 9, 1 };
vector<int> nuts = { 4, 9, 8, 1, 3 };
auto is_matched = sort_bolts_and_nuts(bolts, nuts);
cout << bolts << endl;
cout << nuts << endl;
assert(is_matched);

bolts = { 8, 4, 3, 9, 1 };
nuts = { 5, 9, 8, 1, 3 };
assert(!sort_bolts_and_nuts(bolts, nuts));

return 0;
}``````

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

``````#include <iostream>
using namespace std;

typedef struct Tree
{
pair<int,int> nutbolt;
int low;
int high;
struct Tree *left,*right;
}Tree;

int nuts[]   = {3,4,2,1,7,9,12,11,10};
Tree *root = NULL;

int funcAPI(int nutvalue, int boltvalue)
{
if(nutvalue > boltvalue)
return -1;
else if(nutvalue < boltvalue)
return 1;
else
return 0;
}

Tree *getNode(int nut, int bolt, int low,int high)
{
Tree *t = new Tree;
t->nutbolt.first = nut;
t->nutbolt.second = bolt;
t->low = low;
t->high = high;
t->left = NULL;
t->right = NULL;
return t;
}

int quickPartition(int *bolt,int nut, int low, int high)
{
int pivot = high;
int j = low;
int p = 0 ;
for(int i=low; i <= high;i++)
{
if((funcAPI(nut,bolt[i]) == -1))
{
swap(bolt[i],bolt[j]);
j++;
}
if((funcAPI(nut,bolt[i]) == 0))
{
swap(bolt[i],bolt[j]);
p = j;
j++;

}
}
swap(bolt[j-1],bolt[p]);
return j-1;
}

Tree *insert_into_tree(Tree *t, int *bolts,int nut,int nutindex,int low, int high)
{
if(t == NULL)
{
int boltnumber =  quickPartition(bolts,nut,low,high);;
return getNode(nutindex,boltnumber,low,high);
}
else
{
if(funcAPI(nut,bolts[t->nutbolt.second]) == 1)
{
t->left = insert_into_tree(t->left, bolts,nut,nutindex,low,t->nutbolt.second-1);
}
else
{
t->right = insert_into_tree(t->right, bolts,nut,nutindex,t->nutbolt.second+1, high);
}
return t;
}
}

void Display(Tree *t)
{
if(t)
{
Display(t->left);
cout << "Nutindex:-  " << t->nutbolt.first <<  " Nut value:- " << nuts[t->nutbolt.first] <<"bolt index:- " << t->nutbolt.second << "\n";
Display(t->right);
}

}
void Partition(int *bolts, int *nuts, int size)
{
int index = 0;

while(index != size)
{
int low = 0,high = size;
root = insert_into_tree(root,bolts,nuts[index],index, low, high);
index++;
}
for(int i=0; i < size;i++)
{
cout << bolts[i] << " ";
}
cout << "\n";
Display(root);
//}
}

int _tmain(int argc, _TCHAR* argv[])
{

int bolts[]  = {12,3,2,4,1,9,10,11,7};

Partition(bolts,nuts,sizeof(nuts)/sizeof(int)-1);
return 0;``````

}

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

Here is the algorithm

``````Sort nuts based upon their size // non decreasing
Sort Bolts based upon their size // non increasing
i = 0;j = 0;// i for nuts, j for bolts
while(true)
response  = FitAPI(Nut[i],Bolt[j]);
if response is equal
print combination
i++;j++; // make it better to take care of duplicate cases
else if response is small
i++;
else if response is large
j++;
break if either i or j crosses there respective limit
end``````

Complexity
Time : O(nlogn)
Space : O(1)

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

Here is the algorithm

``````Sort nuts based upon their size // non decreasing
Sort Bolts based upon their size // non increasing
i = 0;j = 0;// i for nuts, j for bolts
while(true)
response  = FitAPI(Nut[i],Bolt[j]);
if response is equal
print combination
i++;j++; // make it better to take care of duplicate cases
else if response is small
i++;
else if response is large
j++;
break if either i or j crosses there respective limit
end``````

Complexity
Time : O(nlogn)
Space : O(1)

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Sort both lists and traverse the two lists at the same time performing linear matching. This traversal uses one cursor on each list. They move forward until one of them reaches the end, which dictates the end of the algorithm.

In Python:

``````bolts = [...]
nuts = [...]

bolts.sort()
nuts.sort()

i = 0
j = 0

matches = 0

while i < n and j < n:
compare = check(bolts[i], nuts[i])
if compare == EQUAL:
# We found a match
matches = matches+1
i = i+1
j = j+1
elif compare == SMALLER:
# Proceed to the next bolt
i = i+1
else:
# Proceed to the next nut
j = j+1``````

Sorting is O(nlogn) with heap sort, while the traversal is O(n).

Edit: this solution is wrong. We aren't allowed to compare nuts with nuts and bolts with bolts.

Comment hidden because of low score. Click to expand.
0

Since no numerical infoemation is available for the sizes of the bolts and nuts, the quick sort should be the right approach using the api provided.

Comment hidden because of low score. Click to expand.
0

Heap sort works as well, doesn't it? I cited it just to avoid possible worst case scenarios for quick sort, which turns it into O(n^2).

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.

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