C++ - how to solve the problem about "Bolts and Nuts"?

Question

C++ / C#

Hello habr. They let me solve the problem. The brain is already simply torn, so save
There are two arrays of, for example, 5 elements. An array of "Bolts" and an array of "Nuts", each Bolt is different in size and each of them has a corresponding nut from another array.
You need to sort both arrays in ascending order, while you cannot compare the size of a bolt with another bolt and the size of a nut with another nut. The only thing that can be compared is the size of the bolt and the size of the nut. Accordingly, there are only 3 states: 1. The nut is smaller than the bolt. 2. The nut fits the bolt.
3. The nut is too big

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

int const SIZE = 5;

class BoltsAndScrews
{

public:
  BoltsAndScrews();
  
  void DisplayBolts();
  void DisplaySmallBolts();
  void DisplayBigBolts();

  void DisplayScrews();
  void DispalyBigScrews();
  

  void addBolt(int);
  void addScrew(int);

  void findMAX();

private:
  int numberOfScrews = 0;
  int numberOfBolts = 0;

  int counter1 = 0;
  int counter2 = 0;
  int max;



  int arrayOfBolts[SIZE];
  int arrayOfScrews[SIZE];

  int arrayOfBigBolts[SIZE];
  int arrayOfSmallBolts[SIZE];

  int arrayOfBigScrews[SIZE];
  int arrayOfSmallScrews[SIZE];
  
  int arrayOfPairs[SIZE];


  

};

BoltsAndScrews::BoltsAndScrews()
{
  
}

int main()
{


  BoltsAndScrews test1;

  test1.addBolt(1);
  test1.addBolt(2);
  test1.addBolt(3);
  test1.addBolt(4);
  test1.addBolt(5);

  test1.addScrew(5);
  test1.addScrew(4);
  test1.addScrew(3);
  test1.addScrew(2);
  test1.addScrew(1);

  cout << endl;
  test1.DisplayBolts();
  test1.DisplayScrews();
  cout << endl;
  test1.findMAX();
  cout << endl << endl;

  test1.DispalyBigScrews();
  cout << endl;
  test1.DisplayBigBolts();

  cin.get();
  cin.get();
  return 0;
}

void BoltsAndScrews::DisplayBolts()
{
  cout << "Array Of  Bolts: ";
  for (int i = 0; i < SIZE; i++)
  {
    cout << arrayOfBolts[i] << " ";
  }
  cout << endl;
}

void BoltsAndScrews::DisplayScrews()
{
  cout << "Array Of Screws: ";
  for (int i = 0; i < SIZE; i++)
  {
    cout << arrayOfScrews[i] << " ";
  }
  cout << endl;
}


void BoltsAndScrews::DispalyBigScrews()
{
  cout << "Array Of BIG Screws ";
  for (int i = 0; i < SIZE; i++)
  {
    cout << arrayOfBigScrews[i] << " ";
  }
  cout << endl;
}

void BoltsAndScrews::DisplayBigBolts()
{
  cout << "Array Of BIG Bolts: ";
  for (int i = 0; i < SIZE; i++)
  {
    cout << arrayOfBigBolts[i] << " ";
  }
  cout << endl;
}

void BoltsAndScrews::addBolt(int x) 
{
  arrayOfBolts[numberOfBolts] = x;
  numberOfBolts++;
}

void BoltsAndScrews::addScrew(int x)
{
  arrayOfScrews[numberOfScrews] = x;
  numberOfScrews++;
}

void BoltsAndScrews::findMAX()
{
  
  for (int i = 0; i < SIZE; i++) //pick fist bolt
  {
    for (int j = 0; j < SIZE; j++) //pick the first scew and compaire it to bolt below. If not math, pick next screw and so on
    {
      if (arrayOfBolts[i] < arrayOfScrews[j])
      {
        cout << "Condition: Screw will go in the bolt." << " Bolt: [" << arrayOfBolts[i] << "] less than Screw: [" << arrayOfScrews[j] <<"]"<< endl;
        
        
    
      }
      
      if (arrayOfBolts[i] == arrayOfScrews[j])
      {
        cout << endl << "Condition: Screw will fit bolt exactly." << " Bolt: [" << arrayOfBolts[i] << "] same as Screw: [" << arrayOfScrews[j] << "]" << endl << endl;
      
        

      }
      
      if (arrayOfBolts[i] > arrayOfScrews[j])
      {
        cout << "Condition: Screw will be loose." << " Bolt: [" << arrayOfBolts[i] << "] bigger than Screw: [" << arrayOfScrews[j] <<"]"<< endl;
        
        
      }
      
      
      
    } // Screw
  
    

  
  } // bolt
}

