1Understand
The idea
Design problems and node types are classes: __init__ sets up the state, and each method reads and updates it. Keep every piece of state on self, initialise all of it in __init__, and make each method do only its part, so the per-operation cost stays what the problem requires.
Intuition
Interview design problems and node types are small classes: __init__ creates the state, methods read and update it through self. Every piece of mutable state belongs on the instance, initialised in __init__, not as a class attribute shared by everyone.
ListNode / TreeNode are the usual shapes: a value plus pointers. Methods should each do one job so the per-operation cost matches what the problem asks for (often O(1) or O(log n)).
Forgetting self or mutating a shared class-level list are the bugs that look mysterious in a hurry.
What you will be able to do
- Define classes with __init__
- Use instance attributes and methods
- Model ListNode / TreeNode
2See it
Walkthrough
Node state on self
Build ListNode(1) → ListNode(2), fields live on the instance.
1 / 4
A class holds state. __init__ must set every field you will read later.
Instance fields are O(1) to read/write. Sharing a mutable class attribute across instances creates cross-talk bugs. Design so each public operation meets its complexity budget; if one method needs a scan, rethink the stored invariant.
Read the walkthrough as text
Min stack sketch. Support push, pop, top, get_min in O(1).
- Keep a stack of pairs
(value, min_so_far)onself, initialised empty in__init__. - On
push(val), the new min isvalif the stack is empty, elsemin(val, self.stack[-1][1]). Append(val, that_min). popdrops the top pair;topandget_minread the top value and top min.
Push 3, then 1: mins on top are 3 then 1. Pop restores min 3, no scan of the stack.
3Recognise it
Kinds of problems (3)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Node classes (ListNode, TreeNode)
Example. Build a linked list or binary tree from problem input.
How. class ListNode: __init__(self, val=0, next=None), link nodes with .next / .left / .right.
Classes with internal state
Example. Design a stack or moving average with encapsulated fields.
How. Store data on self in __init__; methods read and update that instance state.
Methods that mutate state
Example. push/pop on a custom structure used across helper calls.
How. def push(self, x): self.items.append(x), first parameter is always self.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
Forgetting self
Why it happens. A method looks like a plain function with one extra parameter.
How it fails. def push(x): self.stack.append(x), NameError or wrong binding; Python passes the instance as the first arg.
Fix. def push(self, x): ... on instance methods; @staticmethod only when self is not needed.
Mutable class attribute shared across instances
Why it happens. self.items = [] in the method body resembles __init__ assignment.
How it fails. class Node: children = [] then self.children.append(x) shares one list across all Node instances.
Fix. Initialize mutable fields in __init__: self.children = [].
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.