Microsoft Interview Question for Dev Leads Dev Leads


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.

- mrsurajpoudel.wordpress.com November 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

quick sort

google search "Matching Nuts and Bolts Problem"

- Anonymous November 19, 2014 | Flag Reply
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.

- masterjaso November 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous November 19, 2014 | Flag
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'

- Anonymous November 22, 2014 | Flag Reply
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;
}

- anonymous December 16, 2014 | Flag Reply
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;

}

- vipul December 25, 2014 | Flag Reply
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)

- sonesh June 07, 2015 | Flag Reply
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)

- sonesh June 07, 2015 | Flag Reply
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.

- Victor November 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Lee November 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Victor November 19, 2014 | Flag


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