Why does a rolling-maximum deque store reading positions rather than the reading values?
answer
- each stored entry answers two questions
- one end tests magnitude, the other age
- what tells you a candidate aged out?
- repeated readings break value comparisons
- a value is one lookup from a position
basics
~20 sPositions do double duty: the value at a position decides dominance, while the position itself decides expiry. Storing bare values leaves no exact way to tell when a candidate has aged out of the window, and repeated readings then produce wrong answers.
solid answer
~50 sTwo different questions have to be answered on every step, and they need different data. Deciding whether a candidate is dominated needs its *value*, so the back-eviction loop compares the value at the last stored position against the incoming reading. Deciding whether the front candidate has left the window needs its *position*, so the expiry check compares the stored position against `i - k`. A position answers both, because the value is one lookup away; a stored value answers only half. The failure this avoids is concrete: with values alone you would expire the front by comparing it against the reading leaving the window, and whenever readings repeat, that comparison drops a candidate that is still in range and reports a peak lower than the real one. Positions make expiry exact no matter how many duplicates the stream contains.
code
pseudocode · 10 lines# a[0..n-1] = load readings, k = window length
# dq holds POSITIONS; values at those positions strictly decrease
for i in 0..n-1:
while size(dq) > 0 and a[last(dq)] <= a[i]:
drop_last(dq) # dominated by a[i]: uses the VALUE
add_last(dq, i)
if first(dq) == i - k:
drop_first(dq) # aged out: uses the POSITION
if i >= k - 1:
report a[first(dq)] # max of a[i-k+1 .. i]go deeper
Recall that the structure holds positions rather than readings, and that the reading at a position is one lookup away. Being able to state that plainly is enough at this level.
Explain both maintenance steps in one breath: values drive back-eviction, positions drive front-expiry. Expect to be pushed on which of the two repeated readings break.
Produce a concrete sequence with repeats, show the wrong output a value-based expiry gives, and say what kind of test would have caught it before the dashboard lied.
Frame it as an invariant that must survive later edits: if positions are stored, moving to a time-based window touches one predicate; if they are not, it is a rewrite that someone will do under time pressure.
## Two jobs, two kinds of data Every step of a rolling maximum performs two independent maintenance actions on the candidate list, and they ask different questions of the stored entries. **Back-eviction asks about magnitude.** "Is this stored candidate smaller than or equal to the reading that just arrived?" If yes, the stored candidate is dominated — it is older and no larger, so every remaining window containing it also contains the new reading — and it leaves from the back. **Front-expiry asks about age.** "Has the oldest candidate fallen out of the window?" That is a question about *where* the reading sat in the stream, not about how large it was. A stored position answers both questions: the value is recovered with one indexed lookup. A stored value answers only the first. That asymmetry is the whole reason the canonical formulation keeps positions. ## Reading the two loops In the fragment attached to this question, the `while` loop is magnitude-driven and the `if` is age-driven. Note that they touch opposite ends: dominance always removes from the back (the newest, smallest candidates), expiry always removes from the front (the oldest, largest one). A candidate therefore leaves for exactly one of two reasons, and knowing which reason applies to a given line is the fastest way to check an implementation you are reading in a review. ## The failure that duplicates expose Suppose the entries held values only, and expiry were written as "if the front value equals the value that just left the window, drop the front". That reads plausibly, and it survives any stream of distinct readings. Now take readings `5, 3, 5, 1` with window length `3`. - Step 0: candidate list is `[5]`. - Step 1: `3` does not dominate `5`, so the list is `[5, 3]`. - Step 2: `5` dominates both, so the list is `[5]` — this `5` is the third reading, at position 2. - Step 3: reading `1` joins, giving `[5, 1]`. The window is now the last three readings, `3, 5, 1`, whose maximum is `5`. The value leaving the window is the first reading, also `5`. A value-based expiry sees the front value `5` matching the departing value `5` and drops it — but the front candidate is the *third* reading, still comfortably inside the window. The reported peak becomes `1` instead of `5`. With positions stored, the check is `front == i - k`, that is `2 == 0`, which is false, and the correct answer survives. This is not an exotic input. Load readings, prices and counters repeat constantly; flat stretches are the normal case for a metrics stream, not the edge case. ## Variants that are still correct Storing `(position, value)` pairs is perfectly fine and saves a lookup per comparison at the cost of a wider entry. What matters is that *some* positional key is present, because expiry is a positional predicate. If the window is defined by elapsed time rather than by a count of samples — a stream whose readings arrive irregularly — store the arrival timestamp and expire from the front while the front timestamp is older than the current time minus the window duration. Dominance is untouched by that change; only the expiry predicate moves. That is a good illustration of why the two concerns should stay visibly separate in the code: one of them changes with the product requirement, and the other does not. ## What an interviewer is testing The question looks like a detail, and it is really a probe for whether the candidate reconstructed the structure or memorised it. Someone who reasoned it out says "values for dominance, positions for expiry" immediately and can produce the duplicate counterexample on request. Someone who memorised the shape says "that is just how it is written" and then cannot say what breaks when the rule is violated, which is exactly the thing that shows up as a subtly wrong dashboard weeks after the code merged.
- Give a short reading sequence where expiring the front by value instead of position gives a wrong answer.Readings `5, 3, 5, 1` with window length 3. At the last step the front candidate is the third reading (value 5, still in range) while the value leaving the window is the first reading, also 5. A value comparison drops the valid candidate and reports 1 instead of 5.
- Could you store position-and-value pairs instead of bare positions? What changes?It works and saves one lookup per comparison, at the cost of a wider entry and a little duplication. The invariant is unchanged: expiry still tests the position, dominance still tests the value. Bare positions are preferred when the readings are already held in memory.
- How does the expiry test change for a window defined by elapsed time rather than a sample count?Store the arrival timestamp and expire from the front while the front timestamp is older than the current time minus the window duration. Dominance is untouched — only the expiry predicate changes, which is why keeping the two concerns separate in the code pays off.
saying these in an interview costs you the question
- Says only values matter because the answer is a value
- Expires the front by comparing values instead of positions
- Assumes repeated readings do not occur in real streams
- Thinks the position is stored only for reporting purposes
- Mixes the two ends: evicts dominated candidates from the front