[ZZ]对学生朋友的一点建议

对学生朋友的一点建议

2007年6月1日 上午 11:09:00
发表者：Google（谷歌）中国工程研究院 工程师 方坤

自去年春天加入谷歌，我曾多次随公司校园招聘团队一起走访各地院校，帮助公司发掘人才。利用这样的出差机会到处走走看看，饱览祖国大好河山，是我一点小小的私心。但更具挑战性、更激动人心的，还是和我未来的同事们过招，不打不相识嘛。一想到马上就要和这样优秀的人才一起工作，我就兴奋不已，真恨不得现在就买一张单程机票把他/她拽回北京。

然而，在面试过程中，我也相当惋惜地看到，由于种种主客观原因的限制，很多青春韶华的学子未能充分发挥出他们应有的潜力。这里我不讲成绩，只把我遇到过的一些普遍的问题归纳一下，希望对即将踏入社会的学生朋友们能有些许帮助。

实战！实战！

纸上得来终觉浅，绝知此事要躬行。对于一个未来的软件工程师来说，实际编程经验是相当重要的。我们会要求应聘者在紧凑的时间内编写大量的代码，从中考察应聘者的分析能力，编码速度，代码可读性，对所用编程语言的掌握程度，对边界条件与异常状况的处理，数据结构与函数接口的定义，程序运行的效率和应聘者查错纠错的能力等等。一口气列出这么多要求，听上去似乎过于苛刻，其实只要积累了足够的实战经验，每一个应聘者都完全可以满足这些最低限度的要求。

我记得开复对于青年学子们有一个建议，大学四年，至少要编写 10 万行代码。不是每一个人都期望进入谷歌这样的顶级技术公司，但即使对开复的建议打个三折，也还有 3 万行呢，不努力，能行嘛。前来应聘的学生们在编写代码时暴露出这样那样的问题，大都可以归结到同一个原因：锻炼太少。比如"for (int i = 0; i < strlen(s); ++i)"，没有实战经验的人，怎么可能意识到暗藏其间的效率陷阱。再比如内存泄漏，就和初恋一样，没有亲身经历过的人，不会有刻骨铭心的感受，而一旦经历，终身难忘，根本用不着你有多聪明。遗憾的是，我看到许多相当聪颖的学生写出来的代码只能用惨不忍睹来形容，真让我怀疑这是不是就是他们的第一次。大家不要怪谷歌要求高，恕我直言，如果不能持之以恒，下点儿苦功夫，不光谷歌一家，其它公司恐怕也是进不去的。

北京、上海等地的学生，往往有更多实习、兼职机会，接受锻炼之余，还能攒下一笔小钱作零用之资。其它一些地区的学生也许就没有这么幸运，这就尤其需要积极主动，寻找机会，创造机会，把握机会。世界正在变平，互联网的发展改变着地球的面貌，让不发达地区的学生也能相对容易地接触到发达地区的资源。前不久我在西安遇到一个学生，他半年来一直坚持在北京大学的 ACM 网站上参赛、做题，我看他写出来的程序就确实比他大多数同学都要好一些。我相信，只要他能够持之以恒，还会取得更大的进步。我听说浙江大学的 ACM 网站、TopCoder 网站也都是不错的教育资源，感兴趣的同学不妨一看；虽说做竞赛题距离真正的软件开发还有着显著差别，但也不失为一个不错的出发点。

在积累一定编码量的基础上，我建议大家总结经验教训，不断提高自我。如果几万行代码写下来，学 C++ 的不知道 const 怎么用，学 python 的没听说过 GIL，我看也没什么意思。到了这个阶段，我推荐大家读一些经典的进阶书籍，例如《Effective C++》、《Effective Java》等，即使地处偏远地区，也可通过网上书店买到。（我建议编码量太少的同学就先不要读了，会走火入魔的。我见过有学生连引用和指针都没搞清楚，就在那里重载操作符的。）交流也很重要，如果能够与网上网下志同道合的朋友互相帮助，共同进步，当收事半功倍之效。在这一方面，各校的 Google Camp 也许能够起到一定作用。

"我会写代码呀，为什么谷歌不要我？"

一家外包公司或许会满足于雇佣仅能从事简单的、机械性的重复劳动的软件蓝领，而让谷歌苦苦寻觅的，乃是最优秀的软件工程师兼计算机科学家——是的，在谷歌，研究与开发融为一体，软件工程师与计算机科学家当然也合二为一。计算机这几年算是比较热的，能够得偿所愿挤进计算机科学相关专业的学生都是全中国顶尖的人才，如果大学四年荒芜学业，未能取到真经，浪费了这一来之不易的学习机会，是不是太可惜了呢。

遍历一个数组或链表的时间复杂度是多少？对于这样一个不是问题的问题，竟然各地都有相当数量的学生回答说是 O(logN)！有一次我实在忍不住了，提示应聘的学生说："你是如何理解'遍历'一词的涵义呢？"他立刻做恍然大悟状，回答说："哦，对，应该是 O(NlogN)"。我当时失望得一句话都说不出来。类似的例子还有很多。坊间一直传说谷歌的面试题有多难，其实大多数学生都卡在最基础的问题上。少数人费尽气力要收集谷歌曾经用过的面试题，其实我们大多数题目都来自或改编自经典计算机科学教材的习题。

