来自豆瓣三个比较好的书评 Read more »
Author Archives: Jipeng Tan
2012: 生命是一个不断慢热积累的持久过程 Part. 1
生命是一个不断慢热积累的持久过程,绝不会因为单一的事件而毁了一个人的一生,也不会因为单一的事件而救了一个人的一生。
2012年To-Do List
- 治好手
- 读完下面的书
- 技术
- Introduction to information retrieval (前5章)
- Head First Design Pattern (全本+习题)
- Effective Java (全本)
- Git/Maven/VI (可以熟练使用基本功能)
- 程序员修炼之道 (全本)
- Hadoop/HBase (根据工作需要)
- Shell/Perl/Python (根据工作需要)
- Code Complete/代码之美 (根据自己的时间需要)
- 非技术
- How to talking to anyone
- 怪诞行为学
- 黑天鹅
- Never Eat Alone
- 异类
你的灯亮着吗- ???
- Coders at work
- Just For Fun
- The American Revolution
- 做好自己的工作
- 口语和写作
- 自己单独做完一个Project
- 看完Index Pipeline的代码,完全了解大家都在做什么
- 多关心一下自己
- 每天最多工作10小时
- 坚持每周3次的锻炼
- 多和别人交流
- 和别人聊天的时候可以聊和技术不相关的事情
- 每周和Cindy看一部电影,每2~3周去一个地方玩
zz 回溯与递归算法的区别
有人说,回溯实际上是递归的展开,但实际上。两者的指导思想并不一致。
打个比方吧,递归法好比是一个军队要通过一个迷宫,到了第一个分岔口,有3条路,将军命令3个小队分别去探哪条路能到出口,3个小队沿着3条路分别前进, 各自到达了路上的下一个分岔口,于是小队长再分派人手各自去探路——只要人手足够(对照而言,就是计算机的堆栈足够),最后必将有人找到出口,从这人开始 只要层层上报直属领导,最后,将军将得到一条通路。所不同的是,计算机的递归法是把这个并行过程串行化了。
而回溯法则是一个人走迷宫的思维模拟——他只能寄希望于自己的记忆力,如果他没有办法在分岔口留下标记(电视里一演到什么迷宫寻宝,总有恶人去改好人的标记)。
以我之见,其实回溯算法跟递归算法不能以类别形式进行比较,只能以算法的形式上进行区别。
回溯算法其 实是一种试探,该方法放弃关于问题规模大小的限制,并将问题的方案按某种顺序逐一枚举和试验。发现当前方案不可能有解时,就选择下一个方案,倘若当前方案 不满足问题的要求时,继续扩大当前方案的规模,并继续试探。如果当前方案满足所有要求时,该方案就是问题的一个解。放弃当前方案,寻找下一介方案的过程称 为回溯。
而递归算法依赖与前一步的结果,它的结果来源于一条主线,是确定的,而不是试探的结果,这就是其与回溯的区别,而在很多情况下,回溯与递归算法是在一起使用的。
看到回溯算法的时候,我想起了人工智能课里面的深度优先算法,为了最大的减少试探,这个是必须地。完~
读算法导论 Elementary Data Structures
去年在面试MS的时候本问到了一个如何把每个child node添加一个right-sibling指针的题目,当时用层遍历写出来了,后来上网搜发现了一种left-child, right-sibling tree,但是一直不明白为什么会有这种数据结构。
最近在读算法导论Elementary Data Structures这一章的时候,发现了一节专门讲这个问题:
一半的二叉树的node结构是
Parent
Left Child Right Child
但是如果我们要每一个node有n的children,那这个表示结果效率就很低了。
首先不清出道题有多少个children,即使知道了做大children的数目n,不能保证每个node都有n个children,所以再用上述的表达方式就很浪费空间。这就是left-child, right-sibling tree存在的意思。
先上一个left-child, right-sibling tree的图

