Facebook Pixel

Amazon Online Assessment 2021 (OA) - Class Grouping

The Technical Training Academy, often acronymized as TTA, gives a chance to its existing There are n individuals, each with a unique number that signifies their proficiency in a particular area. An organization wants to group these individuals into sessions where the range of proficiency numbers in any given session is not greater than a specified value, 'maxSpread'. The challenge is to figure out the least number of sessions needed to include all individuals without exceeding the 'maxSpread' in any session.

This question is the same as Group division.

Relevant Amazon OA Problems:

Input & Output
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
Example
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

Try it yourself

Invest in Yourself
Your new job is waiting. 83% of people that complete the program get a job offer. Unlock unlimited access to all content and features.
Go Pro