~/problems

Problems

Basics first, then the classics, then company-style assessments. Every problem has tests you run right here; multi-level ones unlock as you go. See the roadmap.

Arrays & hashing

Prefix sums and difference arrays

O(1) range sums (1D and 2D); O(1) range updates with difference arrays.

Visual guide Quiz (10) Spot the pattern
Notes

Recognise it when: you need many range-sum queries on a static array, subarray sums equal to k (with a hash map), or many range updates followed by one read.

P = [0] * (n + 1)
for i, x in enumerate(a): P[i + 1] = P[i] + x
sum(a[l:r]) == P[r] - P[l]

# 2D: S[r+1][c+1] = g[r][c] + S[r][c+1] + S[r+1][c] - S[r][c]
# rect (r1, c1)..(r2, c2) inclusive:
S[r2+1][c2+1] - S[r1][c2+1] - S[r2+1][c1] + S[r1][c1]

# Difference array: add v to a[l..r]
D[l] += v; D[r + 1] -= v   # then prefix-sum D once

Gotchas: stay consistent with 1-indexed prefix arrays and inclusive vs exclusive bounds. Write the 2D formula from a picture.

8 problems

Interview roadmap

Arrays & hashing Counting, lookups, sorting with keys, prefix sums.

Prefix sums and difference arrays guide

esc