YoungForest's blog

国庆节后，我和二师兄有机会前往广东，依次游览了广州、澳门 和 香港。10月6号从北京出发，坐10个小时高铁，来到广州南站，之后落塌广东大厦。

广州

第一天先歇一天，在广州玩。早起去爬越秀公园。由于是长假的最后一天，年轻人都玩累了躺在家里休息，大街上和公园里只能看到大量的中老年人在锻炼身体。在公园里，我终于亲眼看到了生长在南方的“木棉”。想起《致橡树》中的诗句，“我愿做你身旁的一株木棉…“；和 《致橡树》电视剧中的情节。橡树 和 木棉 分别生长在北方和南方，注定不能生长在一起。知道这一点的话，才能体会到《致橡树》中传达的悲伤的情感。

之后到了9点，吃早茶的时间。我们来到“陶陶居”–广州很有名的早茶连锁店，一起吃早茶。早茶是广东的特色。算是早餐，但是可以吃一上午。很多本地人会每天吃早茶，在那里喝一上午的茶，聊一上午的天。很佩服那些吃早茶可以吃一上午的人，羡慕他们的悠闲自在。我是绝对坐不住的，也坐不起。每天早上不学习工作的话，我估计很快就会被淘汰、饿死。早茶 主要包含茶和茶点。一上来会给你一个小盆，后来我才知道是用来涮餐具的。用滚烫的茶水清洗盘子和碗筷，既消了毒，又给餐具带来了茶的清香。茶可以无限续杯，否则怎么坐一上午呢。茶点真是好吃极了，此行不虚。

吃完早茶后，时间还早，我们就去了城南的沙面公园玩。这里有大量租借时期的建筑和遗留。我很喜欢这里。有很多家长带着来自在公园嬉戏，西式建筑也很符合我的口味，每栋都有自己的特色，因为是不同国家修的。让我想起天津的租界和老房子。在这里，我们还误打误撞进了一家豪华的酒店–白天鹅。二楼的自助餐给我留下了深刻印象。385一位，但由于当天还是国庆假期，425一位。我们进去看了看就出来了，还是等以后有钱了再光临这里吧。我对这里的深刻印象不是因为这里的自助餐有多豪华、多可口，而是这里的位置。落地窗外就是珠江，给人一种整座酒店浮在珠江上一样。满足了我对有钱人奢华生活的想象。这样贵的酒店，生意竟然特别好。更是有人包下整个餐厅举办婚礼。中国有钱人真多，贫穷限制了我的想象。我等屁民，还是紧衣缩食，看看就好了。

中午吃饭的时候去了一家网红店–吴财记云吞面。位置极其偏僻，人还居多，几乎座无虚席，等的时间还很长。好在味道还可以。我点的炸云吞，不过二师兄点的云吞面味道就一般了。城南是老城区，怎一个破字了得，一点也没有一线城市的氛围。不过晚上到天河区后，就知道，广州当得起一线的地位。

吃完饭后坐地铁回酒店休息。4点时出发去 中山大学（也叫 双鸭山大学）参观。中山大学的校园很漂亮，妹子也特别多，有个门直接面向珠江，顺江而上就是广州塔。我们骑单车沿着江、跨过桥，总算来到最繁华的天河区了。在这里我们体验了资本主义的奢华和腐败，从此励志好好学习，做共产主义的接班人。我们晚上在地下商场的网红店吃了 鸡煲。打算找个超市买点水果和早餐就回酒店。跟着导航到了一家附近看起来不错的超市，进去后，才一脸蒙蔽，太贵了，消费不起。在二师兄的怂恿下，我破费了一码，买了价值50元的一小盒指头大小的西瓜。最后证明，小西瓜巨难吃，全都浪费了。二师兄这次旅程中都是，聊什么吃的都吹牛说巨好吃。除此之外，没有其他形容词了。等我真正吃到是，发现大多数都一般般，少数食物倒是挺好吃的。我不是个吃货，对这些也没有研究和感受。吃了更多的也是浪费。

澳门

