Here are what we went over in the class. In addition here are the links to the MIT Course I mentioned and to my repo that has a lot more implementations of different types of algorithms and strategies.
In [9]:
def fib(n):
if n < 0:
raise Exception("Index was negative. Cannot have a negative index in a series")
if n < 2:
return n
return fib(n-1) + fib(n-2)
fib(25)
Out[9]:
In [4]:
def fib(n):
if n < 0:
raise Exception("Index was negative. Cannot have a negative index in a series")
if n < 2:
return n
pred_pred, pred = 0, 1
for _ in range(n-1):
current = pred + pred_pred
pred_pred = pred
pred = current
return current
fib(25)
Out[4]:
In [8]:
class Fibber:
def __init__(self):
self.memo = {}
def fib(self, n):
if n < 0:
raise Exception('Index was negative. No such thing as a negative index in a series')
elif n < 2:
return n;
if n in self.memo:
return self.memo[n]
result = self.fib(n-1) + self.fib(n-2)
self.memo[n] = result
return result
fibs = Fibber()
fibs.fib(25)
Out[8]:
There are two approaches to dynamic programming problems.
Guessing + recursion + memoization. Pick out a feature of the problem space that we don't know and brute force an answer. Then we recurse over the problem space until we reach the part that is relevant for our specific instance. Then we memoize. Memoization takes what is often exponential time and makes linear/polynomial.
The second is a bottom-up approach. We build a dynamic programming table until we can solve the original problem.
A child is running up a staircase with n steps and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child can run up the stairs.
Imagine a robot sitting on the upper left corner of grid with r rows and c columns. The robot can only move in two directions, right and down, but certain cells are 'off limits' such that the robot cannot step on them. Design an algorithm to find a path for the robot from the top left to the bottom right.
In [10]:
# Triple Step
class triple_step():
def __init__(self):
self.memo = {}
def triple_step(self, step):
if step < 0:
return 0
self.memo[0] = 1
if step == 0:
return self.memo[0]
self.memo[1] = 1
if step == 1:
return self.memo[1]
result = self.triple_step(step-1) + self.triple_step(step-2) + self.triple_step(step-3)
self.memo[step] = result
return result
t = triple_step()
t.triple_step(4)
Out[10]:
Given a set of tuples that represent the weight and value of different goods, cakes in our examples, find the maximum value we can get given a knapsack with a certain weight restriction. Find the point where the value is maximum and the sum of their weight is equal to the total weight allowed by the knapsack. 0/1 means you cannot split an item.
In [12]:
# a cake tuple (3, 90) weighs 3 kilograms and has a value
# of 90 pounds
cake_tuples = [(7, 160), (3, 90), (2, 15)]
capacity = 20
def max_duffel_bag_value(cake_tuples, weight_capacity):
# we make a list to hold the max possible value at every
# duffel bag weight capacity from 0 to weight_capacity
# starting each index with value 0
#initialize an array of zeroes for each capacity limit
max_values_at_capacities = [0]*(weight_capacity + 1)
for current_capacity in range(weight_capacity + 1):
current_max_value = 0
#iterate through our range of weights from 0 to capacity
for cake_weight, cake_value in cake_tuples:
if cake_weight <= current_capacity:
#check the cake would fit at all
#take the value from the current capacity - the cake weight and add to the value of this cake
max_value_using_cake = cake_value + max_values_at_capacities[current_capacity - cake_weight]
#do this for each cake, take the one that gives us the highest value
current_max_value = max(max_value_using_cake, current_max_value)
#set that max value to the current capacity
max_values_at_capacities[current_capacity] = current_max_value
return max_values_at_capacities[weight_capacity]
max_duffel_bag_value(cake_tuples, capacity)
Out[12]:
In [ ]:
def getPath(self, maze):
if len(maze) == 0 or len(maze[0]) == 0:
return None
path = []
failedPoints = set()
if self.pathFinder(maze, len(maze), len(maze[0]), path, failedPoints):
return path
return None
def pathFinder(self, maze, row, col, path, failedPoints):
if col < 0 or row < 0 or not maze[row][col]:
return False
p = (row, col)
if p in failedPoints:
return False
isAtOrigin = (row == 0) and (col == 0)
if isAtOrigin or self.pathFinder(maze, row, col-1, path, failedPoints) or self.pathFinder(maze, row-1, col, path, failedPoints):
path.append(p)
return True
failedPoints.append(p)
return False
Trees has a direct child/parent relationship and don't contain cycles. Trees are a DAG (directed acyclic graph) with the restriction that each child has one parent.
Binary Trees are a great restricted case of a graph problem that are a great way to get familiar with traversing and interacting with graph structures before jumping to something more abstract.
A binary tree is only a binary tree if an inorder traversal is a sorted list of values.
Full - Every node should have exactly 2 nodes except the leaves. The leaves have 0 children
Complete - Every level, except the last, is completely filled, and all nodes are as far left as possible. A binary tree can be complete with nodes which have a single child if it is the leftmost child.
Balanced - The left and right sides of the tree have a height difference of 1 or less.
Here are some tasks you should know how to do with binary search trees:
In [ ]:
class Node:
def __init__(self, value):
self.v = value
self.right = None
self.left= None
def checkBST(node):
return (checkBSThelper(node, -math.inf, math.inf))
def checkBSThelper(node, mini, maxi):
if node is None:
return True
if node.v < mini or node.v >= maxi:
return False
return checkBSThelper(node.left, mini, node.v) and checkBSThelper(node.right, node.v, maxi)
In [ ]:
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def checkBalanced(root):
if root is None:
return 0
left = checkBalanced(root.left)
right = checkBalanced(root.right)
if abs(left - right) > 1:
return -1
return max(left, right) + 1
There are many graph structures that are useful.
Tries- Tries are great for indexing words, alphabets, anything where you are trying to keep track of words tries are useful. The key to tries are that the letters lie along the edges of the graph and the vertices represent the word up to that point. Make sure that at the end of a word you have a special character to denote that you have reached the end of the word even if there are edges that continue towards another word.
DAG - Directed Acyclic Graphs: DAG are really good structures for represented relationships between items.
In [ ]:
class Trie:
def __init__(self):
self.root_node = {}
def check_present_and_add(self, word):
current_node = self.root_node
is_new_word = False
for char in word:
if char not in current_node:
is_new_word = True
current_node[char] = {}
current_node = current_node[char]
if "End of Word" not in current_node:
is_new_word = True
current_node["End Of Word"] = {}
return is_new_word
In [ ]:
#[2::][1::2]
import collections
words = ["baa", "", "abcd", "abca", "cab", "cad"]
def alienOrder(words):
pre, suc = collections.defaultdict(set), collections.defaultdict(set)
for pair in zip(words, words[1:]):
print(pair)
for a, b in zip(*pair):
if a != b:
suc[a].add(b)
pre[b].add(a)
break
print('succ %s' % suc)
print('pred %s' % pre)
chars = set(''.join(words))
print('chars %s' % chars)
print(set(pre))
free = chars - set(pre)
print('free %s' % free)
order = ''
while free:
a = free.pop()
order += a
for b in suc[a]:
pre[b].discard(a)
if not pre[b]:
free.add(b)
if set(order) == chars:
return order
else:
False
# return order * (set(order) == chars)
alienOrder(words)