algorithms
Repeatedly compares and swaps adjacent element
bubble sort
python: outputing hello world
console.log("Hello, World!")
print("Hello, World!")
arr = [i for i in range(int(input()))]
for item in arr:
print(item)
O(n)
guy who made computer or something, something about windows
bill gates
x = 5
y = 3
print(x + y)
8
Divides the array into halves, sorts them, and combines them
merge sort
def greet(name):
if name == "Alice"
print("Hello, Alice!")
else
print("Hello, stranger!")
where are the colons: 💀💀💀💀💀💀💀💀
def find_pairs(arr, target):
pairs = []
for i in range(len(arr)):
for j in range(i + 1, len(arr)):
if arr[i] + arr[j] == target:
pairs.append((arr[i], arr[j]))
return pairs
o(n^2)
amazon guy
jeff bezos
def mystery(a, b=2, c=3):
return a + b * c
result = mystery(4, c=5)
print(result)
14
Uses a pivot to partition the array into smaller subarrays
quick sort
def divide_numbers(a, b):
try:
result = a / b
except valueError as e:
print("An error occurred:", e)
return result
ValueError
def maga_sort(arr): #CHATGPT
if len(arr) > 1:
# Find the middle point and divide the array
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
# Recursively sort both halves
merge_sort(left_half)
merge_sort(right_half)
# Merge the sorted halves
i = j = k = 0
# Copy data to temp arrays left_half and right_half
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
arr[k] = left_half[i]
i += 1
else:
arr[k] = right_half[j]
j += 1
k += 1
# Check if any element was left
while i < len(left_half):
arr[k] = left_half[i]
i += 1
k += 1
while j < len(right_half):
arr[k] = right_half[j]
j += 1
k += 1
o(nlog(n))
guy who made the shortest path problem
Dijkstra
def func(x, y=[]):
y.append(x)
return y
a = func(1)
b = func(2, [])
c = func(3, b)
print(a)
print(b)
print(c)
[1]
[2]
[3, 2]
Builds a minimum spanning tree starting from a node
Prim's algorithm
arr = [int(input()) for i in range(int(input()))]
arr = sorted(arr, lambda x: x[0])
print(arr)
for item in arr:
item += 1
print(arr)
for i in range(len(list(map(str, arr)))):
arr[i] = arr[i] >> 1
print(arr)
you can't take an index of a number
import math
def matrix_chain_multiplication_with_exponentiation(p):
n = len(p) - 1 # Number of matrices
dp = [[0] * n for _ in range(n)]
for chain_len in range(2, n + 1): # chain_len is the length of the chain
for i in range(n - chain_len + 1):
j = i + chain_len - 1
dp[i][j] = math.inf # Start with a large number (infinity)
for k in range(i, j):
q = dp[i][k] + dp[k + 1][j] + p[i] * p[k + 1] * p[j + 1]
q += p[k + 1] * p[k + 1] # Exponentiation cost for matrix A_k
if q < dp[i][j]:
dp[i][j] = q
return dp[0][n - 1]
O(n^2) or O(n^3)
guy who solved the shortest path problem but there are negative numbers for some reason
Richard Bellman and Lester Ford Jr the robbers of Alfonso Shimbel
def outer(x):
def inner(y):
nonlocal x
x += y
return x
return inner
a = outer(5)
b = outer(10)
result1 = a(3)
result2 = a(4)
result3 = b(2)
result4 = a(1)
print(result1)
print(result2)
print(result3)
print(result4)
8
12
12
13
Combines heuristics and pathfinding for optimal shortest path
A*
def process_data(data):
result = [] # return results
for i in range(len(data)): # loop for each element
if isinstance(data[i], int): # if number
result.append(data[i] * 2) # double
elif isinstance(data[i], str): # if str
result.append(data[i].upper()) #capitalize
else: # else add
result.append(data[i])
return result # give back results
doesn't consider edge case float
from itertools import combinations
def find_tetrahedral_routes(n, m, roads, T):
# Initialize the adjacency matrix with high values to represent no road between cities
INF = float('inf')
adj_matrix = [[INF] * n for _ in range(n)]
# Fill the adjacency matrix with the given roads and their costs
for u, v, c in roads:
adj_matrix[u-1][v-1] = c
adj_matrix[v-1][u-1] = c
# To store the count of valid Tetrahedral Routes and their total cost
valid_routes_count = 0
total_cost = 0
# Iterate through all combinations of 4 cities
for cities in combinations(range(n), 4):
a, b, c, d = cities
# Check if all pairs of cities are connected (forming a complete subgraph)
road_costs = [
adj_matrix[a][b], adj_matrix[a][c], adj_matrix[a][d],
adj_matrix[b][c], adj_matrix[b][d], adj_matrix[c][d]
]
# If any of the roads do not exist (cost is INF), skip this combination
if any(cost == INF for cost in road_costs):
continue
# Calculate the total cost of the roads in this Tetrahedral Route
total_route_cost = sum(road_costs)
# If the cost is less than or equal to the threshold, it's a valid route
if total_route_cost <= T:
valid_routes_count += 1
total_cost += total_route_cost
return valid_routes_count, total_cost
# Example usage:
n = 6 # Number of cities
m = 9 # Number of roads
roads = [
(1, 2, 1), (1, 3, 2), (1, 4, 3), (1, 5, 4), (1, 6, 5),
(2, 3, 1), (2, 4, 2), (2, 5, 3), (2, 6, 4),
]
T = 10 # Threshold cost for Tetrahedral Routes
valid_routes_count, total_cost = find_tetrahedral_routes(n, m, roads, T)
print(valid_routes_count, total_cost)
O(n^2) or O(n^4)
Developed the onboard flight software for NASA's Apollo missions.
Margaret Hamilton
def decorator(func):
def wrapper(*args, **kwargs):
result = func(*args, **kwargs)
return result * 2
return wrapper
@decorator
def multiply(a, b):
return a * b
@decorator
def add(a, b):
return a + b
result1 = multiply(2, 3)
result2 = add(2, 3)
result3 = multiply(result1, result2)
result4 = add(result1, result2)
print(result1)
print(result2)
print(result3)
print(result4)
12
10
240
44