Amazon Software Engineer Interview Experience — A Sparse Sliding Window Over Infinite Bags

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.