High Water Mark

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

Domain
Python
Difficulty
easy
Seniority
L3

Problem

You are given readings, a weather station's hourly temperature log: a non-empty list of integers in hour order. On cold nights every reading can be below zero. For each hour, return the highest temperature recorded up to and including that hour.

Even below zero, one reading still stands above the rest.

Example 1

Input:

readings = [12,5,19,7,3]

Output:

[12,12,19,19,19]

Example 2

Input:

readings = [-8,-3,-11,-5]

Output:

[-8,-3,-3,-3]

Worked solution and explanation

Not the max. The max so far.

This looks like 'find the biggest number' and it is not. You are asked for the high-water-mark at every hour, so a single max() call is useless here: it hands back one scalar when you need the best-so-far at each position. The only way there is to carry a running maximum forward as you walk the list. Here is the part that bites people: that running max has to start from the first reading, not 0. Seed it at 0 because the sunny examples are all positive, and on a cold night your early hours report 0, a temperature that was never on the log. On [-8, -3, -11, -5] a 0-seeded scan emits [0, 0, 0, 0] instead of [-8, -3, -3, -3].

How to get there

Step 1: Seed from the data, not from a guess

Set the running high to readings[0] and make it the first entry of your result. It is a real value from the data, so it can never sit above every actual reading the way 0 does on a cold night. This is the one decision the problem is really testing.

Step 2: Scan and record each hour

Walk the remaining readings once. Replace the running high whenever a reading beats it, then record the current high for that hour. One comparison and one append per element, nothing kept around but the best-so-far.

The solution

Single pass, best-so-far seeded from the first reading
def high_water_marks(readings):
    high = readings[0]
    marks = [high]
    for reading in readings[1:]:
        if reading > high:
            high = reading
        marks.append(high)
    return marks

Common follow-up questions