HackerRank Coding Interview 6. Prefix Scores

Amber Ivanna Trujillo
4 min readDec 8, 2022

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).

--

--

Amber Ivanna Trujillo

I write about Technical stuff, interview questions, and finance Deep Learning, LLM, Startup, Influencer, Executive, Data Science Manager