SyntaxPilot
Courses/Python Coding Questions/Lesson 25
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Python Coding Questions · Lesson 25 of 30

Hashing questions

LRU cache with OrderedDictgroup anagramslongest consecutive sequence

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, so groups[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

  1. present = set(rolls): in becomes O(1), and duplicates disappear.
  2. If x - 1 is present, x is in the middle of someone else's run: skip it.
  3. 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

  1. 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.
  2. What makes an object hashable? Its hash never changes during its life (and equal objects have equal hashes). Immutable built-ins are hashable; list, dict and set are not.
  3. Can a tuple always be a key? Only if everything inside it is hashable: (1, [2]) raises TypeError: unhashable type: 'list'.
  4. 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.
  5. Plain dict vs OrderedDict today? Both keep insertion order (since Python 3.7), but only OrderedDict has move_to_end and popitem(last=False), and its == checks order.
  6. What does functools.lru_cache do? Memoises a function's results for the most recent maxsize argument combinations; cache_info() shows hits and misses. Arguments must be hashable.
  7. 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.
  8. 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²).
  9. defaultdict vs setdefault vs get? defaultdict(list) creates missing values automatically; d.setdefault(k, []) does it per call; d.get(k, 0) reads with a default without inserting.
  10. When is a list better than a set? When order or duplicates matter, or for tiny collections; but for repeated in checks, 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

  • dict and set are hash tables: lookups jump to a slot, O(1) on average; in on a list scans, O(n).
  • LRU cache: a plain dict evicts the first key added; OrderedDict with move_to_end on every use and popitem(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, with defaultdict(list).
  • Longest consecutive sequence: a set, and count only from the start of a run (x - 1 missing): 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.