Sets — unique elements, set operations (union, intersection, difference): Exercises

Throughout, $A$ and $B$ are Python sets. We reuse only four symbols, all defined in the parent:

$\cup$ (union, Python |) — "in $A$ or $B$ ",
$\cap$ (intersection, Python &) — "in $A$ and $B$ ",
$-$ (difference, Python -) — "in $A$ but not $B$ ",
$△$ (symmetric difference, Python ^) — "in exactly one of them".

If any of those feels shaky, the truth-table view lives in Boolean Logic — AND, OR, XOR.

Level 1 — Recognition

Can you read a set correctly and predict its size/contents?

Recall Solution 1.1

WHAT: A set stores each value at most once — duplicate inserts are silently dropped. WHY: each value is hashed to an address; if that address already holds an equal value, insertion is skipped (the mechanism in Hashing and Hashable Types). Collapsing duplicates: ${5, 5, 5, 1, 2, 2, 9} \to {1, 2, 5, 9}$ . There are 4 distinct values, so len(s) prints 4.

Recall Solution 1.2

a = {} → an empty dictionary (Python breaks the {} tie in favour of dicts — see Dictionaries — key-value & why {} is a dict).
b = set() → the empty set ✅. len(b) is 0.
c = {0} → a set with one element, the number 0. It is not empty; len(c) is 1. So only b is an empty set.

Recall Solution 1.3

Membership x in t answers "is an element equal to x present?" — case-sensitive for strings.

"cat" in t → True (exact match present).
"Cat" in t → False ("Cat" ≠ "cat"; different hash, different bucket).
"bird" not in t → True ("bird" is absent, so not in is true).

Level 2 — Application

Run the four operations by hand on concrete data.

Figure — Sets — unique elements, set operations (union, intersection, difference)

Recall Solution 2.1

Read the Venn picture above: left-only petal is $A - B$ , the lens in the middle is $A \cap B$ , the right-only petal is $B - A$ .

Union $A \cup B$ = everything in either petal or the lens = ${1, 2, 3, 4, 5, 6, 7}$ .
Intersection $A \cap B$ = only the shared lens = ${4, 5}$ .
Difference $A - B$ = left petal (in $A$ , not $B$ ) = ${1, 2, 3}$ .
Reverse difference $B - A$ = right petal = ${6, 7}$ . Note $A - B \neq = B - A$ — order matters for $-$ .
Symmetric difference $A △ B$ = both petals, lens removed = ${1, 2, 3, 6, 7}$ .

Recall Solution 2.2

(a) set(nums) collapses to ${1, 3, 7, 9}$ . Wrapping in list() gives those four values, but order is not guaranteed — the set is arranged by hash, not by when you inserted. So all we can promise about the contents is the set ${1, 3, 7, 9}$ . (b) To keep first-seen order, use dict.fromkeys (dict keys are unique and remember insertion order):

ordered = list(dict.fromkeys(nums))   # [7, 3, 1, 9]

First appearances are 7, then 3, then 1, then 9 → [7, 3, 1, 9].

Worked example Exercise 2.3 — Shared and exclusive tags

post1 = {"python", "sets", "hashing", "speed"}
post2 = {"sets", "speed", "lists", "python"}

Find (a) tags in both, (b) tags unique to post1, (c) tags used by exactly one post.

Recall Solution 2.3

(a) both = intersection post1 & post2 = ${python, sets, speed}$ .
(b) only post1 = difference post1 - post2 = ${hashing}$ (the only tag in post1 missing from post2).
(c) exactly one = symmetric difference post1 ^ post2 = ${hashing, lists}$ (hashing only in post1, lists only in post2).

Level 3 — Analysis

Reason about behaviour, mutation, and cost.

Worked example Exercise 3.1 —

union vs update

A = {1, 2}
B = {2, 3}
C = A.union(B)
print(A)        # (i)
print(C)        # (ii)
 
D = {1, 2}
D.update(B)
print(D)        # (iii)

Give (i), (ii), (iii).

Recall Solution 3.1

Key distinction: union returns a new set and leaves the caller untouched; update mutates in place and returns None.

(i) A is unchanged by .union(...) → {1, 2}.
(ii) C is the fresh union → {1, 2, 3}.
(iii) D.update(B) folds B into D → {1, 2, 3}.

Recall Solution 3.2

(a) One membership test costs $O (1)$ for a set (single hash → one bucket) and $O (n)$ for a list (scan all $n$ ). Doing it $k$ times: $set: O (k), list: O (k \cdot n) .$ (b) Worst case each of the $k$ lookups scans all $n$ items: $k \cdot n = 1000 \times 1, 000, 000 = 1, 000, 000, 000 = 1 0^{9} comparisons.$ The set version does about $k = 1000$ hash lookups instead — a factor of $n = 1 0^{6}$ fewer. That gap is why sets exist for membership work.

Worked example Exercise 3.3 — What can go inside a set?

Which of these lines raise TypeError, and why?

