Dictionaries and sets, and the hash table under them

If you learn one data structure well enough to reach for it under pressure, make it the dictionary. A very large share of coding-round questions are a hash table wearing a disguise.

What a dict actually does

A dictionary maps keys to values, and finds a key in roughly constant time regardless of how many keys there are:

marks = {"raja": 87, "anu": 92}
print(marks["anu"])       # 92
marks["vik"] = 78
print(len(marks))         # 3

The trick is hashing. Python computes hash(key) — a number derived from the key's value — and uses it to decide where in an internal array the entry lives. Looking up a key means computing its hash and going straight there, rather than scanning.

Two consequences fall out of that, and both are interview questions.

Keys must be hashable, which in practice means immutable.

d = {}
d["text"] = 1        # str — fine
d[(1, 2)] = 2        # tuple — fine
d[3.5] = 3           # float — fine
d[[1, 2]] = 4        # TypeError: unhashable type: 'list'

If a list could be a key, mutating it after insertion would change its hash and the entry would become unfindable. Python forbids the situation rather than allowing a silent corruption.

Two different keys can hash to the same slot. That is a collision, and it is normal. CPython resolves collisions by probing for another free slot in the same array (open addressing). Lookup stays O(1) on average; the pathological worst case, where everything collides, is O(n).

Order

Since Python 3.7, a dict preserves insertion order — this is part of the language specification, not a CPython accident:

d = {}
d["c"] = 1
d["a"] = 2
d["b"] = 3
print(list(d))        # ['c', 'a', 'b'] — insertion order, not sorted

Insertion order, not sorted order. If you want sorted output, ask for it:

print(sorted(d))                  # ['a', 'b', 'c']  — keys sorted
print(sorted(d.items()))          # [('a', 2), ('b', 3), ('c', 1)]

Note that iterating a dict gives you keys, not pairs:

for k in d:                       # keys
    print(k, d[k])

for k, v in d.items():            # pairs — prefer this
    print(k, v)

for v in d.values():
    print(v)

The two idioms that remove most if statements

get — read with a default instead of crashing.

marks = {"raja": 87}

marks["anu"]              # KeyError
marks.get("anu")          # None
marks.get("anu", 0)       # 0

Counting. This pattern appears in nearly every string or array question:

text = "placement"

# the long way
counts = {}
for c in text:
    if c in counts:
        counts[c] += 1
    else:
        counts[c] = 1

# with get
counts = {}
for c in text:
    counts[c] = counts.get(c, 0) + 1

# with defaultdict — the default is created on access
from collections import defaultdict
counts = defaultdict(int)
for c in text:
    counts[c] += 1

# with Counter — one line, and it is written in C
from collections import Counter
counts = Counter(text)
print(counts)                    # Counter({'e': 2, 'p': 1, ...})
print(counts.most_common(2))     # [('e', 2), ('p', 1)]

Know all four. Write the last one.

defaultdict is worth understanding beyond int, because grouping is the other everyday use:

from collections import defaultdict

students = [("CSE", "raja"), ("ECE", "anu"), ("CSE", "vik")]
by_branch = defaultdict(list)
for branch, name in students:
    by_branch[branch].append(name)

print(dict(by_branch))     # {'CSE': ['raja', 'vik'], 'ECE': ['anu']}

Without defaultdict that needs a setdefault or an if. One caveat: reading a missing key from a defaultdict creates it, which can surprise you when you later count the keys.

Sets

A set is a dict without values — unordered, no duplicates, O(1) membership:

s = {3, 1, 2, 3}
print(s)             # {1, 2, 3} — duplicate gone
print(2 in s)        # True, O(1)

empty = set()        # NOT {}, which is an empty dict

The set operations read like mathematics, and each has an operator form:

a = {1, 2, 3}
b = {3, 4}

print(a | b)     # {1, 2, 3, 4}   union
print(a & b)     # {3}            intersection
print(a - b)     # {1, 2}         difference
print(a ^ b)     # {1, 2, 4}      symmetric difference
print({1, 2} <= a)   # True       subset

The one trick that fixes the most timeouts

# O(n²): `in` on a list scans it every time
def has_duplicate_slow(items):
    for i, x in enumerate(items):
        if x in items[i + 1:]:
            return True
    return False

# O(n): a set membership test is constant time
def has_duplicate(items):
    return len(set(items)) != len(items)

# O(n), and stops at the first repeat
def has_duplicate_early(items):
    seen = set()
    for x in items:
        if x in seen:
            return True
        seen.add(x)
    return False

If a question involves seen before, duplicate, unique, visited or intersection, a set is almost certainly the answer.

For grid problems, remember from lesson 4 that a tuple is hashable:

visited = set()
visited.add((row, col))
if (r, c) in visited:
    ...

Complexity

"O(1) average" is doing work in that table. A hash table trades memory for speed, and its guarantee is amortised average, not worst case. For placement purposes that is fine, and saying "average case constant, worst case linear on collisions" is the answer that sounds like you know why.

Merging and comprehensions

a = {"x": 1}
b = {"x": 9, "y": 2}

print({**a, **b})      # {'x': 9, 'y': 2}  — later wins
print(a | b)           # same, Python 3.9+

squares = {n: n * n for n in range(5)}
print(squares)         # {0: 0, 1: 1, 2: 4, 3: 9, 4: 16}

inverted = {v: k for k, v in squares.items()}

Inverting a dict is a common small task, and worth a sentence of care: if two keys share a value, the inverted dict loses one of them. Say so before your interviewer does.

What to take into an interview

• A dict is a hash table: hash(key) decides where the entry lives, so lookup is O(1) average.
• Keys must be hashable, which means immutable. Lists cannot be keys; tuples can.
• Collisions are normal and resolved by probing. Worst case is O(n).
• Dicts preserve insertion order from Python 3.7 — guaranteed by the language.
• get, setdefault, defaultdict and Counter remove almost every counting if.
• {} is an empty dict; an empty set is set().
• Turning a list into a set turns O(n²) membership loops into O(n).