These are the notes for Python Coding Questions, episode 25: hashing questions. Dictionaries and sets are the secret weapon of coding interviews. We build an LRU cache with OrderedDict, group anagrams in one pass (and meet TypeError: unhashable type: 'list'), and find the longest consecutive sequence in O(n) with a set.
Every program was run with Python 3.13 (python3 main.py), the SyntaxPilot compiler's Python command. Every output below is real. Timings change from machine to machine and run to run; what matters is how they grow.
The big idea: hashing
Real-life example: a hostel wall of letter boxes, one per room number. To find room 214's letters you don't search: you go straight to box 214. A sack with every letter mixed together means checking each one.
| In the hostel | In Python |
|---|---|
| a wall of letter boxes | a hash table: what dict and set are inside |
| room number → its box | hash(key) turns the key into a number that picks the slot |
| go straight to the box | lookup, insert, delete: O(1) on average |
| one big sack of letters | a list: x in my_list checks every item, O(n) |
A hash function turns a value into a whole number (its hash). The same value always gives the same hash, so Python can jump to the right slot instead of searching. Two different keys can land in the same slot (a collision); Python handles that for you, which is why we say O(1) "on average".
import time
rolls_list = list(range(100_000))
rolls_set = set(rolls_list)
start = time.perf_counter()
for x in range(1_000):
-1 in rolls_list # not there: scans all 100,000
print(f"list: {time.perf_counter() - start:.3f} s")
start = time.perf_counter()
for x in range(1_000):
-1 in rolls_set # jumps to one slot
print(f"set: {time.perf_counter() - start:.5f} s")
Output:
list: 0.494 s
set: 0.00003 s
Q1: LRU cache
Real-life example: your study desk has room for only two books; the rest stay on a far shelf. When you need a third book, one goes back. The smart choice is the book you have not touched for the longest time: the least recently used (LRU) one.
A cache is a small, fast store for things you use often (your desk), in front of a big, slow one (the shelf). Evicting means removing an item to make room.
The question: an LRUCache(capacity) with get(key) (the value, or -1) and put(key, value), both O(1). When it's full, evict the least recently used key.
Attempt 1: a plain dict, evict the first key added
A Python dict remembers insertion order, so next(iter(d)) is the first key that was added.
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.data = {} # a dict keeps insertion order
def get(self, key):
return self.data.get(key, -1)
def put(self, key, value):
if key not in self.data and len(self.data) == self.capacity:
oldest = next(iter(self.data)) # the first key added
del self.data[oldest]
self.data[key] = value
desk = LRUCache(2)
desk.put("maths", "Maths book")
desk.put("physics", "Physics book")
print(desk.get("maths")) # we just used maths!
desk.put("chem", "Chemistry book")
print(desk.get("maths"))
print(list(desk.data))
Output:
Maths book
-1
['physics', 'chem']
Wrong: we used maths just before adding chemistry, yet maths was evicted (-1), and physics, untouched, stayed. Why: a plain dict keeps the order keys were added, not the order they were used. That's first in, first out, not least recently used.
The fix: OrderedDict keeps the order of use
collections.OrderedDict is a dict that can reorder its keys in O(1):
move_to_end(key): the key becomes the newest (the right end).popitem(last=False): remove and return the oldest item (the left end).
Rules: on every get and put, move the key to the end. After a put, if there are more than capacity keys, popitem(last=False).
Inside, an OrderedDict is a hash table plus a doubly linked list (episode 23) of the keys: the hash table finds the node, the links move it. Both O(1).
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.data = OrderedDict() # oldest first, newest last
def get(self, key):
if key not in self.data:
return -1
self.data.move_to_end(key) # just used: now the newest
return self.data[key]
def put(self, key, value):
if key in self.data:
self.data.move_to_end(key)
self.data[key] = value
if len(self.data) > self.capacity:
self.data.popitem(last=False) # drop the least recently used
desk = LRUCache(2)
desk.put("maths", "Maths book")
desk.put("physics", "Physics book")
print(desk.get("maths"))
desk.put("chem", "Chemistry book")
print(desk.get("maths"), "|", desk.get("physics"))
print(list(desk.data))
Output:
Maths book
Maths book | -1
['chem', 'maths']
Now physics (least recently used) is evicted and maths stays. Remember: a get is a use too.
The built-in version: functools.lru_cache
For caching a function's results, Python has this built in. maxsize=2 is our desk. cache_info() reports hits (found on the desk) and misses (fetched from the shelf).
from functools import lru_cache
import time
@lru_cache(maxsize=2)
def fetch_book(name):
time.sleep(0.2) # pretend the shelf is far away
return name.title() + " book"
for name in ["maths", "physics", "maths", "chem", "physics", "maths"]:
start = time.perf_counter()
fetch_book(name)
took = time.perf_counter() - start
print(f"{name:8} {'desk ' if took < 0.1 else 'shelf'}")
print(fetch_book.cache_info())
Output:
maths shelf
physics shelf
maths desk
chem shelf
physics shelf
maths shelf
CacheInfo(hits=1, misses=5, maxsize=2, currsize=2)
Q2: Group anagrams
Real-life example: letter tiles. listen, silent and enlist use exactly the same tiles. Words made of the same letters with the same counts are anagrams. Sort each word's tiles A to Z and anagrams give the same signature: eilnst. Keep one tray per signature.
The question: group a list of words into lists of anagrams.
Attempt 1: the sorted list as the key
words = ["listen", "silent", "enlist", "google",
"inlets", "gogole", "cat", "act"]
groups = {}
for w in words:
key = sorted(w) # same letters -> same sorted list
groups.setdefault(key, []).append(w)
print(list(groups.values()))
Output:
Traceback (most recent call last):
File "main.py", line 7, in <module>
groups.setdefault(key, []).append(w)
~~~~~~~~~~~~~~~~~^^^^^^^^^
TypeError: unhashable type: 'list'
TypeError: unhashable type: 'list'. Why: sorted() returns a list. A dict key (and a set item) must be hashable: its hash must never change while it is stored. A list is mutable (it can change after you store it), so its slot would become wrong; Python refuses it.
| Hashable (can be a key) | Not hashable |
|---|---|
int, float, str, bool, None |
list |
tuple (of hashable items) |
dict |
frozenset |
set |
print(hash("eilnst") == hash("eilnst"), hash((1, 2)) == hash((1, 2)))
d = {("e", "i", "l"): "a tuple key works"}
print(d[("e", "i", "l")])
print(hash([1, 2]))
Output:
True True
a tuple key works
Traceback (most recent call last):
File "main.py", line 4, in <module>
print(hash([1, 2]))
~~~~^^^^^^^^
TypeError: unhashable type: 'list'
The fix: an immutable signature and defaultdict(list)
"".join(sorted(w))turns the sorted letters into a string: immutable, so hashable. (tuple(sorted(w))works too.)collections.defaultdict(list): a missing key starts as an empty list automatically, sogroups[key].append(w)just works.
from collections import defaultdict
words = ["listen", "silent", "enlist", "google",
"inlets", "gogole", "cat", "act"]
groups = defaultdict(list)
for w in words:
key = "".join(sorted(w)) # a string: immutable, so hashable
groups[key].append(w)
for key, group in groups.items():
print(key, group)
print(sorted("listen"), "".join(sorted("listen")))
print(hash("eilnst") == hash("".join(sorted("silent"))))
Output:
eilnst ['listen', 'silent', 'enlist', 'inlets']
eggloo ['google', 'gogole']
act ['cat', 'act']
['e', 'i', 'l', 'n', 's', 't'] eilnst
True
With a plain dict you'd need setdefault, or you get a KeyError for the first word of each group:
groups = {}
for w in ["cat", "act"]:
groups["".join(sorted(w))].append(w)
Output:
Traceback (most recent call last):
File "main.py", line 3, in <module>
groups["".join(sorted(w))].append(w)
~~~~~~^^^^^^^^^^^^^^^^^^^^
KeyError: 'act'
Complexity: n words of length up to k: each is sorted once, O(n · k log k) time, O(n · k) space. Comparing every pair of words instead would be O(n² · k log k).
Q3: Longest consecutive sequence
Real-life example: the teacher writes roll numbers as students walk in: 12, 4, 10, 2, 11, 3, 13, 1. The longest run of consecutive roll numbers is 1, 2, 3, 4 (or 10..13): length 4.
The question: the length of the longest run of consecutive integers, in O(n). Sorting first works but is O(n log n).
Attempt 1: count up from every number, with in on a list
import time
def longest_run(rolls):
best = 0
for x in rolls:
length = 1
while x + length in rolls: # is the next roll number here?
length += 1
best = max(best, length)
return best
print(longest_run([12, 4, 10, 2, 11, 3, 13, 1]))
for n in [400, 800, 1_600]:
rolls = list(range(n, 0, -1)) # one long run
start = time.perf_counter()
longest_run(rolls)
print(n, f"{time.perf_counter() - start:.2f} s")
Output:
4
400 0.06 s
800 0.45 s
1600 3.37 s
Correct, but double n → about 8× the time. Why: two problems. x + length in rolls on a list scans the list, O(n). And we count up from every number, even ones in the middle of a run. A run of n numbers, counted from every start, each step a full scan: O(n³).
The fix: a set, and count only from the start of a run
present = set(rolls):inbecomes O(1), and duplicates disappear.- If
x - 1is present,xis in the middle of someone else's run: skip it. - Only a start counts up:
x + 1,x + 2, ...
Every number is skipped once or counted once inside one run: O(n) time, O(n) space. (Using a set but counting from every number would still be O(n²) on one long run.)
import time
def longest_run(rolls):
present = set(rolls) # O(1) "is it here?"
best = 0
for x in present:
if x - 1 in present: # not the start of a run
continue
length = 1
while x + length in present:
length += 1
best = max(best, length)
return best
print(longest_run([12, 4, 10, 2, 11, 3, 13, 1]))
print(longest_run([5, 5, 6]), longest_run([]), longest_run([-2, -1, 7]))
for n in [4_000, 1_000_000]:
rolls = list(range(n, 0, -1))
start = time.perf_counter()
longest_run(rolls)
print(n, f"{time.perf_counter() - start:.2f} s")
Output:
4
2 0 2
4000 0.00 s
1000000 0.12 s
Common mistakes (and what you really see)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| evicting the first key added | get("maths") → -1 right after using it |
order of adding, not of use | OrderedDict + move_to_end |
no move_to_end in get |
a book you just read is evicted | a read is a use | move on get and put |
popitem() with no argument |
evicts the newest item | the default is last=True |
popitem(last=False) |
key = sorted(w) |
TypeError: unhashable type: 'list' |
lists are mutable | "".join(sorted(w)) or tuple(...) |
groups[key].append(w) on a plain dict |
KeyError: 'act' |
the key isn't there yet | defaultdict(list) or setdefault |
x in some_list inside a loop |
seconds for 1,600 items | in on a list is O(n) |
convert to a set once |
| counting up from every number | O(n²) even with a set | runs are recounted | start only where x - 1 is missing |
hash([1, 2]) or a list in a set |
TypeError: unhashable type: 'list' |
lists are mutable | tuple([1, 2]) |
Your turn: the first repeated roll number (solution)
Question: a careless monitor writes some roll numbers twice. Return the first number that is written a second time, or None. For [7, 3, 9, 3, 7] the answer is 3 (3 repeats before 7 does).
Idea: one pass with a set of numbers already seen. The first r that is already in seen is the answer. O(n) time, O(n) space.
def first_repeat(rolls):
seen = set()
for r in rolls:
if r in seen:
return r
seen.add(r)
return None
print(first_repeat([7, 3, 9, 3, 7]), first_repeat([1, 2, 3]), first_repeat([]))
Output:
3 None None
Mini project: a tiny cached book lookup
The functools.lru_cache example above is the mini project: a slow "fetch from the shelf" function wrapped with @lru_cache(maxsize=2). Try changing maxsize to 3 and watch the hits go up, or call fetch_book.cache_clear() to empty the desk.
Practice questions (with solutions)
1. Group words by their letter counts (no sorting): two words are anagrams if every letter appears the same number of times.
Solution
Count the 26 letters into a list, then use tuple(counts) as the key (a list can't be a key). O(n · k) time for lowercase words.
from collections import defaultdict
def group_by_counts(words):
groups = defaultdict(list)
for w in words:
counts = [0] * 26
for ch in w:
counts[ord(ch) - ord("a")] += 1
groups[tuple(counts)].append(w) # a tuple: hashable
return list(groups.values())
print(group_by_counts(["listen", "silent", "google", "gogole", "cat", "act", "tac"]))
Output:
[['listen', 'silent'], ['google', 'gogole'], ['cat', 'act', 'tac']]
2. Two-sum with a dict (episode 8 revisited): the indexes of two numbers that add up to a target.
Solution
For each number, check if its partner target - x was seen before; remember each value's index. O(n).
def two_sum(nums, target):
index_of = {} # value -> index
for i, x in enumerate(nums):
if target - x in index_of:
return index_of[target - x], i
index_of[x] = i
return None
print(two_sum([2, 7, 11, 15], 9), two_sum([3, 3], 6), two_sum([1, 2], 7))
Output:
(0, 1) (0, 1) None
3. Count subarrays that add up to k (prefix sums).
Solution
A prefix sum is the running total up to a position. A subarray ending here sums to k exactly when an earlier running total equals running - k. Count earlier totals in a dict. O(n).
def count_subarrays(nums, k):
count, running = 0, 0
seen = {0: 1} # prefix sum -> how many times
for x in nums:
running += x
count += seen.get(running - k, 0)
seen[running] = seen.get(running, 0) + 1
return count
print(count_subarrays([1, 1, 1], 2), count_subarrays([3, 4, 7, -2, 2, 1, 4, 2], 7))
Output:
2 6
4. Same pattern: do two strings follow the same letter pattern (egg and add yes, foo and bar no)?
Solution
Two dicts, one each way, so no two letters map to the same letter. O(n).
def same_pattern(a, b):
if len(a) != len(b):
return False
a_to_b, b_to_a = {}, {}
for x, y in zip(a, b):
if a_to_b.setdefault(x, y) != y or b_to_a.setdefault(y, x) != x:
return False
return True
print(same_pattern("egg", "add"), same_pattern("foo", "bar"), same_pattern("ab", "aa"))
Output:
True False False
Quick quiz
What does this print?
from collections import OrderedDict
d = OrderedDict(a=1, b=2, c=3)
d.move_to_end("a")
d.popitem(last=False)
d["d"] = 4
print(list(d))
(A) ['b', 'c', 'd'] (B) ['c', 'a', 'd'] (C) ['a', 'c', 'd'] (D) ['b', 'a', 'd']
Answer
(B). move_to_end("a") gives b, c, a. popitem(last=False) removes the oldest, b. Adding d puts it at the end: c, a, d.
from collections import OrderedDict
d = OrderedDict(a=1, b=2, c=3)
d.move_to_end("a")
d.popitem(last=False)
d["d"] = 4
print(list(d))
Output:
['c', 'a', 'd']
Interview questions
- Why are dict and set lookups O(1)? They are hash tables: the key's hash picks the slot directly. O(1) on average; many collisions can make it slower.
- What makes an object hashable? Its hash never changes during its life (and equal objects have equal hashes). Immutable built-ins are hashable;
list,dictandsetare not. - Can a tuple always be a key? Only if everything inside it is hashable:
(1, [2])raisesTypeError: unhashable type: 'list'. - What is an LRU cache? A fixed-size cache that evicts the least recently used item. Built with a hash map plus a doubly linked list (
OrderedDict), O(1) get and put. - Plain dict vs OrderedDict today? Both keep insertion order (since Python 3.7), but only
OrderedDicthasmove_to_endandpopitem(last=False), and its==checks order. - What does
functools.lru_cachedo? Memoises a function's results for the most recentmaxsizeargument combinations;cache_info()shows hits and misses. Arguments must be hashable. - How do you group anagrams? A dict from a signature (sorted letters as a string, or a tuple of 26 counts) to a list of words.
- Why count only from the start of a run? So each number is visited by just one counting loop: O(n) total instead of O(n²).
defaultdictvssetdefaultvsget?defaultdict(list)creates missing values automatically;d.setdefault(k, [])does it per call;d.get(k, 0)reads with a default without inserting.- When is a list better than a set? When order or duplicates matter, or for tiny collections; but for repeated
inchecks, use a set.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Hash function | Turns a value into a number used to pick a slot | hash("eilnst") |
| Hash | The number a hash function returns | same value → same hash |
| Hash table | Slots found by hash: what dict and set are | {"a": 1}, {1, 2} |
| Collision | Two keys landing in the same slot | handled by Python |
| Hashable | Has a hash that never changes; can be a key | str, tuple |
| Mutable / immutable | Can / cannot change after creation | list / str |
TypeError: unhashable type |
Using a mutable value as a key | {[1]: 2} |
| Cache | A small fast store in front of a slow one | the study desk |
| Evict | Remove an item to make room | send a book back |
| LRU | Least Recently Used: untouched the longest | physics |
OrderedDict |
A dict that can reorder keys in O(1) | move_to_end |
move_to_end(key) |
Make the key the newest | after a get |
popitem(last=False) |
Remove the oldest item | eviction |
functools.lru_cache |
A built-in LRU cache for function results | @lru_cache(maxsize=2) |
| Hit / miss | Found in the cache / had to fetch | cache_info() |
| Anagram | Same letters, same counts, rearranged | listen, silent |
| Signature | A key that is equal for all anagrams | "eilnst" |
defaultdict(list) |
A dict whose missing keys start as [] |
grouping |
setdefault |
Get a key, inserting a default if missing | d.setdefault(k, []) |
KeyError |
Reading a key that isn't in a dict | groups["act"] |
| Set | Unique items with O(1) membership | set(rolls) |
| Consecutive sequence | Integers that follow each other | 1, 2, 3, 4 |
| Prefix sum | The running total up to a position | count subarrays with sum k |
| O(n³) | Double n, 8× the time | today's attempt 1 |
Summary
dictandsetare hash tables: lookups jump to a slot, O(1) on average;inon a list scans, O(n).- LRU cache: a plain dict evicts the first key added;
OrderedDictwithmove_to_endon every use andpopitem(last=False)evicts the least recently used, O(1). For functions,functools.lru_cache. - Keys must be hashable:
sorted(w)is a list (TypeError: unhashable type: 'list'); use"".join(sorted(w))or a tuple, withdefaultdict(list). - Longest consecutive sequence: a set, and count only from the start of a run (
x - 1missing): O(n). - Next episode: two pointers and the sliding window: a pair with a target sum, the container with the most water, and the best sum of k days in a row.