What kind of problems do hash map questions show up in, and what is the common shape of the solution?
They show up in any problem where you have to remember what you have already seen, and the shape of the answer is almost always the same.
So what are the problems? Here are the common ones. Finding a duplicate. Finding the first letter that repeats. Counting how often things appear. Two Sum, where you want to know whether you have seen the other half of a pair. Grouping things that share a property. Finding the intersection of two lists. And the running sum, where you keep the sum of everything up to each position.
And what is the common shape? You walk through the data once, and you keep a dictionary as you go. For each item you either look something up in the dictionary, or you add something to it. And when the lookup succeeds, that is your answer.
def first_repeat(text):
counts = {}
for char in text:
counts[char] = counts.get(char, 0) + 1
if counts[char] == 2:
return char
return None
So the rule to remember is this. Whenever the question says "have I seen this before", a dictionary is the answer, and the code is always the same shape.
The next two questions in this topic look at counting and at the one case where a dictionary is slow.