去港澳的行程是早就规划好的，也正是这两个特别行政区吸引了二师兄，否则，单单一个广州他是不会和我来的。我提前一个月办好了港澳通行证，当时还经历了一些小波折。出入境管理中心的网站今年更新了，但最近新系统一直处于宕机状态。不知道是有意还是无意，但这无疑很大地提高了公民出境的难度。我等不到系统修复了，只好去不需要预约的海淀出入境大厅办理了港澳通行证。从办理到收到，算上休息日一共14天，效率还可以。二师兄是在我之后办的。他的做法是不停地刷新预约系统，偶尔就可以进去，完成了预约，在花园路派出所就直接办了，而且还办了二次往返的签注。我只有一次出入境的签注，但已经足够了。

如何欢度2018年最后一个假期–国庆节呢？我选择了跟团(北京初心户外)去河北丰宁的坝上草原骑马。9月30号晚19点半在惠通西街南口集合上大巴。一路向北，9点半到达一个北京最北的服务站时，已经感觉很冷了。晚上近12点到达丰宁县的一个农家乐住宿时，天气已经非常冷了。据房东说，前一天刚刚下过雪，所以这两天非常冷。后来国庆节后刷朋友圈时，看到去什么沙漠、戈壁、火山的，无一例外都是很冷。所以，秋天去这些地方，还是要三思而后行的，做足充分准备的。出发前，领队反复强调需要带厚衣服，最好是羽绒服。我从小怕冷，直接带了最厚的羽绒服–500g 绒的加拿大鹅。据说这衣服去南极都没问题，我没去过南极，不知真假。但这件衣服抵抗秋天的草原夜晚的温度，还是一点问题也没有的。

2014年9月，我误打误撞来到了北航计算机学院。没想到“侯门一入深如海，从此萧郎是路人“，从一个从没有接触过代码的小鲜肉，成长为未来的工程师。这四年的时光是我技术和三观成长的重要阶段，可以说，大学塑造了之后的我。其中，有值得肯定的部分，也有我现在一心想要摒弃的缺点。

北航的课程以基础扎实著称。计算机科学的基础课程：计算机组成原理、操作系统、编译原理、计算机网络，分别分布大二大三在4个学期，每学期这些基础课都属于重课，需要花费大量的精力。现在看来，重视这些基础课程简直太正确了。我大四参加了多场实习面试和实习，深刻体会到这些基础在面试和工作中的重要程度。只是当时大多数学生的motivation不足，并不能理解学院的良苦用心。我自认为在学院学习成绩名列前茅，奖学金和各种证书也拿了一大把。但对于这些cs基础，并不敢叫嚣自己理解了，更多地是谦虚地告诉自己，很多还需要补习。年轻的时候欠下的帐迟早要还的。这四年来，貌似学了很多，其实学到很少。其实，最好的学习方法是，在学院的课程配合下，主动地进行学习。阅读每个topic的扩展材料，而不是老师把材料的链接放在ppt上，自己连下载都不下载。多多上网搜集信息，泡图书馆。

虽然平时经常和朋友们吐槽课程设置不合理，但我不得不承认，计算机学院的很多本科课程的设置还是极其合理并富有前瞻性的，尤其是结合其他高校的课程设置来看。北航计算机学院全国第三的排名也并非浪得虚名。比如，大一上的大学计算机基础就是教python，更可怕的是，是几乎所有专业的同学都要学，不限于计算机，还有人文、经济、数学、飞行器。后来写的代码多了，才知道掌握python确实是必要的。尤其是15年后，机器学习大火之后。python是机器学习的必备语言。而据我所知，并没有其他高校从14年就将python设置为全校的必修课。
大一的时候，我们要上很多课，其中大多数是数学课，编程课程每学期只有一两节。每门数学课还都是大课重课，需要花费很多的精力。包括 数学分析、高等代数、概率与统计这些基础课程，也有 离散数学、集合论、图论 这些和计算机相关的数学课。当时大家都笑称，“进错了专业，其实是数学系”。之前有过编程经验的同学更是无法理解，因为他们选择计算机专业时就期待着更多实践课程，可以动手写代码。现在看来，对数学课的重视一点也不为过。只是当初too young, too naive，无法理解老师们的良苦用心。真的就像大一时候班主任告诉我们的一样，基础数学课的有用程度是 概率统计 > 线性代数 > 微积分。后来接触机器学习后，才知道数学真TMD重要。年轻的时候总是认为自己很牛逼，知道自己需要什么，不需要什么；认为学院很傻逼，老师很古板。其实呀，真正傻逼的还是自己。

