Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Sets and dictionaries

Sets and dictionaries: hash-based collections for uniqueness, fast lookup, mapping keys to values, with syntax, operations, and exam-ready examples.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Engineers use sets and dictionaries to manage data efficiently: sets to keep only unique items and test membership quickly, dictionaries to map keys (like IDs, sensor names) to values (like readings). They underpin fast algorithms, configuration handling, counting, indexing, and de-duplication in real-world Python projects.

Key ideas

  • frozenset — Definition: An immutable set; once created, its elements cannot change. It is itself hashable if all its elements are hashable, so it can be used as a key in a dictionary or as an element of another set.
  • Dictionary (dict) — Definition: A dictionary is a mapping from unique, hashable keys to values. Assumptions: keys must be hashable and unique; values can be any type. Since Python 3.7, dictionaries preserve insertion order (the order in which keys were first inserted). Operations for key lookup, insertion, and deletion have average-case O(1) time complexity. In the worst case, these can degrade to O(n).
  • Uniqueness constraint — For sets: duplicates collapse to a single element. For dictionaries: inserting a value with an existing key replaces the old value.
  • Unordered vs ordered — Sets are unordered and do not preserve insertion order; therefore indexing like s[0] is invalid. Dictionaries preserve insertion order for keys, but they are still conceptually mappings; random access by numeric index is not allowed.
  • Set operations — Precise definitions for two sets A and B:
    • Union: A ∪ B = { x | x ∈ A or x ∈ B }
    • Intersection: A ∩ B = { x | x ∈ A and x ∈ B }
    • Difference: A − B = { x | x ∈ A and x ∉ B }
    • Symmetric difference: A Δ B = { x | (x ∈ A) xor (x ∈ B) } Python provides operators |, &, -, ^ implementing these exactly.
  • Subset and superset — For sets A and B:
    • Subset: A ⊆ B if every element of A is also in B.
    • Proper subset: A ⊂ B if A ⊆ B and A ≠ B.
    • Similarly, superset A ⊇ B and proper superset A ⊃ B. Python provides methods: A.issubset(B), A.issuperset(B), and operators <=, <, >=, >.
  • Dictionary entries (items) — Each key-value pair is called an item. dict.items() returns a dynamic view of items; changes in the dict reflect in the view.
  • Key lookup semantics — d[k] raises KeyError if k is absent; d.get(k, default) returns default (or None if not given) instead of raising an error.
  • Mutability — Sets and dictionaries are mutable: you can add/remove elements/items. frozenset is immutable; tuple is immutable but only hashable if all its elements are hashable.
  • Equality — Sets: equality is by element equality ignoring order. Dicts: equality is by key set and corresponding value equality.
  • Comprehensions — Compact syntax to build collections:
    • Set comprehension: {expr for var in iterable if condition}
    • Dictionary comprehension: {key_expr: value_expr for var in iterable if condition}
  • Iteration semantics — Iterating a set visits elements in an arbitrary order; do not assume any order. Iterating a dict yields keys in insertion order. Iterating dict.items() yields (key, value) pairs in insertion order.
  • Common derivation/trace asked in exams — “Show how duplicates are removed using sets and why time complexity is improved compared to lists.” Step-by-step derivation:
    1. Given list L of length n, checking membership with x in L is O(n) worst- and average-case (linear scan).
    2. Converting to set S = set(L) costs O(n) average, builds a hash table of unique elements (duplicates collapsed during insertion).
    3. Now membership x in S is O(1) average due to hashing (constant expected time per lookup), so repeated membership tests across m queries cost O(m) average versus O(m·n) for list.
  • Diagram to draw (if asked “illustrate hashing for dict”) — Draw a rectangle labeled “Hash table (array of buckets)”. Inside, draw numbered slots 0..N−1. From a sample key (e.g., key="ENGR101"), show an arrow: key → hash(key) → index = hash(key) mod N → slot. At the slot, draw a small list/chain or open-address probe sequence showing the stored (key, value). Label: hash function, index computation, collision handling (probing or chaining), and that equality is checked to confirm the correct key after a collision.

Formulas

  • Set constructor: set(iterable)
  • Add/remove: s.add(x), s.update(iterable), s.remove(x) (KeyError if absent), s.discard(x) (no error if absent), s.pop() (removes and returns an arbitrary element), s.clear()
  • Set relations and queries: len(s), x in s, x not in s, s.issubset(t), s.issuperset(t), s.isdisjoint(t)
  • Set operations (operators): s | t, s & t, s - t, s ^ t
  • Set operations (methods): s.union(t, ...), s.intersection(t, ...), s.difference(t, ...), s.symmetric_difference(t) and their in-place forms s |= t, s &= t, s -= t, s ^= t
  • frozenset: fs = frozenset(iterable)
  • Dict literals: {'a': 1, 'b': 2}
  • Empty dict: {}; constructor: dict() or dict(a=1, b=2)
  • Dict comprehension: {k: v for k, v in iterable}
  • Access: d[k] (KeyError if absent), d.get(k, default)
  • Insert/update: d[k] = v, d.update(other_or_kwargs)
  • Remove: d.pop(k) (KeyError if absent), d.pop(k, default) (returns default if absent), d.popitem() (removes and returns the last inserted (key, value) pair), del d[k] (KeyError if absent), d.clear()
  • Views: d.keys(), d.values(), d.items()
  • Safe insert-if-absent: d.setdefault(k, default)
  • Iteration: for k in d:, for k, v in d.items():

Worked examples

Example 1: Remove duplicates and perform set algebra Complete Python program:

# Program: Read two lines of integers, build sets, and print union, intersection, difference, symmetric difference.
# Input format (two lines):
#   10 20 20 30 40
#   30 40 50

