Micro-questions over the sliding window pattern. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. Why it exists
1. What does the naive approach cost, and why is that wasteful?
Answer
— each query recomputes the same sliding sums over and over from scratch.
2. State the fix.
Answer
Compute the first window’s sum once, then slide it one step at a time, adding the new element and subtracting the one that falls out.
3. Why is the result ?
Answer
Each element enters and leaves the window at most once.
4. What does Codility call this?
Answer
The caterpillar method — same technique, a front and back index each only ever moving forward.
B. The vocabulary
5. Define a sliding window.
Answer
A contiguous subarray or substring that moves one element at a time, maintaining a fixed or variable size — a camera panning across a scene.
6. Fixed-size versus variable-size?
Answer
Fixed: size is constant; slide by removing the element that falls out the back and adding the one entering the front. Variable: the window grows and shrinks depending on a condition.
7. Give an example of each.
Answer
Fixed: a 3-day moving average. Variable: longest substring without repeating characters.
C. Fixed-size windows
8. Write the update step.
Answer
window_sum += nums[i] - nums[i - k] # add new, drop oldest — O(1)9. Trace [2,1,5,1,3,2], .
Answer
[2,1,5] = 8 → [1,5,1] = 7 → [5,1,3] = 9 (best) → [1,3,2] = 6.
10. Does it still work with negative numbers?
Answer
Yes. new_sum = old_sum - nums[i-k] + nums[i] is valid regardless of sign — the algorithm does not assume positivity.
D. Variable-size windows
11. Describe the longest-substring-without-repeats loop.
Answer
Expand the right edge each iteration; while the constraint is violated, shrink from the left, removing characters from seen. Record the best length each step.
12. Why is it despite the nested while inside the for?
Answer
Each character is added to seen at most once and removed at most once across the whole run — total operations bounded by , not .
13. What familiar analysis is that?
Answer
The same amortised argument as dynamic array resizing — the loop looks nested, but the total work across the run is linear.
14. Describe minimum window substring.
Answer
Track a need counter of required characters and a missing count. Expand right; whenever missing == 0 the window is valid, so record it and shrink from the left until it stops being valid.
E. When the aggregate is not invertible
15. Why can sliding window maximum not use add-one-drop-one?
Answer
Max is not invertible. Knowing the old max and the element that left tells you nothing about the new max if the departing element was the max.
16. What structure does it use instead?
Answer
A monotonic deque storing indices with decreasing values.
17. Describe its two while loops.
Answer
- Pop from the front any index that has fallen out of the window.
- Pop from the back any index whose value is the incoming one — it can never be the max again.
18. Where is the answer at each step?
Answer
nums[dq[0]] — the front of the deque, once the window is full.
F. Trade-offs
19. What is the fixed-size window’s precondition?
Answer
An invertible aggregate. Sum and count work; max, min and median do not.
20. When should you use prefix sums instead?
Answer
When the problem requires checking every possible window — e.g. “find all subarrays with sum equals ”. A window cannot help there, especially with negative values, because shrinking is no longer monotone.
21. Summarise the pattern in one sentence.
Answer
Maintain a contiguous span and update it incrementally as it moves — linear because every element enters and leaves exactly once, however nested the loops look.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Sliding Window — the pattern
- Two Pointers — Question Bank
- Monotonic Stack — Question Bank — the deque variant
- Prefix Sum — Question Bank — what to use when the window cannot shrink monotonically
Software engineering
Infrastructure & security
Computer science
Hardware & engineering