Interview Problems: Minimum Number of Groups
Tags: algorithms, interview, beginners, coding
Published: 2023-09-01 18:12:40

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 `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 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:

```cpp

#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)|