Python · Exercise 6 of 6 Previous
Advanced
Replace a slow scan with the right data structure
common_items(a, b) returns the items of a that also appear in b, in the order of a (an item that repeats in a stays repeated). The version below works but is slow: it scans the list b for every item.
Rewrite it so it is fast on big inputs by using the right data structure. The checks count how many == comparisons your code makes on special items, so you cannot pass by timing luck: a quadratic scan makes tens of thousands of comparisons, a good version makes only a few hundred.
What Check tests
common_items([1, 2, 2, 3], [2, 3, 4])returns[2, 2, 3]- An empty input gives an empty list
- Strings work too
- The inputs are not changed
- It makes few comparisons on large inputs
- The program prints
[2, 2, 3]
Stuck? One hint at a time
The solution unlocks after your first Check. Try first: that is where the learning happens.
main.py
Sign in to run your code.
Output
Press Run to see what your program prints.