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]
  • 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
Class Grouping Amazon OA
Class Grouping Amazon OA

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;
}

Amazon OA 2023 Questions with Solution

  1. Shopping Patterns Solution Amazon OA 2023
  2. Reorder Data in Log Files Solution Amazon OA 2023
  3. Top K Frequent Words Solution Amazon OA 2023
  4. Trees Height Solution Amazon OA SDE 2023
  5. Counting Binary Substrings Amazon OA 2023
  6. Grid Connections Amazon OA 2023
  7. Shipment Imbalance Amazon OA 2023
  8. Max Profit Amazon OA 2023
  9. Find Lowest Price Amazon OA 2023
  10. Decode String Frequency Amazon OA 2023
  11. Simple Cipher Amazon OA 2023
  12. Valid Discount Coupons Amazon OA 2023 Solution
  13. Count Maximum Teams Amazon OA 2023
  14. Minimum Coin Flips Amazon OA 2023
  15. Max Average Stock Price Amazon OA 2023 Solution
  16. Robot Bounded In Circle Amazon OA 2023
  17. Shopping Options Amazon OA 2023 Solution
  18. Fill The Truck Maximum Units on a Truck Amazon OA Solution
  19. Maximize Score After N Operations Number Game Solution Amazon OA 2023
  20. Slowest Key Amazon OA 2023 Solution
  21. Five Star Seller Maximum Average Pass Ratio Amazon OA 2023
  22. Split String Into Unique Primes Amazon OA 2023 Solution
  23. Storage Optimization Amazon OA 2023 Solution
  24. Minimum Difficulty of a Job Schedule Amazon OA 2023 Solution
  25. Autoscale Policy Utilization Check Amazon OA 2023
  26. Optimal Utilization Solution Amazon OA 2023
  27. Merge Two Sorted Lists Solution Amazon OA 2023
  28. Two Sum Unique Pairs Solution Amazon OA 2023
  29. Amazon Music Pairs Amazon OA 2023 Solution
  30. Find Max products Amazon OA 2023 Solution
  31. Get encrypted number Amazon OA 2023 Solution
  32. Find Total Imbalance Amazon OA 2023 Solution
  33. Find Total Power Amazon OA 2023 Solution

Leave a Comment

five × 1 =