Answer 1

The most interesting thing is that I initially wrote to you about complexity and even gave an answer) See for yourself: getting pairs is quadratic complexity, then insertion sorting (if that code was used that I gave you) is also quadratic sorting. Total 2 * n^2, but 2ka is a constant, and constants are not taken into account in the upper estimate, so the complexity of the entire algorithm is also quadratic.

Answer 2

The task is easy, but... it's you being interviewed, not the collective Internet mind.

Answer 3

I don't know c++, but maybe the python code will help you.

bolts = (4, 3, 2, 1, 5)
gaiki = (1, 2, 3, 4, 5)

sp = [] # тут будет список списков

for bolt in bolts:
    for gaika in gaiki:
        if gaika == bolt:
            sp.append([gaika, bolt]) # добавляем пары в список sp

print(sp)

n = 1
while n < len(sp): # пузырьковая сортировка.
    for i in range(len(sp)-n):
        if sp[i][0] > sp[i+1][1]:  # сравниваем болт и гайку.
            sp[i],sp[i+1] = sp[i+1],sp[i]
    n += 1
print(sp)

Answer 4

I didn’t look at the code, but if I understood the condition correctly, then you need to loop through each bolt and calculate how many nuts for each bolt have a smaller size.
I describe the case when it is assumed that all dimensions are unique. For non-unique ones, the idea will have to be slightly modified.
For example bolts A = { 2, 3, 7, 5, 4 } and nuts B = { 3, 7, 2, 4, 5
} A0 zero. This will be the position (zero) A0 in the sorted array. Here, by the way, you can also find the case where they are equal (B2) during the bypass - and we also set B2 to the zero position. (If it is possible to use an additional array, then we simply form it by inserting data into the required positions, if not, then we swap the elements in the existing one)
We take the second bolt A1 = 3. The number of smaller nuts is 1. So A1 remains in A1. Along the way, we found B0, which we put in position B1.
The third bolt A2 = 7. The number of smaller nuts is 4. So we put A2 in A4. We find an equal nut - B1 and put it also with index 4, that is, in B4. And so on until the end. We get 2 sorted arrays in ascending order.
True, it turns out that the complexity is quadratic, there will be time to try to think about it. If you misunderstood something from the condition, then just clarify.

Answer 5

I don't know c++ but something like that....

for(x=0;x<size-1;x++)
for(y=x+1;y<size;++y)
if (array1[x]>array2[y])
{
    temp=array1[x];
    array1[x]=array1[y];
    array1[y]=temp;
    temp=array2[x];
    array2[x]=array2[y];
    array2[y]=temp;
}

Answer 6

Algorithmic complexity - upper estimate of algorithm complexity. For example, the O(n) estimate means that the complexity is linear, that is, in the simple case, the array is traversed once; O(n ² ) - quadratic, each element of the array is compared with each; Bubble sort has an estimate of O(n*log(n)). You can read briefly here

Answer 7

I came to the stage when I have two identical arrays, which are a pair (bolt + nut) Ex. arrayOfScrews[0] = arrayOfBolts[0], arrayOfScrews[1] = arrayOfScrews[1] and so on.
Now in my head there is a picture that needs to be compared with each other, but not a bolt with the next bolt, but a bolt with the next nut, because it is the size of the next bolt.
Good people, who can write such a function? My head doesn't boil at all.
Here's the code:

#include <iostream>
#include <string>

using namespace std;

int const SIZE = 5;
int const SIZE2 = 2;
int const SIZE3 = 5;

class BoltsAndScrews
{

public:
  BoltsAndScrews();

  void DisplayBolts();
  void DisplayScrews();

  void DisplayArrayOfPairs();

  void addBolt(int);
  void addScrew(int);

  void findPairs();
  void fillOut2Darray(int, int);

  void Sort();


private:
  int numberOfScrews = 0;
  int numberOfBolts = 0;

  int counter1 = 0;
  int counter2 = 0;
  int max;

  int BoltsByMax[SIZE];
  int ScrewsByMax[SIZE];

  int arrayOfBolts[SIZE];
  int newArrayOfBolts[SIZE];
  int arrayOfScrews[SIZE];
  int newArrayOfScrews[SIZE];


  int arrayOfPairs[SIZE2][SIZE3];

};

BoltsAndScrews::BoltsAndScrews()
{

}