顺便提一句，上面提到的那个答错的学生乃是一流大学中成绩名列前茅的优秀生，门门功课（包括所有计算机专业课）均在 90 分以上。反差何其大也！

诚信为本

我曾服务于多家公司，注意到不同的公司之间，乃至同一公司内不同的面试官之间，对应聘者的要求都会有所差别，或看重潜质，或偏好经验，或强调态度。但有一点大家是共同的：如果应聘者在诚信上有疑问，谁也不敢要。

总体而言，现在的学生其诚信还是相当不错的，大大超出了我们的期望。然而，不和谐音也还是有的。我们曾在某著名高校进行笔试，就发现有学生严重作弊，他们毁掉自己的机会不说，整个学校的名声也受到拖累。面试中偶尔也能遇到诚信堪忧的学生。有一次我出了一道题，前来应聘的学生明明以前见过这道题，却告诉我说没见过，自以为得计，可他那一纵即逝的狡黠一笑哪里逃得过我洞若观火的锐利眼神。大哥，你又不是专业演员，为什么要玩这样的花招？我每年面试的求职者在百人以上，捣鬼是过不了我这一关的。两点之间直线最，说真话最简单。

做最好的自己

不是每一个人都会加入某一家具体的公司，但每一个人都可以成功，成为最好的自己。我这里所谈，既不系统亦欠简练，但确实是我在几次校园招聘之旅中发现的一些具有共性的问题，故不避好为人师之讥，罗列于此。我当然知道，本文的首要目标读者——大一新生是不听劝的，他们更愿意把所有的错误亲自重犯一遍。话虽如此，只要能够对一个学生有所启迪，我的时间就不算白费。

[ZZ]胡侃学习(理论)计算机

作者是南大毕业的，现在美国某校做教授
看完以后我实在不好意思说自己是计算机科学与技术专业的毕业生。

发信人: sir (阿涩), 信区: Mathematics
标 题: 胡侃学习(理论)计算机(0)
发信站: 南京大学小百合站 (Mon Oct 8 03:57:41 2001), 站内信件

我也来冒充一回高手，谈谈学习计算机的一点个人体会。
由于我是做理论的，所以先着重谈谈理论。

记得当年大一，刚上本科的时候，每周六课时数学分析，
六课时高等代数，天天作业不断(那时是六日工作制)。
颇有些同学惊呼走错了门:咱们这到底念的是什么系？
不错，你没走错门，这就是(当时的)南大计算机系。系
里的传统是培养做学术研究，尤其是理论研究的人。而
计算机的理论研究，说到底了就是数学，虽然也许是
正统数学家眼里非主流的数学。

数学分析这个东东，咱们学计算机的人对它有很复杂
的感情。爱它在于它是第一门，也是学分最多的一门
数学课，又长期为考研课程--94以前可以选考数学分析
与高等代数，以后则并轨到著名的所谓“工科数学一”。
其重要性可见一斑。恨它则在于它好象难得有用到的
机会，而且思维跟咱们平常做的这些离散/有限的工作
截然不同。当年出现的怪现象是：计算机系学生的高中
数学基础在全校数一数二(希望没有冒犯其它系的同学)，
教学课时数也仅次于数学系，但学完之后的效果却几
乎是倒数第一。其中原因何在，发人深思。

我个人的浅见是：计算机类的学生，对数学的要求固然
跟数学系不同，跟物理类差别则更大。通常非数学专业
的所谓“高等数学”，无非是把数学分析中较困难的理论
部分删去，强调套用公式计算而已。而对计算机系来说，
数学分析里用处最大的恰恰是被删去的理论部分。说得
难听一点，对计算机系学生而言，追求算来算去的所谓
“工科数学一”已经彻底地走进了魔道。记上一堆曲面积分
的公式，难道就能算懂了数学分析？

中文的数学分析书，一般都认为以北大张筑生老师的
“数学分析新讲”为最好。我个人认为南大数学系的“数学
分析教程”也还不错，至少属于典型的南大风格，咱们
看着亲切。随便学通哪一本都行。万一你的数学实在
太好，这两本书都吃不饱，那就去看菲赫金哥尔茨的
“微积分学教程”好了--但我认为没什么必要，毕竟你
不想转到数学系去。

吉米多维奇的“数学分析习题集”也基本上是计算型的
东东。如果你打算去考那个什么“工科数学一”，可以
做一做。否则，不做也罢。

中国的所谓高等代数，就等于线性代数加上一点多项式
理论。我以为这有好的一面，因为可以让学生较早感觉
到代数是一种结构，而非一堆矩阵翻来覆去。当年我们
用林成森，盛松柏两位老师编的“高等代数”，感觉相当
舒服，我直到现在还保留着教材。此书相当全面地包含
了关于多项式和线性代数的基本初等结果，同时还提供
了一些有用的比较深的内容，如Sturm序列，Shermon
-Morrison公式，广义逆矩阵等等。可以说，作为本科
生如能吃透此书，就可以算高手。后来它得以在南大出
版社出版，可惜好象并轨以后就没有再用了。

