Bloomberg

原帖地址:一亩三分地

昨天上午面的,第一次onsite, 准备了好久,面经也看了,结果两轮游了。
Round1:
中国小哥主面,白人小哥shadow。随便问了问简历然后就开始出题了。代码我都是用python写的。
Q1: Reverse LinkedList,我开始用循环写的,他说可以,然后要我用递归写,写完给了一个case要我walk through一下。然后设计test case.
Q2: LRU cache. 开始我说用python里的OrderedDict, 他说可以。follow up不用OrderedDict怎么实现,我说OrderedDict内部实际上就是hashmap+linedlist, 所以可以用hashmap+doubly linked list. get set 都是O(1)
Q3: Binary Tree Right Side View. 开始我用两个list实现bfs, print 每层的最后一个node. follow up能不能用一个queue实现,我说可以,层与层之间push一个None节点进去用来区分,如果不能push None怎么办,那就用一个count统计每层节点数。
然后问他们问题。感觉这一轮挺顺利的,还蛮开心。
Round2:
进来两个中国人,一个挺客气的,另一个一脸严肃像欠他钱似得,态度感觉很傲慢,后来知道他在bb干了14年。
上来也是先问简历,简历上我写了一个跟agile development的相关的东西,然后开始问agile development(万万没想到啊,没准备这个,对agile development并没有什么理解,失误了)。
Q1: 比较nice的中国人,问题跟LRU差不多,股票价格变动很频繁,要求实现一个data structure, 可以get最新的股票价格,但是如果五分钟之内股票价格没有更新,就返回0.
开始我想的是用一个hashmap,value是价格+时间,get的时候对比时间,如果差值小于五分钟,就返回0. 他说由于股票价格更新很频繁,所以必须要把五分钟之前的数据从hashmap里面删除(我心想一个key一个value啊,股票就那么多,能有多少数据啊,但是你要求删就删吧)。所以我还是用hashmap+doubly linked list 的结构,hashmap的value是linkedlist的里面的节点,节点要存股票名+时间+价格,每次更新把节点提到linkedlist的头部,然后定期从尾部检查linkedlist,把五分钟之前的数据删除。get set时间复杂度也都是O(1). 一脸严肃的主面问了一句,你怎么知道linkedlist的头和尾在哪里呢?头和尾都存在head和tail的variable里面啊(口述没有写代码)。。。主面纠结了一下好像没懂,另一个中国人表示已经懂了。然后这题就算过了。
Q2: 1024游戏设计,主面出的。
给了一个move方法,参数没给,要我自己设计。我设计成move(grid,direction),grid是一个二维数组代表当前的状态。然后在里面用写了if direction==”RIGHT”,主面就问我为什么要这么写,我说很清楚就知道这里就是move right啊,都不用注释,他问还有没有其他的写法,我说可以if direction==0然后0代表right,还有就是用enum, if direction==Direction.Right. 问了这几种写法的区别,那种最好,我说用enum, 效率比比较string要快,直观而且不会像==0出现invalid数值比如5。然后他说你这样岂不是要用四个if, 我说是吧,我想了想也许只需要两个吧, 先写完move right这部分再说,后面再看能不能合并这几个情况,然后就开始写,我才写了几句,定义了几个变量,主面又问为什么要这么写,没必要吧,这样吧,你第一步先shift一下,把所有数字放到最右边,好吧,我就按他的写,写了一下有几个bug, 改来改去,自己也急了,没冷静思考,弄了半天shift总算写完了。第二步是merge相同的数字,又是各种bug改来改去,主面这时候就没怎么说话了,就一脸你错了你又错了的表情,然后差不多move right快写完的时候他说时间到了,你问我我们问题吧,我。。。这个时候就知道跪了,没面好。
agile development没准备好是有些失策,但是这个主面语气态度,根本就没有帮助我解决问题的意思,感觉一直在刁难我,1024那个题虽然之前没写过,但是也并不是什么难题,最开始我是想边shift边merge的,他总是打断我,要我按他的思路写,在我遇到问题的时候又不提示我,好无语。

希望面经能帮到大家。

补充内容 (2015-8-11 12:02):
有个地方写错了,大于五分钟才返回0