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

"""
Explanation: Apple Stocks
Suppose we can access yesterday's stock prices as a list where:
1. The indices are the time in minutes past trade opening time, which was 09:30am 
2. The values are the price in dollars of Apple stock at the time
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. 
```python
stock_prices_yesterday = [10, 7, 5, 8, 11, 9]
get_max_profit(stock_prices_yesterday)
returns 6 (buying for $5 and selling $11)
```
My Mistakes

Didn't deal with length of less then 2 Didn't deal with edge case of decreasing numbers Didn't skip the first element Unnessearily kept the high score Naming could be more descriptive
In general their solution cuts out a lot and focuses more on keeping track of max_profit instead of the pieces needed to compute it, like my solution.
End of explanation
"""


# 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]

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]

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]

"""
Explanation: Cake Thief
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. 
0/1 Knapsack Problem
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
End of explanation
"""


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

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

"""
Explanation: Fibonacci
End of explanation
"""


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

"""
Explanation: Inflight Entertainment
Write a function that takes a list of movie times and an integer equal to the length of the flight and returns a boolean indicating whether there is are two numbers in movie_lengths whose sum equals flight_length.
Do not count the same movie twice.
End of explanation
"""


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'


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

"""
Explanation: Million Gazillion Engine
There is a crawler that keeps a list of all the websites that it visits, now the crawler has been growing for some time- how do we trim the amount of space taken up by visited?
End of explanation
"""


# 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
    

"""
Explanation: Find Rotation Point
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.
End of explanation
"""


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

"""
Explanation: Second largest item binary tree
Get the second largest item in a binary tree
Mistakes
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. 

Forgot to acknowledge that the second largest item isn't necessarily the parent of the largest item, the rightmost item can have a subtree with a value greater than the leftmosts' parent.
End of explanation
"""


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')
                

"""
Explanation: Parenthesis Matching
Usually we would use a stack for storing questions like this.
End of explanation
"""