国内较好的高等代数教材还有清华计算机系用的那本，
清华出版社出版，书店里多多，一看就知道。特点嘛，
跟南大那本差不太多。

但以上两本书也不能说完美无缺。从抽象代数的观点
来看，高等代数里的结果不过是代数系统性质的一些
例子而已。莫宗坚先生的“代数学”里，对此进行了深刻
的讨论。然而莫先生的书实在深得很，作为本科生恐
怕难以接受，不妨等到自己以后成熟了一些再读。

概率论与数理统计这门课很重要，可惜少了些东西。

少了的东西是随机过程。到毕业还没有听说过Markov
过程，此乃计算机系学生的耻辱。没有随机过程，
你怎么分析网络和分布式系统？怎么设计随机化算法
和协议？据说清华计算机系开有“随机数学”，早就是
必修课。人家可是工科学校，作为自以为“理科计算机
系”出身的人，我感到惭愧。

另外，离散概率对计算机系学生来说有特殊的重要性。
现在，美国已经有些学校开设了单纯的“离散概率论”
课程，干脆把连续概率删去，把离散概率讲深些。我们
不一定要这么做，但应该更加强调离散概率是没有疑
问的。

计算方法是最后一门由数学系给我们开的课。一般学生对
这门课的重视程度有限，以为没什么用。其实，做图形
图像可离不开它。而且，在很多科学工程中的应用计算，
都以数值的为主。

这门课有两个极端的讲法：一个是古典的“数值分析”，
完全讲数学原理和算法；另一个是现在日趋流行的“科学
与工程计算”，干脆教学生用软件包编程。南大数学系
的几位老师做了件大好事，把前者的一本极为经典的
教材翻译出版了：德国Stoer的“数值分析引论”。如果
你能学会此书中最浅显的三分之一，就算没有白上过
计算方法这门课！而后一种讲法似乎国内还没有跟上
潮流？不过，只要你有机会在自己的电脑上装个matlab
之类，完全可以无师自通。

本系里，通常开一门离散数学，包括集合论，图论，
和抽象代数，另外再单开一门数理逻辑。这样安排，
主要由于南大的逻辑传统：系里很多老师都算莫先生
的门人，就连孙先生都是逻辑专业出身(见孙先生自
述)。

不过，这么多内容挤在离散数学一门课里，是否
时间太紧了点？另外，计算机系学生不懂组合和
数论，也是巨大的缺陷。要做理论，不懂组合或
者数论吃亏可就太大了。

从理想的状态来看，最好分开六门课：集合，
逻辑,图论，组合，代数，数论。这个当然不现实，
因为没那么多课时。也许将来可以开三门课：集合
与逻辑，图论与组合，代数与数论。

不管课怎么开，学生总一样要学。下面分别谈
谈上面的三组内容。

古典集合论，北师大出过一本“基础集合论”不错。
南大出版朱梧(木贾)老师的“集合论导引”也许观点更
高些，但他的书形式化得太厉害，念起来吃力。

数理逻辑，莫先生的书自然是经典。然而我们也
不得不承认，此书年代久远，光读它恐怕不够。
尤其是命题/谓词演算本身有好多种不同的讲法，
多看几家能大大开阔自己的视野。例如陆钟万老师
的“面向计算机科学的数理逻辑”就不错。朱老师也
著有“数理逻辑教程”一书，但也同样读起来费力些。

总的来说，学集合/逻辑起手不难，但越往后越感觉
深不可测。建议有兴趣的同学读读朱老师的“数学
基础引论”--此书有点时间简史的风格，讲到精彩处，
所谓“天花乱坠，妙雨缤纷”，令人目不暇接。读完
以后，你对这些数学/哲学中最根本的问题有了个大概
了解，也知道了山有多高，海有多深。
学完以上各书之后，如果你还有精力兴趣进一步
深究，那么可以试一下GTM系列中的"Introduction
to Axiomatic Set Theory"和"A Course of Mathematical
Logic"。这两本都有世界图书的引进版。你如果
能搞定这两本，可以说在逻辑方面真正入了门，
也就不用再浪费时间听我瞎侃了。：)

据说全中国最多只有三十个人懂图论(当年上课时陈道蓄
老师转引张克民老师的话)。此言不虚。图论这东东，
技巧性太强，几乎每题都有一个独特的方法，让人头痛。
不过这也正是它魅力所在：只要你有创造性，它就能
给你成就感。所以学图论没什么好说的，做题吧。

国内的图论书中，王树禾老师的“图论及其算法”非常
成功。一方面，其内容在国内教材里算非常全面的。
另一方面，其对算法的强调非常适合计算机系(本来
就是科大计算机系教材)。有了这本书为主，再参考
几本翻译的，如Bondy&Murty的“图论及其应用”，
邮电出版社翻译的“图论和电路网络”等等，就马马
虎虎，对本科生足够了。

