Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
2.
Brute Force Approach
3.
Quick Sort (Divide & Conquer algorithm)
4.
Divide and Conquer Algorithm
5.
Using Hashmap
6.
Frequently Asked Questions
6.1.
How do you perform quicksort?
6.2.
What is meant by quicksort?
6.3.
Why is quicksort called Quick?
6.4.
Is quicksort faster than bubble sort?
6.5.
Is merge sort better than quicksort?
7.
Conclusion
Last Updated: Mar 27, 2024

Nuts and Bolts Problem | Set 1

Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

In this article, we will be discussing an exciting problem that is very popular in developer interviews. This is the well-known Nuts and Bolts problem.

It’s quite easy to solve the problem in the brute force approach but and a slight twist of an idea that directly comes from sorting is used to optimize the code for this problem. Let us first see the problem statement.

nuts and bolts

Problem Statement

Given a set of n nuts of different sizes and n bolts of different sizes. There is a one-one mapping between nuts and bolts. Match nuts and bolts efficiently. Constraint: Comparison of a nut to another nut or a bolt to another bolt is not allowed. It means nut can only be compared with bolt and bolt can only be compared with a nut to see which one is bigger/smaller.

Another way of asking this problem is, given a box with locks and keys where one lock can be opened by one key in the box. We need to match the pair and we cannot match locks with locks or keys with keys.

Brute Force Approach

The brute force idea is to traverse the bolts/nuts array for each of the nuts/bolt’s elements i.e., for each nut there will be n comparisons in the worst case and vice versa.

Code Implementation:
 

#include <iostream>
using namespace std;
// Constraint: Comparison of a nut to another nut or a bolt to another bolt is not allowed.
//It means nut can only be compared with bolt and bolt can only be compared with nut to see which one is bigger/smaller.
void solve(char *nut, char *bolt, int n){
	for(int i = 0;i<n;i++){
		//O(n^2) approach , we cannot compare bolts and bolts as well as nuts and nuts
		//elese we could have just sorted the two arrays
		char curr_nut = nut[i];
		for(int j = i;j<n;j++){
			if(bolt[j] == curr_nut){
				//swap bolt[i] & bolt[j]
				int temp = bolt[i];
				bolt[i] = bolt[j];
				bolt[j] = temp;
				break;
			}
		}
	}
}
int main() {
	// your code goes here
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		char *bolt = new char[n];
		char *nut = new char[n];
		for(int j = 0;j<n;j++)cin>>nut[j];
		for(int i = 0;i<n;i++)cin>>bolt[i];
		solve(nut,bolt,n);
		for(int j = 0;j<n;j++)cout<<nut[j]<<" ";
		cout<<endl;
		for(int i = 0;i<n;i++)cout<<bolt[i]<<" ";
	
	}
	return 0;
}


Time Complexity: O(n^2), where n is the number of elements in the array each. Well, the brute force approach is quite slow, so to optimise it we will be using a very interesting algorithm- Divide & Conquer using the QuickSort technique.

Let us first see the quicksort algorithm.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Quick Sort (Divide & Conquer algorithm)

It is a type of algorithm which divides the array into two parts using a pivot element. The idea is to place the pivot element in its correct place such that the pivot element has all elements smaller in the left side and all elements on the right side of it are greater when ascending order.

quick sort

Let us see the code implementation:
 

#include <iostream>
using namespace std;
int partition(int *arr,int s,int e){
//partition function to make two parts of the array placing the pivot element in its correct position
	int i = s-1;
	for(int j = s;j<e;j++){
		if(arr[j]<arr[e])
			{
				i = i+1;
				swap(arr[i],arr[j]);
			}
	}
	swap(arr[i+1],arr[e]);
	return i+1;
}
void quicksort(int *arr,int s,int e){
	if(s<e){ //checking if the s,e are in bounds		
		int p = partition(arr,s,e);
		cout<<p<<endl;
		quicksort(arr,s,p-1);
		quicksort(arr,p+1,e);
	}
}
void print(int arr[],int n){
	for(int i = 0;i<n;i++)
		cout<<arr[i]<<" ";
}
int main() {
	// your code goes here
	int n;
	cin>>n;
	int *arr = new int[n];
	for(int i = 0;i<n;i++)
		cin>>arr[i];
	quicksort(arr,0,n-1);
	print(arr,n);
	return 0;
}