# Read two lines and split into ints
A = set(map(int, input().split()))
B = set(map(int, input().split()))

print("A:", A)
print("B:", B)
print("Union:", A | B)
print("Intersection:", A & B)
print("A-B:", A - B)
print("B-A:", B - A)
print("Symmetric difference:", A ^ B)
print("Is A subset of B?", A <= B)
print("Are A and B disjoint?", A.isdisjoint(B))

Sample input:

10 20 20 30 40
30 40 50

Exact output (order of set elements may differ because sets are unordered, but structure will match):

A: {40, 10, 20, 30}
B: {40, 50, 30}
Union: {50, 20, 40, 10, 30}
Intersection: {40, 30}
A-B: {10, 20}
B-A: {50}
Symmetric difference: {50, 10, 20}
Is A subset of B? False
Are A and B disjoint? False

Note: Your printed sets may show elements in a different order, which is correct.

Example 2: Word frequency using dictionary (case-insensitive, punctuation-stripped) Complete Python program:

# Program: Count word frequencies in a single input line, case-insensitive.
# Input: a single line of text.
# Output: each word with its count in insertion order of first appearance.

import string

text = input().strip()
# Normalize: lowercase, remove punctuation
translator = str.maketrans('', '', string.punctuation)
words = text.lower().translate(translator).split()

freq = {}
for w in words:
    # Insert or increment using get
    freq[w] = freq.get(w, 0) + 1

# Print results in insertion order of first appearance of each word
for w, c in freq.items():
    print(f"{w} {c}")

Sample input:

To be, or not to be: that is the question.

Exact output:

to 2
be 2
or 1
not 1
that 1
is 1
the 1
question 1

Example 3: Reverse a mapping and use frozenset as a key Complete Python program:

# Program: Given student -> branch mapping, make branch -> set of students using dict and set.
# Then, construct an immutable key (frozenset of top scorers) and store a summary in another dict.

# Input format:
#   First line: n (number of students)
#   Next n lines: name branch score
# Example:
#   5
#   Ayan ECE 8.7
#   Beena CSE 9.1
#   Charan ME 8.7
#   Divya CSE 9.5
#   Ekta ECE 8.3

n = int(input())
by_branch = {}
by_name = {}
for _ in range(n):
    name, branch, score_s = input().split()
    score = float(score_s)
    by_name[name] = (branch, score)  # dict: name -> (branch, score)
    # build branch -> set of names
    s = by_branch.setdefault(branch, set())
    s.add(name)

# find max score and the set of toppers (names with that score)
max_score = max(sc for (_, sc) in by_name.values()) if by_name else 0.0
toppers = {name for name, (_, sc) in by_name.items() if sc == max_score}

# use frozenset as a key in a summary dict
summary = {frozenset(toppers): ("max_score", max_score)}

print("Branches:", by_branch)
print("Toppers:", toppers)
print("Summary:", summary)

Sample input:

5
Ayan ECE 8.7
Beena CSE 9.1
Charan ME 8.7
Divya CSE 9.5
Ekta ECE 8.3

Exact output (set element order may vary; dicts preserve insertion order of keys):

Branches: {'ECE': {'Ekta', 'Ayan'}, 'CSE': {'Divya', 'Beena'}, 'ME': {'Charan'}}
Toppers: {'Divya'}
Summary: {frozenset({'Divya'}): ('max_score', 9.5)}

Common mistakes

  • Using unhashable types as set elements or dict keys, e.g., set([[1, 2]]) or {[1, 2]: 'x'} cause TypeError. Use tuples instead of lists when you need to hash a sequence.
  • Forgetting KeyError: using d[k] for possibly-missing keys. Prefer d.get(k) or d.setdefault(k, default) or check if k in d:.
  • Confusing remove and discard on sets. remove raises KeyError if the element is absent; discard does nothing if absent.
  • Expecting a stable order in printed sets and then writing exact-order-dependent test output. For exams, write that set output order may vary.
  • Misusing update on dict thinking it appends items like a list; it merges another mapping, overwriting existing keys.
  • Expecting 1 and True to be distinct dict keys: bool is a subclass of int (True == 1 and hash(True) == hash(1)), so they collide and the later assignment overwrites the former.
  • Assuming popitem() removes a random item. In current Python, it removes the last inserted item (LIFO), not arbitrary.
  • Writing a tuple with one element as (1) which is just 1. Must write (1,) to get a 1-tuple; relevant when using tuples as dict keys.
  • Forgetting that equality of sets/dicts compares contents, not identity; two separately created dicts with same items are equal (==) but not the same object (is).

For your exam

  • Programs: Remove duplicates, set algebra; frequency count with dict; reverse mapping (value to set of keys) using setdefault; comprehension-based construction.
  • Diagram: Hash table for dict with labeled hash → index → collision resolution → equality check.
  • Reasoning/derivation: Time-complexity advantage of sets/dicts vs lists; why keys must be hashable; immutability and hash-stability link.
  • Full-marks answers include: correct syntax, explanation of behavior (errors/exceptions where relevant), mention of order properties (set unordered, dict insertion order), and example outputs that acknowledge unordered display for sets.

Quick check

  1. Which statement correctly creates an empty set, and which creates an empty dict?
  2. What is the difference between s.remove(x) and s.discard(x) for a set s?
  3. In Python 3.7+, does a dict preserve insertion order? What does popitem() remove?

Answers: 1) set() is an empty set; {} is an empty dict. 2) remove raises KeyError if x is absent; discard does nothing if x is absent. 3) Yes, dicts preserve insertion order; popitem() removes the last inserted item (LIFO).

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?