The first online-assessment question was set in Amazon's financial team. An analyst had an infinite line of bags numbered from 1 onward. Information about the money in the bags was given as continuous, nonintersecting segments. Every bag inside a segment held the segment's stated amount, while every bag outside the supplied segments held zero. The goal was to choose exactly k consecutive bags that maximized the total money. Because the answer could be large, it had to be returned modulo 10^9 + 7.
Formally, segment was an n x 3 array. Each row described an inclusive range [segment[i][0], segment[i][1]] and the amount segment[i][2] in every bag in that range.
For the example:
k = 5
n = 4
segment = [[1, 4, 2], [6, 6, 5], [7, 7, 7], [9, 10, 1]]
The money in bags 1 through 10 was:
Bag: 1 2 3 4 5 6 7 8 9 10
Money: 2 2 2 2 0 5 7 0 1 1
All other bags held zero. The five-bag windows in the example were:
[1 - 5] = 2 + 2 + 2 + 2 + 0 = 8
[2 - 6] = 2 + 2 + 2 + 0 + 5 = 11
[3 - 7] = 2 + 2 + 0 + 5 + 7 = 16
[4 - 8] = 2 + 0 + 5 + 7 + 0 = 14
[5 - 9] = 0 + 5 + 7 + 0 + 1 = 13
[6 - 10] = 5 + 7 + 0 + 1 + 1 = 14
The subsegment from the third bag through the seventh had the maximum total, so the answer was 16.
The function signature was:
def calculateMaximumConsecutiveSum(k, segment):
# Write your code here
It returned the maximum total money in exactly k consecutive bags, modulo 10^9 + 7. The constraints were:
1 <= n <= 2 * 10^5
1 <= k <= 10^9
1 <= segment[i][0] <= segment[i][1] <= 10^9
1 <= segment[i][2] <= 10^6
No two segments intersected. In essence, the problem asked for the maximum-sum sliding window of length exactly k over a very long sparse array whose value was constant inside each interval.
Discussion
Loading comments…