Sets
Set Operations
Union, intersection, difference
Interview: Mathematical set operations — commonly tested in algorithm interviews
Python sets support all standard mathematical set operations: union, intersection, difference, and symmetric difference. Each has both an operator and method form. These operations are highly optimized using hash table internals.
Four Core Operations
- Union (|): All elements from both sets — O(len(s) + len(t))
- Intersection (&): Elements in both sets — O(min(len(s), len(t)))
- Difference (-): Elements in first set but not second — O(len(s))
- Symmetric difference (^): Elements in either set but not both — O(len(s) + len(t))
Relationship Tests
- Subset (<=):
{1,2} <= {1,2,3}→ True - Proper subset (<):
{1,2} < {1,2,3}→ True (not equal) - Superset (>=):
{1,2,3} >= {1,2}→ True - Disjoint:
{1,2}.isdisjoint({3,4})→ True (no common elements)
Operator vs Method
- Operators (|, &, -, ^): Require both operands to be sets
- Methods (.union(), .intersection(), etc.): Accept any iterable as argument
- Example:
s.union([1,2,3])works buts | [1,2,3]raises TypeError
Performance Insight
Intersection is optimized to iterate over the smaller set and check membership in the larger. This means small & large and large & small have the same performance.
Use Cases
Permission/authorization checking (subset tests)
Finding common interests/tags between users
Data filtering and deduplication
Algorithm problems: connected components, set cover
Common Mistakes
Using operators with non-set types (| requires both operands to be sets; use .union() for iterables)
Confusing subset (<=) with proper subset (<): <= allows equal sets, < does not
Forgetting that set operations create new sets (don't modify originals unless using &= etc.)
Not knowing that intersection is optimized for the smaller set