大学期间究竟要不要参加各类比赛呢？我认为完全没必要，除非你对该比赛有强烈的兴趣，或者比赛的经历和奖项可以给你带来足够的收益。
从现在看来，我参加比赛的经历并未获得足够的收益，反而投入了一部分时间和经历。
我大学期间参加过各种各样的比赛，主要集中于学科竞赛和编程比赛。首先是数学建模竞赛，估计是很多大学生都有机会参与的。我曾经和2位同学一起参加了2016年的美赛和国赛。现在看来是一件蛮可笑的事情。我们之前没有任何关于建模的数学基础和写作训练，试图水一个奖项，最后当然竹篮打水一场空。诚然很多同学也是熬夜几天，水了一个二等奖，但这个奖项的收益有多大呢？美赛几乎都是中国人在参加，大家也知道奖项并不能证明你的能力。大一上数学分析的时候，杨小远老师就说，她在数学学院招收研究生的时候，发现很多人都有美赛的奖项，但面试一问就露馅了，数学和建模能力一般。获奖更多的是抱大腿和比赛本身的水分。
所以，我认为，很多时候，奖项只是锦上添花的东西，更重要的是，你在准备比赛和参加比赛的过程中，收获的能力和成长。
我在大二的时候，也参加过大学生数学竞赛（非数学类）。在竞赛的培训期间，因为太难了，很多材料都只做了不到1/3。就是这样，我竟意外地获得了全国三等奖。但实话说，这个奖项对我没多大作用（当然对评奖学金是有用的），而且我在准备竞赛的时候并没有全力以赴，收获到的能力和成长都是有限的。

大学期间，我一直没想明白自己以后要做什么。没有清晰的目标，就没有细致的规划。很多机会其实也就这样错过了，机会总是留给有准备的人的。这样时间不能说是浪费掉了，但却没有被高效利用起来。大一大二大三一直在上课。由于高考的失利阴云一直笼罩在我的心里，我到了大学仍然学习很认真，生怕落后。大三到了决定出路的时候，自己才发现周围少部分同学早早地准备了出国、保研、工作，此时正是丰收前的最后冲刺。而我像大多数人一样，匆匆忙忙地度过了大学的前几年。我由于成绩不错，被老师鼓动保研了。
就像很多游戏里的职业系统一样，玩家达到某一等级后，就可以选择不同的职业，专学该职业的技能，购买该职业的装备。有经验的玩家会早早准备着这一步，可能从0级就决定好之后的职业了。然后向着这个职业修炼，因此技能点和金钱一点也不浪费。而我就像新手玩家一样，早期由于晋升道路很明显和固定，一路打怪升级，由于天赋玩的还不错。但到了选择职业这一步，就蒙蔽了。货比三家，还是选择了人数最多的职业。心想，选的人多自然有其道理。进入职业后，由于前期的专项积累不够，与有经验的玩家有差距甚至是被吊打，也不足为奇了。

大四在外实习了一年，接触了业界的不少前辈。从75后到80后，还有不少90后。通过比较和自己在实验室的生活，我发现自己更适合和喜欢工作。我本身性格内向，对数理也很感兴趣，大学接触编程后，也是兴趣盎然。相比很多同学对编程的不温不火，甚至排斥，我对编程可以算是热爱了。大二折腾了一年，自学了Linux、git、鼓捣个人博客、网站。这些折腾到后来给了我丰厚的回报，尤其是Linux和git 2项，在之后的工作学习中有大量的使用。数学上的优势也让我可以接触到算法岗的工作。但由于没有丝毫准备，当时的我并不能放弃读研，转而工作。因为程序员的短缺，我本科毕业找到一份看上去还不错的工作不难。但并不能找到顶尖的工作。程序员也分很多种，前端、后端，架构、算法。我也不清楚其中的差别，莽莽撞撞地去工作很危险。所以，我就打算继续读研了。趁着读研期间的学生身份，多出去实习几次。一是可以体验不同的工种，找到自己适合的；二是可以锻炼自己的能力，丰富简历内容，为明后年找工作做准备。

