Interview Question: Find similarities between two arrays. C++

Kartikeya Mishra
5 min readOct 21, 2023

--

Company Interviews Using C++ Data Structures and Algorithms

#include <bits/stdc++.h> 
pair < int , int > findSimilarity(vector < int > arr1, vector < int > arr2, int n, int m)
{
unordered_map<int, int> map;
for(int i = 0; i< n; i++){
map[arr1[i]]++;
}
int intersection = 0;
for(int i =0; i<m; i++){
if(map[arr2[i]]>0){
intersection ++;
map[arr2[i]]--;
}
}
int unionSize = n+m - intersection;
return make_pair(intersection, unionSize);
}

English :

This C++ code defines a function `findSimilarity` that takes two vectors (`arr1` and `arr2`) of integers, as well as their respective sizes `n` and `m`, and calculates the intersection and union sizes of the two sets represented by these vectors.

Here’s a step-by-step explanation of the code:

1. It includes the necessary C++ standard library header, `<bits/stdc++.h>`. This header is not part of the C++ standard, but it’s commonly used in competitive programming environments and includes many other standard headers like `<iostream>`, `<vector>`, and more.

2. The function `findSimilarity` takes two vectors of integers (`arr1` and `arr2`) and their respective sizes `n` and `m` as parameters.

3. It declares an `unordered_map` named `map` to store the frequency of each unique integer in the `arr1` vector. The keys of the map are the unique integers from `arr1`, and the values are their respective frequencies.

4. It then loops through `arr1` and populates the `map` with the frequency of each integer in `arr1`.

5. It initializes a variable `intersection` to 0. This variable will be used to keep track of the number of elements that are common to both `arr1` and `arr2`.

6. The code then loops through `arr2` and checks if each element exists in the `map`. If it does, it means the element is present in both `arr1` and `arr2`, so it increments the `intersection` variable and decrements the count of that element in the `map`.

7. After processing all elements of `arr2`, the code calculates the size of the union of the two sets. It does this by adding the sizes of `arr1` and `arr2` and subtracting the `intersection` size. The union size is stored in the `unionSize` variable.

8. Finally, the function returns a `pair` containing two values: `intersection` and `unionSize`. These two values represent the number of elements that are common to both vectors (`intersection`) and the size of their union (`unionSize`).

This code essentially computes the intersection and union of two sets represented by vectors `arr1` and `arr2` using an `unordered_map` to efficiently keep track of the elements and their frequencies.

Hindi :

यह सी++ कोड एक फ़ंक्शन ‘findSimilarity’ को परिभाषित करता है जो दो पूर्णांक सूचियों (‘arr1’ और ‘arr2’) और उनके संबंधित आकारों ’n’ और ‘m’ को पैरामीटर के रूप में लेता है, और इन सूचियों द्वारा प्रतिष्ठित दो समूहों के संवाद और संयोजन आकार की गणना करता है।

यहां कोड का एक कदम-दर-कदम विवरण है:

1. इसमें आवश्यक C++ मानक पुस्तकालय हैडर ‘<bits/stdc++.h>’ को शामिल किया गया है। यह हेडर C++ मानक का हिस्सा नहीं है, लेकिन यह प्रतिस्पर्धी प्रोग्रामिंग परियोजनाओं में आमतौर पर प्रयुक्त होता है और ‘<iostream>’, ‘<vector>’ जैसे अन्य मानक हेडरों को शामिल करता है।

2. फ़ंक्शन ‘findSimilarity’ दो पूर्णांक सूचियों (‘arr1’ और ‘arr2’) और उनके संबंधित आकारों ’n’ और ‘m’ को पैरामीटर के रूप में लेता है।

3. यह ‘unordered_map’ घोषित करता है जिसे ‘map’ कहा जाता है, ताकि ‘arr1’ सूची में हर अद्वितीय पूर्णांक की आवृत्ति को संग्रहित किया जा सके। मानचिह्न में ‘arr1’ के अद्वितीय पूर्णांक होते हैं, और उनकी संबंधित आवृत्तियाँ होती हैं।

4. फिर ‘arr1’ के माध्यम से लूप चलाता है और ‘map’ को हर पूर्णांक की आवृत्ति के साथ भरता है।

5. यह ‘विशेषिकरण’ को 0 पर प्रारंभ करता है। इस प्रारंभिकीकरण चर द्वारा उन तत्वों की संख्या को ट्रैक करने के लिए उपयोग किया जाएगा जो ‘arr1’ और ‘arr2’ दोनों में सामान्य हैं।

