~/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.

String hashing

String hashing / Rabin-Karp

Rolling polynomial hash for O(1) substring comparison.

Quiz (10) Spot the pattern
Notes

Recognise it when: you need fast substring equality, pattern matching, or the longest repeated substring (with binary search on the length).

B, M = 131, (1 << 61) - 1
h = [0] * (n + 1); p = [1] * (n + 1)
for i, ch in enumerate(s):
    h[i + 1] = (h[i] * B + ord(ch)) % M
    p[i + 1] = p[i] * B % M
def get(l, r):                     # hash of s[l:r]
    return (h[r] - h[l] * p[r - l]) % M
  • Rabin-Karp: compare the pattern's hash with every window's hash, and confirm matches with a direct comparison if you're worried about collisions.
  • Longest duplicate substring: binary search the length L, with a set of window hashes of length L.

Gotchas: collisions. Use a big modulus (2^61 - 1) or two hashes. Keep % M everywhere.

6 problems

Advanced & competitive

String hashing Rolling hashes and Rabin-Karp.

esc