Class Grouping Amazon OA 2022 Solution

Page Contents

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

Also See: Amazon OA Online Assessment 2022 Questions and Answers

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:

1levels = [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`
• `0<=maxSpread<=10^9`

SOLUTION

Program: Class Grouping Amazon OA Solution in Python