再进一步，世界图书引进有GTM系列的"Modern
Graph Theory"。此书确实经典！国内好象还有一
家出版了个翻译版。不过，学到这个层次，还是
读原版好。搞定这本书，也标志着图论入了门，呵呵。
组合感觉没有太适合的国产书。还是读Graham和Knuth
等人合著的经典“具体数学”吧，有翻译版，西电出的。

抽象代数，国内经典为莫宗坚先生的“代数学”。此书
是北大数学系教材，深得好评。然而对本科生来说，
此书未免太深。可以先学习一些其它的教材，然后
再回头来看“代数学”。国际上的经典可就多了，GTM
系列里就有一大堆。推荐一本谈不上经典，但却最简
单的，最容易学的：
http://www.math.miami.edu/...
这本“Introduction to Linear and Abstract Algebra"
非常通俗易懂，而且把抽象代数和线性代数结合起来，
对初学者来说非常理想。不过请注意版权问题，不要
违反法律噢。

数论方面，国内有经典而且以困难著称的”初等数论“
(潘氏兄弟著，北大版)。再追溯一点，还有更加经典
(可以算世界级)并且更加困难的”数论导引“(华罗庚先生
的名著，科学版，九章书店重印)。把基础的几章搞
定一个大概，对本科生来讲足够了。但这只是初等数
论。本科毕业后要学计算数论，你必须看英文的书，
如Bach的"Introduction to Algorithmic Number Theory"

理论计算机的根本，在于算法。现在系里给本科生
开设算法设计与分析，确实非常正确。环顾西方世界，
大约没有一个三流以上计算机系不把算法作为必修的。

算法教材目前公认以Corman等著的"Introduction to
Algorithms"为最优。对入门而言，这一本已经足够，
不需要再参考其它书。南大曾翻译出版此书，中文名
为”现代计算机常用数据结构与算法“。pie好象提供了
网上课程的link，我也就不用废话。

最后说说形式语言与自动机。我们用过北邮的教材，
应该说写的还清楚。但是，有一点要强调：形式语言
和自动机的作用主要在作为计算模型，而不是用来
做编译。事实上，编译前端已经是死领域，没有任何
open problem。如果为了这个，我们完全没必要去学
形式语言--用用yacc什么的就完了。北邮的那本，在深
度上，在跟可计算性的联系上都有较大的局限，现代
感也不足。所以建议有兴趣的同学去读英文书......不过
英文书中好的也不多，而且国内似乎没引进这方面的
教材。

入门以后，把形式语言与自动机中定义的模型，和
数理逻辑中用递归函数定义的模型比较一番，可以
说非常有趣。现在才知道，什么叫”宫室之美，百官
之富“！

发信人: sir (阿涩), 信区: Mathematics
标 题: 胡侃学习计算机--理论之外(0)
发信站: 南京大学小百合站 (Mon Oct 15 05:26:00 2001), 站内信件

如果计算机只有理论，那么它不过是数学的一个分支，而
不成为一门独立的科学。事实上，在理论之外，计算机
科学还有更广阔的天空。我一直认为，4年根本不够学习
计算机的基础知识，因为面太宽了......


一个一流计算机系的优秀学生决不该仅仅是一个编程高
手，但他一定首先是一个编程高手。

我上大学的时候，第一门专业课时程序设计，现在好象
改成了计算机科学导论？不管叫什么名字，总之，念计
算机的人就是靠程序吃饭。

去年在计算机系版有过一场争论，关于第一程序设计语言
该用哪一种。我个人认为，用哪种语言属于末节，关键在
养成良好的编程习惯。当年老师对我们说，打好基础后
学一门新语言只要一个星期。现在我觉得根本不用一个
星期--前提是先把基础打好。

数据结构有两种不同的上法：一种把它当成降低要求的
初级算法课，另一种把它当成高级的程序设计课。现在
国内的课程好象介乎两者之间，而稍偏向前者。我个人
认为，假如已经另有必修的算法课，恐怕后一个目的更
重要些。

国内流行的数据结构书也有两种：北大的红皮书(许卓
群等著，高教版)和清华的绿皮书(严蔚敏等著，清华版)。
两书差距不大。红皮书在理论上稍深一些，当然离严格
的算法书还差好远。绿皮书更易接受些，而且佩有一本
不错的习题集，但我觉得它让学生用伪代码写作业恐怕
不见得太好。最好还是把算法都code以后debug一番，
才能锻炼编程能力。

汇编预言和微机原理是两门特烦人的课。你的数学/理论
基础再好，也占不到什么便宜。这两门课之间的次序也
好比先有鸡还是先有蛋，无论你先学哪门，都会牵扯另
一门课里的东西。所以，只能静下来慢慢琢磨。这就是
典型的工程课，不需要太多的聪明和顿悟，却需要水滴
石穿的渐悟。

有关这两门课的书，电脑书店里不难找到。弄几本最新
的，对照着看吧。

模拟电路这东东，如今不仅计算机系学生搞不定，
电子系学生也多半害怕。如果你真想软硬件通吃，那么
建议你先看看邱关源的“电路原理”，也许此后再看模拟
电路底气会足些。

教材：康华光的“电子技术基础”还是不错的。有兴趣也
可以参考童诗白的书。

