Build fluency in the vocabulary of expanding and shrinking a contiguous range as it moves across data.
0 / 5 completed
1 / 5
At standup, a dev mentions scanning an array by expanding and shrinking a contiguous range of indices as it moves across the data, rather than re-scanning the entire range from scratch for every possible starting position. What is this technique called?
The sliding window technique expands and shrinks a contiguous range of indices as it moves across the array, reusing work already done for the previous position instead of recomputing a result from scratch for every possible starting index. A hash collision is an unrelated hash-table concept about two keys sharing a bucket. This incremental expand-and-shrink approach is exactly what turns a naive quadratic scan over every possible subrange into a single linear pass across the data.
2 / 5
During a design review, the team picks a sliding window over recomputing a running sum from scratch for every possible subarray, specifically so adding one element and removing another only costs a constant amount of work each time. Which capability does the sliding window provide here?
The sliding window provides a linear-time scan overall, since each element only ever gets added to the window's running sum once, when it enters, and removed once, when it leaves, rather than being re-summed from scratch for every subarray it happens to be part of. Recomputing the sum from scratch for every possible subarray instead repeats the same additions over and over, which is exactly the quadratic-time cost the sliding window is designed to avoid. This constant-cost-per-shift property is what makes the sliding window the standard technique for problems asking about a contiguous subarray satisfying some running condition.
3 / 5
In a code review, a dev notices a solution to a contiguous-subarray problem re-sums the entire current window from scratch on every single shift, instead of just adding the newly entered element and subtracting the one that left. What does this represent?
This is a missed sliding-window optimization, since re-summing the entire window from scratch on every shift repeats nearly the same additions over and over across overlapping windows, turning what could have been a single linear-time pass into an overall quadratic-time solution. A cache eviction policy is an unrelated concept about discarded cache entries. This is exactly the kind of subtle inefficiency a performance-focused reviewer flags, since the fix, tracking just the entering and leaving elements, is a small, mechanical change that removes an entire order of magnitude of redundant work.
4 / 5
An incident report shows a data-processing job that scans a large array for the maximum-sum contiguous subarray of a fixed length ran far slower than expected on large inputs, because its implementation re-summed the entire current window from scratch on every shift instead of tracking the sum incrementally. What practice would prevent this?
Updating the window's running sum incrementally, by adding only the newly entered element and subtracting only the element that just left, reduces the per-shift cost to a constant amount of work, turning the overall scan back into a linear-time pass, which is exactly the fix for the slowdown described in this incident. Continuing to re-sum the entire window from scratch on every shift is exactly what made the job scale so poorly as the input array grew large. This incremental-update pattern is the entire point of the sliding window technique, and skipping it defeats the technique's main benefit even while superficially using a window.
5 / 5
During a PR review, a teammate asks why the team reaches for a sliding window instead of just checking every possible contiguous subarray directly with a nested loop, given that both approaches are conceptually simple to write. What is the reasoning?
A nested loop over every possible subarray repeats nearly the same additions across ranges that heavily overlap with each other, which adds up to quadratic time overall as the input grows, since the same elements get re-summed again and again from different starting points. A sliding window instead reuses the sum already computed for the previous position, updating it in constant time per shift, which brings the total cost down to a single linear pass across the whole array. The tradeoff is that a sliding window requires the underlying condition to be maintainable incrementally as elements enter and leave, which isn't true of every possible subarray problem, so the nested-loop approach is sometimes still the only option available.