Two solutions, one problem
In Data Structures you learned what lists, dictionaries, and sets are, and you met Big-O notation for describing how work grows with input size. This course is about algorithms: step-by-step procedures for solving problems. The interview game is almost never "can you code", it is "can you pick the faster procedure".
Here is the question we will use all lesson: does any pair of numbers in a list add up to a target?
There are two honest ways to solve it:
- Check every pair (a nested loop).
- Walk the list once, remembering what you have seen in a set, and ask "have I already seen
target - n?"
Both are correct. They are not equally fast, and we can measure that instead of guessing.
Code exercise · python
Run this. Both functions solve the same problem, and each one counts its own steps. Compare the two step counts for a 100-item list.
Reading the numbers
The target 197 is only reachable as 98 + 99, the very last pair the nested loop tries. So pair_slow did 4,950 steps (that is every pair of 100 items: 100·99/2) while pair_fast did 100 steps, one per item.
That is the practical meaning of Big-O you learned in Data Structures:
| Solution | Steps for n items | Big-O |
|---|---|---|
pair_slow | about n²/2 | O(n²) |
pair_fast | about n | O(n) |
At n = 100 the gap is 4,950 vs 100. At n = 100,000 it is about five billion vs 100,000. Counting steps on small inputs is how you check your Big-O guess against reality.
Quiz
Why is pair_fast so much faster than pair_slow?
Code exercise · python
Your turn. dup_slow finds a duplicate by checking every pair. Write dup_fast: one pass with a set named seen, counting one step per loop iteration, returning (True, steps) at the first repeat or (False, steps) at the end. Run to compare step counts.
Problem
pair_slow checks every pair. For a list of 1,000 items, how many pairs is that in the worst case? Use n·(n-1)/2. Enter the number.