# Nuts & Bolts Problem (Lock & Key problem)

Objec­tive:  Given ‘n’ Nuts and ‘n’ Bolts of different sizes. There is one-to-one mapping between nuts and bolts. Write an algorithm to find all matches between nuts and bolts

Note: This problem can also be framed as- Given ‘n’ keys and ‘n’ locks. There is one-to-one mapping between keys and locks, means each lock has a specific key and can be unlocked using that key only. Write an algorithm to find all matches between keys and locks.

You are allowed to compare only nuts with bolts (or keys with locks), nuts with nuts or bolts with bolts comparisons are not allowed.

Example:

```[] nuts = {'

Approach:

Brute Force –

Compare each nut (or key) will all the bolts (or locks) till we do not find the match.

Time Complexity: O(n2)

Code:
.gist table { margin-bottom: 0; }

Use Hash Map:

Insert all the nuts as key and its position as value into Hash Map.

Iterate through all the bolts and check for the nuts in the hash map and put it into the right place.

Code:

.gist table { margin-bottom: 0; }

Output:

(Hash Map) Matched nuts and bolts are:
[%, @, x, \$, &]
[%, @, x, \$, &]

Reference - http://www.geeksforgeeks.org/nuts-bolts-problem-lock-key-problem-set-2-hashmap/
, '%', '&', '*', 'x'}
[] bolts = {'%', 'x', '*', 'Approach:
Brute Force –
Compare each nut (or key) will all the bolts (or locks) till we do not find the match.
Time Complexity: O(n2)
Code:
.gist table { margin-bottom: 0; }

Use Hash Map:

Insert all the nuts as key and its position as value into Hash Map.
Iterate through all the bolts and check for the nuts in the hash map and put it into the right place.

Code:
.gist table { margin-bottom: 0; }

Output:

Reference - http://www.geeksforgeeks.org/nuts-bolts-problem-lock-key-problem-set-2-hashmap/
, '&'}
Output:
Matched nuts and bolts are:
[\$, %, &, *, x]
[\$, %, &, *, x]
Approach:
Brute Force –
Compare each nut (or key) will all the bolts (or locks) till we do not find the match.
Time Complexity: O(n2)
Code:
.gist table { margin-bottom: 0; }

Use Hash Map:

Insert all the nuts as key and its position as value into Hash Map.
Iterate through all the bolts and check for the nuts in the hash map and put it into the right place.

Code:
.gist table { margin-bottom: 0; }

Output:

Reference – http://www.geeksforgeeks.org/nuts-bolts-problem-lock-key-problem-set-2-hashmap/
__________________________________________________
Top Companies Interview Questions..-

Microsoft
Amazon
more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

Related Posts:Find duplicates Characters in the given StringFind the only element in array which appears only onceMajority Element – Part 1Sum of all Unique elements in a given arrayProduct of all Unique elements in a given array.Print all Unique elements in a given arrayPrint maximum occurring character in a StringAll elements appears thrice and one element appears once. Find that element in…Find duplicates in an given array in O(n) time and O(1) extra space.Remove Duplicates from a stringShare this:LinkedInPrintTumblrFacebookTwitterEmailRedditLike this:Like Loading...

```