Interview Practice #interviewing #complete

maxProfit.py

#!/usr/bin/env python3

"""
I have an ordered historical list of daily prices of quizlet coin - the hot new cryptocurrency.

[100, 50, 120, 100, 300, 250, 1]


What is the best profit I could have made from 1 purchase and 1 sale of Quizlet Coin?

(No shorting, must buy before you sell)


Extensions:

    What is the best profit I could have made with unlimited purchases and sales?
    What if there is a fee of 5% to buy Quizlet Coin?
"""

def maxProfitTwoTransactions(prices):
    # Our max profit starting out is 0 since we have not purchased or sold any
    # quizlet coins, if we don't sell for a gain then max profit will remain at
    # 0.
    maxProfit = 0
    # We will be searching for the minimum price. In this case, all numbers, except
    # for infinity, are less than infinity. So if we see a smaller amount, set
    # that to the minimum price.
    minPrice = float("inf")

    # We will be either updating our minimum price or will be calculating our
    # max profit as we loop through our prices. After the min price is updated,
    # then we can sell. If we find a bigger price, since min price remains the
    # minimum, we can still easily calculate the max profit and compare it with
    # the current max price and update. This would represent holding on to a stock
    # and selling it later.
    for i in range(len(prices)):
        # If a price is lower than our current minimum price, then use this value.
        if prices[i] < minPrice:
            minPrice = prices[i]
        # Update our max profit if we can make a bigger profit.
        elif prices[i] - minPrice > maxProfit:
            maxProfit = prices[i] - minPrice

    return maxProfit

# Given example

# The max profit for this problem can be achieved by buying the quizlet coin at
# 50 and then selling at 300 for a profit of 250.
dailyPrices = [100, 50, 120, 100, 300, 250, 1]
assert maxProfitTwoTransactions(dailyPrices) == 250

# Simple test cases

# In this case, minPrice is updated to 10 for the first price, but on the second
# price, i=1 and prices[1] - minPrice is not greater than maxProfit, so it remains
# at 0.
assert maxProfitTwoTransactions([10, 10]) == 0

# Ensure a profit is returned, in this case 10-1.
assert maxProfitTwoTransactions([100, 1, 10]) == 9

# Ensure we hold on until to our coin at price 1 until we reach 1000.
assert maxProfitTwoTransactions([100, 1, 100, 1000]) == 999