What you will learn
- Why patterns beat memorising hundreds of problems.
- A four-question routine for recognising which pattern a problem needs.
- The hash map pattern: trade memory for O(1) lookups.
Patterns, not problems
Most interview questions are variations on about fifteen ideas. If you know the idea and the signals that point to it, an unseen problem becomes “which pattern is this, and what’s the twist?” This course teaches one pattern per lesson, each with:
- Signals: words in the problem that suggest the pattern.
- A template: the shape of the code you’ll write.
- Worked problems in Python, all run before publishing, with output shown.
- Practice links to the matching section of the DSA patterns cheat sheet, which lists problems from the Blind 75, LeetCode 150 and the DSA master sheet.
When you read a new problem, ask:
- What’s the input shape? Sorted array, string, tree, graph, intervals, grid?
- What’s asked? A count, a max/min, all combinations, yes/no, a path?
- What are the constraints? n ≤ 20 suggests exponential search; n ≤ 10⁵ needs O(n log n) or better.
- What would brute force be, and which repeated work could a pattern remove?
The hash map pattern
Signals: “find a pair/complement”, “have we seen this before?”, “count occurrences”, “group items that share a property”, and a brute force with a nested loop that only looks things up.
Idea: store what you’ve seen in a dictionary or set so each lookup is O(1) on average instead of an O(n) scan.
"""Hash map pattern: remember what you've seen to replace a nested loop."""
from collections import Counter, defaultdict
def two_sum(nums, target):
seen = {} # value -> index
for i, x in enumerate(nums):
if target - x in seen:
return [seen[target - x], i]
seen[x] = i
return None
def group_anagrams(words):
groups = defaultdict(list)
for w in words:
groups["".join(sorted(w))].append(w) # same letters -> same key
return list(groups.values())
def top_k_frequent(nums, k):
return [x for x, _ in Counter(nums).most_common(k)]
if __name__ == "__main__":
print(two_sum([3, 8, 11, 4, 6], 10))
print(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))
print(top_k_frequent([4, 1, 4, 2, 2, 4, 3], 2))
Output:
[3, 4]
[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
[4, 2]
- Two sum: for each number, ask whether its complement has been seen; store the number after checking so it can’t pair with itself. O(n) instead of O(n²).
- Group anagrams: anagrams share a canonical key (sorted letters). Choosing the right key is the whole trick in grouping problems. A 26-count tuple is an O(L) alternative to sorting.
- Top-k frequent: count with a
Counter, then select.most_common(k)uses a heap internally; the heaps lesson shows how.
Complexity note: hash operations are O(1) on average. Interviewers sometimes ask about worst cases (many collisions); mention it if relevant.
Practise: hash map problems on the cheat sheet.
Key takeaways
- Learn patterns with their signals; most problems are a known pattern plus a twist.
- Check input shape, the question, constraints and the brute force before coding.
- Hash maps turn “search for X” inside a loop into O(1) lookups.
- In grouping problems, the design decision is the key you group by.
Exercises
- Solve “contains duplicate” and “valid anagram” with a set and a counter.
- Change
two_sumto return all index pairs that sum to the target. - Rewrite
group_anagramswith a 26-letter count tuple as the key.
Quiz
- Why does
two_sumstorexonly after checking for its complement? - Which constraint suggests an exponential algorithm is acceptable?
- What is the key for grouping anagrams?
Show answers
- So an element can’t pair with itself (for example target 10 and a single 5).
- A very small n, around 20 or less.
- A canonical form shared by all anagrams: the sorted letters, or a tuple of 26 letter counts.