Programming Flashcards
What are the common ways to represent a graph?
1) Adjacency Matrix
- Common way to represent a graph as a matrix
- Square matrix where the rows and columns represent the vertices of the graph, and the entries (elements) of the matrix indicate whether there is an edge between the corresponding vertices
Example of an undirected graph with 4 vertices (A, B, C, D) and 4 edges (A-B, B-C, C-D, D-A)
A --- B
D --- C
A B C D
A 0 1 0 1
B 1 0 1 0
C 0 1 0 1
D 1 0 1 0
2) Adjacency List
- In a adjacency list, each vertex is associated with a list of its neighboring vertices directly connected to it
Example of an undirected graph with 4 vertices (A, B, C, D) and four edges
A --- B
C --- D
{
"A": ["B", "C"],
"B": ["A", "D"],
"C": ["A", "D"],
"D": ["B", "C"],
}
paths = defaultdict(list)
for edge in edges:
paths[edge[0]].append(edge[1])
paths[edge[1]].append(edge[0])
|
Graph Traversal using DFS
- DFS starts from a selected source node (or a starting point) and explores as deeply as possible along each branch before backtracking
- The algorithm visits nodes in a depth ward motion until it reaches a leaf node with no unexplored neighbors. At that point, it backtracks and explores other unexplored branches
1) Initialize
- Choose a starting node as the source node
- Create a hashset or array for marking the source node as visited
2) Visit the current node
- Process the current node (eg print or perform any other operation you need to do)
3) Recursive approach (Using Recusion)
- For each unvisited neighbor of the current node:
- Recursively call the DFS function with the neighbor as the new current node
- Mark the neighbor as visited
4) Stack-Based Approach (Using an Explicit Stack)
- Push the starting node onto the stack
- While the stack is not empty:
- Pop a node from the stack (current node)
- Process the current node (eg print or perform any other operation)
- For each unvisited neighbor:
Push onto the stack
Mark as visited
5) Backtracking
- If there are no more unvisited neighbors for the current node, backtrack by returning from the recursive function (if recursion) or popping nodes from the stack until a node with unvisited neighbors is found (if using an explicit stack)
6) Termination
- The DFS algorithm terminates when all nodes reachable from the source node have been visited
- This means that all the connected components of the graph have been explored
Graph Traversal using Breadth First Search (BFS)
- Explores a graph’s vertices (nodes) level by level
- Starts from a selected node and moves outward to visit all the nodes at the same distance from the source before moving on to nodes at the following distance
- BFS is particularly useful for finding the shortest path in unweighted graphs and for systematically exploring graphs
1) Use a queue
- BFS uses a queue to keep track of the nodes to be visited
- Follows FIFO principle
2) Initialization
- Select a source node to begin the traversal
- Create an empty queue to hold the nodes to be visited
- Mark the source node as visited and enqueue it onto the queue
3) Traversal
- While the queue is not empty:
- Dequeue a node from the from of the queue (let’s call it “current node”)
- Process the current node (print it, perform operation)
- Enqueue all the unvisited neighbors of the current node into the queue
- Mark each enqueued neighbor as visited
4) Termination
- The BFS algorithm continues until the queue becomes empty, meaning all reachable nodes from the source node have been visited
BFS Algo for Graphs
https://leetcode.com/explore/learn/card/queue-stack/231/practical-application-queue/1372/
https://algo.monster/problems/graph_bfs
Implement classic binary search
def binary_search(arr: List[int], target: int) -> int:
l, r = 0, len(arr) - 1
index = -1
while l <= r:
mid = (l + r) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
l = mid + 1
else:
r = mid - 1
return index
- Time complexity: O(log n)
- Space complexity: O(1)
- A monotonic function is a function that is either non-decreasing or non-increasing. Given x1 and x2 where x1 > x2, we should have f(x1) >= f(x2)
- The precondition for binary search is to find a monotonic function f(x) that returns either True or False
- We will call the function “feasible” to signify whether the element at the current index is feasible (True) or not (False) to meet the problem constraints
def binary_search(arr: List[int], target: int) -> int:
left, right = 0, len(arr) - 1
first_true_index = -1
while left <= right:
mid = (left + right) // 2
if feasible(mid):
first_true_index = mid
right = mid - 1
else:
left = mid + 1
return first_true_index
Recursion
What makes a function properly recursive?
1. Base case/exit.
2. Recursive call. Calling the function with different arguments in order to break the problem down to its fundamental parts
- Function calls push a frame object onto the stack, returning pops them off
- At every step of the return journey, the returned value is computed against the state of each frame!
- each frame has its own state and that that state persists while it waits for the return to occur
Frame: Whenever a function is called, a new frame is opened in which the function performs its computation. Once the computation is finished, the results are returned to the calling function and the frame, along with the function and its contents, is discarded.
Strategy for recursion
- What’s the simplest possible input
- Play around w/ examples and visualize
- Generalize the pattern
- Write code by combining recursive pattern with base case
Full, Complete, and Perfect Binary Trees
Full Binary Tree
- Every node has 0 or 2 children
Complete Binary Tree
- All levels are completely filled except possibly the last level and all nodes in the last level are as far left as possible
Perfect binary tree
- All nodes have 2 children and all leaf nodes have the same level
Binary Search Tree
A special type of binary tree in which every node follows the ordering property
all left descendants < node < all right descendants
Balanced Binary Tree
Every node in a balanced binary tree fulfills the condition:
- The height difference of the left and right subtree of the node is not more than 1
Pre-order Traversal
- Visit the current node first
- Then the left subtree
- Finally the right subtree
def preorder(root: Node | None) -> list[int]:
result = []
def dfs(node: Node | None) -> None:
if not node:
return
result.append(node.val)
dfs(node.left)
dfs(node.right)
dfs(root)
return result
In-order Traversal
- Visit the left subtree
- Then the current node
- Finally the right subtree
def in_order_traversal_bst(tree: Node | None) -> list[int]:
"""
Given a binary search tree, return the in-order traversal of its nodes' values.
"""
res = []
def dfs(tree):
if not tree:
return
dfs(tree.left)
res.append(tree.val)
dfs(tree.right)
dfs(tree)
return res
Post-order Traversal
- Visit the left subtree
- Then the right subtree
- Finally the current node
def postorder(root: Node | None) -> list[int]:
"""
Processes the root/node after its subtrees
"""
result = []
def dfs(node: Node | None) -> None:
if not node:
return
dfs(node.left)
dfs(node.right)
result.append(node.val)
dfs(root)
return result
Implement DFS Fundamental Algorithm for Finding a target within a tree
def dfs(root: Node | None, target):
# https://algo.monster/problems/dfs_intro
if root is None:
return None
if root.val == target:
return root
# return non-null return value from the recursive calls
left = dfs(root.left, target)
if left is not None:
return left
# at this point, we know left is null, and right could be null or non-null
# we return right child's recursive call result directly because
# - if it's non-null we should return it
# - if it's null, then both left and right are null, we want to return null
return dfs(root.right, target)
# FYI, can also be simplified to
#return dfs(root.left, target) or dfs(root.right, target)
