Programming Problems about Stocks

LeetCod 122:  Best Time to Buy and Sell Stock II

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.empty()) return 0;
     
        int max_output = 0;
       
        int max_profit_normal = 0;
        int max_profit_sell_at_i = prices.back();
       
       
        for (int i = prices.size()-2; i >= 0; --i) {
            max_profit_normal = max(max_profit_sell_at_i - prices[i], max_profit_normal);
            max_profit_sell_at_i = max_profit_normal + prices[i];
        }
       
        return max_profit_normal;
       
    }
};


LeetCode 123:  Best Time to Buy and Sell Stock III

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).


class Solution {
public:
    int maxProfit(vector<int>& prices) {
       
        vector<int> min_prices(prices.size(), 0);
       
        int min_val = numeric_limits<int>::max();
       
        for (int i = 0; i < prices.size(); ++i) {
            min_val = min(min_val, prices[i]);
            min_prices[i] = min_val;
        }
       

       
        vector<int> max_prices(prices.size(), 0);
       
        int max_val = numeric_limits<int>::min();
       
        for (int j = prices.size()-1; j >=0; --j) {
            max_val = max(max_val, prices[j]);
            max_prices[j] = max_val;
        }
       
       
        vector<int> max_profit(prices.size(), 0);
        int max_profit_so_far = 0;
       
        for (int i = 0; i < prices.size(); ++i) {
            max_profit_so_far = max(max_profit_so_far, prices[i] - min_prices[i]);
            max_profit[i] = max_profit_so_far;
        }
       
               
        vector<int> max_profit_from_right(prices.size(), 0);
        int max_profit_so_far_from_right = 0;
       
        for  (int i = prices.size()-1; i >= 0; --i) {
            max_profit_so_far_from_right = max(
                max_profit_so_far_from_right, max_prices[i] - prices[i]);
            max_profit_from_right[i] = max_profit_so_far_from_right;
        }
       

        int output = 0;
        for (int i = 0; i < prices.size(); ++i) {
            output = max(output, max_profit[i] + max_profit_from_right[i]);
        }
       
        return output;

       
    }
};




LeetCode 309: Best Time to Buy and Sell Stock with Cooldown

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)


class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.empty()) return 0;
       
        int n = prices.size();
        vector<int> maxProfit(n, 0);
       
        for (int i = n-2; i >= 0; --i) {
           
            int maxProfit_if_buy_at_i = numeric_limits<int>::min();
           
            for (int j = i+1; j < n; ++j) {
                maxProfit_if_buy_at_i = max(maxProfit_if_buy_at_i,
                                            prices[j] - prices[i] + (j + 2 < n ? maxProfit[j + 2] : 0));
            }
           
            maxProfit[i] = max(maxProfit[i+1], maxProfit_if_buy_at_i);
        }
       
        return maxProfit[0];
       
    }
};


LeetCode 188: Best Time to Buy and Sell Stock IV

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).


class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
       
        if (prices.empty()) return 0;
       
        int ndays = prices.size();
       
       
       
        if (k >= prices.size()/2) {
            int res = 0;
            for (int i = 1; i < prices.size(); ++i)
                res += max(prices[i] - prices[i-1], 0);
            return res;
        }
       
        vector<int> B(ndays,0);
        vector<int> S(ndays,0);
       
        int max_val_B;
        int max_val_S;
       
        for (int kk = 0; kk < k; ++kk){
            //cout << "===== " << kk << " =====" << endl;
            max_val_B = numeric_limits<int>::min();
            max_val_S = numeric_limits<int>::min();
            for (int i = 0; i < ndays; ++i) {
                max_val_B = max(max_val_B, S[i]-prices[i]);
                max_val_S = max(max_val_S, max_val_B + prices[i]);
                B[i] = max_val_B;
                S[i] = max_val_S;
            }
           
        }
       
        return S.back();
       
    }
};

Late Binding Behavior in Python

One interesting mistake mentioned in https://www.toptal.com/python/top-10-mistakes-that-python-programmers-make is the late binding behavior in Python.

Here is the problem, suppose we want to have the following function:

def create_multiplier():
    return [lambda x: x * i for i in range(5)]

for func in create_multipler():
    print(func(2))


We expect the code to print 0,2,4,6,8 while the actual output is 8,8,8,8,8.  As explained in the post
"This happens due to Python’s late binding behavior which says that the values of variables used in closures are looked up at the time the inner function is called. So in the above code, whenever any of the returned functions are called, the value of i is looked up in the surrounding scope at the time it is called(and by then, the loop has completed, so i has already been assigned its final value of 4)."

And the author propose a hack solution to the problem:

>>> def create_multipliers():
...     return [lambda x, i=i : i * x for i in range(5)]
...
>>> for multiplier in create_multipliers():
...     print multiplier(2)
...
0
2
4
6
8

There is another solution to handle this problem, we define the create_multipliers as:

>>> def create_multipliers():
...     return (lambda x: x * i for i in range(5))

Instead of returning a list we return a generator. In this case, when the function is called, the i in range(5) only moves one step ahead.  

>>> def create_multipliers():
...    return (lambda x : x * i for i in range(5))
>>> for func in create_multipliers():
...    print(func(2))
0
2
4
6
8

Implementation of Singleton in Python

This is a simple implementation of the singleton in Python


class Singleton(type):
    def __new__(cls, name, bases, namespace):
        namespace['_instance'] = None
        return super(Singleton, cls).__new__(cls, name, bases, namespace)



class SingletonBase(metaclass=Singleton):

    def __new__(cls, *args, **kwargs):
        if cls._instance is None:
            print("Create new instance for class {}".format(cls.__name__))
            instanceof = super(SingletonBase, cls).__new__(cls)
            cls._instance = instanceof
            return instanceof
        else:
            print("The class {} has been instantiated".format(cls.__name__))
            return cls._instance




class MyClass(SingletonBase):
    def __init__(self,val):
        self._val = val



if __name__ == '__main__':
    x = MyClass(10)
    y = MyClass(20)
    print("pointer of x: {}".format(x))
    print("pointer of y: {}".format(y))
    assert x is y
    print("x._val: {}".format(x._val))
    print("y._val: {}".format(y._val))

Implementation of immutable class in Python 3.5

# In this script, we will implement an Immutable class.
# The implementation is developed with Python 3. In order to run the code with Python2.7, we need to change the
# __setattr__ function in ImmutableBase to _setattribute__ function .


class ImmutableMeta(type):
    def __new__(cls, name, bases, namespace):
        namespace['_instances'] = []
        return super(ImmutableMeta, cls).__new__(cls, name, bases, namespace)


class ImmutableBase(metaclass=ImmutableMeta):

    def __setattr__(self, name, val):
        if self in self._instances:
            raise Exception("The class is immutable.")
        self.__dict__[name] = val

    def __getattribute__(self, item):
        if item == '__dict__' and self in self._instances:
            raise Exception("Not allowed to access __dict__.")
        return super(ImmutableBase, self).__getattribute__(item)

    def __init__(self):
            self._instances.append(self)

class MyImmutableClass(ImmutableBase):
    def __init__(self, x):
        self.x = x
        super(MyImmutableClass, self).__init__()



if __name__ == '__main__':
    instanceof = MyImmutableClass(10)
    instanceof.x = 200