Just a post to test if catagory and rss feed works well.

Today I solve another problem on leetcode, the process of solving this issue just like the old saying: “踏破铁鞋无觅处，得来全不费功夫”, which means people spared a lot of efforts on a problem but it was solved in a unexpected simple way.

Ok, let’s talk about the problem:

1
2
3
4
5

  Given a list of non negative integers, arrange them such that they form the largest number.
  
  For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.
  
  Note: The result may be very large, so you need to return a string instead of an integer.

So the first thing I need to do is transfer integers into strings, which will help in the following comparasion. Next, I sorted the numbers based on their first digits because obsiviousl, 9** is greater than 1**. Aftr that, I extracted numbers with same first digits and do the comparation.

In the comparation, those numbers will be combine to form the biggest number they can. This is the most important part. At first, I wrote a complicated algorithm which did comparasion using a[:length] > b[:length], and lots of code handle conner case – one of the number is longger. The code went really long like

This code went well expect for the test cases like [8308, 830] or [101,10]: No matter how I compared thoes numbers, they are ‘equal’. But when I combined them with different order, the result differed. I spent a long time trying to figure(playing) a(3ds) method(game). Suddenly, I came out with a idea: “why not do the comparision by combine digits in different order and see which result is larger?”. It Works, and the final algorithm became really simple:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

class Solution:
    # @param num, a list of integers
    # @return a string
    def largestNumber(self, num):
        num = [ str(n) for n in num ]
        # sort by the first digit 
        sorted_num = sorted(num, key = lambda x : x[0], reverse = True)

        # for number with same 'first number', combine them to get biggest
        result = ''
        for i in xrange(9, -1, -1):
            i = str(i)
            num_group = [ num for num in sorted_num if num[0] == i]
            if len(num_group)>0:
                result += self.maxNum( num_group )
        # check if number is zero
        if int(result) == 0:
            result = '0'
        return result

    def maxNum( self, nums ):
        """
        Given numbers(list of string) with same first digits, 
        combine them to get max number(string).
        """
        result = ''
        while len(nums) != 1:
            # init a winner and its index
            win = nums[0]
            win_index = 0
            win_length = len(win)

            # find a num, if added to result, yield biggest number
            for index in xrange(1, len(nums)):
                num = nums[index]
                result1 = win + num
                result2 = num + win
                if result1>result2:
                    num_win = False
                else:
                    num_win = True

                if num_win:
                    win = num
                    win_index = index
                    win_length = len(num)

            # append the winner to the result
            result += nums.pop(win_index)
        # append the last number
        result += nums[0]
        return result

About TDD:

In Last day’s interview, I was asked about my idea of TDD(Test Drive Development), I just answered:“I think it is usual, I wrote test for my codes.”, which equals to answered nothing. These two days I developed leetcode’s answer with the help of OnlineJudge’s test cases, I did realise that writing test cases norishes a developer.

Every time programmers write tests，they try covering every special cases they know， therefore codes pass their own tests are their best products within their ability. But when things come to production, codes will prossibly encouter cases that make it fail, which, just like a hole in developer’s mind. Every time developer find such a case, it find a hole in his mind he never knows, then he fixes it. Day after dats, after millions of holes are fix, his mind hardly has hole. Therefore, his products, his codes, will become unbelievably stable.

That’s my understand of TDD – Test Drive Developer.

Just for fun, don’t take it seriously. :)

今天去个创业公司面试了，总体来说不是很满意。一方面是在面谈的时候没能够控制好自己的情绪，让对方不断说“没关系，这个不是说你上班……”什么的。其实我应该要控制好自己的情绪，然后想想怎么表达自己的想法，说服别人。这方面我一直做不好。另一个问题是笔试的时候再次把自己鄙视了 －－ 题目都不会(=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个周期求和就是最大利益。这个版本的代码没留着，因为缺陷很明显：如果股票小幅下跌后大幅上涨，我们就不赢该再下跌的时候把股票卖了，这样会浪费操作次数，导致利润降低。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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. 这些组合在能够实现，操作次数满足条件的情况下的最大利润。

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

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下有空慢慢想。

最近一直在纠结一个问题：我手上有一本《操作系统原理》，看？还是不看？

请原谅我这个选择困难症患者在这个无聊的问题上纠结这么久。我为此特地在知乎上搜索了将尽一个小时。他人的观点基本你可以总结成两类

1
2

1. 学！程序员三大浪漫之一，好好打地基，万丈高楼平地起。不仅学，习题好好做。
2. 随意！前端要用操作系统原理吗？写ajax要你自己实现TCP/IP?用得着就学。用不着别管。

按照这里面的思路去回答问题，估计在纠结两百年也纠结不出来：谁知道知识在什么时候用到？未知的世界永远未知。但是在方向不明确，或者去完全没需求和收益的情况下，去实现编译器或者操作系统什么的……抱歉，太浪漫的事情我做不了。So，为了走出这两个极端，我回答了自己几个问题：

1
2
3
4
5
6

1.我浪漫过吗？
  浪漫过
2.有用吗？
  有
3.那么学不学？
  学

是的，我也曾经浪漫。在课余时间的时候抱着一本《编译原理》在啃，幻想着把习题做完之后成为编程高手。当然我这种渣渣最后还是屈服在了懒惰之下，书只看了前几章就丢在了一边，自己写编译器什么的更是天方夜谭。

即便如此，这段经历带给我的好处也是十分明显的。这个好处体现在，在面对些语言的trick（语法糖）的时候，我能够很快地理解并且掌握。比如之前在看《ruby元编程》，前半部分我就毫无压力，全当是在复习《编译原理》。原因很简单，因为我在《编译原理》中理解了block和变量作用范围的概念，ruby里面再怎么变化，也逃不出编译器（解释器）的范围。

这个书啊，并不是说看完了他能给你提供什么技能，能够帮助招工赚钱，尤其是基础类别的书。它能提供的，更多是一种概念。越是基础的知识，其中的概念就越抽象，也越能代表更多的事物。很多的概念、名词，其实都是新瓶装旧酒。这酒没变，瓶子其实不怎么重要。

概念是个很重要的东西，很多时候缺少一个概念就会使人停滞不前。因为你意识不到自己的缺陷，也无法找到改进的方法。比如之前在看Scrapy的源代码的时候，对signal和callback函数很难理解。查了很多相关库的API文档，懂得了函数的用法，却衍生出了更多不懂的概念，使自己更加迷糊。这说白了，就是对操作系统的工作机理缺乏理解。这就体现了《操作系统》这本书所能给我带来的优势。

其实不仅是书，视频、经历、人等各种能够为我们带来新概念和新事物的东西，都要勇于接受。一堵墙，打破一个点，就有机会窥见另一面的整个世界。

那么……

1
2
3
4
5
6
7
8

1.学不学？
  学！
2.为什么学？学到什么程度？
  了解和掌握操作系统的基本概念和运行机制。
3.怎么学？习题你还做不做？
  就当看科普书，记住概念。习题做小题，目的是帮助巩固概念。
4.你还写不写操作系统了？
  写！个！屁！给钱我就写。

好，那么现在剩下的问题就只有一个了：

1

怎么啃掉这几百页的英文大部头？

呵呵，SB ，买英文书 (= =||凸

I’ve always want a English technical blog. i’ve tried wordpress, which is far from satisfying to inserting code.

Now, I have a try on octopress. Hope it work well~