FastPrep
Problem · Binary Search

TikTok Video Relevance Adjustment

Learn this problem
● MediumAmazonOA
See Amazon hiring insights

Problem statement

Note: This problem statement is currently incorrect. Please do not use this problem for practice right now.

Given an array videoScores, of length n, representing the current relevance scores of videos in the recommendation system (i.e., how much a video matches the user's interests, with higher values indicating better matches), the task is to adjust the scores to make all the videos no longer recommended (i.e., reduce all the scores to 0 or below).

Each adjustment decreases one of the video scores by a fixed integer value x. The task is to find the minimum value of x such that after performing at most maxAdjustments adjustments, all the relevance scores will become non-positive (i.e., less than or equal to zero).

Function

getMinAdjustments(videoScores: int[], maxAdjustments: int) → int

Complete the function getMinAdjustments in the editor below.

getMinAdjustments takes the following parameter:

  1. int videoScores[n]: the current relevance scores of videos in the recommendation system
  2. int maxAdjustments: the maximum number of adjustments allowed

Returns

int: the minimum possible integer x required

Examples

Example 1

videoScores = [4, 3, 2, 7]maxAdjustments = 5return = 2

If x = 1, elements can be decreased by 1 in an operation and it would take a total of 6 adjustments to make all the elements non-positive which exceeds the maxAdjustments allowed.

If the chosen x = 2, then:

  • In the first operation, we decrease the first element. The array becomes [-1, 2, 3]
  • In the second operation, we decrease the second element. The array becomes [-1, 0, 3]
  • In the third operation, we decrease the third element. The array becomes [-1, 0, 1]
  • In the fourth operation, we decrease the third element again. The array becomes [-1, 0, -1]
Hence, x = 2 is the minimum possible integer respecting the given conditions. Thus, the answer is 2.

Constraints

  • 1 ≤ n ≤ 105
  • 1 ≤ videoScores[i] ≤ 109
  • n ≤ maxAdjustments ≤ 109

More Amazon problems

drafts saved locally
public int getMinAdjustments(int[] videoScores, int maxAdjustments) {
    // write your code here
}
videoScores[4, 3, 2, 7]
maxAdjustments5
expected2
checking account