Python practice

Python hashing practice questions

13 problems, ordered from easiest. They run in your browser, and 7 are free.

Start with Find Intersection
On this page13 sections
  1. The idea in a minute
  2. The question behind most hashing problems
  3. A search through a list is slow, a lookup is not
  4. The tool box
  5. Pattern 1: have I seen this before?
  6. Pattern 2: count, then look at the counts
  7. Pattern 3: remember where, find a partner (Two Sum)
  8. Pattern 4: group things that are the same underneath
  9. What is allowed as a key
  10. What hashing costs
  11. Questions people ask
  12. Now try it yourself
  13. More Python topics

The idea in a minute

Dictionaries and sets let you jump straight to an item instead of searching for it. Most hashing problems start out looking like a loop inside a loop, and end as one pass with a lookup.

You will see how much faster a lookup is, then use it for duplicates, counting, the famous two sum, and grouping anagrams.

The question behind most hashing problems

Picture finding a friend's number in your phone. You do not read every contact from the top. You type the name and jump straight to it. That jump is what a hash table does, and Python's dictionaries and sets are hash tables.

So the idea in one sentence: if you keep what you have already seen in a dictionary or a set, then "have I seen this before?" takes one step instead of a search through everything.

A search through a list is slow, a lookup is not

Python2,000 lookups, list against set
import time
n = 20000
as_list = list(range(n))
as_set = set(as_list)
targets = range(n - 2000, n)

t = time.perf_counter()
hits = sum(1 for x in targets if x in as_list)
list_time = time.perf_counter() - t

t = time.perf_counter()
hits2 = sum(1 for x in targets if x in as_set)
set_time = time.perf_counter() - t

print(hits, hits2, "set is faster:", set_time < list_time)
2000 2000 set is faster: True

Same answers, but x in as_list checks items one by one, up to 20,000 each time, while x in as_set jumps. I print whether the set was faster instead of the exact times, because your timings will not match mine. On any machine the set wins by a very large margin.

The tool box

ToolUse it whenLooks like
setYou only care whether something existsseen = set(); x in seen
dict (value = count)You need to countcounts[x] = counts.get(x, 0) + 1
dict (value = index or data)You need to remember where or whatseen[x] = i
dict (value = list)You need to groupgroups.setdefault(key, []).append(x)

Pattern 1: have I seen this before?

PythonContains a duplicate?
def has_duplicate(nums):
    seen = set()
    for n in nums:
        if n in seen:
            return True
        seen.add(n)
    return False

print(has_duplicate([3, 1, 4, 1, 5]))
print(has_duplicate([3, 1, 4, 5]))
True
False

One pass. For each number, check the set first, then add. The order of those two lines matters, and we will see why in a minute.

Pattern 2: count, then look at the counts

PythonWhich words appear once, and which most?
from collections import Counter
words = ["pune", "goa", "pune", "delhi", "goa", "pune"]
counts = Counter(words)
print(counts)
print([w for w, c in counts.items() if c == 1])
print(counts.most_common(1))
Counter({'pune': 3, 'goa': 2, 'delhi': 1})
['delhi']
[('pune', 3)]

Pattern 3: remember where, find a partner (Two Sum)

The famous one. Given numbers and a target, find the two numbers that add up to it. The slow way checks every pair, a loop inside a loop. The hash way asks, at each number: has the partner I need already gone past?

Watch the lookup find the pair

Step 1 / 5
1nums = [2, 7, 11, 15]
2target = 9
3seen = {}
4for i, n in enumerate(nums):
5    if target - n in seen:
6        print(seen[target - n], i)
7        break
8    seen[n] = i
What the loop knows
seen = {}
Line 3
seen will remember each number and where it was. Looking a key up in a dictionary takes one step.
PythonFind a pair that adds up to the target
nums = [2, 7, 11, 15]
target = 9
seen = {}
for i, n in enumerate(nums):
    if target - n in seen:
        print(seen[target - n], i)
        break
    seen[n] = i
0 1

For each number we work out the partner we need (target - n) and check if we saw it earlier. If yes, we are done. If not, we remember this number and its position for later ones to find. We stored n as the key and its index as the value because the answer needs positions.

PythonEdge cases: a repeated number, no answer, one number
def two_sum(nums, target):
    seen = {}
    for i, n in enumerate(nums):
        if target - n in seen:
            return [seen[target - n], i]
        seen[n] = i
    return None

print(two_sum([3, 3], 6))
print(two_sum([1, 2, 3], 10))
print(two_sum([5], 10))
[0, 1]
None
None
Watch outCheck before you store

We look in seen before adding the current number. If we added first, the number could pair with itself: with nums = [5] and target 10, it would wrongly answer 'found'. [3, 3] still works because the second 3 finds the first.

Pattern 4: group things that are the same underneath

Group words that are anagrams of each other. Two words are anagrams if their sorted letters match, so the sorted letters make a good key. The key has to be something that cannot change, so we turn the sorted letters into a tuple (or a string).

PythonGroup anagrams
words = ["listen", "silent", "enlist", "google", "gogole", "cat", "act"]
groups = {}
for w in words:
    key = "".join(sorted(w))
    groups.setdefault(key, []).append(w)
print(list(groups.values()))
[['listen', 'silent', 'enlist'], ['google', 'gogole'], ['cat', 'act']]

What is allowed as a key

A hash table has to turn the key into a number and get the same number every time. That is why a list cannot be a key (it can change), while a tuple or string can.

PythonCoordinates as tuples
visited = set()
visited.add((2, 3))
print((2, 3) in visited, (3, 2) in visited)
try:
    visited.add([2, 3])
except TypeError as e:
    print("TypeError:", e)
True False
TypeError: unhashable type: 'list'

What hashing costs

  • Memory. You are trading space for speed, because the dictionary or set holds everything you have seen.
  • Order. Sets have no positions, so you cannot ask for the third item.
  • Collisions are rare and Python handles them, you do not need to worry about them in problems.
  • If the input is already sorted, two pointers may do the same job with no extra memory.

Questions people ask

Is a lookup in a dictionary really one step?

On average, yes. That is why people say O(1). In the very rare worst case it can be slower, but you can ignore that for interviews and everyday work.

When do I use a set and when a dict?

Set if you only ask 'is it there?'. Dict if you need to attach something to it: a count, an index, a list.

Why did my loop get faster after I added a set?

You replaced a scan of the whole list on every iteration with a direct jump. Whenever you write 'if x in some_list' inside a loop, ask if that list should be a set.

Keep this checklist handy

  • Decide what the key is and what the value is before you write the loop.
  • Add to the dictionary after you check it, or an item can match itself.
  • Keys must be hashable. Use a tuple, not a list, when a key has several parts.

Now try it yourself

13 hashing problems. They run right here in your browser, and you can start anywhere.

Stretch

Interview style. Take your time.

  1. 13A simple LRU-style access cache

Want a guided order across every topic? Open the practice sheets or the Python hub.

More Python topics