int main()
{


  BoltsAndScrews test1;

  test1.addBolt(1);
  test1.addBolt(2);
  test1.addBolt(3);
  test1.addBolt(4);
  test1.addBolt(5);

  test1.addScrew(5);
  test1.addScrew(4);
  test1.addScrew(3);
  test1.addScrew(2);
  test1.addScrew(1);

  cout << endl;
  test1.DisplayBolts();
  test1.DisplayScrews();
  cout << endl;
  test1.findPairs();
  cout << endl << endl;



  test1.DisplayArrayOfPairs();
  cout << endl << endl;
  test1.Sort();

  cin.get();
  cin.get();
  return 0;
}

void BoltsAndScrews::DisplayBolts()
{
  cout << "Array Of  Bolts: ";
  for (int i = 0; i < SIZE; i++)
  {
    cout << arrayOfBolts[i] << " ";
  }
  cout << endl;
}

void BoltsAndScrews::DisplayScrews()
{
  cout << "Array Of Screws: ";
  for (int i = 0; i < SIZE; i++)
  {
    cout << arrayOfScrews[i] << " ";
  }
  cout << endl;
}


void BoltsAndScrews::DisplayArrayOfPairs()
{
  cout << "Array Of Pairs: " << endl;

  for (int j = 0; j < 5; j++)
  {
    cout << newArrayOfBolts[j] << " ";
  }

  cout << endl;

  for (int i = 0; i < 5; i++)
  {
    cout << newArrayOfScrews[i] << " ";
  }
  cout << endl;


}
void BoltsAndScrews::addBolt(int x)
{
  arrayOfBolts[numberOfBolts] = x;
  numberOfBolts++;
}

void BoltsAndScrews::addScrew(int x)
{
  arrayOfScrews[numberOfScrews] = x;
  numberOfScrews++;
}

void BoltsAndScrews::fillOut2Darray(int x, int y)
{


  int bolt = x;
  int screw = y;

  newArrayOfBolts[counter1] = bolt;
  newArrayOfScrews[counter2] = screw;

  counter1++;
  counter2++;

  cout << "FillOutThing - " << bolt << " " << screw << endl << endl;

  return;

}

void BoltsAndScrews::Sort()
{
  

  int index = 0;
  int count1 = 0, count2 = 0;;
  
  do
  {
    
    for (int i = 0; i < SIZE; i++)
    {
      if (newArrayOfBolts[i] >= newArrayOfScrews[i])
      {
        cout << newArrayOfBolts[i] << " = " << newArrayOfScrews[i] << endl;
        
        BoltsByMax[count1] = newArrayOfBolts[i];
        ScrewsByMax[count2] = newArrayOfScrews[i];
        index = i;
      }

    }



    count1++;
    count2++;
    index++;

    cout << endl << "Bolts By Max: ";
    for (int i = 0; i < SIZE; i++)
    {
      cout << BoltsByMax[i];
    }

    cout << endl << "Screws By Max: ";
    for (int i = 0; i < SIZE; i++)
    {
      cout << ScrewsByMax[i];
    }

  } while (index > SIZE);
    
  
    
}

void BoltsAndScrews::findPairs()
{

  for (int i = 0; i < SIZE; i++) //pick fist bolt
  {
    for (int j = 0; j < SIZE; j++) //pick the first scew and compaire it to bolt below. If not math, pick next screw and so on
    {
      if (arrayOfBolts[i] < arrayOfScrews[j])
      {
        cout << "Condition: Screw will go in the bolt." << " Bolt: [" << arrayOfBolts[i] << "] less than Screw: [" << arrayOfScrews[j] << "]" << endl;
      }

      if (arrayOfBolts[i] == arrayOfScrews[j])
      {
        cout << endl << "Condition: Screw will fit bolt exactly." << " Bolt: [" << arrayOfBolts[i] << "] same as Screw: [" << arrayOfScrews[j] << "]" << endl << endl;

        cout << endl << "bolt " << arrayOfBolts[i];
        cout << endl << "screw " << arrayOfScrews[j] << endl << endl;;

        newArrayOfBolts[counter1] = arrayOfBolts[i];
        newArrayOfScrews[counter2] = arrayOfScrews[j];
        counter1++;
        counter2++;

        /*fillOut2Darray(arrayOfBolts[i], arrayOfScrews[j]);*/

      }

      if (arrayOfBolts[i] > arrayOfScrews[j])
      {
        cout << "Condition: Screw will be loose." << " Bolt: [" << arrayOfBolts[i] << "] bigger than Screw: [" << arrayOfScrews[j] << "]" << endl;
      }


    } // Screw

  } // bolt

}

The function I'm actually interested in is Sort()

Answer 8

Guys, thanks for the help! So I finished this task.
The following problem has arisen. According to this algorithm, now I was bombarded with the question "please provide the algorithmic complexity of your algorithm in Big O notation as well"
I have no idea what it is) Maybe someone came across this?