# Class Grouping Amazon OA 2023 Solution

## Class Grouping Amazon OA 2023 Solution

Amazon Technical Academy (ATA) provides in-demand, technical training to current Amazon employees looking to broaden their skill sets. ATA has admitted a group of n prospective trainees with varying skill levels. To better accommodate the trainees, ATA has decided to create classes tailored to the skill levels. A placement examination will return a skill level that will be used to group the trainees into classes, where levels[i] represents the skill level of trainee i. All trainees within a class must have a skill level within maxSpread, a specified range of one another. Determine the minimum number of classes that must be formed.

Input

• levels: the skill level for each student
• max_spread: the maximum allowed skill difference between any two class members of a class

Output : the minimum number of classes that can be formed

Examples

Example 1:

Input:

• levels = [1, 4, 7, 3, 4]

Output

`3`

Explanation:

The trainee must be within maxSpread = 2 levels of each other. In this case, one optimal grouping is {1, 3}, {4, 4}, and {7}. Another possible grouping is {1}, {3, 4, 4}, {7}. There is no way to form fewer than 3 classes.

Constraints

• 1<=n<=10^5
• 1<=level[i]<=10^9

### SOLUTION

One possible solution to this problem is to sort the trainees based on their skill levels, and then iterate through the sorted list, grouping trainees into classes as we go along. We can start with the first trainee as the first class, and then add subsequent trainees to the current class as long as their skill level is within maxSpread of the highest skill level in the class. If a trainee’s skill level is outside of this range, we start a new class with that trainee as the first member.

Program: Class Grouping Amazon OA Solution in Python

``````def min_classes(levels, max_spread):
# Sort the trainees by skill level
levels.sort()

current_class = [levels[0]]  # Start the first class with the first trainee

# Iterate through the remaining trainees
for i in range(1, len(levels)):
# If the trainee's skill level is within maxSpread of the highest
# skill level in the current class, add them to the class
if levels[i] - current_class[-1] <= max_spread:
current_class.append(levels[i])
# Otherwise, start a new class with the trainee as the first member
else:
num_classes += 1
current_class = [levels[i]]

return num_classes
``````

Note that the Java implementation uses an ArrayList to store the current class, while the C++ implementation uses a vector. The rest of the algorithm is the same for both languages.

Program: Class Grouping Amazon OA Solution in Java

``````public static int minClasses(int[] levels, int maxSpread) {
Arrays.sort(levels);  // Sort the trainees by skill level

List<Integer> currentClass = new ArrayList<>();
currentClass.add(levels[0]);  // Start the first class with the first trainee

// Iterate through the remaining trainees
for (int i = 1; i < levels.length; i++) {
// If the trainee's skill level is within maxSpread of the highest
// skill level in the current class, add them to the class
if (levels[i] - currentClass.get(currentClass.size() - 1) <= maxSpread) {
}
// Otherwise, start a new class with the trainee as the first member
else {
numClasses++;
currentClass = new ArrayList<>();
}
}

return numClasses;
}
``````

Program: Class Grouping Amazon OA Solution in C++

``````#include <algorithm>
#include <vector>

int minClasses(std::vector<int>& levels, int maxSpread) {
std::sort(levels.begin(), levels.end());  // Sort the trainees by skill level

std::vector<int> currentClass;
currentClass.push_back(levels[0]);  // Start the first class with the first trainee

// Iterate through the remaining trainees
for (int i = 1; i < levels.size(); i++) {
// If the trainee's skill level is within maxSpread of the highest
// skill level in the current class, add them to the class
if (levels[i] - currentClass.back() <= maxSpread) {
currentClass.push_back(levels[i]);
}
// Otherwise, start a new class with the trainee as the first member
else {
numClasses++;
currentClass.clear();
currentClass.push_back(levels[i]);
}
}

return numClasses;
}
``````