数字电路比模拟电路要好懂得多。阎石的书也算一本好
教材，遗憾的一点是集成电路讲少了些。真有兴趣，到
东南无线电系去旁听他们的课。

计算机系统结构该怎么教，国际上还在争论。国内能找
到的较好教材为Stallings的"Computer Organization
and Architecture:Designing for Performance"(清华影印
本)。国际上最流行的则是“Computer architecture: a
quantitative approach", by Patterson & Hennessy。

操作系统可以随便选用Tanenbaum的"Operating System
Design and Implementation"和"Modern Operating
System"两书之一。这两部都可以算经典，唯一缺点
就是理论上不够严格。不过这领域属于Hardcore System,
所以在理论上马虎一点也情有可原。

如果先把形式语言学好了，则编译原理中的前端我看只要
学四个算法：最容易实现的递归下降；最好的自顶向下
算法LL(k)；最好的自底向上算法LR(k)；LR(1)的简
化SLR(也许还有另一简化LALR?)。后端完全属于工程
性质，自然又是another story。

推荐教材：
Aho等人的著名的Dragon Book: "Compilers: Principles,
Techniques and Tools".
或者Appel的"Modern Compiler Implementation in C".

学数据库的第一意义是告诉你，会用VFP编程不等于懂
数据库。(这世界上自以为懂数据库的人太多了！)数据库
设计既是科学又是艺术，数据库实现则是典型的工程。
所以从某种意义上讲，数据库是最典型的一门计算机课
--理工结合，互相渗透。

推荐教材：Silberschatz, et al., "Database System
Concepts".

网络的标准教材还是来自Tanenbaum:”Computer
Networks"(清华影印本)。不过，网络也属于Hardcore
System，所以光看书是不够的。建议多读RFC，从
IP的读起。等到能掌握10种左右常用协议，就没有几个
人敢小看你了。

必须结束这篇“胡侃”了，再侃下去非我力所能及。其实
计算机还有很多基础课都值得一侃，如程序设计语言原
理，图形图像处理，人工智能等等。怎奈我造诣有限，
不敢再让内行耻笑。

最后声明：前后的两篇“胡侃”只针对本科阶段的学习。
即使把这些全弄通了，前面的路还长......

[ZZ]李开复：算法的力量

算 法是计算机科学领域最重要的基石之一，但却受到了国内一些程序员的冷落。许多学生看到一些公司在招聘时要求的编程语言五花八门就产生了一种误解，认为学计 算机就是学各种编程语言，或者认为，学习最新的语言、技术、标准就是最好的铺路方法。其实大家都被这些公司误导了。编程语言虽然该学，但是学习计算机算法 和理论更重要，因为计算机算法和理论更重要，因为计算机语言和开发平台日新月异，但万变不离其宗的是那些算法和理论，例如数据结构、算法、编译原理、计算 机体系结构、关系型数据库原理等等。在“开复学生网”上，有位同学生动地把这些基础课程比拟为“内功”，把新的语言、技术、标准比拟为“外功”。整天赶时 髦的人最后只懂得招式，没有功力，是不可能成为高手的。

算法与我

当我在1980年转入计算机科学系时，还没有多少人的专业方向是计算机科学。有许多其他系的人嘲笑我们说：“知道为什么只有你们系要加一个‘科学 ’，而没有‘物理科学系’或‘化学科学系’吗？因为人家是真的科学，不需要画蛇添足，而你们自己心虚，生怕不‘科学’，才这样欲盖弥彰。”其实，这点他们 彻底弄错了。真正学懂计算机的人（不只是“编程匠”）都对数学有相当的造诣，既能用科学家的严谨思维来求证，也能用工程师的务实手段来解决问题——而这种 思维和手段的最佳演绎就是“算法”。

记得我读博时写的Othello对弈软件获得了世界冠军。当时，得第二名的人认为我是靠侥幸才打赢他，不服气地问我的程序平均每秒能搜索多少步棋， 当他发现我的软件在搜索效率上比他快60多倍时，才彻底服输。为什么在同样的机器上，我可以多做60倍的工作呢？这是因为我用了一个最新的算法，能够把一 个指数函数转换成四个近似的表，只要用常数时间就可得到近似的答案。在这个例子中，是否用对算法才是能否赢得世界冠军的关键。

还记得1988年贝尔实验室副总裁亲自来访问我的学校，目的就是为了想了解为什么他们的语音识别系统比我开发的慢几十倍，而且，在扩大至大词汇系统 后，速度差异更有几百倍之多。他们虽然买了几台超级计算机，勉强让系统跑了起来，但这么贵的计算资源让他们的产品部门很反感，因为“昂贵”的技术是没有应 用前景的。在与他们探讨的过程中，我惊讶地发现一个O(n*m)的动态规划(dynamic programming)居然被他们做成了O (n*n*m)。更惊讶的是，他们还为此发表了不少文章，甚至为自己的算法起了一个很特别的名字，并将算法提名到一个科学会议里，希望能得到大奖。当时， 贝尔实验室的研究员当然绝顶聪明，但他们全都是学数学、物理或电机出身，从未学过计算机科学或算法，才犯了这么基本的错误。我想那些人以后再也不会嘲笑学 计算机科学的人了吧！

