What’s one thing you learned? What’s still confusing?
Heaps, Priority Queues & Graphs
Min/max heaps, heapq, Dijkstra, topological sort, Union-Find.
Testing with pytest: Beyond Basic assert
Parametrize, fixtures, pytest.raises, and pytest-cov.
Building APIs with FastAPI
REST APIs with FastAPI, Pydantic validation, serving ML models, testing endpoints.
Interactive Labs for This Track
Loop Visualizer
You're a factory robot repeating the same task on an assembly line — watch how loops automate repetitive work
List Slicing
You have a playlist of 50 songs — grab just tracks 10 through 20 with a single slice expression
Sorting Algorithms
You're organizing a library of 10,000 books — which sorting method is fastest?
Ask questions, share insights
delete has three distinct cases (the third is famously hairy). is_valid_bst has a cross-level bug that catches even senior engineers. Self-balancing trees (AVL, Red-Black) are what make sortedcontainers.SortedList and std::map reliable. The Trie powers every autocomplete you've ever typed into. Expression trees evaluated by postorder are the canonical use of postorder traversal.Delete has three cases that must be handled in order:
from __future__ import annotations
from typing import Any, Optional, Tuple
class BSTNode:
def __init__(self, val: Any) -> None:
self.val = val
self.left: Optional[BSTNode] = None
self.right: Optional[BSTNode] = None
class BST:
def __init__(self) -> None:
self.root: Optional[BSTNode] = None
self._size: int = 0
# (insert/search/min from Part 1 omitted for brevity)
def _min_node(self, node: BSTNode) -> BSTNode:
"""Helper: return the node with minimum value in a subtree."""
while node.left is not None:
node = node.left
return node
def delete(self, val: Any) -> None:
"""
Delete val from the BST. Three cases:
1. Node is a leaf → just remove it
2. Node has ONE child → replace node with that child
3. Node has TWO children → replace with inorder successor (smallest
value in right subtree), then delete the inorder successor
O(h).
"""
self.root, deleted = self._delete_recursive(self.root, val)
if deleted:
self._size -= 1
def _delete_recursive(
self, node: Optional[BSTNode], val: Any
) -> Tuple[Optional[BSTNode], bool]:
"""Returns (new_subtree_root, was_deleted)."""
if node is None:
return None, False # value not found
deleted = False
if val < node.val:
node.left, deleted = self._delete_recursive(node.left, val)
elif val > node.val:
node.right, deleted = self._delete_recursive(node.right, val)
else:
# Found the node to delete
deleted = True
# Case 1: Leaf node — just remove it
if node.left is None and node.right is None:
return None, True
# Case 2a: Only right child exists — replace with right child
if node.left is None:
return node.right, True
# Case 2b: Only left child exists — replace with left child
if node.right is None:
return node.left, True
# Case 3: Two children
# Find the INORDER SUCCESSOR: smallest value in the right subtree
# Why inorder successor? It is the next largest value — maintains BST property
successor = self._min_node(node.right)
node.val = successor.val # copy successor's value into current node
# Delete the successor from the right subtree
node.right, _ = self._delete_recursive(node.right, successor.val)
return node, deletedWhen you delete a node with two children, you need a replacement that keeps the BST property: greater than everything in the left subtree, less than everything in the right subtree. The two valid choices are:
std::set C++ implementations alternate between successor and predecessor as a balance heuristic.)Inorder successor of 5 = 6 (smallest in right subtree). Copy 6's value into the deleted node's position. Delete the original 6 node from the right subtree — which falls into Case 1 (leaf) or Case 2 (one child).
is_valid_bst checks only parent vs immediate child — and it gives the wrong answer on subtly invalid trees.max_val tightens when you go left, min_val tightens when you go right.def kth_smallest(self, k: int) -> Any:
"""
Return the k-th smallest element (1-indexed).
Uses inorder traversal — stops early after k nodes.
O(h + k) time, O(h) space for the call stack.
"""
count = [0]
result = [None]
def _inorder(node):
if node is None or count[0] >= k:
return
_inorder(node.left)
count[0] += 1
if count[0] == k:
result[0] = node.val
return
_inorder(node.right)
_inorder(self.root)
if result[0] is None:
raise ValueError(f"k={k} is out of range")
return result[0]The trick: inorder visits values in sorted order, so the k-th visited node is the k-th smallest. Use a counter and short-circuit when you hit k.
balance_factor(node) = height(node.left) - height(node.right)
# Must be in {-1, 0, +1} for AVL property to hold.
# +1: left-heavy | 0: balanced | -1: right-heavy
| Case | Detection | Fix |
|---|---|---|
| Left-Left (LL) | New node added to left child's left subtree | rotate_right(node) |
| Left-Right (LR) | New node added to left child's right subtree | rotate_left(node.left) then rotate_right(node) |
| Right-Right (RR) | New node added to right child's right subtree | rotate_left(node) |
| Right-Left (RL) | New node added to right child's left subtree | rotate_right(node.right) then rotate_left(node) |
Inserting 1, 2, 3 into an AVL tree:
rotate_left(1):| Criteria | AVL | Red-Black |
|---|---|---|
| Balance strictness | Stricter (|BF| ≤ 1) | Looser (black-height balance) |
| Lookup speed | Faster (shorter height) | Slightly slower |
| Insert/delete | More rotations | Fewer rotations |
| Use case | Read-heavy workloads | Write-heavy (Linux kernel, Java TreeMap) |
sortedcontainers.SortedListsortedcontainers.SortedList, which uses a B-tree variant in C-level data structures:from sortedcontainers import SortedList
sl = SortedList()
sl.add(5); sl.add(3); sl.add(7); sl.add(1)
print(list(sl)) # [1, 3, 5, 7] — always sorted
print(sl.bisect_left(4)) # 2 — O(log n) binary search
sl.discard(3) # O(log n) delete
print(sl.count(5)) # 1 — O(log n)SortedList whenever you need guaranteed O(log n) sorted-structure operations in production Python. Implement an AVL yourself only when interviewers ask, or when you need to customize the comparison protocol.Trie After Inserting 'cat', 'car', 'card', 'care'
from typing import List, Optional
class TrieNode:
"""A node in a Trie. Each node stores its children in a dict."""
def __init__(self) -> None:
self.children: dict[str, TrieNode] = {}
self.is_end: bool = False # True if a complete word ends here
class Trie:
"""
Prefix tree for string operations.
All operations are O(L) where L = length of the string.
Applications: autocomplete, spell-check, IP routing tables.
"""
def __init__(self) -> None:
self.root = TrieNode()
def insert(self, word: str) -> None:
"""O(L) where L = len(word)."""
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end = True
def search(self, word: str) -> bool:
"""Exact word match. Both the path AND is_end must be True. O(L)."""
node = self._traverse(word)
return node is not None and node.is_end
def starts_with(self, prefix: str) -> bool:
"""Any word starts with prefix. Only path needs to exist. O(L)."""
return self._traverse(prefix) is not None
def _traverse(self, text: str) -> Optional[TrieNode]:
node = self.root
for char in text:
if char not in node.children:
return None
node = node.children[char]
return node
def autocomplete(self, prefix: str) -> List[str]:
"""All words starting with prefix. O(L + W) where W = total chars in matches."""
node = self._traverse(prefix)
if node is None:
return []
results: List[str] = []
def dfs(current_node: TrieNode, current_word: str) -> None:
if current_node.is_end:
results.append(current_word)
for char, child in current_node.children.items():
dfs(child, current_word + char)
dfs(node, prefix)
return sorted(results)
# Demo
trie = Trie()
for word in ["cat", "car", "card", "care", "bat", "bad"]:
trie.insert(word)
print(trie.search("car")) # True
print(trie.search("ca")) # False — 'ca' is a prefix but not a complete word
print(trie.starts_with("ca")) # True
print(trie.autocomplete("ca")) # ['car', 'card', 'care', 'cat']
print(trie.autocomplete("ba")) # ['bad', 'bat']+, -, *, /). Postorder traversal naturally evaluates the tree: process both subtrees (the operands) before applying the operator.Expression Tree: (3 + 4) * (5 - 2)
3 + 4 = 7. Visit 5, 2, then compute 5 - 2 = 3. Apply *: 7 * 3 = 21.from typing import Optional
class ExprNode:
def __init__(self, value: str) -> None:
self.value = value
self.left: Optional[ExprNode] = None
self.right: Optional[ExprNode] = None
def evaluate(node: Optional[ExprNode]) -> float:
"""Evaluate an expression tree using postorder. O(n)."""
if node is None:
return 0.0
# Leaf node: it's a number
if node.left is None and node.right is None:
return float(node.value)
left_val = evaluate(node.left)
right_val = evaluate(node.right)
ops = {
"+": lambda a, b: a + b,
"-": lambda a, b: a - b,
"*": lambda a, b: a * b,
"/": lambda a, b: a / b,
}
if node.value not in ops:
raise ValueError(f"Unknown operator: {node.value}")
return ops[node.value](left_val, right_val)
# Build (3 + 4) * (5 - 2) manually
root = ExprNode("*")
root.left = ExprNode("+")
root.right = ExprNode("-")
root.left.left = ExprNode("3")
root.left.right = ExprNode("4")
root.right.left = ExprNode("5")
root.right.right = ExprNode("2")
print(evaluate(root)) # 21.0is_valid_bst requires propagated min/max bounds — checking only parent vs immediate child silently passes invalid trees with cross-level violations; this is one of the most common interview mistakessortedcontainers.SortedList rather than implementing rotations yourselfThe delete operation for a BST node with TWO children uses the 'inorder successor'. Why not use the predecessor (largest value in the left subtree) instead?