Python for Interviews

Dictionaries & Sets

Hash-based lookups: key-value maps, membership tests and set operations.

Easy, about 60 minutes to practise.

1Understand

The idea

A dict or set answers "have I seen this?" in O(1) on average, which is what turns most O(n²) brute forces into O(n). Use d.get(k, default) instead of checking first, iterate with .items(), and remember that only immutable values (numbers, strings, tuples) can be keys.

Intuition

A dict answers "what do I know about this key?" in expected O(1). A set answers "have I seen this?" the same way. That single upgrade turns many nested-loop scans into one pass.

Use d.get(k, default) or if k in d instead of bare d[k] when the key might be missing. Iterate with .items() when you need both key and value. Keys must be immutable: numbers, strings, tuples of immutables, never a list.

Sets also give cheap union, intersection and difference when comparing collections.

What you will be able to do

  • Read and update dictionaries safely
  • Use sets for O(1) membership
  • Know which values are hashable

2See it

Walkthrough

Seen set / dict in one pass

nums = [3, 1, 3], ask "have I seen this?" in O(1) average.

1 / 4

i
3
1
3
012
i → index 0

seen

  • ∅ empty

Empty set. At index 0, value 3 is new.

seen = set()

Average O(1) lookup/insert; worst-case hashing is rare in interviews. Space is O(u) for u distinct keys. Prefer a set when you only need membership; use a dict when you must store an index, count or partner value.

Read the walkthrough as text

First duplicate. Given nums = [2, 5, 1, 2, 3], return the first value that repeats when scanned left to right.

  1. Start with an empty set seen.
  2. At 2: not in seen → add it.
  3. At 5, then 1: same.
  4. At the second 2: already in seen → return 2.

In code:

  • seen = set()
  • for x in nums:
  • if x in seen:
  • return x
  • seen.add(x)

Using a list for seen would make every in scan O(n) and the whole algorithm O(n²).

3Recognise it

Kinds of problems (5)

Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.

  • Lookup with get and in

    Example. Increment a counter or read an optional key.

    How. d.get(k, default) avoids KeyError; `k in d` tests membership before d[k].

  • Counting by hand

    Example. Frequency of each character in a string.

    How. count[ch] = count.get(ch, 0) + 1 in one pass over the input.

  • Iterating items

    Example. Print or aggregate every key-value pair.

    How. for k, v in d.items(), not range(len(d)); keys() and values() when you only need one side.

  • Set membership and deduplication

    Example. Have we seen this value before?

    How. Put items in a set; `x in seen` is average O(1) vs scanning a list.

  • Union, intersection and difference

    Example. Users in both cohorts, or in A but not B.

    How. a | b, a & b, a - b (and |=, &=) express Venn operations in one line.

Common mistakes

Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.

  • KeyError on missing keys

    Why it happens. d[key] is the fast path when you expect every key to exist.

    How it fails. count[x] += 1 on first sighting raises KeyError before the increment runs.

    Fix. count[x] = count.get(x, 0) + 1, or check `x in count` before updating.

  • Membership tests on lists instead of sets

    Why it happens. A list can hold the same values as a set with simpler syntax.

    How it fails. seen = []; for each step `if x in seen` scans the whole list, O(n²) on large inputs.

    Fix. Use a set for membership, or a dict when you need an associated value (index, count).

  • Using a list as a key or set element

    Why it happens. Anything collectable feels valid as a set element or dict key.

    How it fails. set([1, 2]) or {(1, 2): "ok"} vs using [1, 2] as a key → TypeError: unhashable type.

    Fix. Keys and set elements must be immutable, use tuple(lst) or a canonical string key.

4Check yourself

Concept check

A short quiz on this lesson before you practise. Optional, and it does not gate coding.

Ready to practise?

Mastery comes from solving. The lesson is optional context.

All lessons