网络时代的算法

有人也许会说：“今天计算机这么快，算法还重要吗？”其实永远不会有太快的计算机，因为我们总会想出新的应用。虽然在摩尔定律的作用下，计算机的计 算能力每年都在飞快增长，价格也在不断下降。可我们不要忘记，需要处理的信息量更是呈指数级的增长。现在每人每天都会创造出大量数据（照片，视频，语音， 文本等等）。日益先进的纪录和存储手段使我们每个人的信息量都在爆炸式的增长。互联网的信息流量和日志容量也在飞快增长。在科学研究方面，随着研究手段的 进步，数据量更是达到了前所未有的程度。无论是三维图形、海量数据处理、机器学习、语音识别，都需要极大的计算量。在网络时代，越来越多的挑战需要靠卓越 的算法来解决。

再举另一个网络时代的例子。在互联网和手机搜索，如果要找附近的咖啡店，那么搜索引擎该怎么处理这个请求呢？最简单的办法就是把整个城市的咖啡馆都 找出来，然后计算出它们的所在位置与你之间的距离，再进行排序，然后返回最近的结果。但该如何计算距离呢？图论里有不少算法可以解决这个问题。

这么做也许是最直观的，但绝对不是最迅速的。如果一个城市只有为数不多的咖啡馆，那么这么做应该没什么问题，反正计算量不大。但如果一个城市里有很多咖啡馆，又有很多用户都需要类似的搜索，那么服务器所承受的压力就大多了。在这种情况下，我们该怎样优化算法呢？

首先，我们可以把整个城市的咖啡馆做一次“预处理”。比如，把一个城市分成若干个“格子(grid)”，然后根据用户所在的位置把他放到某一个格子里，只对格子里的咖啡馆进行距离排序。

问题又来了，如果格子大小一样，那么绝大多数结果都可能出现在市中心的一个格子里，而郊区的格子里只有极少的结果。在这种情况下，我们应该把市中心 多分出几个格子。更进一步，格子应该是一个“树结构”，最顶层是一个大格——整个城市，然后逐层下降，格子越来越小，这样有利于用户进行精确搜索——如果 在最底层的格子里搜索结果不多，用户可以逐级上升，放大搜索范围。

上述算法对咖啡馆的例子很实用，但是它具有通用性吗？答案是否定的。把咖啡馆抽象一下，它是一个“点”，如果要搜索一个“面”该怎么办呢？比如，用 户想去一个水库玩，而一个水库有好几个入口，那么哪一个离用户最近呢？这个时候，上述“树结构”就要改成“r-tree”，因为树中间的每一个节点都是一 个范围，一个有边界的范围（参考:http://www.cs.umd.edu/~hjs/rtrees/index.html）。

通过这个小例子，我们看到，应用程序的要求千变万化，很多时候需要把一个复杂的问题分解成若干简单的小问题，然后再选用合适的算法和数据结构。

并行算法：Google的核心优势

上面的例子在Google里就要算是小case了！每天Google的网站要处理十亿个以上的搜索，GMail要储存几千万用户的2G邮箱， Google Earth要让数十万用户同时在整个地球上遨游，并将合适的图片经过互联网提交给每个用户。如果没有好的算法，这些应用都无法成 为现实。

在这些的应用中，哪怕是最基本的问题都会给传统的计算带来很大的挑战。例如，每天都有十亿以上的用户访问Google的网站，使用Google的服 务，也产生很多很多的日志(Log)。因为Log每份每秒都在飞速增加，我们必须有聪明的办法来进行处理。我曾经在面试中问过关于如何对Log进行一些分 析处理的问题，有很多面试者的回答虽然在逻辑上正确，但是实际应用中是几乎不可行的。按照它们的算法，即便用上几万台机器，我们的处理速度都根不上数据产 生的速度。

那么Google是如何解决这些问题的？

首先，在网络时代，就算有最好的算法，也要能在并行计算的环境下执行。在Google的数据中心，我们使用的是超大的并行计算机。但传统的并行算法 运行时，效率会在增加机器数量后迅速降低，也就是说，十台机器如果有五倍的效果，增加到一千台时也许就只有几十倍的效果。这种事半功倍的代价是没有哪家公 司可以负担得起的。而且，在许多并行算法中，只要一个结点犯错误，所有计算都会前功尽弃。

那么Google是如何开发出既有效率又能容错的并行计算的呢？

Google最资深的计算机科学家Jeff Dean认识到，Google所需的绝大部分数据处理都可以归结为一个简单的并行算法：Map and Reduce（http://labs.google.com/papers/mapreduce.html）。 这个算法能够在很多种计算中达到相当高的效率，而且是可扩展的（也就是说，一千台机器就算不能达到一千倍的效果，至少也可以达到几百倍的效果）。 Map and Reduce的另外一大特色是它可以利用大批廉价的机器组成功能强大的server farm。最后，它 的容错性能异常出色，就算一个 server farm宕掉一半，整个fram依然能够运行。正是因为这个天才的认识，才有了Map and Reduce算法。借助该算法， Google几乎能无限地增加计算量，与日新月异的互联网应用一同成长。

