Interview Problems: Minimum Number of Groups

Hey Guys! This is an interview problem I recently faced in the online assessment test of a company that visited my university.

---

The problem is as follows:

Question: Minimum Number of Security Groups

There are n devices in a security group where the vulnerability of the ith group is given by vulnerabilities[i]. All devices in a group must have the same vulnerability level and difference between the sizes of any two groups must not exceed by 1.

Find the minimum number of groups to ensure security of a network.

---

Example 1:

Input: vulnerabilities = {2,1,3,3,3,2}
Output: 4
Explanation: Groups: {1},{2,2},{3,3},{3}.

Example 2:

Input: vulnerabilities = {2,2,3,3,2,2,2,3,2,3,2}
Output: 4
Explanation: Groups: {2,2,2,2},{2,2,2},{3,3,3,3}.

---

Intuition:

• From the look of it, I had this idea that the maximum devices we can ever have in a group is minimum frequency of any security level plus one.
• Let's understand this from our example 1 and 2. We have been given a security level one and it has only 1 frequency. But we must include every device, so we make it's group.
• This is our minimum count as well, so now every group we make must be of size either minCount-1, minCount, minCount+1.
• We can form a 2 size of groups for 2 and 3. Now we have a 3 left which we shall put into another group of size 2.
• We shall follow a greedy algorithm here to minimize but making it such that if possible to make groups we make it of largest size possible.

Approach:

Here's how the code works:

• I begin by defining a function called getMinimumGroups that takes a vector of integers called vulnerability as input. This vector represents the vulnerability levels of individuals.
• Inside the function, I declare a hash map called hashMap. This map will be used to count the occurrences of each vulnerability level. The key represents the vulnerability level, and the value represents the count of individuals with that vulnerability level.
• I then iterate through the vulnerability vector using a range-based for loop. For each vulnerability level (it), I increment the count in the hashMap for that level.
• Next, I initialize a variable minCountto a very large value (1e5), which will be used to keep track of the minimum count among all vulnerability levels.
• I iterate through the hashMap using another range-based for loop. Inside this loop, I compare the count of each vulnerability level with minCount and update minCount if the current count is smaller.
• After finding the minimum count (minCount) among all vulnerability levels, I initialize a variable cnt to zero. This variable will store the total number of groups needed.
• I iterate through the hashMap once again to calculate the total number of groups (cnt). For each vulnerability level (it), I use the ceil function to calculate the number of groups needed to accommodate individuals with that vulnerability level. The formula used is (it.second / (minCount + 1)). The minCount + 1 is used to ensure that no group remains empty, as it represents the minimum count among all levels plus one.
• Finally, I print the value of minCount to check the minimum vulnerability count, and then return the integer value of cnt, which represents the minimum number of groups required to accommodate all individuals with their respective vulnerability levels.

Code:

#include <bits/stdc++.h>

using namespace std;

int getMinimumGroups(vector<int>& vulnerability){
    map<float,float> hashMap;

    for(auto it : vulnerability){
        hashMap[it]++;
    }

    float minCount = 1e5;

    for(auto it : hashMap){
        minCount = min(minCount,it.second);
    }

    int cnt = 0;
    for(auto it : hashMap)
        {
            cnt = cnt + ceil((it.second/(minCount+1)));

    }



    cout << "Mincount: " <<  minCount << endl;
    return (int)cnt;
}


int main() {
    vector<int> vulnerabilities = {3, 1, 2, 2, 3, 3};
    vector<int> tests = {2,2,2,2,2,2,2,3,3,3,3};
    int result = getMinimumGroups(vulnerabilities);
    int result2 = getMinimumGroups(tests);
    // Print the groups
    cout << result << endl;
    cout << result2 << endl;
    return 0;
}

---

Complexity Analysis:

Algorithm	Time Complexity	Space Complexity
HashMap	O(N)	O(N)