Suppose we can access yesterday's stock prices as a list where:
So stock_price_yesterday[60] = 500
Write a program that takes stock_prices_yesterday and returns the best profit I could have made from 1 purchase and 1 sale of 1 Apple stock yesterday.
stock_prices_yesterday = [10, 7, 5, 8, 11, 9]
get_max_profit(stock_prices_yesterday)
returns 6 (buying for $5 and selling $11)
In [ ]:
def get_max_profit(stock_prices_yesterday):
if len(stock_prices_yesterday) < 2
raise IndexError('Getting a profit requires at least 2 prices')
min_price = stock_prices_yesterday[0]
max_profit = stock_prices_yesterday[1] - stock_prices_yesterday[0]
for index, current_price in enumerate(stock_prices_yesterday):
if index == 0;
continue
potential_profit = current_price - min_price
max_profit = max(max_profit, potential_profit)
min_price = min(min_price, current_price)
return max_profit
The queen has cakes you want to steal. She has two types but unlimited quantities of each. You have a limited size bag, how do you decide how many and which cakes to steal. This is a knapsack problem. But how do we solve it.
Given a set of tuples, find where the amount of their value is maximum and the sum of their weight is equal to some total weight amount. O/1 knapsack problem means you cannot split the item.
si pounds vi dollars
knapsack carries at most s pounds
There are two ways to solve this, graphs and dynamic programming. We can imagine this like the games, we have a series of graphs, and decisions, and states. We have to keep track of our state: capacity, total weight of items taken so far.
In the graph we can represent the node and edges where nodes are the item I am looking at and the total weight and the edges are the weight of an additional item.
In the graph representaiton you build the graph and then pass it to a minnimum path (spanning tree) algorithim.
Time complexity: O(nW) where n is the number of items and Wis the capacity of knapsack
In [ ]:
# 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
max_values_at_capacities = [0]*(weight_capacity + 1)
for current_capacity in xrange(weight_capacity + 1):
current_max_value = 0
for cake_weight, cake_value in cake_tuples:
if (cake_weight <= current_capacity):
max_value_using_cake = cake_value + max_values_at_capacities[current_capacity - cake_weight]
current_max_value = max(max_value_using_cake, current_max_value)
max_values_at_capacities[current_capacity] = current_max_value
return max_values_at_capacities[weight_capacity]
In [ ]:
value = [60, 100, 120]
weight = [10, 20, 30]
capacity = [50]
n = len(value)
def knapSack(capacity, weight, value, n):
K = [[0 for x in range(capacity+1)] for x in range(n+1)]
for i in range(n+1):
for wt in range(capacity + 1):
if i == 0 or capacity == 0:
K[i][wt] = 0
elif weight[i-1] <= wt:
K[i][wt] = max(value[i-1] + K[i-1][wt-weight[i-1]], K[i-1][wt])
else:
K[i][wt] = K[i-1][wt]
return K[n][W]
In [ ]:
value = [60, 100, 120]
weight = [10, 20, 30]
capacity = [50]
n = len(value)
def knapSack(capacity, weight, value, n):
K = [[0 for x in range(capacity+1)] for x in range(n+1)]
for i in range(n+1):
for wt in range(capacity + 1):
if i == 0 or capacity == 0:
K[i][wt] = 0
elif weight[i-1] <= wt:
K[i][wt] = max(value[i-1] + K[i-1][wt-weight[i-1]], K[i-1][wt])
else:
K[i][wt] = K[i-1][wt]
return K[n][W]
In [ ]:
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
In [ ]:
def fib(n):
if n < 0:
raise Exception("Index was negative. Cannot have a negaitve index in a series")
if n < 2:
return n
prev_prev = 0
prev = 1
for _ in xrange(n-1):
current = prev + prev_prev
prev_ prev = prev
prev = current
return current
In [ ]:
def inflight_entertainment(movie_lengths, flight_length):
movie_lengths_seen = set()
for first_movie_length in movie_lengths:
matching_second_movie_length = flight_length - first_movie_length
if matching_second_movie_length in movie_length_seen:
return True
movie_lengths_seen.add(first_movie_length)
return False
In [ ]:
I know the answer to this problem is a trie, but I don't really know how to implement a trie - and this is the problem- I'm pulling a cheap time move an just looking ahead to the answer.
You could also use a bloom filter for this answer, with run-length encoding.
### Keys to a Trie
Implement as a highly nested hash map, you can use other things, nodes, or pointers
Use a \* character to represent 'end of entry'
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
I flipped through a dictionary, starting from the middle and picked out words that I didn't know. I added those words to a list and continued until I hit the end of the book. Then I started at the beginning of the dictionary and started from there. Now I have a mostly alphabetical list except that there is a rotation point where it flips, find this rotaiton point.
In [ ]:
# So this clearly looks like a binary search problem except
# I still find myself a little lost as too how to implement
# these, so lets do that tomorrow morning
def find_rotation_point(words):
first_word = words[0]
floor_index = 0
ceiling_index = len(words) -1
while floor_index < ceiling_index:
guess_index = floor_index + ((ceiling_index - floor_index) / 2)
if words[guess_index] >= first_word:
floor_index = guess_index
else:
ceiling_index = guess_index
if floor_index + 1 == ceiling_index:
return ceiling_index
Get the second largest item in a binary tree
First, need to practice tree traversals - dijkstra and a few others are simple ways to do this.
I had a good start. The part I missed was where the second largest element can be the rightmost element of a left subtree rather than the rightmost element. Otherwise I have to get confortable writing tree traversals.
In [ ]:
def find_largest(root_node):
current = root_node
while current:
if not current.right:
return current.value
current = current.right
def find_second_largest(root_node):
if root_node is None or \
(root_node.left is None and root_node.right is None):
raise Exception('Tree must have at least 2 nodes')
current = root_node
while current:
if current.left and not current.right:
return find_largest(current.left)
if current.right and \
not current.right.left and \
not current.right.right:
return current.value
current = current.right
In [ ]:
def get_closing_paren(sentence, opening_paren_index):
open_nested_parens = 0
position = opening_paren_index + 1
while position <= len(sentence) -1:
char = sentence[position]
if char == '(':
open_nested_parens += 1
elif char == ')':
if open_nested_parens == 0:
return position
else:
open_nested_parens -= 1
position += 1
raise Exception('No closing parenthesis')