Module 9 · map and multimap: A Key Finds Its Value
CP and Interview Pack: map Patterns, Questions and the Bug Gallery
ProReading
LeetCode, a website of practice problems for coding interviews, opens its list with problem 1, "Two Sum", rated Easy. It gives a list of numbers and a target, and it asks for the positions of two numbers that add up to the target. Bob checks every pair, which is O(n²): fine for ten numbers, but about 5,000,000,000 pairs for 100,000. Amara keeps a map from each number to its position, and her whole solution is pattern 1.
Checking what this lesson needs for you…
What is inside CP and Interview Pack: map Patterns, Questions and the Bug Gallery
- Pattern 1: two sum, a value and its position
- Pattern 2: counting pairs of neighbours
- Pattern 3: a difference map for ranges on a long line
- Pattern 4: coordinate compression, a first look
- Nine interview questions, with model answers