Lessons · Python · look it up in a dict

Remember what you have seen, in a dict

Walk the data once; store each thing you see in a dict keyed by what you will later need to look up.

Hone is a place to practise programming. This is one of its lessons, written out in full and free to read without an account.

What it is for

This one pattern solves a huge family of interview and real problems: finding pairs, matching records, deduplicating, counting, grouping. It turns 'search backwards' into 'look it up'.

How to think about it

Ask: when I am standing at item i, what would I need to know about earlier items to decide right now? Store exactly that as you go, keyed so the lookup is one step.

Worked example

logins = [("ada", 9), ("bo", 11), ("ada", 15)]

Name and hour. We want the first name that logs in twice.

seen = {}

Name to first hour.

for name, hour in logins:

One pass.

    if name in seen:

Instant check against everything earlier.

        print(name, "again at", hour); break

ada again at 15.

    seen[name] = hour

Remember for later.

Your turn

Count how many times each word appears.

counts = {}
for w in words:
    counts[w] = counts.(w, 0) + 1

The trap

Storing everything and then searching the dict with a loop. The whole point is that the key is the thing you will search by.

Practise look it up in a dict on HoneA question on it now, a coding challenge where there is one, and it is remembered for review. Free, no email needed.