🧠 Algorithms & Problem Solving, lesson 6 of 6
Classic problems
Two-sum, palindromes, anagrams, stacks and queues: patterns worth knowing.
12 min
2 exercises
2 quizzes
0/4 solved
Getting Python ready… examples can run in a moment.
Some problems appear again and again, in coding interviews and in real programs. Each has a neat trick.
Two-sum: given numbers and a target, find two that
add up to it. Checking every pair is O(n²). Better:
walk once and remember each number's index in a dict.
For each x, is target - x already there?
Two-sum with a dict
One pass, O(n). Add a print(i, x, seen) inside the
loop to watch the dict fill up.
Palindromes read the same backwards: "racecar",
"Never odd or even". Clean the text first (lowercase,
letters and digits only), then compare it with its
reverse s[::-1], or walk two pointers inwards.
Palindromes two ways
The pointer version can stop at the first mismatch and needs no reversed copy. Try "A man, a plan, a canal: Panama".
What does this print?
Anagrams use exactly the same letters: "listen" and
"silent". Compare sorted(a) == sorted(b), or compare
letter counts with Counter. To group anagrams,
use the sorted letters as a dict key.
Grouping anagrams
Add "tab" to the list. Which group does it join?
Anagram checker
Write are_anagrams(a, b) that ignores case and
spaces: "Dormitory" and "Dirty room" are anagrams.
Watch out: "aab" and "abb" use the same letters but
not the same counts.
Stacks and queues. A stack is last-in,
first-out (LIFO), like a pile of plates: a list with
append and pop. A queue is first-in,
first-out (FIFO), like a line at a shop: a deque
with append and popleft.
Stacks power undo buttons, the browser back button and bracket matching.
Undo stack, service queue
The stack undoes the newest action first; the queue serves the oldest customer first.
What does this print?
Balanced brackets
Write is_balanced(text): True if every (,
[ and { is closed by the matching bracket in the
right order. Ignore all other characters. Use a stack:
- opening bracket → push it
- closing bracket → the top of the stack must be its partner (pop it)
- at the end, the stack must be empty