Module 11 · Iterators: The Thing Between a Container and an Algorithm
CP and Interview Pack: Iterator Patterns, Questions and the Bug Gallery
ProReading
The CSES Problem Set has problem 1084, "Apartments", in its Sorting and Searching section. There are n applicants and m apartments, and each applicant accepts any apartment whose size is within k of the size they want. How many applicants can get an apartment? Bob tries every applicant against every apartment, 4 × 10^10 pairs when both counts are 200,000. Amara sorts both lists and walks one iterator along each. Her solution is pattern 3.
Checking what this lesson needs for you…
What is inside CP and Interview Pack: Iterator Patterns, Questions and the Bug Gallery
- Pattern 1: a position is end minus begin
- Pattern 2: lower_bound minus begin, one index into two vectors
- Pattern 3: two sorted containers walked in step
- Pattern 4: two iterators closing in
- Ten interview questions, with model answers