Microsoft Interview Question
Dev Leads Dev LeadsCountry: India
Interview Type: In-Person
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.
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'
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;
}
#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;
}
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)
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)
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.
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.
1. Randomly choose a nut and partition the bolts ( smaller bolt than the nut | matched bolt | larger bolt than the nut)
- mrsurajpoudel.wordpress.com November 20, 20142. 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.