cs-036 — Rainfall Windows
| Field | Value |
|---|---|
| id | cs-036 |
| difficulty | Advanced |
| topics | aggregation, windows |
| lecture | lecture-09 |
| estimated time | 5-minute attempt + 10-minute discussion |
| prerequisites | the full Block I-III toolbox and proof-shaped reasoning |
| objective | make and justify design decisions where the method itself is the challenge |
| solution | held by the instructor; discussed after the attempt |
Problem
For a window of the last k days, report the running maximum without re-summing the whole window each time. A gentle sliding-window preview.
Your deliverable is the computed aggregates for the worked instance, the accumulator update rules, and one test input that breaks a careless initialisation. If the problem is ambiguous anywhere, state the assumption you are making and carry on — a stated assumption is part of a good answer.
Examples
- Input: rain [3, 5, 2, 8, 1, 4], window k = 3
- Output: window maxima: 5, 8, 8, 8 (windows [3,5,2], [5,2,8], [2,8,1]... recheck: [2,8,1] -> 8, [8,1,4] -> 8)
Solve for the worked instance first. Then ask what would change if one number, name, or condition were replaced by something stranger.
What to notice
- Naive recomputes each window in O(nk). One step better: keep the running max with a decreasing deque - or at least avoid re-scanning when the old max leaves.
- Every aggregate here is a small machine: state + update rule.
- The initial value is part of the algorithm, not a detail.
Discussion starter
After the solution is revealed, the class spends five minutes on this prompt: "Where exactly would this solution break first if the input grew to a million items — and would anything break at all?"
Constraints and assumptions
- Difficulty: Advanced (functions, dictionaries, and algorithmic reasoning assumed).
- Topics: aggregation, windows.
- Classroom-scale inputs unless the problem says otherwise.
- Time-box: about five minutes for the attack plan; the full argument may exceed the box - outline the proof strategy instead of grinding details.
- Optional stretch (not required): describe an alternative approach and say when it beats the obvious one.
Hints and extension
- First nudge: identify the pattern the worked instance uses before computing anything.
- If stuck after three minutes, write the input/output line you expect and trace the smallest example by hand.
- After the reveal, attempt the extension below before the next lecture.
- Extension challenge: Recompute all aggregates in a second pass and argue which pass you would keep.