算法并不局限于计算机和网络

举一个计算机领域外的例子：在高能物理研究方面，很多实验每秒钟都能几个TB的数据量。但因为处理能力和存储能力的不足，科学家不得不把绝大部分未 经处理的数据丢弃掉。可大家要知道，新元素的信息很有可能就藏在我们来不及处理的数据里面。同样的，在其他任何领域里，算法可以改变人类的生活。例如人类 基因的研究，就可能因为算法而发明新的医疗方式。在国家安全领域，有效的算法可能避免下一个911的发生。在气象方面，算法可以更好地预测未来天灾的发 生，以拯救生命。

所以，如果你把计算机的发展放到应用和数据飞速增长的大环境下，你一定会发现；算法的重要性不是在日益减小，而是在日益加强。

2005届cs ss大牛的求职小结

今天在学院的网页上看到“就业之星”Yu Xing前辈的就业小结，非常精彩。想必不论是本科的小弟弟妹妹们还是和我们这样的即将面临就业的ss们，都是很有帮助的。特别是文中提到了作为一个计算机牛人所应该具备的某些素质。感慨：如果不想走弯路的xdjm们一定要好好规划自己的学习道路～～

原文如下：

随着work版的人数下降到三位数，06-07年度的Job Hunter大潮渐行渐远了。在大潮中淘到金的实不胜数，我也只是其中比较幸运的一位而已——拿到了大多数计算机系学生梦寐以求的Google的 Offer。另外，在研究生期间，我曾担任过微软技术俱乐部主席的职务，使得我与微软有着很深层的接触，再加上找工作期间也面了不少IT名企，希望我在这里共享的经验，可以帮助大家在来年找到称心如意的职位。:)

一、内练一口气，外练筋骨皮
先引用一段我同寝的杨超（他也拿到了Google的Offer）的一段我很佩服的话吧：“大三，还年轻，没必要追技术，不然很容易浮沙高台的。还是好好打牢基础吧，什么The Art of Computer Programming啊，Introduction to Algorithms啊，Concrete Mathematics啊，把它看上个十遍八遍，英语也最好能学好。这其实就是和练武功一样的，内功牛了，根本不必在乎这些外家的招式，就像张君宝，有了九阳神功的内力，就算使套平常的武当长拳也照样牛。”

其实找工作也是一样的，招聘其实就是把自己的内力展示给公司看的过程，实力是一切的保证。所以，要找到满意的工作，首先在大学的学习期间要努力扩充自己的知识，这样才能在最后游刃有余，笑傲江湖。

当然也不是说外家招式没用，在内功充盈的情况下，再去锻炼一下实际的能力是非常有益处的。一方面增强了实际经验，而很多公司在面试的时候就喜欢从实际情况中选题让你去分析；另一方面也巩固了理论知识，实践是检验真理的唯一标准嘛。至于实践方式，则不一而足。举个例子说，如果对算法感兴趣的，可以去参加校算法竞赛，加入集训队系统学习训练，接下来争取参加Regional甚至World Final，在做题和比赛中领悟算法的真谛；如果是潜心于软件开发的，那么认真做实验室的项目，也可以自己抽空去做做一些有意义的实际开发兼职，要相信每一笔认真的付出都会是你面试时候的一个资本。

总之，先争取可以当上一名内外兼修的武林高手，那么你离成功已经不远了。

二、Who am I?
事实上，“内家功夫”是有很多种的，也绝少有人可以做到兼各家所长。既然各人有各人的长处，那么明确地知道自己长于何处，短在何方是很有必要的。

因为不同的公司对人才有自己的定义，他们各自需要有不同技能特点的员工，因而笔试面试等考核的方向也不一样。比如说，Google喜欢有算法背景的学生，需要应聘者有扎实的基本功，严谨的逻辑思考能力和足够的智力水平，所以Google的面试方向主要是数据结构与算法题，计算机基础知识和一些puzzle；我也面试过Microsoft的ATC（亚洲工程院），面试过程与Google比较类似，不过ATC要求更多的工程能力，比如在现场编程的时候，要求更多的Exception Handling，还要求有完整的Test Case（Accuracy/Failure/Stress），而在算法难度上则比Google要求低一些；而Autodesk要求较强的C++能力和 MFC基础，NI要求扎实的C++基本功，Morgan Stanley要求清晰的逻辑、至少一样过硬的技术和优秀的项目经验……

优秀的公司千千万，只有明白自己的长处才能选择出适合自己的应聘方向，并不是所有的牛企、名企、米企都适合每个人投的。比如你不擅长算法编程，那么你在面试Google和Microsoft的时候肯定会觉得吃力；比如你所长是Java，那么去一家只要C++的公司吃闭门羹的概率也会非常大。

知己知彼，百战不殆，这句兵法的箴言用在这里再恰当不过了。

三、君子坦荡荡
这里的意思是说，在面试的时候，要体现真实的自我。

