How do you recognise a familiar pattern in a new interview question?
You look at what the question is asking for and you match it to the shape of the answer you have seen before. The question asks for a set of things that have been seen, so you think of a hash set.
the clue in the question the pattern
-------------------------------- -------------------------------
have I seen this before? a hash set or a hash map
how many times does this appear? counting with a dictionary
what is the smallest ending? the tails list
what is the next bigger thing? a monotonic stack
shortest path, no weights breadth first search
the shortest path with weights Dijkstra
the smallest total for each dynamic programming
And there are four questions that you can ask yourself, in this order. What does the question want back. What is the input shape. What is the simplest thing that could do the job. And what is the constraint that rules the simple thing out.
def has_duplicates(values):
seen = set()
for value in values:
if value in seen:
return True
seen.add(value)
return False
And the constraint is what makes the difference between two questions that look the same. If the question says that the list has a million items and you have to answer in constant time, then the nested loop version is out and the hash set version is in.
And there is a fourth question that people forget. What does the question ask for at the end. A count, a list, a path, or the value itself. The answer shape often tells you the pattern straight away. If it wants the path then you probably need to keep the parents. If it wants a count then you probably need a table or a memo.
And there is one more thing that is worth knowing about. The fastest way to recognise a pattern is to have seen it recently. So the list of questions you have practised is more useful than any clever trick. The twenty questions that come up most often cover most of the interviews.
So the rule to remember is this. The input shape and the wanted output together point at the pattern.
The next two questions in this topic cover the list of patterns and the near misses.