Module 10 · unordered_set and unordered_map: Hashing, Collisions and the Anti-Hash Test
CP and Interview Pack: Hash Patterns, Questions and the Bug Gallery
ProReading
The CSES Problem Set, a free collection of contest problems, has problem 1640, "Sum of Two Values", in its Sorting and Searching section. Among n numbers, find two positions whose values add up to x. Bob tries every pair, about 2 × 10^10 of them for n = 200,000. Module 9's pack solved the same two-sum pattern with a map, in O(n log n). Amara makes one hash lookup per number, and her solution is pattern 1.
Checking what this lesson needs for you…
What is inside CP and Interview Pack: Hash Patterns, Questions and the Bug Gallery
- Pattern 1: two-sum with a seeded hash
- Pattern 2: anagram groups under a sorted key
- Pattern 3: a memo for numbers too big for an array
- Pattern 4: a machine that repeats, and a jump to second 10^18
- Ten interview questions, with model answers