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…