一位Google程序员的算法学习之路

2017-04-01 07:15:00
2puT
转贴
322
摘要:一位Google程序员的算法学习之路


关于

严格来说,本文题目应该是我的数据结构和算法学习之路,但这个写法实在太绕口——况且CS中的算法往往暗指数据结构和算法(例如算法导论指的实际上是数据结构和算法导论),所以我认为本文题目是合理的。


这篇文章讲了什么?

  1. 我这些年学习数据结构和算法的总结。

  2. 一些不错的算法书籍和教程。

  3. 算法的重要性。


初学

第一次接触数据结构是在大二下学期的数据结构课程。然而这门课程并没有让我入门——当时自己正忙于倒卖各种MP3和耳机,对于这些课程根本就不屑一顾——反正最后考试划个重点也能过,于是这门整个计算机专业本科最重要的课程就被傻逼的我直接忽略过去了。


直到大三我才反应过来以后还要找工作——而且大二的折腾证明了我并没有什么商业才能,以后还是得靠码代码混饭吃,我当时惊恐的发现自己对编程序几乎 一无所知,于是我给自己制订了一个类似于建国初期五年计划的读书成长计划,其中包括C语言基础、数据结构以及计算机网络等方面的书籍。


读书计划的第一步是选择书籍,我曾向当时我觉得很牛的”学长”和”大神”请教应该读哪些算法书籍,”学长”们均推荐《算法导论》,还有几个”大神”推荐计算机程序设计艺术(现在我疑心他们是否翻过这些书),草草的翻了下这两本书发现实在看不懂,但幸运的是我在无意中发现了豆瓣这个神奇的网站,里面有很多质量不错的书评,于是我就把评价很高而且看上去不那么吓人的计算机书籍都买了下来——事实证明豆瓣要比这些”学长”或是”大神”靠谱的多得多。


数据结构与算法分析——C语言描述


33



数据结构与算法分析——C语言描述是我学习数据结构的第一本书:当时有很多地方看不懂,于是做记号反复看;代码看不明白,于是抄到本子上反复研读;一些算法想不通,就把它所有的中间状态全画 出来然后反复推演。事实证明尽管这种学习方法看起来傻逼而且效率很低,但对于当时同样傻逼的我却效果不错——傻人用傻办法嘛,而且这本书的课后题大多都是 经典的面试题目,以至于日后我看到编程之美的第一反应就是这货的题目不全是抄别人的么。


至今记得,这本书为了说明算法是多么重要,在开篇就拿最大子序列和作为例子,一路把复杂度从O(N3)杀到O(N2)再到O(NlgN)最后到O(N),当时内心真的是景仰之情=如滔滔江水连绵不绝,尼玛为何可以这么屌。


此外,我当时还把这本书里图算法之前的数据结构全手打了一遍,后来找实习还颇为自得的把这件事放到简历里,现在想想真是傻逼无极限。


凭借这个读书成长计划中学到的知识,我总算比较顺利的找到了一份实习工作,这是后话。


入门

我的实习并没有用到什么算法(现在看来就是不停的堆砌已有的API,编写一堆自己都不知道对不对的代码而已),在发现身边的人工作了几年却还在和我做同样的事情之后,我开始越来越不安。尽管当时我对自己没什么规划,但我清楚这绝壁不是我想做的工作。



微软的梦工厂



在这个摇摆不定的时刻,微软的梦工场成了压倒骆驼的最后一支稻草,这本书对微软亚洲研究院的描写让我下定了”找工作就要这样的公司”的决心,然而我又悲观的发现无论是以我当时的能力还是文凭,都无法达到微软亚研院的要求,矛盾之下,我彻底推翻了自己”毕业就工作”的想法,辞掉实习,准备考研。


考研的细节无需赘述,但至今仍清楚的记得自己在复试时惊奇且激动的发现北航宿舍对面就是微软西格玛大厦,那种离理想又进了一步的感觉简直爽到爆。


算法设计与分析


我的研究生生涯绝对是一个反面典型——翘课,实习,写水论文,做水研究,但有一点我颇为自得——从头到尾认真听了韩军教授的算法设计与分析课程。


韩军给我印象最深的有两点:课堂休息时跑到外面和几个学生借火抽烟;讲解算法时的犀利和毫不含糊。




尽管韩军从来没有主动提及,但我敢肯定算法设计与分析基础就是他算法课程事实上的(de-facto)教材,因为他的课程结构几乎和这本书的组织结构一模一样。


如果数据结构与算法分析——C语言描述是我的数据结构启蒙,那么韩军的课程和算法设计与分析基础就是我的算法启蒙,结合课程和书籍,我一一理解并掌握了复杂度分析、分治、减治、变治、动态规划和回溯这些简单但强大的算法工具。


算法引论



算法引论是我这时无意中读到的另一本算法书,和普通的算法书不同,这本书从创造性的角度出发——如果说算法导论讲的是有哪些算法,那么算法引论讲的就是如何创造算法。结合前面的算法设计与分析基础,这本书把我能解决的算法问题数量扩大了一个数量级。


之后,在机缘巧合下,我进入微软亚洲工程院实习,离理想又近了一步,自我感觉无限牛逼。


巩固

在微软工程院的实习是我研究生阶段的一个非常非常非常重要的转折点:


  1. 做出了一个还说的过去的小项目。

  2. 期间百度实习面试受挫,痛定思痛之下阅读了大量的程序设计书。

  3. 微软的实习经历成为了我之后简历上为数不多的亮点之一(本屌一没成绩,二没论文,三没ACM)。


这里就不说1和3了(和本文题目不搭边),重点说说2。


由于当时组内没有特别多的项目,我负责的那一小块又提前搞定了,mentor便很慷慨的扔给我一个Kinect和一部Windows Phone让我研究,研究嘛,自然就没有什么deadline,于是我就很鸡贼的把时间三七开:七分倒腾Windows Phone,三分看书&经典论文。


然而一件事打断了这段安逸的生活——百度实习面试


基友在人人发百度实习内推贴,当时自我感觉牛逼闪闪放光芒,于是就抱着看看国内IT环境+虐虐面试官的变态心理投了简历,结果在第一面就自己的师兄爆出翔:他让我写一个stof(字符串转浮点数),我磨磨唧唧半天也没写出完整实现,之后回到宿舍赶快写了一个版本发到师兄的邮箱,结果对方压根没鸟我。


这件事对我产生了很大的震动——


  • 原来自己连百度实习面试都过不去。

  • 原来自己还是一个编程弱逼。

  • 原来自己还是一个算法菜逼。


痛定思痛,我开始了第二个”五年计划”,三七开的时间分配变成了七三开:七分看书,三分WP。而这一阶段的重点从原理(Principle)变成了实现(Implementation)——Talk is cheap, show me the code.



原文地址:http://mp.weixin.qq.com/s/orgLQsnFQeBON_VN-qSXqQ

发表评论
评论通过审核后显示。
联系我们