Coding Flashcards
Kahn’s Algorithm
Ideal for problems where you need to find a linear ordering of tasks or nodes with dependencies like task scheduling, resolving package dependencies in software, or course prerequisites. It is especially useful for finding the topological sort (ordering) of a directed acyclic graph.
Uses concept of “Indegree” which is the number of edges directed into a node.
Process:
1. Compute Indegrees (with nodes that have 0 indegrees, appearing first in the topological order).
2. Initialize Queue: Put all nodes with zero in degree into queue.
3. Process the Queue: - remove a node from front of queue, and add it to the topological order, - reduce each neighbor by 1 degree - If any indegree becomes zero, add to queue.
4. Repeat until queue is empty.
5. check for cycles. If nodes in sort are less than graph, means cycle and there is no valid order.
O(V + E)
String Operations
from datetime import datetime
Date to string: date.strftime(‘%Y-%m-%d’)
String to date: datetime.strptime(D, ‘%Y-%m-%d’)
Instatiate Stack and Queue
LIFO vs FIFO
~~~
from collections import deque
stack = deque()
stack.append(1)
stack.append(2)
stack.pop()
= 2
queue = deque()
queue.append(1)
queue.append(2)
queue.popleft()
= 1
~~~
Graph / Dictionary Initializaiton
from collections import from collections import defaultdict
graph = defaultdict(list)
for i in range(1, 4):
graph['A'].append(i)
for i in range(4, 7):
graph['B'].append(i)
{
'A' = [1,2,3]
'B' = [4,5,6]
}
`
What is DFS?
Graph traversal algorithm that starts at a source node and explores as far as possible along each branch before backtracking.
How?
- Uses a stack to remember nodes for backtracking
- Can be implemented recursively or iterativley (using stack).
When?
- to explore all possible paths
- to traverse or explore deeply before visiting sibling nodes (for maze solving, or cycle detection)
Recursive:
def dfs(graph, node, visited):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
Iterative:
def dfs(graph, start):
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visitied:
stack.append(neighbor)
return visited
Complexity: O(V + E)
What is BFS?
BS is a graph traversal algorithm that explores all the nodes at the present depth level before movign on to the nodes at the next depth level. It uses a queue to keep track of nodes to explore next. Used for unwieghted shortest path problems.
How?
- Starts at source node and explores immediate neighbors first, then moves on to the neighbors’ neighbors.
- Uses FIFO queue to keep track of which nodes to explore next.
When?
- Finding the shortest path in unweighted graphs. Exploring all nodes or levels in a graph in a breadth-wise manner.
- Checking if a graph is bipartite.
- Connected components in an unweighted graph.
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
bfs_result = []
while queue:
node = queue.popleft()
bfs_result.append(node)
if node not in visited:
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visitied:
queue.append(neighbor)
visited.add(neighbor)
return visited
Time = O(V + E) Space = O(V)
Dijsktra’s Algorithm
It is a greedy algorithm used to find the shortest path from a starting node (source) to all other nodes in a graph with non-negative edge weights. It works by expanding outward from the source node, always choosing the next node with the shortest known distance.
How?
- Uses a pirority queue (min-heap) to always expand the next node with the smallest current distance.
- Each node keeps track of the shortest distance to itself from the source
- When the shortest path to a node is determiend that node is marked as “processed”
When?
- When you need the shortest path with non-negative weghts.
import heapq
def dijkstra(graph, start):
distances = {node: float(‘inf’) for node in graph}
distances[start] = 0
priority_queue = [(0, start)]
while priority_queue:
current_distance, current_node = heapq.heappop(priority_queue)
if current_distance > distances[current_node]:
continue
for neighbor, weight in graph[current_node]:
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))
return distances
Time: O((V + E) log V), Space = O(V + E) b/c needs to store distances and the graph
Bellman-Ford
Algorithm used to find the shortest path from a single source node to all other nodes in a graph. Unlike Dijkstra’s Algorithm, Bellman-Ford works with graphs that have negative edge weights
How?
- Relaxing all edges up to V-1 times (where V is the number of verticies). Key idea is that the shortest paht from the source to any node can have at most V-1 edges.
O(V * E) O(V)
In-Order Traversal
Left subtree -> Root -> Right subtree
Commonly Used for:
- Retrieving nodes of a binary search tree (BST) in sorted order
Pre-Order
Root -> Left subtree -> Right subtree
Used for:
- Tasks like copying or serializing a tree
Post-Order
Left subtree -> Right subtree-> Root
Used For:
- process or delete child nodes before their parent node
Binary Search Array
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1Binary Search Tree
def binary_search_bst(root, target):
if root is None:
return False # Target not found
if root.value == target:
return True # Target found
elif target < root.value:
return binary_search_bst(root.left, target) # Search in the left subtree
else:
return binary_search_bst(root.right, target) # Search in the right subtree
def binary_search_bst_iterative(root, target):
while root is not None:
if root.value == target:
return True
elif target < root.value:
root = root.left
else:
root = root.right
return False
O(logn)
Merge Sort
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
merged, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
merged.extend(left[i:])
merged.extend(right[j:])
return merged
O(nlogn)
