How to Approach a Problem 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 the whole method: read, trace, find edge cases, estimate the cost, solve and read input like a judge. Decide the plan first, then write it.
The method in six steps
Stress test is running a fast solution and a brute-force solution on many small random inputs and stopping at the first input where their answers differ.
Read closely, work examples, list edge cases, write a brute force, make it faster, then test the fast version against the slow one. Here the method solves one small problem.
def first_repeat(ids): seen = set() for value in ids: if value in seen: return value seen.add(value) return None
assert first_repeat([4, 9, 4, 7]) == 4assert first_repeat([1, 2, 3]) is Noneassert first_repeat([]) is Noneprint("ok")Example 1 · Whole problem with fake input
import io, sys
sys.stdin = io.StringIO("6 14\n8 3 11 5 9 2\n")
n, target = map(int, input().split())amounts = list(map(int, input().split()))seen = set()answer = "NO"for amount in amounts: if target - amount in seen: answer = "YES" break seen.add(amount)print(answer)YES
What this code does
- The first line holds n and the target. The second line holds the amounts.
- The loop stops at the first pair that adds up to the target, and the answer is the word the statement asks for.
Example 2 · Stress test against brute force
import random
def slow(values): return max(sum(values[i:j]) for i in range(len(values)) for j in range(i + 1, len(values) + 1))
def fast(values): best = current = values[0] for value in values[1:]: current = max(value, current + value) best = max(best, current) return best
rng = random.Random(3)for _ in range(300): values = [rng.randint(-6, 6) for _ in range(rng.randint(1, 7))] assert slow(values) == fast(values), valuesprint("300 random cases match")300 random cases match
What this code does
- The slow version tries every block of consecutive values. The fast one keeps the best block that ends at the current value.
- Random small inputs include all-negative lists, where a careless start value would fail.
The set makes it one pass. The asserts cover a repeat, no repeat and an empty list.
Estimate before you code
From n in the constraints, pick the method that fits the step budget. Then write only that one.
def method(n): if n <= 3_000: return "double loop" if n <= 1_000_000: return "one pass or sort" return "formula or binary search"
print(method(2_000), method(200_000))Example 3 · Pick the method from n
def method(n): if n <= 3_000: return "double loop" if n <= 1_000_000: return "one pass or sort" return "formula or binary search"
for n in (500, 100_000, 10**9): print(n, method(n))500 double loop 100000 one pass or sort 1000000000 formula or binary search
What this code does
- The same problem needs different methods at different sizes.
- Read the limit first, then decide.
Roughly ten million simple steps fit in a second of Python, so the step count of each method decides.
A judge-ready template
Read all tokens once, solve in a function, collect answers, print once. The same shape works for most problems.
import sys
def solve(values): return max(values)
def main(): data = sys.stdin.read().split() n = int(data[0]) print(solve(list(map(int, data[1:1 + n]))))
main()Keeping solve separate from reading lets you test it with asserts and reuse it.
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
Write first_repeat(ids) returning the first id that has already appeared, or None. Print the results for [4, 9, 4, 7] and [1, 2].
4 None
Exercise 2· Easy
The text stands in for the input: a count, then the values. Read all tokens at once and print the smallest value.
3
Exercise 3· Medium
Write second_largest(values) for distinct values, returning None when there are fewer than two. Print the results for [9, 9, 4], [5] and [], one per line.
4 None None
Exercise 4· Medium
Check by assert that the set-based has_pair agrees with a double-loop version on 100 random small cases (seed 5). Print ok at the end.
ok
Exercise 5· Medium
The text stands in for the input: the number of cases, then per case the line n target and the line of n values. Print YES or NO per case: do two different positions add up to the target?
YES NO
Exercise 6· Medium
Write longest_run(values) returning the length of the longest block of equal neighbours. Print the result for [5, 5, 5, 2, 2, 5] and for [].
3 0
Exercise 7· Hard
Count the blocks of consecutive values (any length) whose sum is zero in [1, -1, 2, -2, 3] with one pass and a dictionary of prefix sums. Print the count.
3
Exercise 8· Hard
Find the largest sum of 3 consecutive values in [2, 1, 5, 1, 3, 2] with a sliding window that adds the new value and removes the old one. Print it.
9
Interview questions
Questions interviewers ask on this topic.
Finish up
Mark complete & continue
Next: Must-do problems: How to Approach a Problem