Daily Archives: December 21, 2015


刷题总结 3

刷了Leetcode 308道题和lintcode的一些题,有一些总结和经验,写在这里。 0. General Sense Trade off between space and time 如果时间复杂度要求更高的话,我们就要尝试开辟更多的空间来做trade off。比如从DFS改到DP,开辟DP数组;或者由linear search改成hash table。 Corner cases Overflow, duplicate, negative integers in array, empty input, off-by-one error, etc.. 1. BFS & DFS – 广度优先搜索,深度优先搜索 任何问题都可以用BFS或DFS来解,因为两者的本质是遍历解空间,尝试所有的可能的组合,简单粗暴。但是它们的复杂度会很大,最坏可能达到n^n。 两个算法最终都会遍历整个解空间,不同点在于遍历顺序。BFS会由中心向四周扩散来遍历,适合寻找最短路径的长度;DFS会先一条路走到底,并通过call stack保存访问路径,适合返回符合条件的路径。 相关题目:Number of Islands http://www.sunny-song.com/leetcode-number-of-islands/ 2. DP – 动态规划 DFS 和 BFS的复杂度过大,其中一个原因是他们做了过多的重复计算。我们可以通过开辟DP数组,记录历史数据,来避免重复计算。DP的关键是构造状态转移方程。其中有一维DP数组,二维DP数组,根据情况而定。 在复杂的题目中,我们还需要维护两个DP数组,一个为local,储存局部最优解;一个为global,储存全局最优解。 有一个规律,如果题目中出现given you […]


北美IT求职总结 – Google – New Grad 7

最终去向:Google Software Engineer, New Grad, Mountain View 学校项目:Yale CS MS (一年) 签了Google的offer,withdraw了Bloomberg和Oracle的面试,算是结束了自己的求职之路。激动是有的,因为二十多年来,终于实现了经济独立。 但也有些失落,因为其他的可能性都随之崩塌。近期都不会再碰算法题了,Leetcode的解题记录也停在了308。写下这篇文章,总结求职中的经验和教训,也希望帮到后来人。 图:Shu Tao 白岩松说,永远不要相信老人写的回忆录,因为他们会选择性地回忆过去,只留下筛选后的内容。于是他们的人生轨迹与抉择看起来是那么的顺理成章。我会尽量客观地写这一年来我做的事情,中间有些许经验,也有不少教训。 选择学校 申请学校时我就决定毕业后找工作。出于经济考虑,自己最终从CMU MIIS,Cornell Meng和Yale CS中选择了后者。每当自己在朋友圈或是Facebook上看到CMU的同学凌晨三点发的写代码的状态,就会感慨这可能是自己差一点选择的生活。感慨过后,自己就又去继续思考晚上到底是炖鸡还是炖牛肉的哲学问题去了。 耶鲁的课程对找工作的帮助微乎其微,我想大部分学校的课程都是这样。因为课程目的就不是为了帮助学生找工作,而是训练学生理解计算机原理,甚至是独立思考,和面对未来生活的能力。当然也有学校诸如MIT就开设了Hacking a Google Interview这样的神课,那就是另外一个故事了。不过,耶鲁计算机系的教授单拎出来都是各个领域的神牛。比如Avi Silberschatz,你可能没听过他的名字,但你一定用过他的教材。 此外,在耶鲁读书,还会给你机会认识一群优秀的同学。 练习白板 图:Bo Song 刷题的环境很重要,尤其是能和一群优秀的人一起准备面试。头脑风暴之后,我们往往能把算法复杂度降低一个量级。这种感觉有点像高三复习备战高考,整间教室的人都朝着同一个目标努力。曾和另一位拿了Yale和Cornell Offer,同样纠结去哪家的同学聊天,她觉得刷题的环境和校友资源是选择学校的考量。我表示认同。因为你的水平取决于你周围人水平的平均值,这种影响是潜移默化的。 我本科的一位同学(浙大),本科毕业前就收到了谷歌的offer,同时一位杭州IT公司的老板也极力挽留他。后者开出的价码很诱人,“谷歌给你什么,我就给你什么。并且直接让你领导一个团队。”这位同学讲,最后一个条件对他的诱惑力很大,但转念一想团队里那些人的水平,最终还是选择去谷歌。“很希望与一群优秀的人共事,会让自己也不断进步。”他说。 很有幸能在耶鲁认识这么多优秀的同学,感谢他们带给我的积极影响。我可能是找工作找得最快的一个,但绝对不会是找得最好的一个。祝愿大家都能拿到理想的offer。学校项目可以改变人的气质,我们也可以改造Yale CS MS的形象。 Yale CS MS 2015 Fall 部分同学 图:Aohan Lin 准备面试 我开始刷题(Leetcode)是在2015年1月份,也就是大四下学期,那时刚准备完申请。这里还保存着我Leetcode上AC的第一道题的题解:http://www.sunny-song.com/best-time-to-buy-and-sell-stock/ 如果按照时间顺序从旧到新地看的话,可以一览我的代码从稚嫩笨拙(too young too simple)到还算整洁规范(neat and clean)的成长过程。 […]