The Output Peak

A hard Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
hard
Seniority
L5
Asked in
Amazon

Problem

A monitoring job emits net-throughput readings run-length encoded in readings as [value, count] pairs, where one pair can stand in for hundreds of millions of identical readings. Find the consecutive run of readings with the greatest total and return that total together with the run, given back as the [value, count] pairs that cover it. The input always holds at least one reading and the run can never be empty, so when every reading is negative the answer is the single least-negative one; if several runs tie for the greatest total, take the one that starts earliest.

One stretch outpaced all the others.

Example 1

Input:

readings = [[3,4],[-1,5],[4,2]]

Output:

[15,[[3,4],[-1,5],[4,2]]]

Example 2

Input:

readings = [[-4,2],[-1,3],[-9,1]]

Output:

[-1,[[-1,1]]]

Worked solution and explanation

What this problem is really testing

This is the maximum-run problem wearing a compression costume. The skill being probed: can you run the greedy extend-or-restart pass over [value, count] segments instead of individual readings, so a pair standing in for a hundred million values costs you one step, not a hundred million? Anyone can expand the pairs and scan the flat array on paper. Do it in code and a single realistic input exhausts memory before you compute anything. The real move is to weight each segment by its count, fold it into the running total, and record the winning run's boundaries as you go, then remember that an all-negative stream collapses to one lone reading, not a whole negative segment.

Why you cannot just expand it

Expand then scan
Build [value] * count for every pair, concatenate, then run an element-level pass. Correct on toy inputs, but a pair with count 100000000 makes a list that never fits in memory. The approach is dead on arrival for real traffic.
Fold the segments
Never materialize. Each pair contributes value * count to the running sum in constant time, so the whole pass is O(number of pairs) regardless of how many readings each pair represents.

Building the pass

Step 1: Fold each pair into a segment total

For pair [value, count], the whole segment is worth value * count. This single number is all the running pass needs from that pair, no matter how large the count.

Step 2: Extend or restart on each segment

Add the segment to the current run, unless the run has gone negative, in which case start fresh at this segment. Track the index where the current candidate began.

Step 3: Commit the boundaries when the run wins

Whenever the current total beats the best seen, record the current start index and this index as the winning run's boundaries. Slice those pairs at the end.

Step 4: Handle the all-negative collapse

Compute the largest single value across all pairs. If it beats the best run total, every reading was negative and the answer is that one reading, returned as [[value, 1]], never the whole segment.

The solution

Segment-weighted pass with boundary tracking
def max_reading_run(readings):
    best_sum = None
    best_lo = best_hi = 0
    cur_sum = 0
    cur_lo = 0
    for i, (value, count) in enumerate(readings):
        segment = value * count
        if cur_sum + segment < segment:
            cur_sum = segment
            cur_lo = i
        else:
            cur_sum += segment
        if best_sum is None or cur_sum > best_sum:
            best_sum = cur_sum
            best_lo, best_hi = cur_lo, i
    best_single = max(value for value, count in readings)
    if best_single > best_sum:
        return [best_single, [[best_single, 1]]]
    run = [list(pair) for pair in readings[best_lo:best_hi + 1]]
    return [best_sum, run]

Common follow-up questions