056. Sets

Aryan’s monitor scans processes every 5 seconds. After 10 scans, the raw name list has duplicates — Chrome, Slack, PyCharm appearing in every scan:

all_names = []
for snapshot in history:
    for proc in snapshot:
        all_names.append(proc["name"])

print(len(all_names))   # 10 scans × 50 procs = 500 entries

He needs the set of unique process names to build a stable display:

seen = set(all_names)
print(len(seen))  # ~50 — deduplicated

# O(1) membership check — critical in a hot loop
watched = {"Chrome", "Slack", "PyCharm"}
for proc in current_snapshot:
    if proc["name"] in watched:   # O(1), not O(n)
        alert(proc)

Aryan also uses set difference to find new processes that appeared since the last scan:

prev_pids = {p["pid"] for p in last_snapshot}
curr_pids = {p["pid"] for p in curr_snapshot}

new_pids  = curr_pids - prev_pids   # appeared since last scan
gone_pids = prev_pids - curr_pids   # terminated since last scan

Sets turn what would be nested O(n²) loops into clean one-liners.

💡 Fun fact: Python sets are implemented as hash tables — the same data structure as Python dicts — which is why x in my_set is O(1) while x in my_list is O(n). This O(1) membership check was critical to Google’s early search indexing: their inverted index used set-like structures to compute which documents contained all query terms in milliseconds, even across billions of pages.

⚠️ Watch out: {} creates an empty dict, not an empty set. To create an empty set, you must use set(). This trips up nearly every beginner: my_set = {}; my_set.add(1) raises AttributeError: 'dict' object has no attribute 'add'. Always use set() for empty sets, never {}.

🤔 Think about it: Sets store only unique elements, so converting `[1, 1, 2, 3, 3]` to a set and back to a list removes duplicates — but the order is lost. If Aryan needs to deduplicate a list while preserving insertion order, he can’t use `set()` alone. How would you deduplicate a list while keeping the first occurrence of each element in its original position?

Learning objectives

Use set() to deduplicate lists
Apply set operations: & (intersection), | (union), - (difference)
Use sets for O(1) membership checking

Key concepts

set
union
intersection
difference

Try it

Concept detail

Sets are unordered collections of UNIQUE elements. No duplicates, no guaranteed order. Create: {1, 2, 3}, set([1,2,3]), set() (empty — NOT {}, which is an empty dict!).

Set operations: A | B — union: elements in A OR B (or both) A & B — intersection: elements in BOTH A and B A - B — difference: elements in A but NOT in B A ^ B — symmetric difference: in A or B but NOT both A <= B — subset: all A elements are in B A.isdisjoint(B) — True if A and B share no elements

Performance: x in my_set — O(1) (hash table lookup) x in my_list — O(n) (linear scan)

This makes sets ideal for membership checks in hot loops. Downsides: unordered (no indexing), elements must be hashable (no lists inside sets). frozenset is an immutable set — can be used as a dict key.

Solution

def unique_items(lst):
    return list(set(lst))

def common_elements(lst1, lst2):
    return set(lst1) & set(lst2)

def unique_to_first(lst1, lst2):
    return set(lst1) - set(lst2)

def count_unique(lst):
    return len(set(lst))

Tests

def test_unique_items():
    result = unique_items([1, 2, 2, 3, 3, 3])
    assert set(result) == {1, 2, 3}
    assert len(result) == 3  # no duplicates

def test_common_elements():
    result = common_elements([1, 2, 3, 4], [3, 4, 5, 6])
    assert result == {3, 4}

def test_common_elements_none():
    result = common_elements([1, 2], [3, 4])
    assert result == set()

def test_unique_to_first():
    result = unique_to_first([1, 2, 3], [2, 3, 4])
    assert result == {1}

def test_count_unique():
    assert count_unique([1, 1, 2, 2, 3]) == 3

def test_count_unique_all_different():
    assert count_unique([1, 2, 3]) == 3