面试官们都是身经百战的，你的隐瞒基本上很难逃过他的目光。比如在Microsoft，面试时的5位面试官在每一轮面试完之后，是有一次碰头会议的，除非你“圆谎”的能力无与伦比，否则一点点纰漏也会在面试官之间的交流下无所遁形。公司对诚信看的是很重要，即便不是什么严重的隐瞒，可能也会使你的分数大打折扣。

我在面试微软的时候，最后一轮的Boss面。前面的编程我完成的很出色，接下来的技术聊天中，作为.Net资深专家的他问了我一些. Net底层方面的问题。其实.Net我用的非常多，不过大多是在项目开发中，对于底层的实现，我却没有深究过。于是我只能按照我的想法，和对于C++， JAVA等的经验，尽我所能地来回答他的问题。面试结束后，Boss对我说，他相信我不是不懂装懂，但是对于自己不知道的问题，应该大胆地说“我不知道”，要“truly be yourself”，没有一个人可以什么都懂的，学习的态度和诚实的精神在一定程度上比优秀的学识更重要。这些话，我拿出来与大家共勉。

四、三日自省吾身，自信自然出色
在笔试面试过程中遇到的失败是很正常的，失败是成功之母嘛。但如果不对前面的失败进行归纳总结，那么接下来等着你的，可能还会是失败。

我曾看到过有人在被拒之后义愤填膺，在BBS上谴责甚至诅咒对方公司，这些都是没有必要的。找工作如同寻找生活中的另一半，是一个双向选择的过程；公司没有选择自己，是自己表现不够优秀，或者也可能是双方不合适。与其不满，还不如低下头来深省一下自身来的有效得多。

首先问问自己，我在笔试或者面试的过程中，有没有哪里有缺陷，做得不好的。比如说有哪部分知识掌握得不够清晰，那么在去面试下一个同类型公司的时候，先要把这部分补上；或者说是因为面试迟到导致面试官不满而失败的，那么下次要留心守时了，等等。

另外，要看看自己在面试之前是不是准备得足够充分。这里要提出的一点是，给各个公司的简历并不应该都一样。简历是应聘者的门面，不同的公司对应聘者的能力方向要求不同，那么在他们看简历的时候对于你的各方面表现评价也会不同。可能公司A特别看重的你的这个特质，而在公司B那里就不是那么重要。所以，如果时间充裕，应该针对不同类型的公司制作不同的简历。还有最好在面试前多认真了解一下目标公司，这会使你在面试的时候比较得心应手，对于面试官来说，他也会欣喜你的诚意，同时也是一种对自己负责任的态度。

在遭受被拒的打击后，千万不要自暴自弃，要以良好的心态去相信“天生我材必有用”。然后做出更大的努力去争取下一次成功。我在最终被Google录取之前，也受到过几次失败，但我始终在下一次尝试的时候面带笑容，信心满满。成功源于心态，我觉得确实是这样。

五、海投or not，这是个问题
另外，来说下海投，我总共投了6、7个公司，算不得多，因为我个人不喜欢海投。海投的问题在于，除非一路下来顺理成章地收了很多 offer，否则一连串的打击肯定会对后面的面试心态产生影响，到了自己真正心仪的公司可能就发挥不出来；另外，数个月来回奔波对于体力是一个考验，这也会影响到后面的面试状态。

在这里说一个故事，在森林里面有一群猴子，有一天有一只猴子捡到一只手表，聪明的他很快搞清楚了手表的作用，于是乎猴群有了在阴雨天也可以知道时间的智者，他于是就被封为王。猴王认为是手表给了他一切，于是他拼命在森林里找寻第二只第三只手表。不幸的是，后面捡来手表的时刻都不一致，由于弄不清究竟哪个时间是对的，面对来询问时间的猴子，猴王也只能支支吾吾，直至被赶下王位了事。

这个“手表定律”带给我们一种非常直观的启发：对于任何一件事情，不能同时设置两个不同的目标，否则将使这件事情难以完成。

我觉得对于找工作，虽然不能说定多个目标一定不好，但是定太多的目标是肯定会互相干扰的。所以应该选择合适的公司，有目的有主次地去尝试，同时要学会适度地中途放弃。

但是肯定有人会说，海投也没什么不好，一方面我可以承受得住，另一方面这可以增加我的面试经验。嗯，这个理由我也认同，因为这本来就是个仁者见仁，智者见智的问题么。:)

六、与善人居，如入芝兰之室
最后在这里，顺便提一下学习生活环境的问题，也同时感谢我的室友、朋友们对我的促进和帮助。

熟悉我的人都知道，我大一时候的成绩是比较差的，但是到了本科后半段，尤其是研究生阶段，学习成绩突飞猛进，技术能力也进步神速。这一方面是个人自制力的问题，另一方面就是我找到了一个可以帮助我促使我进步的集体——算法集训队。研究生和我同寝室的，也都是集训队的翘楚，在他们的帮助下和日常交流中，我真的学到了很多东西。于是我借这里向他们几个以及整个集训队说声谢谢。

多和优秀的人在一起，你也会学着变得优秀的。这是真的。

已经写的比较长了，就在这里收尾吧。祝大家都能心想事成，愿我们浙江大学的牌子在业界内越打越响。Best Wishes to all! :)