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 thehashMap
for that level. - Next, I initialize a variable
minCount
to 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 withminCount
and updateminCount
if the current count is smaller. - After finding the minimum count (
minCount
) among all vulnerability levels, I initialize a variablecnt
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)). TheminCount
+ 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 ofcnt
, 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) |
Top comments (1)
Update! The solution is partially wrong. It does not pass all the testcases in the test it was asked.
Apologies regarding the same.