FastPrep
Problem · Sorting

Compute Relative Player Ratings

Learn this problem
● MediumAmazonNEW GRADOA
See Amazon hiring insights

Problem statement

A newly launched game on the The Banana Inc gaming platform has introduced a distinctive player rating system that evaluates players based on both their skill levels and absolute ratings. The goal is to determine each player's relative rating, which is derived from the sum of the absolute ratings of up to k players who have strictly lower skill levels than the player in question.

There are n players in the game, where each player i possesses:

  • A skill level represented by skills[i]
  • An absolute rating denoted as ratings[i]

The relative rating for each player i is calculated as the highest possible sum of the absolute ratings of at most k players who have a skill level strictly less than skills[i]. In other words, among all players whose skill is strictly less than skills[i], take the k largest absolute ratings (or all of them if fewer than k exist) and sum them.

For example, if skills = [1, 2, 3, 4], ratings = [40, 30, 20, 10], and k = 2, then the relative ratings are [0, 40, 70, 70].

Given skills, ratings, and k, implement a function called getRelativeRatings that returns each player's relative rating.

Parameters:

  • skills (List[int]): An array of integers where skills[i] represents the skill level of the i-th player.
  • ratings (List[int]): An array of integers where ratings[i] represents the absolute rating of the i-th player.
  • k (int): The maximum number of top ratings to consider for computing the relative rating.

Function

getRelativeRatings(skills: int[], ratings: int[], k: int) → long[]

Examples

Example 1

skills = [1, 2, 3, 4]ratings = [40, 30, 20 ,10]k = 2return = [0, 40, 70, 70]

For each player, sum the largest k = 2 absolute ratings among players with strictly lower skill.

  • Player with skill 1: no player has lower skill, so relative rating = 0.
  • Player with skill 2: only skill 1 (rating 40) is lower, so relative rating = 40.
  • Player with skill 3: skills 1 and 2 (ratings 40 and 30) are lower; sum of top 2 = 70.
  • Player with skill 4: skills 1, 2, 3 (ratings 40, 30, 20) are lower; the top 2 are 40 and 30, summing to 70.

Hence the answer is [0, 40, 70, 70].

Example 2

skills = [1, 7, 5]ratings = [0, 0, 1]k = 1return = [0, 1, 0]
Example 2 illustration
With k = 1, choose one maximum skill level less than the current one. No skill level is less than 1. For skill lelvel 7, skill level 5 and 1 are lower but only 5 has a relative rating > 0. The only skill level less is 1 with a rating of 0. Hence the answer is [0, 1, 0].

Constraints

  • 1 ≤ n ≤ 2 * 10^5
  • 0 ≤ k ≤ n - 1
  • 1 ≤ skills[i] ≤ 10^9
  • 0 ≤ ratings[i] ≤ 10^9

More Amazon problems

drafts saved locally
public long[] getRelativeRatings(int[] skills, int[] ratings, int k) {
  // write your code here
}
skills[1, 2, 3, 4]
ratings[40, 30, 20 ,10]
k2
expected[0, 40, 70, 70]
checking account