Classes & OOP

Defining classes (OOP design)

The "Helper functions," "Object equality," and "Type hints" sections all assume you can write a class — this is the foundation under them. LC design problems (caches, tries, rate limiters, iterators) are graded on clean class structure, so this matters directly for the FDE coding round.

Anatomy

class Trie:
    def __init__(self):           # constructor — runs automatically on Trie()
        self.root = TrieNode()    # instance attribute, stored on the object

    def insert(self, word):       # method — first parameter is always `self`
        node = self.root          # reach attributes through self.
        ...

• class Name: declares the type; Name() creates an instance and Python calls __init__ for you.
• __init__(self, ...) is the constructor: initialize all instance attributes here so every instance starts in a consistent state. It returns nothing.
• self is the instance the method was called on. Python makes it explicit (unlike this in Java/JS). You declare it as the first parameter but don't pass it at the call site — trie.insert(w) binds trie to self.
• Instance attributes (self.x = ...) live on the object; each instance has its own copy. This is the default home for per-object state.

Instance vs class attributes

class Counter:
    total_made = 0                # CLASS attribute — one copy shared by ALL instances
    def __init__(self, start):
        self.value = start        # INSTANCE attribute — separate per object
        Counter.total_made += 1

• Instance attribute: unique per object — the default for state.
• Class attribute: a single shared copy on the class. Fine for constants/shared config; a trap for mutable per-object state (a class-level [] or {} is shared, so every instance mutates the same one). When in doubt, set state in __init__.

Composition — classes holding other classes

The common design shape: a public container class holds instances of an internal helper class. Trie → TrieNode is the canonical example.

class TrieNode:                   # internal building block
    def __init__(self):
        self.children = {}        # {char: TrieNode} — holds more of its own kind
        self.is_end = False

class Trie:                       # public API the caller uses
    def __init__(self):
        self.root = TrieNode()

• TrieNode.children maps to more TrieNodes — a self-referential structure built entirely by composition (objects referencing objects), no inheritance required.
• The character labels the dict key (the edge), not the node — so the node stays minimal.
• This "public container + internal node" split recurs everywhere: LRU (cache holding doubly-linked-list nodes), graphs (graph holding nodes), etc.

The _private convention

Python has no enforced access control. A leading underscore is a convention meaning "internal, not part of the public contract":

class Trie:
    def insert(self, word): ...   # public API
    def _walk(self, prefix):      # internal helper — `_` signals private
        ...

Nothing stops outside code from calling _walk, but the underscore tells readers (and tooling) not to. Use it for helpers that aren't part of the class's public surface.

Interview shape

For a design problem the graded structure is: __init__ sets up state, each public operation is one short single-purpose method, internal helpers are _-prefixed. Match the method names the problem gives you exactly (insert, search, startsWith — not add/find). Inheritance and abstract base classes (ABC, @abstractmethod, super().__init__()) build on this — covered at the Cache ABC exercise.

Helper functions (nested vs class method)

Both work for tree-recursion / repeated-logic helpers. Nested is slightly more pythonic for one-off helpers; class method for shared / OOP-heavy problems.

# NESTED with CLOSURE + LIST ACCUMULATOR — no nonlocal needed (mutation)
class Solution:
    def someMethod(self, root):
        result = []                          # captured by closure
        def dfs(node):
            if not node: return
            result.append(node.val)          # in-place mutation
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        return result


# NESTED with CLOSURE + SCALAR ACCUMULATOR — needs nonlocal
class Solution:
    def someMethod(self, root):
        best = 0
        def dfs(node):
            nonlocal best                    # required to reassign outer scalar
            if not node: return 0
            l, r = dfs(node.left), dfs(node.right)
            best = max(best, l + r + node.val)
            return node.val + max(l, r)
        dfs(root)
        return best


# INNER WITH PARAMETERS — same syntax as any function
def outer():
    multiplier = 3                           # captured by closure
    def scale(x):                            # x is a normal parameter
        return x * multiplier                # uses param + captured value
    print(scale(5))                          # 15


# PARAMETERS SHADOW outer names — pure local
def outer():
    x = "outer"
    def inner(x):                            # parameter x, scoped to inner only
        print(x)                             # whatever was passed
    inner("argument")                        # "argument"
    print(x)                                 # "outer" — untouched


# RECURSIVE INNER — parameter changes per call, closure carries shared state
def outer(root):
    out = []
    def dfs(node):                           # `node` differs per call
        if not node: return
        out.append(node.val)
        dfs(node.left)
        dfs(node.right)
    dfs(root)
    return out


# CLASS METHOD ALTERNATIVE — helper as regular method on Solution
class Solution:
    def someMethod(self, root):
        return self._dfs(root)
    def _dfs(self, node):
        if not node:
            return 0
        return 1 + max(self._dfs(node.left), self._dfs(node.right))
# Underscore prefix `_dfs` is convention for "internal helper, not public API"

Object equality (== vs is, custom __eq__)

== checks equality; is checks identity (same memory address). For built-in types Python provides sensible == semantics. For user-defined classes the default == falls back to identity — same as is.

# BUILT-INS — sensible default equality (element-wise, value-based)
[1, 2, 3] == [1, 2, 3]            # True
(1, 2) == (1, 2)                  # True
{1, 2} == {2, 1}                  # True (sets are unordered)
{"a": 1} == {"a": 1}              # True
"abc" == "abc"                    # True

# USER CLASSES — default `==` is identity (same memory) unless you override
class Foo:
    def __init__(self, x):
        self.x = x

a = Foo(1)
b = Foo(1)
a == b                            # False — different objects, no __eq__ defined
a is b                            # False
a == a                            # True — same object


# CUSTOM EQUALITY — define __eq__
class Foo:
    def __init__(self, x):
        self.x = x
    def __eq__(self, other):
        return isinstance(other, Foo) and self.x == other.x
    def __hash__(self):
        return hash(self.x)       # define if you want hashability (use as dict key or in a set)

a = Foo(1)
b = Foo(1)
a == b                            # True — same x value


# LEETCODE TIP — TreeNode and ListNode (as LC provides them) have NO __eq__
# so `node1 == node2` is identity comparison. This is exactly what you want
# for LC 236 (LCA) and similar: "is this the same node as p?"

Two rules of thumb:

• For built-in containers (list, dict, set, tuple, str): == does the right thing (value comparison).
• For custom classes without __eq__: == is identity — usually what you want for "is this the same instance?" Override only when value-equality semantics are needed.
• If you override __eq__, override __hash__ too (or set it to None to make instances unhashable). Otherwise Python's data structures get inconsistent — two equal objects might hash to different buckets.

Type hints

Python is dynamically typed. Type annotations are optional and not enforced at runtime — they're purely for readability and static checkers (mypy, IDE autocomplete).

def add(a, b):                    # works, types inferred at runtime
    return a + b

def add(a: int, b: int) -> int:   # purely advisory; behavior identical
    return a + b

LC convention: keep type hints on the top-level method (LC provides them in boilerplate), drop them on helper functions to keep code tight.

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:    # hints kept
        def dfs(node):                                       # hints dropped
            if not node: return 0
            return 1 + max(dfs(node.left), dfs(node.right))
        return dfs(root)