以上，就是我大学四年的复盘。主要集中在学习和人生规划方面。因为我认为这些才是大学生需要主要思考的问题。
我的大学生活绝不能算是成功，相反，与身边优秀的人相比，可以算是失败了。所以，这篇文章，更多的是教训、而不是经验。希望自己以后可以引以为戒。

岁月是把杀猪刀

岁月是把杀猪刀，有些人千刀万剐，有些人刀枪不入。

昨天参与了景驰科技的实习生面试。此次实习生面试是实验室统一安排的，并不是我自己找的。
形式为在线面试。总共2轮，预计每轮1小时，实际上第二轮只问了半个小时。第一轮用的Skype，通话质量比较差，视频输出也没有。第二轮，用的微信语音 + collabedit。效果好了很多。

技术面都很简单。因为是招数据标注平台的码农实习生嘛，自然要求超级低。感觉自己要被廉价卖掉了。

Description: https://leetcode.com/problems/kth-largest-element-in-an-array/description/
Solution: https://leetcode.com/problems/kth-largest-element-in-an-array/discuss/
Difficulty: Medium

这是二师兄面试景驰的一道题目。因为他的面试在上午，我的在下午。所以，和他交流过面试内容后，我把他被面的题目都做了一遍。包括这道题目和找硬币。

我的动态规划

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

class Solution:
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        memo = {}
        mi = nums[0]
        ma = nums[0]
        for i in range(len(nums)):
            ma = max(ma, nums[i])
            mi = min(mi, nums[i])
            memo[(i, i+1)] = mi
            memo[(i, 1)] = ma
            
        def find(n, k):
            if (n, k) in memo:
                return memo[(n, k)]
            
            n_sub_1_k = find(n-1, k)
            
            if nums[n] <= n_sub_1_k:
                return n_sub_1_k
            
            n_sub_1_k_sub_1 = find(n-1, k-1)
            
            if nums[n] >= n_sub_1_k_sub_1:
                return n_sub_1_k_sub_1
            else:
                return nums[n]
            
        return find(len(nums)-1, k)

时间复杂度 O(n^2)，memo中的每个元素需要遍历一遍;
空间复杂度 O(n^2)，创建一个二维的memo.

结果：TLE 超时。
还不如直接快排找第k个值。

选择算法

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

class Solution:
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        def partition(nums, lo, hi):
            i = lo + 1
            j = hi
            
            while True:
                while i <= hi and nums[i] < nums[lo]:
                    i += 1
                while j > lo and nums[j] > nums[lo]:
                    j -= 1
                
                if i >= j:
                    break
                    
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
                j -= 1
                
            nums[lo], nums[j] = nums[j], nums[lo]
            
            return j
        
        lo = 0
        hi = len(nums) - 1
        k = len(nums) - k
        
        while lo < hi:
            j = partition(nums, lo, hi)
            if j < k:
                lo = j + 1
            elif j > k:
                hi = j - 1
            else:
                break
            
        return nums[k]

和快排很像，尤其是partition部分。
时间复杂度O(n)，空间复杂度O(n)。
具体解释见Discuss。

8月21号 至 8月28号，带着自我放逐的心情，我去山东玩了7天。小时候（2008年）曾跟着爸爸和旅行团来过山东旅游，经典的旅游城市，包括青岛、烟台、威海 和 隔海相望的大连，都逛了一圈。当时年纪尚小，天真烂漫，只觉得不用上学，来到陌生的地方旅游，十分有趣。如今十年过去了，同样的景点，却有不一样的心情和感受。

此次旅行是临时决定的。之前同学叫着去重庆做毕业旅行，我由于种种原因没去成。8月中旬后，经历了情感上的波折和三毛流浪文学的洗脑，恰好有山东的同学(我们可以称之为“女声男”，因为其声音特别有雌性)邀请我去山东一起玩。我便答应了。希望通过此次旅行让心情好过一点，让匆忙的旅行占据自己的大脑，不去想不该想的苦恼。