Time Complexity: O(nlogn), where n is the number of elements in the array. After we have seen the Quicksort algorithm now let us see how this can be used to optimise our problem.

Divide and Conquer Algorithm

The idea is to make two partitions considering the bolt element as a pivot for each case, and then arranging the nuts arrays according to the condition where the elements in the nuts array which are smaller than the pivot area on the left side and the larger area on the right side.

Let us see the code implementation:
 

#include<iostream>
using namespace std;
int partition(char *array, int low, int high, char pivot) {  
   int i = low;
   for(int j = low; j<high; j++) {
      if(array[j] <pivot) {    
         swap(array[i], array[j]);
         i++;
      }else if(array[j] == pivot) { 
        char temp = array[j];
        array[j] = array[high];
        array[high] = temp;
         j--;
      }
   }
  char temp = array[j];
        array[j] = array[high];
        array[high] = temp;
   return i;    
}

void solve(char *nut, char *bolt[], int low, int high) {
   if(low < high) {
      int pivotpos = partition(nut, low, high, bolt[high]);
      partition(bolt, low, high, nut[pivotpos]); 
      solve(nut, bolt, low, pivotpos - 1);
      solve(nut, bolt, pivotpos+1, high);
   }
}

int main() {
  int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		char *bolt = new char[n];
		char *nut = new char[n];
		for(int j = 0;j<n;j++)cin>>nut[j];
		for(int i = 0;i<n;i++)cin>>bolt[i];
		solve(nut,bolt,0,n);
		for(int j = 0;j<n;j++)cout<<nut[j]<<" ";
		cout<<endl;
		for(int i = 0;i<n;i++)cout<<bolt[i]<<" ";
	}
  return 0;
}


Time Complexity: O(nlogn), where n is the number of elements in each array.

Using Hashmap

Another way of solving this problem is by using a Hashmap. The idea here is to store the bolts and their corresponding pair of nuts in a map of key-value pairs. Although this increases the space complexity but reduces the time complexity to linear order.

Code Implementation:

#include <bits/stdc++.h>
using namespace std; 
// function to match nuts and bolts
void solve(char *nut, char *bolt, int n)
{
    unordered_map<char, int> mp;
    //storing in the map
    for (int i = 0; i < n; i++)
        mp[nut[i]] = i;
    for (int i = 0; i < n; i++)
        if (mp.find(bolt[i]) != mp.end())
            nut[i] = bolt[i];
}
int main() {
  int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		char *bolt = new char[n];
		char *nut = new char[n];
		for(int j = 0;j<n;j++)cin>>nut[j];
		for(int i = 0;i<n;i++)cin>>bolt[i];
		solve(nut,bolt,n);
		for(int j = 0;j<n;j++)cout<<nut[j]<<" ";
		cout<<endl;
		for(int i = 0;i<n;i++)cout<<bolt[i]<<" ";
	}
  return 0;
}


Time Complexity: O(n), where n is the number of elements in each array.

Space Complexity: O(n), where n is the number of elements in each array. 

You can easily run this code yourself with java online compiler.

Also check out Addition of Two Numbers in Java here.

Frequently Asked Questions

How do you perform quicksort?

In quicksort, we first select a pivot, with which comparisons are made to make two partitions. The exact process is then repeated for both the partitions until the array is sorted.

What is meant by quicksort?

Quicksort is a divide and conquer algorithm used to sort the elements in an array.

Why is quicksort called Quick?

Quicksort is called quick because it is faster than other sorting algorithms when sorting small data sets.

Is quicksort faster than bubble sort?

Yes, quicksort is faster than bubble sort.

Is merge sort better than quicksort?

Merge sort is often preferred over quicksort because of the latter’s inefficiency with large data sets.

Conclusion

In this article, we discussed about a problem named as Nuts and Bolts Problem, how it works and how to implement it, but this isn’t the end.

Keeping the theoretical knowledge at our fingertips helps us get about half the work done. To gain complete understanding, practice is a must. A variety of coding questions from interviews are available here.

Apart from this, you can also check Coding Ninjas Studio, where you’ll find thousands of other coding questions to practice and interview experiences of scholars in renowned product-based companies.

Happy learning!

Previous article
Duck Number in Java
Next article
Bubble Sort in Java
Live masterclass