Foundations

3 / 170

FoundationsLesson 3 of 5About 37 min

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.

1values = [4, 8, 15, 16, 23, 42]2 3print(23 in values)          # O(n), scans until found4print(23 in set(values))     # O(1) average, one hash lookup

Sets

A set holds distinct values with no order. Use it whenever the question is membership rather than counting.

1seen = set()2seen.add(3)3seen.add(3)              # adding twice changes nothing4print(len(seen), 3 in seen)5 6a = {1, 2, 3}7b = {2, 3, 4}8print(a & b, a | b, a - b)   # intersection, union, difference

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.

1ages = {"ana": 31, "bo": 27}2ages["cy"] = 453 4print(ages["ana"])5print(ages.get("dee"))          # None instead of KeyError6print(ages.get("dee", 0))       # supply your own default7 8for name, age in ages.items():9    print(name, age)

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.

1from collections import Counter, defaultdict2 3counts = defaultdict(int)4for ch in "banana":5    counts[ch] += 1          # no need to check whether ch exists yet6print(dict(counts))7 8print(Counter("banana"))9print(Counter("banana").most_common(2))10 11groups = defaultdict(list)12for word in ["ant", "bee", "ape"]:13    groups[word[0]].append(word)14print(dict(groups))

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.

1nums = [1, 2, 3, 4, 5, 6]2 3print([n * n for n in nums if n % 2 == 0])4print({n % 3 for n in nums})5print({n: n * n for n in nums if n < 4})

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.

1seen = {}2 3point = [3, 4]4# seen[point] = "visited"     # TypeError: unhashable type: 'list'5seen[tuple(point)] = "visited"6print(seen)

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· 5 min

Predict the output: reading a defaultdict

Read carefully. Type the two lines of output.

Python

1from collections import defaultdict2 3d = defaultdict(int)4d["a"] = 15print(d["b"])6print(len(d))

Printed output

Select all that apply· 5 min

Which of these can be a dict key?

Select every value that Python will accept as a dictionary key.

Code lab· 14 min

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.

solution.py

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 tests to see output.