Leetcode Battle Field and 面试小日记

今天去个创业公司面试了，总体来说不是很满意。一方面是在面谈的时候没能够控制好自己的情绪，让对方不断说“没关系，这个不是说你上班……”什么的。其实我应该要控制好自己的情绪，然后想想怎么表达自己的想法，说服别人。这方面我一直做不好。另一个问题是笔试的时候再次把自己鄙视了－－题目都不会(=T_T=)。

也算加深了一点职场上对程序员的要求的了解。一个是技术方面，首先要基础好：理论懂得各种名词基本理论，比如搞互联网通信就知道HTTP和socket是怎么回事，写后台就要回thread和process；另外技能熟练，常用的包的常用概念和API要熟悉。这个决定了程序员能不能用。如果不能用，但是长期留，就可以看看他聪不聪明，聪明慢慢学。如果短期留，最好基础和技能都扎实，直接形成生产力。这里两方面我都没做好：知识不扎实又不能长期留。所以技术上跪。

另一个是做人方面：程序员的价值观最好跟自己团队相近，一起工作才能有化学反应。人与人之间的愉快交流会促进交流和学习，这样大家才能一块成长和迸发新想法，而不是说简单的完成任务，每天原地踏步，死水一潭。今天跟Boss交流，我很不理解的一个方面就是：明明编程语言和包／库是工具，他们具有不同特性，然后程序员应该根据不同需求使用不同语言／包。但是他却根据人的特性，然后给人贴上不同语言的label：”我觉得你更适合python社区“ 这个我一听，心想“怎么能这样呢？搞反了啊。”,然后就激动了，然后就失控了。估计他也聊得不开心。总的来说，双方都没反应，二跪。

反正今天就是跪了一下午，上来发发泄。不过后期的学习计划也明确了下:

如果准备去互联公司工作，首先互联网通信协议和计算机网络要精通（基本功好），然后相关包要API要熟悉（技能足），上来就是战斗力（劳动力）。总的来说不要求基础好，但要要求API熟记。
如果准备大公司保养，一个劲儿算法学好。大公司有钱，不着急形成战斗力，可以慢慢培养人才。算法基础好，往哪里转都合适。但是因为大公司一般都没有现成包可以使用，一切自己开发，所以对算法要求很高。总的来说不要求工具玩得出神入化，但是基础好。

LeetCode Battle Field:

好吧，回来说下这今天在做的一道leetcode。以后leetcode和hackerrank相关刷题blog都有这个leetcode battle field的flag。

先看题目:

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.

基本题目意思是，给定一个股价序列prices和可操作（一买一卖）次数k，求最大利益。

这道题目也是做了两个思路。首先最基本的是，股票必定低买高卖，因此先求极点。这个是没问题的。第一个思路是，股票一买一卖一个周期，把所有周期求出来，然后sort一下，取前k个周期求和就是最大利益。这个版本的代码没留着，因为缺陷很明显：如果股票小幅下跌后大幅上涨，我们就不赢该再下跌的时候把股票卖了，这样会浪费操作次数，导致利润降低。

意识到这一点之后，这个题目变的很难。因为要有全局眼光。首先为股票写一个类

class Stock():
    def __init__(self, buy_date, buy_price, sale_date, sale_price):
        self.buy_price = buy_price
        self.buy_date = buy_date
        self.sale_price = sale_price
        self.sale_date = sale_date
        self.profit = sale_price - buy_price

    def  __repr__(self):
        return  str({
        'buy_price': self.buy_price ,
        'buy_date': self.buy_date ,
        'sale_price': self.sale_price,
        'sale_date': self.sale_date ,
        'profit': self.profit })

这个class代表了一直股票的所有关键参数：买卖时间和买卖价格，然后计算出利润。然后这个问题转化成两个：

求取所有可能拥有的股票（所有可能买卖组合）
这些组合在能够实现，操作次数满足条件的情况下的最大利润。

1 很简单，求所有极值点然后排列组合就好。2 的话，主要满足一个需求股票必须全卖之后才能全买，不能说连着买两次。简单地说就是买卖区间不能重叠。一开始考虑写成一个树，结点是一个股票，他的子结点是买了那只股票之后剩下的其他可能的股票。然后求取depth＝k的所有路径上的利润。但是这个方法很难实现，而且空间复杂度高。后来仔细一想其实这个就是个小递归（动态规划？）。这个问题就变成了：

假设N手获得最大利益
那么第一手的利益和剩下的N-1手的利益相加必定是最大的
求取所有可能的第一手，与对应N－1手的最大利益，相加，看看那个利润最大
对N-1手采用 1 直到省下一次操作次数，这时可以直接在所有选择中求max

跟着这个做出了这个算法：

class Solution:
    # @return an integer as the maximum profit 
    def __init__(self):
        self.have = False
        self.profits = []

    def possibleStocks(self, k, prices):
      """get all possible stocks
      """
        # get all possible operate point
        buy_points = []
        sale_points = []
        # conner case
        if prices[0] < prices[1]:
            buy_points += [0]
        if prices[-1] > prices[-2]:
            sale_points += [len(prices)-1]

        # general case
        for date in xrange(1, len(prices) - 1):
            if prices[date-1] <= prices[date] and\
                prices[date+1] <= prices[date]:
                sale_points += [ date ]

            if prices[date-1] >= prices[date] and\
                prices[date+1] >= prices[date]:
                buy_points += [ date ]


        # get all possible stock
        stocks = []
        for buy_point in buy_points:
            for sale_point in sale_points:
                if buy_point > sale_point:
                    break
                else:
                    b_d = buy_point
                    s_d = sale_point
                    b_p = prices[buy_point]
                    s_p = prices[sale_point]
                    # stocks should earn money
                    if s_p > b_p:
                        stocks += [ Stock(b_d, b_p, s_d, s_p) ]
        return stocks

    def findMaxProfit( self, operation, stocks, earliest_time ):
      """  
      Given possible stocks, operation tims and earliest 
      operating time, get max profits
      """
        # remain stocks could not be bought before last stock saled
        stocks = [stock for stock in stocks if stock.buy_date >= earliest_time ]
        # if no stock fulfill reuqirement reutrn0
        if stocks == []:
            return 0
        if operation == 1: # if only 1 operation left, choose max profit
            return max([ stock.profit for stock in stocks ])
        else: # 找出 N－1手 和 第N手 的最大利益
            operation -= 1
            possible_profits = [0]
            for index in xrange(len(stocks)):
                left_stocks = list(stocks)
                left_stocks.pop(index)
                possible_profits += \
                    [self.findMaxProfit(operation, left_stocks, stocks[index].sale_date) + stock.profit]
            return max( possible_profits )

    def maxProfit(self, k, prices):
        if len(prices) <= 1:
            return 0
        if len(prices) == 2:
            return max( 0, prices[1] - prices[0] )
        stocks = self.possibleStocks( k, prices )
        return self.findMaxProfit( k, stocks, 0)

这个算法花了很多时间调conner case，结果是没问题的，但是超时。之前用到List.index()方法，真心慢，没看源码，估计不少Python，丢弃了，依旧超时。目前不知道改进方法。后来认真想想，这个应该用动态规划？回去翻翻书.也可能是中间多了一个Stock（），应该直接根据buy()和sale()写算法会更快。先刷后面的题目。这个POST把这个题目mark下有空慢慢想。