LeetCode - 347.Top K Frequent Elements QuestionEditorial Solution My Submissions

347. Top K Frequent Elements  QuestionEditorial Solution  My Submissions
Total Accepted: 28149
Total Submissions: 63972
Difficulty: Medium
Given a non-empty array of integers, return the k most frequent elements.

For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note:
You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

    def topKFrequent(self, nums, k):
        """
        All elements in the nums array can be a candidate of the final outputs. We use the dictionary candidates to count the number of appearance of candidates.
        
        
        """
        count_qualified = 0     # number of qualified candidates
                                # the initial value is obviously 0.
        level = 0               # if candidates[n] > level the n is qualified
                    
        candidates = {}
        
        for n in nums:
            candidates[n] = candidates.get(n,0) + 1  # add 1 to the count
            
            if candidates[n] == level + 1:    

                # this is the only case we care. If candidates[n] <= offset, 

                # then n is not qualified and no impact on the count_effect
                # for candidates[n] > offset + 1, it means that n has been 

                # already counted as qualified. So no impact neither
                count_qualified += 1           # add 1 more qualified candidate 
                
                if count_qualified > k:        

                    # if the number of quanlified candidates is greater than 

                    # the target, we will increase the level of qualification 
                    level += 1
                    for item in candidates.values():# update the count_quanlified
                        if item == level:
                            count_qualified -= 1
        
        
        res = [key for key,val in candidates.items() if val > level]
                        
        return res

One Line Code Challenge: Special Merge

Suppose we have two data frames:

In[29]: df_data
Out[29]: 
   A  B  C  val_0
0  Y  M  1      1
1  Y  F  1      2
2  N  M  1      3
3  N  F  1      4
4  Y  M  2      5
5  Y  F  2      4
6  N  M  2      3
7  N  F  2      2

In[30]: df_rule
Out[30]: 
   A    B   C  val_1
0  Y  NaN NaN    100
1  N    F NaN    200

2  N    M NaN    300

In the context of an ordinary merge on ['A','B','C'], there is no matches because there are NaN in the df_rule.

In the context of a special merge, we allow NaN to be anything. That is to say
(Y,M,1) can match with (Y,M,NaN) (or (Y,NaN,1)etc)

The task is to achieve this special merge.

Solution:
df_rule.groupby(df_rule.apply(lambda x: '-'.join(x[x.notnull()].index.values), axis=1)).apply(lambda df: pd.merge(df, df_data,on=df.dropna(axis=1,how='all').columns.intersection(df_data.columns).tolist(), how='left',suffixes=('_to_remove','')))[df_rule.columns.union(df_data.columns)]

One Line Code Challenge: compute the list of prime factors

factors = lambda n, k=2: ([k] + factors(n / k) if n % k == 0 else factors(n, k+1)) if n > 1 else []


In[17]: factors(3)
Out[17]: [3]
In[18]: factors(4)
Out[18]: [2, 2]
In[19]: factors(9)
Out[19]: [3, 3]
In[20]: factors(18)
Out[20]: [2, 3, 3]
In[21]: factors(24)
Out[21]: [2, 2, 2, 3]
In[22]: factors(1)
Out[22]: []

Python -- Pandas -- Add a new level to the column in DataFrame

Here is the situation, we have a data frame df

          X         Y         Z
0  0.738596  0.852906  0.333422
1  0.820456  0.014704  0.233935
2  0.118291  0.714536  0.176275
3  0.032417  0.819386  0.949590
4  0.739559  0.923865  0.791574

And for some reason, we want to add a new level to the columns. Unlike adding new level to index, it seems that there is no available function in Pandas to handle this problem.

We can of course do it "manually", something like this:

df.columns = pd.MultiIndex.from_arrays(np.vstack((np.asarray(['test'] * df.shape[1]), df.columns.tolist())))

A more general function is

def add_new_level(index, new_level):
    arrays = np.asarray(index.get_values().tolist()).T
    new_arrays = np.vstack((new_level, arrays))
    return pd.MultiIndex.from_arrays(new_arrays)

(not sure if this is the simplest one, have some doubts)

and the data frame becomes:
       test                  
          X         Y         Z
0  0.738596  0.852906  0.333422
1  0.820456  0.014704  0.233935
2  0.118291  0.714536  0.176275
3  0.032417  0.819386  0.949590
4  0.739559  0.923865  0.791574

or we can play some trick like this one:

df = pd.concat([df], axis=1, keys=['test'])

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