中文


Vermont滑雪

跟学联的同学来滑雪,度过圣诞节。 同行的大部分是学长学姐,拖家带口,十六人里有十对。 今年美东遭遇厄尔尼诺,平均气温上升0.4度。雪场的雪都没有多少,只开了k1(黑道)和蓝道,以及儿童乐园。 现在蓝道的底部练了一下,发现上次吉林滑雪的一些知识点自己还依稀记得,内八字,身体前倾,重心放低。 然后直接和张超上了缆车,去了蓝道的顶端。张超说要滑s型,内八字刹不住的。 我一愣,纳尼,我压根没学过s型好吧,直接就给我来个这么陡的坡。 于是我一开始一路都是滚下来的。 后来逐渐掌握了要领,关键是移动重心。重心要在左右脚中来回移动。这样才能转弯,甚至有时要抬起一个雪板。 滑了三次蓝道,很过瘾。最后一次没怎么摔。觉得逐渐掌握了要领。 租了一个大house,晚上十六个人开party。还是挺难忘的回忆。 张超,赵珺,吴宽林,刘婉晴, 鲁乔,黄晨星,Roger,赵祎,翁馨玉,汤晓阳,尘鲁斌,群群,陈卓,王俊,陈全。 陈晨,Vincent,   虽然同为学联的主席,但鲁乔和宣哲民却是完全不同的风格。 后者更有气场,前者更亲民。 当然,这只是我的第一感觉,或许深入了解之后,又会是不一样的感受。


刷题总结 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)的成长过程。 […]


[leetcode] Additive Number

Additive number is a positive integer whose digits can form additive sequence. A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two. For example: “112358” is an additive number because […]