Description: https://leetcode.com/problems/convert-bst-to-greater-tree/description/
Solution: https://leetcode.com/problems/convert-bst-to-greater-tree/solution/
Difficulty: Easy

此题虽为Easy难度，但一遍写对还是很困难的。
看到二叉树，就要想到用递归解决。本题的一个trick是，如何把需要累加的值这个信息，在递归过程中传递。

递归调用右子树时，需要返回整个右子树的和，将这个和加到根节点上。具体到我的解法，右子树的和可能存在于2个地方。1. 右子树的最左叶子节点 2. 右子树的根节点(此时，右子树无左子树)。

递归调用左子树时，需要把根节点和右子树的和，这些信息传递进去，加到右子树的最左叶子上（也就是右子树中最大的那个值）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def convertBST(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        def convert(root, addition):
            if root == None:
                return addition
            root.val += convert(root.right, addition)
            if root.left == None:
                return root.val
            return convert(root.left, root.val)
        
        convert(root, 0)
        
        return root

时间复杂度O(n)，需要遍历每个节点一次。
空间复杂度 平均O(log n)，最差O(n)，递归调用的最大深度。

看过Solution后，惊觉自己把问题搞得太复杂了。传递累加的值这一信息，通过一个全局变量维护即可。然后再对树右序遍历，代码写起来也简单很多。Solution中的Approach #3最好，其空间复杂度为O(1)。

迭代版本（无递归）

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

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def convertBST(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        total = 0
        stack = []
        
        node = root
        
        while len(stack) > 0 or node != None:
            while node != None:
                stack.append(node)
                node = node.right
            
            node = stack.pop()
            
            total += node.val
            node.val = total
            
            node = node.left
        
        return root

Description: https://leetcode.com/problems/single-number/description/
Solution: https://leetcode.com/problems/single-number/solution/
Difficulty: Easy

题目的难点在于：Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

我苦思冥想，实在无法同时满足时间复杂度O(n)，空间复杂的O(1)的要求。跑去看题解，Approach 4满足条件。使用了异或的位运算的性质，确实需要技巧。也可以看到评论区充满了"awesome"的感叹。会者不难，以后再遇到就Easy了。

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ret = 0
        for i in nums:
            ret ^= i
            
        return ret

一个清华的毕业生做为面试官，一开始问了我之后的工作意向。我回答说是“算法工程师”，其实我这次面的是开发岗，就被大佬教育了一顿。说你是不是投错组了，还没找到自己感兴趣的方向嘛。之后问我，现在在快手的实习是做什么的？我讲了一些。然后又被diss了。说这些特征工程之后都会被深度学习所取代的。

正式进入面试只问了2个问题：维护最小值的队实现，和 维护最小指的栈实现。

之后本来有二面的，后来没找到面试官就不了了之了。

我是对这次面试结果不抱太大期望的，毕竟过程比较水，也不是很愉快。果然之后face++那边一直都没有消息。

为了更快地锻炼自己数据挖掘的能力，我计划最近一个月花一定的时间在kaggle比赛上。目前的计划是把Tutorial上的比赛、Datasets和牛人们的notebook跟完作为入门。之后再选择一个简单的常规比赛参加。
至于最后是否像欢哥一样走上数据挖掘竞赛之路，看入门之后的感受。自己是否愿意继续花大量的精力在上面。

数据挖掘的能力主要分为2部分：

• 机器学习
• 特征工程

之前在快手推荐组实习的时候，工作也涉及这些。推荐系统也算是数据挖掘的一个分支，从结果上看，是预测某个item是否会被用户点击。

Titanic: Machine Learning from Disaster作为大多数人入门kaggle的第一步，确实是对数据挖掘技巧的集中体现。相反，最近在kaggle上比较火的比赛，都是和CV或NLP相关的。领域知识的要求更高，淡化了通用的数据挖掘技能。
在kaggle上还有许多其他的教程可供用户学习，我今后会选择其中的一些进行重点学习，争取在开学前入门kaggle。