6. कोड फिर ‘arr2’ के माध्यम से लूप चलाता है और हर तत्व की मौजूदगी की जांच करता है कि क्या वह ‘map’ में है। यदि हां, तो इसका मतलब है कि यह तत्व ‘arr1’ और ‘arr2’ दोनों में मौजूद है, इसलिए यह ‘विशेषिकरण’ चर को बढ़ाता है और ‘map’ में उस तत्व की गणना करता है।

7. ‘arr2’ के सभी तत्वों को प्रोसेस करने के बाद, कोड दो समूहों के संयोजन के आकार की गणना करता है। इसका मतलब है कि ‘arr1’ और ‘arr2’ के आकारों को जोड़कर ‘विशेषिकरण’ आकार को घटाते हुए। संयोजन आकार ‘unionSize’ चर में संग्रहित किया जाता है।

8. आखिरकार, फ़ंक्शन दो मानों को संग्रहित करने वाल

ा एक ‘pair’ लौटाता है: ‘विशेषिकरण’ और ‘संयोजन आकार’। ये दो मान ‘arr1’ और ‘arr2’ दोनों सूचियों में मौजूद तत्वों की संख्या को प्रतिनिधित करते हैं (‘विशेषिकरण’) और उनके संयोजन का आकार (‘संयोजन आकार’)।

इस कोड ने आपके सामने आने वाले दो सूचियों के संवाद और संयोजन की गणना कर दी है, और तत्वों और उनकी आवृत्तियों को संयंत्रित रूप से ट्रैक करने के लिए ‘unordered_map’ का उपयोग किया है।

Hinglish :

Is C++ code mein ek function `findSimilarity` define kiya gaya hai jo do vectors (`arr1` aur `arr2`) ko integers ki tarah le leta hai, sath hi inke alag-alag sizes `n` aur `m`, aur in vectors dvara prastut do sets ki intersection aur union sizes ka calculation karta hai.

Yahaan code ki kadam-se-kadam vyakhya hai:

1. Ismein jaruri C++ standard library header, `<bits/stdc++.h>` ko shamil kiya gaya hai. Ye header C++ standard ka hissa nahi hai, lekin ise aksar pratiyogita programming paristhitiyon mein istemal hota hai aur ismein `<iostream>`, `<vector>`, aur anya standard headers jaise kai aur shamil hote hain.

2. Function `findSimilarity` do integers ke vectors (`arr1` aur `arr2`) aur unke alag-alag sizes `n` aur `m` ko parameters ke roop mein leta hai.

3. Isne `unordered_map` ko `map` naam se ghoshit kiya hai, jise `arr1` vector mein har ek unique integer ki frequency ko store karne ke liye istemal kiya jata hai. Map ke keys `arr1` ke unique integers hote hain aur values unki corresponding frequencies hoti hain.

4. Fir yah `arr1` ke saath loop chalata hai aur har integer ki frequency ko `map` mein bhar deta hai.

5. Ek variable `intersection` ko 0 par initialize kiya jata hai. Is variable ka upayog dono sets `arr1` aur `arr2` mein common elements ki sankhya ko track karne ke liye kiya jayega.

6. Fir code `arr2` ke saath loop chalata hai aur har element ko check karta hai ki kya wo `map` mein maujood hai ya nahi. Yadi hai, to iska matlab hai ki yah element dono sets `arr1` aur `arr2` mein maujood hai, isliye `intersection` variable ko badhata hai aur `map` mein us element ki frequency ko ghatata hai.

7. `arr2` ke sare elements ko process karne ke bad, code dono sets ki union size ka calculation karta hai. Iska matlab hai ki `arr1` aur `arr2` ke sizes ko jodkar `intersection` size ko ghatakar. Union size `unionSize` variable mein store ki jati hai.

8. Ant mein, function ek `pair` ko return karta hai jisme do values hoti hain: `intersection` aur `unionSize`. Ye do values yani ki dono vectors (`intersection`) ke common elements ki sankhya ko aur unka union size (`unionSize`) ko prastut karte hain.

Is code mein basically `unordered_map` ka istemal karke `arr1` aur `arr2` dvara prastut do sets ki intersection aur union ko calculate kiya gaya hai, taki tatvaon aur unke frequencies ko prabhavi roop se track kiya ja sake.

--

--

Kartikeya Mishra
Kartikeya Mishra

Written by Kartikeya Mishra

Computer science engineer nomad exploring digital world. Learning and teaching while having fun.