Amazon Online Assessment 2021 (OA) - Class Grouping

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.

This problem is same as Group division.

Relevant Amazon OA Problems:

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]
2max_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

Try it yourself

Solution

Title

Script

Lorem Ipsum is simply dummy text of the printing and typesetting industry. Lorem Ipsum has been the industry's standard dummy text ever since the 1500s, when an unknown printer took a galley of type and scrambled it to make a type specimen book.

Contrary to popular belief, Lorem Ipsum is not simply random text.

1  >>> a = [1, 2, 3]
2  >>> a[-1]
3  3

Get premium for instant access to all content and solutions

Upgrade