FastPrepPrefix Scores With the Running Maximum
Problems/Prefix Scores With the Running Maximum

Prefix Scores With the Running Maximum

C3.ai logoC3.ai● MediumNEW GRADOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: This was the second of two questions in a 2023 C3.ai new grad online assessment. The author posted screenshots of the questions, and only the worked example could be read. It walks a small array prefix by prefix, adds the current largest value to each element in turn, and lists the score of every prefix, with the sum taken modulo 10^9 + 7.

The statement here is rebuilt from that worked example. The part that could not be read leaves out the limits. Here every value is positive, the walk uses exact values and only the final sum is reduced, and the limits are our choice. The examples are new, and the report's worked example is one of the hidden tests.

Our version is about 90% the same as the reported question.

You are given an integer array arr of length n. For every k from 1 to n, find the score of the first k elements:

  1. Copy the first k elements into a new array a.
  2. Walk through a from left to right. At each index i, take the current maximum of the whole array a and add it to a[i]. The maximum includes the values already changed and the values not reached yet.
  3. The score is the sum of a after the walk, modulo 109 + 7.

The walk uses the exact values. Only the final sum is taken modulo 109 + 7.

Return an array scores of length n, where scores[k - 1] is the score of the first k elements.

Function

getPrefixScores(arr: int[]) → int[]

Examples

Example 1

arr = [3,1,2]return = [6,13,22]

Prefix [3]: the maximum is 3, so it becomes [6]. Score 6.

Prefix [3, 1]: add the maximum 3 to the first element to get [6, 1]. Now the maximum is 6, so the second element becomes 7: [6, 7]. Score 6 + 7 = 13.

Prefix [3, 1, 2]: [3, 1, 2] becomes [6, 1, 2], then [6, 7, 2], then the maximum is 7, so [6, 7, 9]. Score 6 + 7 + 9 = 22.

Example 2

arr = [2,5]return = [4,19]

Prefix [2]: it becomes [4]. Score 4.

Prefix [2, 5]: the maximum of the whole array is 5, even though 5 has not been visited yet, so the first element becomes 7: [7, 5]. Now the maximum is 7, so the second element becomes 12: [7, 12]. Score 7 + 12 = 19.

Example 3

arr = [1000000000,1000000000]return = [999999993,999999972]

Prefix [1000000000]: it becomes [2000000000]. 2000000000 mod 1000000007 = 999999993.

Prefix [1000000000, 1000000000]: it becomes [2000000000, 1000000000], then the maximum is 2000000000, so [2000000000, 3000000000]. The exact sum is 5000000000, and 5000000000 mod 1000000007 = 999999972. The walk uses the exact values; only the final sum is taken modulo 109 + 7.

Constraints

  • 1 <= arr.length <= 2000
  • 1 <= arr[i] <= 109

More C3.ai interview questions

  • Drop Recent Duplicate MessagesOA · Seen Oct 2026
  • Maximum K-Star SumOA · Seen Oct 2026
  • Largest Square Sub-Grid Within a Sum LimitOA · Seen Jan 2023
  • Tree Node With Maximum BeautyOA · Seen Nov 2022
  • Count Vowel Strings With Follow RulesOA · Seen Apr 2022
  • Photo Album Insert OrderOA · Seen Apr 2022
  • Sort by Frequency, Then ValueOA · Seen Apr 2022
  • Count Distinct Binary Search TreesOA · Seen Mar 2022
  • Count Palindromic Subsequences of Length KOA · Seen Mar 2022
  • Fewest Turns to Open a Wheel LockPHONE SCREEN · Seen Nov 2024

Similar questions at other companies

  • Online No-Intercept Linear RegressionTwo Sigma · OATwo Sigma interview questions
  • Array Challenge (QR Intern)Akuna Capital · OAAkuna Capital interview questions
  • Capping Portfolio WeightsCapstone Investment Advisors · OA
  • Count Subarrays with a Perfect-Square ProductMicrosoft · OAMicrosoft interview questions
  • Repeated Mirror XORMathWorks · OAMathWorks interview questions
  • Stacked Item and Category DiscountsPalantir · OAPalantir interview questions
  • Macaron Order PriceOpenAI · OAOpenAI interview questions
  • Daily Settlement for Long and Short PositionsBelvedere Trading · OA
  • Count Attack Vectors by Divisor RangeVisa · OAVisa interview questions
  • Prime Factor VisitationMaven Securities · OAMaven Securities interview questions

Interview reports that mention this question

  • C3.ai New Grad Interviews: 25 Experiences (Part 1 of 2)

C3.ai interview experiences

  • C3.ai FDE and Other New Grad Roles: 5 Experiences (Part 2 of 2)
  • C3.ai New Grad Forward Deployed Engineer Interview: 1 Experience
All C3.ai interview questionsSee C3.ai hiring insights
Saved
class Solution {
    public int[] getPrefixScores(int[] arr) {
        // Write your code here.
    }
}
Checking account…