Learn about general trees in Python (not just binary trees).
# General Tree Node
class TreeNode:
def __init__(self, val):
self.val = val
self.children = []
def print_tree(root, level=0):
print(' ' * level + str(root.val))
for child in root.children:
print_tree(child, level+1)
# Build a tree
root = TreeNode('A')
root.children.append(TreeNode('B'))
root.children.append(TreeNode('C'))
root.children[0].children.append(TreeNode('D'))
root.children[0].children.append(TreeNode('E'))
root.children[1].children.append(TreeNode('F'))
print_tree(root)
# Tree traversal (DFS, BFS)
def dfs(root):
print(root.val, end=' ')
for child in root.children:
dfs(child)
def bfs(root):
from collections import deque
queue = deque([root])
while queue:
node = queue.popleft()
print(node.val, end=' ')
queue.extend(node.children)
print('DFS:')
dfs(root)
print('\nBFS:')
bfs(root)
# Find node by value
def find_node(root, value):
if root.val == value:
return root
for child in root.children:
found = find_node(child, value)
if found:
return found
return None
print('\nFind E:', find_node(root, 'E').val)
Understand hashmaps in Python using the built-in dict and defaultdict.
# Hashmap with dict
hm = {'a': 1, 'b': 2}
hm['c'] = 3
print(hm)
print(hm.get('d', 'not found'))
# defaultdict
from collections import defaultdict
dd = defaultdict(list)
dd['x'].append(1)
dd['x'].append(2)
print(dd)
# Iteration
for k, v in hm.items():
print(k, v)
# Counter
from collections import Counter
cnt = Counter('banana')
print(cnt)
# Dict comprehension
squares = {x: x**2 for x in range(5)}
print(squares)
# Nested dicts
nested = {'outer': {'inner': 42}}
print(nested['outer']['inner'])
Learn about hashtables and how Python's dict is implemented as a hashtable.
# Custom hashtable (simple)
class HashTable:
def __init__(self, size=10):
self.size = size
self.table = [[] for _ in range(size)]
def _hash(self, key):
return hash(key) % self.size
def set(self, key, value):
idx = self._hash(key)
for i, (k, v) in enumerate(self.table[idx]):
if k == key:
self.table[idx][i] = (key, value)
return
self.table[idx].append((key, value))
def get(self, key):
idx = self._hash(key)
for k, v in self.table[idx]:
if k == key:
return v
return None
def remove(self, key):
idx = self._hash(key)
for i, (k, v) in enumerate(self.table[idx]):
if k == key:
del self.table[idx][i]
return True
return False
ht = HashTable()
ht.set('a', 1)
ht.set('b', 2)
print(ht.get('a'))
print(ht.get('b'))
print(ht.get('c'))
ht.remove('a')
print(ht.get('a'))
Explore heaps in Python using the heapq module.
import heapq
# Min heap
h = []
heapq.heappush(h, 3)
heapq.heappush(h, 1)
heapq.heappush(h, 2)
print(heapq.heappop(h))
print(h)
# Max heap (invert values)
h = []
for val in [3, 1, 2]:
heapq.heappush(h, -val)
print(-heapq.heappop(h))
print(h)
# Heapify
nums = [5, 2, 8, 1]
heapq.heapify(nums)
print(nums)
# Priority queue with tuples
pq = []
heapq.heappush(pq, (2, 'task2'))
heapq.heappush(pq, (1, 'task1'))
heapq.heappush(pq, (3, 'task3'))
while pq:
print(heapq.heappop(pq))
# K largest/smallest
nums = [5, 2, 8, 1, 9, 3]
print(heapq.nlargest(3, nums))
print(heapq.nsmallest(2, nums))
Learn about graphs in Python: adjacency list, adjacency matrix, and traversals.
# Adjacency list
graph = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'D'],
'D': ['B', 'C']
}
print(graph)
# BFS
from collections import deque
def bfs(graph, start):
visited = set([start])
queue = deque([start])
while queue:
node = queue.popleft()
print(node, end=' ')
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
print('BFS:')
bfs(graph, 'A')
# DFS
def dfs(graph, node, visited=None):
if visited is None:
visited = set()
visited.add(node)
print(node, end=' ')
for neighbor in graph[node]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
print('\nDFS:')
dfs(graph, 'A')
# Adjacency matrix
matrix = [
[0,1,1,0],
[1,0,0,1],
[1,0,0,1],
[0,1,1,0]
]
print('\nAdjacency Matrix:')
for row in matrix:
print(row)
# Graph class with add/remove
class Graph:
def __init__(self):
self.adj = {}
def add_vertex(self, v):
if v not in self.adj:
self.adj[v] = []
def add_edge(self, u, v):
self.add_vertex(u)
self.add_vertex(v)
self.adj[u].append(v)
self.adj[v].append(u)
def remove_edge(self, u, v):
if v in self.adj.get(u, []):
self.adj[u].remove(v)
if u in self.adj.get(v, []):
self.adj[v].remove(u)
def remove_vertex(self, v):
for u in self.adj.get(v, []):
self.adj[u].remove(v)
self.adj.pop(v, None)
def __str__(self):
return str(self.adj)
g = Graph()
g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('B', 'D')
print('\nGraph class:')
print(g)