s1 = {(1, 2), (3, 4)}     # (a)
s2 = {[1, 2], 3}          # (b)
s3 = {1, "one", (1,)}     # (c)
s4 = {{1, 2}, 3}          # (d)

Recall Solution 3.3

A set element must be hashable — roughly, immutable so its hash never changes (see Hashing and Hashable Types).

(a) OK ✅ — tuples are immutable, hence hashable.
(b) TypeError ❌ — a list is mutable, so unhashable.
(c) OK ✅ — an int, a str, and a 1-element tuple are all hashable.
(d) TypeError ❌ — a plain set is itself mutable, so it can't be an element. (The immutable cousin frozenset would work.)

Level 4 — Synthesis

Combine operations to solve a real task; verify an identity.

Recall Solution 4.1

Left side — symmetric difference (in exactly one set): $A - B = {1, 2}, B - A = {5}, A △ B = {1, 2} \cup {5} = {1, 2, 5} .$ Right side — union minus the shared middle: $A \cup B = {1, 2, 3, 4, 5}, A \cap B = {3, 4},$ $(A \cup B) - (A \cap B) = {1, 2, 3, 4, 5} - {3, 4} = {1, 2, 5} .$ Both give ${1, 2, 5}$ ✔. The picture: union collects everything; the intersection is the "double-counted" lens; remove it and only the two exclusive petals survive — exactly "in one set only."

Worked example Exercise 4.2 — Access control with sets

Users have permissions. admin, editor, and guest are sets of allowed actions:

admin  = {"read", "write", "delete", "publish"}
editor = {"read", "write", "publish"}
guest  = {"read"}

Answer in set-operation form and give the result: (a) Actions an editor can do that a guest cannot. (b) Actions unique to admin (no one else has). (c) Is every guest action also an editor action? (One boolean.)

Recall Solution 4.2

(a) editor beyond guest = editor - guest = ${write, publish}$ . (b) admin-only vs the union of the others: $admin - (editor \cup guest) = {delete} .$ Because editor | guest = ${read, write, publish}$ , subtracting from admin leaves {"delete"}. (c) "every guest action is an editor action" is the subset test guest <= editor (equivalently guest.issubset(editor)). Since guest = {"read"} and "read" ∈ editor, this is True.

Level 5 — Mastery

Design and prove — no hand-holding.

Recall Solution 5.1

WHAT: flatten every value into one set, then take its length. WHY a set: it dedups automatically and joins effortlessly via union. Using set().union(*map(set, data)) unions all sublists at once:

distinct = set().union(*map(set, data))
print(len(distinct))

Values seen: $1, 2, 3, 4$ → distinct set ${1, 2, 3, 4}$ → count 4. (Equivalently len({x for row in data for x in row}) — a set comprehension.)

Recall Solution 5.2

(a) Take $A = {1, 2}$ , $B = {2, 3}$ : $A - B = {1}, B - A = {3}, {1} \neq = {3} .$ So $-$ is not symmetric. (b) The symmetric difference $△$ is order-independent because it unions both differences: $A △ B = (A - B) \cup (B - A) = {1} \cup {3} = {1, 3},$ $B △ A = (B - A) \cup (A - B) = {3} \cup {1} = {1, 3} .$ Same result → $A △ B = B △ A$ ✔. Union is commutative, so wrapping the two (non-symmetric) differences in a union restores symmetry.

Recall Solution 5.3

Design idea: keep a seen set. Walk left to right; if the current item is already in seen, it's the first repeat — return it. Membership is $O (1)$ , so total is $O (n)$ .

def first_dup(seq):
    seen = set()
    for x in seq:
        if x in seen:      # O(1) check
            return x
        seen.add(x)
    return None

Trace on [3, 1, 4, 1, 5, 3]:

step	x	seen before check	in seen?	action
1	3	{}	no	add 3
2	1	{3}	no	add 1
3	4	{1,3}	no	add 4
4	1	{1,3,4}	yes	return 1

Answer: 1 (the second 1 is the first value seen twice).

Recall Self-test checklist

I can predict len after duplicates collapse. Level 1 ::: yes
I compute all four ops from a Venn picture. Level 2 ::: yes
I explain union vs update and the $O (1)$ vs $O (n)$ gap. Level 3 ::: yes
I verify $A △ B = (A \cup B) - (A \cap B)$ and model permissions. Level 4 ::: yes
I design an $O (n)$ duplicate detector and prove non-commutativity. Level 5 ::: yes

Connections

Parent topic
Boolean Logic — AND, OR, XOR — the AND/OR/XOR behind $\cap, \cup, △$
Big-O Notation & Time Complexity — why the set version wins
Hashing and Hashable Types — why $O (1)$ membership works
Tuples — immutable sequences — valid hashable set elements
Lists — ordered, indexed collections — order vs speed trade-off
Dictionaries — key-value & why {} is a dict — {} is a dict, dict.fromkeys keeps order