Sets, Membership & Dedup

The last piece is the set. A set is just a hash map that stores keys and no values - so it inherits the same O(1) average membership test, minus the bookkeeping of associated data. Whenever the only question is "have I seen this before?", a set is the right tool.

Membership: "is this in the collection?"

Testing membership against a set is constant time, the same buckets-and-hash idea from Phase 1. Against a list it would be a linear scan.

banned = {"root", "admin", "guest"}   # a set literal

print("admin" in banned)
print("alice" in banned)

True
False

What just happened: each in test hashed the string and checked one bucket - no walking the collection. For a handful of names it hardly matters, but for a blocklist of a million entries checked on every request, set-vs-list is the difference between instant and sluggish.

De-duplication that preserves order

Need the unique items, in the order they first appeared? Walk once, keeping a set of what you've already emitted. The set answers "seen it?" in O(1); the result list keeps the original order.

def dedupe(items):
    seen = set()
    result = []
    for x in items:
        if x not in seen:
            seen.add(x)
            result.append(x)
    return result

print(dedupe([3, 1, 3, 2, 1, 1, 5]))

[3, 1, 2, 5]

What just happened: the first time each value shows up it's added to both seen and result; every later repeat is caught by x not in seen and skipped. One pass, order preserved. (If you don't care about order, list(set(items)) is the one-liner - but it may reorder the elements, for reasons we hit at the bottom of this phase.)

Finding the first duplicate

Same set, slightly different question: what's the first value that repeats? Return it the moment you see a value already in the set.

def first_duplicate(items):
    seen = set()
    for x in items:
        if x in seen:
            return x
        seen.add(x)
    return None

print(first_duplicate([2, 4, 3, 4, 5, 2]))

4

What just happened: 2, 4, 3 all go into seen as first sightings. The next 4 is already there, so it's returned immediately - the scan stops early instead of running to the end. 2 also repeats later, but 4's repeat comes first.

Gotcha 1: keys (and set members) must be hashable

A hash map can only hash things that don't change - so mutable values like lists and dicts can't be keys or set members. Immutable ones (numbers, strings, tuples) are fine.

seen = set()
seen.add((1, 2))          # a tuple is immutable -> hashable, fine
print((1, 2) in seen)

try:
    seen.add([1, 2])      # a list is mutable -> unhashable
    print("added a list?!")
except TypeError:
    print("Cannot add a list: unhashable type")

True
Cannot add a list: unhashable type

What just happened: the tuple (1, 2) hashes fine and goes in. Trying to add the list [1, 2] raises a TypeError for an unhashable type - because a list can change after insertion, its hash would go stale and the map could never find it again. The fix when you need a list-like key is to convert it to a tuple first.

Gotcha 2: the worst case really is O(n)

"O(1) average" is a promise about the typical case. If many keys collide into the same bucket, the map degrades toward a linear scan of that bucket. In normal use this never bites - hash functions spread keys well - but it's why the guarantee is "average," not "always." For adversarial input (a service where users control keys), it's a real, if rare, concern.

Gotcha 3: don't rely on set ordering

A Python dict preserves insertion order (guaranteed since Python 3.7). A set does not - its iteration order follows the internal bucket layout, which you shouldn't depend on.

nums = {30, 10, 20, 50, 40}   # a set, not sorted, not insertion-ordered
print(nums)
print(sorted(nums))           # ask explicitly if you want an order

{50, 20, 40, 10, 30}
[10, 20, 30, 40, 50]

What just happened: the set prints in some bucket-driven order that is neither sorted nor the order written

• and that exact ordering is an implementation detail you should never build logic on. When order matters, be explicit: use sorted(...) for sorted output, or the order-preserving dedupe from earlier for first-seen order. (Your printed line for the set above may differ from what's shown here, which is exactly the point.)

💡 Key point. Reach for a set when you only need "seen it or not," a dict when you need to associate a value (a count, an index, an object) with each key, and a list when order and duplicates both matter. Picking the right one is most of what makes hash-based code fast and correct.

[
  {
    "q": "Why can't a Python list be used as a set member or dict key?",
    "choices": ["Lists are too big", "Lists are mutable, so their hash could change and the map could no longer find them - they're unhashable", "Lists are slower than tuples", "It's only a style rule, not enforced"],
    "answer": 1,
    "explain": "Hash-based structures need a stable hash. A mutable list could change after insertion, invalidating its hash, so Python forbids it with `TypeError: unhashable type`."
  },
  {
    "q": "You need the unique items from a list, in the order they first appeared. What's the safest approach?",
    "choices": ["list(set(items)) - it always keeps order", "Walk once with a `seen` set, appending each first-seen item to a result list", "Sort the list, then remove neighbors", "There's no way to preserve order"],
    "answer": 1,
    "explain": "`list(set(...))` may reorder because set iteration order isn't guaranteed. A `seen` set plus a result list keeps O(1) membership checks while preserving first-seen order."
  }
]