HackerRank Coding Interview 6. Prefix Scores

Time to complete — 30 minutes

Question Type = Medium

Asked in = Microsoft, Uber, Lyft, Bloomberg, Morgan Stanley, Apple, and Google.

Skills: arrays, sorting, greedy algorithm, prefix array

Insights — It should be read very carefully read and you must ask questions in between.

Question —

For any array of positive integers a[a[1]..a[k]], its score(a) is calculated as follows:

• For each a[i] where 1 ≤ i ≤ k in order, add the current maximum element in the array to a[i].
• score(a[k]) is the sum of the final elements in a. Since the sums may become large, score(a) should be calculated modulo (10⁹ +7).

Example

arr = [1, 2, 3]

Since there are 3 elements in arr, k will range from 1 to 3.

current    new     
k i arr[1:k]   max       a    score(a)
- - -------- -------  ------- -------
1 1 [1]         1      [2]       2

2 1 [1,2]       2      [3,2]
  2             3      [3,5]     8
3 1 [1,2,3]     3      [4,2,3]
  2             4      [4,6,3]
  3             6      [4,6,9]  19

• In the first iteration, k = 1. The array to consider, a[] = arr[1:k] = [1]. The maximum value in the array is 1. Add 1 to a[1] = 1 so a’ = [2]. All elements have been processed, so calculate the sum of the elements: 2. score(a) when k = 1 is 2. 2 modulo(10⁹ +7) = 2.
• In the second iteration, k = 2. The array to consider is a = arr[1:2] = [1, 2]. The maximum value is 2. Add 2 to a[1] = 1 so a’ = [3, 2]. The largest value is 3. Add it to a[2] = 2 so a’ = [3, 5]. score(a) when k = 2 is 8. 8 modulo (10⁹ +7) = 8.
• Repeat the process for k = 3.

Return [2, 8, 19], an array of scores for each value of k. Since the sums may become large, each value should be calculated modulo (10⁹ +7).

Function Description

Complete the function getPrefixScores in the editor below.

getPrefixScores has the following parameter:

int arr[n]: an array of integers

Returns

int[[n]: the scores for each value of k, modulo (10⁹ + 7).