Sliding Window Checkpoint
A review of this module. Skip it if you feel confident; the next module does not need it.
Fix the mistakes
The slips that cost marks in this module. Spot each one, then check the fix.
This checkpoint mixes all four window shapes. For each question, decide first: is the size fixed, what must the window remember, and what makes it valid. Then write the loop.
Fixed or variable?
Window pattern is the habit of asking three questions: is the block size fixed or not, what must the window remember, and what makes it valid. The answers choose the code.
First read the question. If it names a block size, such as the best 3 days, the window is fixed. If it asks for the longest or shortest block that follows a rule, the window changes size.
sales = [4, 2, 7, 1, 3, 6]k = 3total = sum(sales[:k])best, start = total, 0for right in range(k, len(sales)): total += sales[right] - sales[right - k] if total > best: best, start = total, right - k + 1print(best, start)Example 1 · Best three days and where they start
revenue = [120, 80, 150, 90, 60, 200, 40]k = 3total = sum(revenue[:k])best, start = total, 0for right in range(k, len(revenue)): total += revenue[right] - revenue[right - k] if total > best: best, start = total, right - k + 1print(best, start)350 0
What this code does
- The window ends at right, so it starts at right - k + 1.
- Only a strictly bigger total updates the answer, so the first best window wins a tie.
A fixed window moves with one pointer and a formula for the item that leaves. A variable window moves two pointers on its own.
What does the window remember?
A number is enough for sums. A set remembers which items are inside. A Counter remembers how many of each. A deque remembers candidates for the maximum or minimum.
from collections import Counter
text = "eceba"window = Counter()left = best = 0for right, ch in enumerate(text): window[ch] += 1 while len(window) > 2: window[text[left]] -= 1 if window[text[left]] == 0: del window[text[left]] left += 1 best = max(best, right - left + 1)print(best)Example 2 · Longest run with at most two products
from collections import Counter
orders = ["pen", "pen", "ink", "pad", "ink", "ink", "pen"]window = Counter()left = best = 0for right, item in enumerate(orders): window[item] += 1 while len(window) > 2: window[orders[left]] -= 1 if window[orders[left]] == 0: del window[orders[left]] left += 1 best = max(best, right - left + 1)print(best)4
What this code does
- The rule is "at most two different products", so
len(window) <= 2. - The same code works for letters or for list items.
Choose the smallest memory that can answer the rule. A sum is cheaper than a Counter, and a Counter is cheaper than a sort.
Check the edges
Test the window code on an empty list, a window larger than the list, negative numbers, and a case with no answer. Decide what to return before you write the loop.
def shortest(nums, target): left = total = 0 best = len(nums) + 1 for right, value in enumerate(nums): total += value while total >= target: best = min(best, right - left + 1) total -= nums[left] left += 1 return best if best <= len(nums) else 0
print(shortest([], 5), shortest([1, 1], 9), shortest([9], 9))Example 3 · Edge cases in one function
def shortest(nums, target): left = total = 0 best = len(nums) + 1 for right, value in enumerate(nums): total += value while total >= target: best = min(best, right - left + 1) total -= nums[left] left += 1 return best if best <= len(nums) else 0
print(shortest([], 5))print(shortest([1, 1], 9))print(shortest([9], 9))print(shortest([2, 3, 1, 2, 4, 3], 7))0 0 1 2
What this code does
- The loop does not run for an empty list.
- The result 0 means "no such block".
An empty list and an impossible target both return 0. A single item that already reaches the target gives 1.
Module quiz
Questions from the whole module. Your first answer is your score.
Problems
Graded easy to hard, using everything from this module.
Try each one yourself first. Use the hint if you get stuck. Mark it as done when it works.
Exercise 1· Easy
Print the average of the best (highest-sum) window of size 2 in [3, 9, 4, 8, 1], with one decimal.
6.5
Exercise 2· Easy
Print the length of the longest piece of "abcbdea" with no repeated letter.
5
Exercise 3· Easy
Print the length of the shortest block of [3, 1, 4, 1, 5, 9, 2] with a sum of at least 14.
2
Exercise 4· Medium
Print how many blocks of "abcabcab" are an anagram of "abc".
6
Exercise 5· Medium
Print the length of the longest piece of "aabacbebebe" with at most 3 different letters.
7
Exercise 6· Medium
Print the maximum of every window of size 3 in [5, 3, 4, 8, 1, 2, 9].
[5, 8, 8, 8, 9]
Exercise 7· Hard
Print the shortest piece of "XYZAXBYZAB" that contains the letters "XYZ".
XYZ
Exercise 8· Hard
Print how many blocks of [1, 1, 2, 1, 1] contain exactly 3 odd numbers. Count blocks with at most 3 odds and subtract blocks with at most 2 odds.
2
Interview questions
Questions interviewers ask on this topic.
Finish up
Mark complete & continue
Next: Must-do problems: Sliding Window