Class Grouping Amazon OA 2023 Solution

Contents

1 Class Grouping Amazon OA 2023 Solution
- 1.1 SOLUTION
2 Amazon OA 2023 Questions with 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]
max_spread = 2

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
0<=maxSpread<=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()
    
    num_classes = 1  # Start with one class
    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
    
    int numClasses = 1;  // Start with one class
    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) {
            currentClass.add(levels[i]);
        }
        // Otherwise, start a new class with the trainee as the first member
        else {
            numClasses++;
            currentClass = new ArrayList<>();
            currentClass.add(levels[i]);
        }
    }
    
    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
    
    int numClasses = 1;  // Start with one class
    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;
}

Class Grouping Amazon OA 2023 Solution

SOLUTION

Amazon OA 2023 Questions with Solution

Leave a Comment Cancel reply