从图中,每个node现在只有3个指针
- left-sibling的指针
- most left child的指针
- 指向parent的指针
这样对于一个有n个children的树的结构就能很好的表示出来了。
Salesforce Phone Screen
Salesforce面了3个phone screen总算遇到一个Java的DEV的职位,感觉这个公司总是喜欢那种从JS+CSS到JAVA到SQL都会的全能人物。
简单说说一下面的题目:
Presentation Layer:
JavaScript是不是面向对象的语言?
JavaScript中prototype是什么意思?
CSS是什么? 如何解释Cascading?
Java:
现在有一个5G的文件存放数字,数字范围从1~1000,内存只有4G如何把5G的文件排序输出到另一个文件?
刚开始相当然的说了外排,或者在内存中简历Min Heap或者loser tree,后来说如何优化,然后就想到了bit map,但是问题是不知到每个数字重复的次数。最后想到的方法就是在内存中简历一个长度为1000的数组,index代表数字,内容是counter。
Database:
什么是normalization,举一个normalization的例子,什么是denormalization,举例
Brain teasers:
经典的疯狗问题的变形,当时完全没有想出来。。。但是总结出来答案就是有多少只狗,就在多少天有枪响。
面的一般,没怎么准备而且外面风很大,估计挂了,move on吧。
组会又被欺负
最近要做的事情很多,本来有一个mapreduce程序要要code review+重构,然后REST API不知道为什么又都要我来做了,然后新开的session anaylsis要读很多的doc,加上间断的有面试,或者被小老板叫过去救火,经常到周五组会的时候忘记自己到底做了多少东西。平时写完一块就跟team mate在IM上确定一下。结果开组会的时候team mate就说我那部分没有做完,影响到到他的进度了,但实际大部分都是我写完了交给他的。这时候再跟他说已经写完了,人家就会一副刚知道的样子说:哦?你写完了。。。当时就觉得很气氛,拿着senior的title,Linkedin上一对recommendation,结果工作就这个态度,还是说看我新来的?
以后不跟这或在IM说上说了,以后进度直接写邮件,然后CC给小老板,但都建一个FOLD来存这写邮件,开会的时候都扫一遍,team wiki一定要没事就刷刷,省得事情太多忙着忙着就忘记了。
Amazon Phone 2nd
今天Amazon2面,customer service tech team。
白人GG。上来什么直接让写代码,什么都没问。题目是求binary tree的高度。写了一个最简单的递归算法,然后让求复杂度,结果悲剧的说成了指数。
然后是test case:null, 1 node, full tree, left > right, right > left, list tree
如果是一个如果书中间有cycle怎么办?回答是hashtable
如果不让用global定义怎么办?回答是加一个参数 treeheight(node, hashtable)
如果不让改变函数接口怎么办?开始没想出来后来说写helper class
treeheight(node) {
treeHeightHelper(node, hashtable)
}
然后45分钟就过去了,不知道能不能还有onsite了,BLESS ME
MapReduce Join操作 (zz+总结)
Amazon Phone 第一轮
总的来说难度偏低,而且常规题目比较多,基本上所有题都在MITBBS上有原题,但是准备的不好,所以打起来感觉很一般。
Coding题目:写一个fibonacci的函数。
重点是可以用try, catch exception来检测不合法输入。递归的写法复杂度是O(2^n)
概念题:
树的定义,查找时间,最好,最坏(n),什么是二叉树。
class:定义了interface/Type/Implementation 细节
object:为止class type的class,class的基础形态
OOD题目:设计一个card游戏
AMAZON OOD的题目一直都不知到思路是什么,然后又问了我个card的题目,就更晕了,只好说不会玩card,面试官也很囧,题目就改成perfect shuffle了。
3月份
今天正好是到RIM 2个月,跟老板谈了前2个月做的东西和剩下2个月的安排。小老板还是一如既往的nice,说错的不做,让我赶快把暑假的schedule定下来。大老板还是很挑,基本上我做的所有东西以后都要大改动。而且很悲剧的是还完全没法跟上他的思路,1个月前第一次谈就是这样,一个月之后还是没有变。基本上谈话的内容可以总结出来:
技术:
- 不了解现在到底在做什么,为什么要这么做。换个说法就是对HADOOP,MAPREDUCE和HBASE的理解还只是停留在WIKI和INTRODUCTION的程度。
- 数据库设计的太教科书,用来当例子没有问题,但是数据量一大一起来就完全没法跑。自己在设计的时候没有考虑到Capacity这个概念。设计的系统能运行多久,最大能存放多少数据?有什么解决方法?也许最后一个问题对于一个intern来说太刁难了,但是头两条在自己做的时候只是感觉会出问题,并没有做真正具体的分析。
- MapReduce Programming上面花的时间还是太少,现在只有一个主程序使用了MR,其它的还是用用J2SE做的,这就导致了第一个问题。
- 需要多看一下用MR实现的算法,大老板提到了一个Shortest Path,这周要看完。
- 实习剩下的计划基本定下来了,根据twitter的格式,先现在的Prototype做一套API,完成界面和数据库的交互。架好cluster,然后写一个MR的程序来完成Session(AppFront, AppBackground, Boudnrate的时间段提取,几个mapper+reducer)
其它:
- 英语还是很差,基本用语没问题,但是想很准备的表示出自己想的想法还是有一些困难,还有2周就要preseatation了。估计有的忙。
瓶颈:
在RIM待了2个月还是没有突破或者有什么明显的变化。发现这个瓶颈是第二个学期,于是第三个学期把自己的生活安排的很满,希望有什么变化,可惜只是感觉自己强了一点,这个学期到RIM实习,刚开始感觉进步很快,但是等到稳定了之后发现自己也只是强了一些,还是看不到突破的影子,最明显的表现就是自己的心态、生活的习惯和跟不上大老板的思维。
开始有些害怕,怕自己就这个样子,毕竟已经不再年轻,不能在挥霍。但是我想我已经不能靠给自己压力和靠所谓的毅力。因为先从规律的生活开始。
懒惰:
自从拿到了RIM的口头OFFER,竟然开始有点懒得找工作了。但是自从去了GOOGLE之后感觉又有了希望。希望能在6月份之前拿到GOOGLE的OFFER,或者起码有一次ON-SITE。
MISC:
最近开始玩WHATSAPP,BBM,FOURSQUARE。。。真有意思,不是很了解为什么会有这么APP,商业模式到底是什么?
Recent Comments