# High Water > Every reading remembers the highest that came before. Canonical URL: Domain: Python · Difficulty: easy · Seniority: L4 ## Problem Given `readings`, a monitoring service's integer readings in arrival order, return the highest value the service has seen so far after each reading, one value per reading. ## Example 1 Input: ``` readings = [3,1,4,1,5,9,2] ``` Output: ``` [3,3,4,4,5,9,9] ``` ## Example 2 Input: ``` readings = [5,2,2,8] ``` Output: ``` [5,5,5,8] ``` ## Worked solution and explanation ### What this really is Strip off the monitoring costume and this is a running maximum: a scan that folds each reading against the peak already seen. Every output position depends on every reading before it, so there is no memoryless transform that produces it. The thing being probed is whether you thread one accumulated value across the stream instead of treating each element in isolation. Most candidates who miss it fall into one of two holes: they write an elementwise map that has no memory and lets the value dip back down, or they recompute max over a growing prefix slice at each position and quietly turn a linear pass into quadratic work. > **See it as a fold** > > The whole problem collapses to one idea: carry a running peak, and at each reading emit max(peak, reading), which also becomes the new peak. That is a left fold that yields its intermediate results. In Python, itertools.accumulate(readings, max) IS exactly that scan, no bookkeeping required. ### The trap The trap is reaching for the shape you already know. A comprehension is the reflex, and the only comprehension that produces the right answer is the one that recomputes max(readings[:i+1]) at every index. It looks clean and it passes the two visible cases, but each step rescans a prefix that grows with the stream, so the total work is 1 + 2 + ... + n. At ten thousand readings that is fifty million comparisons for a problem that needs ten thousand. **Per-slice recompute (rejected)** [max(readings[:i + 1]) for i in range(len(readings))]. Correct output, but every position rescans a longer prefix. O(n^2) time, and it degrades exactly when the stream gets long. **Single scan (accepted)** list(accumulate(readings, max)). One left-to-right pass, each reading compared once against the running peak. O(n) time, O(n) output, and the empty case falls out for free. **Running peak as a scan** ```python from itertools import accumulate def high_water_marks(readings): return list(accumulate(readings, max)) ``` *One linear pass; accumulate folds each reading against the peak with max.* If you would rather not lean on accumulate, the explicit fold is the same shape and just as fast. Both are a single pass carrying one variable, and both hand back a real list. **The explicit fold, for comparison** ```python def high_water_marks(readings): result = [] peak = None for r in readings: peak = r if peak is None else max(peak, r) result.append(peak) return result ``` *Same O(n) pass written by hand; useful when you want to show the state you are threading.* > **Do not hand back the iterator** > > accumulate returns a lazy iterator, not a list. Forgetting the list() wrapper is the most common way this fails grading: the assertion compares against a list and a bare accumulate object is not equal to it. Wrap it. If the interviewer instead asks for a streaming version, that same iterator is the answer, so know which one they want. > **Where the two diverge** > > On the ~10k readings this problem allows, the scan does about 10,000 comparisons and finishes instantly. The per-slice comprehension does about 50,000,000. Both are correct; only one survives the scale question the interviewer asks next. > **Why this shows up** > > This is the toy version of a cumulative window aggregation. In Spark you would order the stream by timestamp and take a running max over an unbounded preceding window (partitioned per device or per key). The mental model is identical: fold each new event against the accumulated peak rather than re-aggregating a growing history every time. ## Common follow-up questions - Now the readings arrive one at a time and you cannot hold them all in memory. How does your answer change? _(Tests whether they realize accumulate is already lazy: drop the list() wrapper and yield the running peak per event.)_ - Return the running minimum and the running maximum together in a single pass. _(Tests generalizing the fold to carry a tuple of accumulated state instead of one scalar.)_ - Port this to Spark over an event stream ordered by timestamp and partitioned per device. What construct gives you the running peak per key? _(Tests mapping the scan onto a windowed cumulative aggregation rather than a self-join.)_ ## Related - [All practice problems](https://datadriven.io/problems) - [Mock interview mode](https://datadriven.io/interview/high_water) - [Python Interview Questions](https://datadriven.io/python-interview-questions) - [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep) - [Daily Challenge](https://datadriven.io/daily) --- Source: DataDriven (https://datadriven.io). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.