Foundations
Dicts, sets, and counting
The hash table is the highest-leverage tool in the whole course. This is how you drive it in Python.
Why these matter so much
Checking whether a value is in a list takes time proportional to the length of the list. Checking whether it is in a set or a dict takes constant time on average. Almost every time you turn an O(n squared) solution into an O(n) one, that swap is what did it.
Sets
A set holds distinct values with no order. Use it whenever the question is membership rather than counting.
Dicts
A dict maps keys to values. Since Python 3.7 it keeps insertion order, which is occasionally useful and should never be relied on for correctness in an interview answer unless you say so out loud.
Counting without the boilerplate
Counting occurrences is so common that Python ships two tools for it. defaultdict makes a missing key spring into existence with a default; Counter goes further and counts an iterable in one call.
Tip
Counter returns zero for missing keys
Counter is documented to return a zero count for an item it has never seen rather than raising KeyError. That makes comparisons safe without any guarding: counts[ch] works whether or not ch was in the input.
defaultdict behaves differently. Reading a missing key from a defaultdict inserts it. If you loop over a defaultdict while reading keys that might be absent, you will grow it as you go, which has surprised people mid-interview.
Comprehensions
Comprehensions build a list, set, or dict in one expression. Used well they remove noise. Used badly they hide a nested loop inside something that looks like a single line, so keep them to one level in interview code.
Gotcha
Lists cannot be dict keys
Keys must be hashable, which in practice means immutable. Strings, numbers, and tuples work. Lists, dicts, and sets do not.
This comes up the moment you want to key something by a signature that is naturally a list of values. The fix is to convert it to a tuple first.
Cost
What these actually cost
Average case is what you quote in an interview. Worst case for hash collections is O(n), which happens when every key collides. It effectively never happens with Python's built-in hashes on ordinary data, but knowing it exists is the difference between reciting and understanding.
| Operation | list | set | dict |
|---|---|---|---|
| x in s | O(n) | O(1) average | O(1) average |
| add or set item | O(1) append at end | O(1) average | O(1) average |
| delete item | O(n) by value | O(1) average | O(1) average |
| index by position | O(1) | not supported | not supported |
| keeps order | yes | no | yes, insertion order |
Predict the output: reading a defaultdict
Read carefully. Type the two lines of output.
Which of these can be a dict key?
Select every value that Python will accept as a dictionary key.
Counting drills
Three functions built on dicts and sets. first_repeat returns the first value that appears twice, scanning left to right, or None. char_counts returns a plain dict of character counts. common_elements returns the values present in both lists, sorted ascending.
Tests
print(first_repeat([1, 3, 5, 3, 1]))
print(first_repeat([1, 2, 3]))
print(char_counts("banana"))
print(common_elements([4, 1, 2, 1], [2, 4, 9]))Output
Run the tests when you are ready.