12/21 Bloomberg Onsite

原帖地址:一亩三分地

大概分享下今天在Bloomberg onsite的经历。 首先HR带着所有人参观公司。Bloomberg总部还是很气派的,设计和格调都显得非常上档次。参观完顶楼后发放100刀的卡和lunchbox。紧接着第一轮的面试官就陆续来把人领走了。 第一轮,小印(主面)+老白。上来先花几分钟自我介绍+稍微聊聊简历,进入coding环节。第一题是这样的:提供一个数组,代表楼层高度。一栋楼有view的楼层数和在它之前的所有楼的高度有关。比如[4,7, 9, 6, 8]这个数组,第一栋楼的所有4层都有view,第二栋楼有7-4=3层有view,第三栋楼有9-7=2层有view,第四栋楼和第五栋楼没有任何楼层有view,因为前面最高的楼(9层)比它们都高。所以答案是4+3+2+0+0=9。这题明显是买卖股票I的变体。楼主用同样的思路写出来,面试官表示满意。小印问有没有更好的解法,想不出来。他说了我还是没有get,只好做恍然大悟状+跪舔一番。第二题是在binarytree中寻找target value并输出所在的层数(假设root为0层)。楼主直接BFS写完。小印问如果要输出targetvalue从root开始的所有祖先的值,怎么修改。楼主说既然是这样那得用DFS了。老白问为啥一开始不用DFS。我晕,一开始又没有说要输出所有祖先啊。只好扯一番DFS,BFS的优缺点。第三题UniquePaths原题,很简单的DP。楼主只好先假装思索一阵再写出来。第四题是面经里出现过几次的sensor题。就是假设一个track上有众多sensor,能在每个赛车通过时检测出来。让做一个设计,能实时更新排名 。楼主先提出用一个Status Class,来保存每辆车的离终点的距离(其实也就是通过的sensor)以及通过该sensor的时间。用一个HashMap来存每辆赛车的状态,再用一个heap保存top K。Heap的comparator先判断距离,距离相等的情况下判断时间。两个面试官有点无法follow,觉得没必要那么麻烦。于是楼主提出每个sensor可以保存一个自增的counter,在赛车通过的时候counter++,赛车也同时获得这个counter的值。另外,离终点远的sensor的counter用一个比较大的初始值,离终点近的sensor用小的初始值。这样就能够保证通过离终点近的sensor赛车始终有比其它赛车小的值,同时又能区分出通过相同sensor的赛车的顺序。小印表示goodenough。再问了几个问题,这轮结束,带到下一个房间。 第二轮,小印(主面)+国人。上来还是先花几分钟自我介绍+稍微聊聊简历,进入coding环节。小印出题:k个LinkedList,每个LinkedList中的元素无序且可能重复。让输出一个新的LinkedList,保存原来每个LinkedList中都出现过的值。没做过这题,就想了个不那么优化但可行的解法:用HashMap存每个数在几个LinkedList中出现过,最后输出出现过k次的ListNode。对于每个LinkedList,用一个HashSet来保证重复的元素只计了一次。写完code小印说OK,让优化。于是想了想,去掉了HashSet。接着国人大哥出了个非常别扭的题:给一个array,例如[3,2, 6, 5, 7],找到最大的一个数x,使得array中比x大的元素的数目不超过x。比如x=1时,有5个元素比x大;x=2时有4个,x=3时有3个,所以答案是3。我花了10分钟才理解是什么意思,汗都听出来了。最后用二分的思路写了个方案:x从1开始,每次*2,直到比x大的元素个数比x小,然后再从x/2到x之间用二分搜索找。大哥不满意这种O(nlogn)的方法,说对于每个x,都要遍历array一次找出有多少个数比x小,让优化。到这实在搞不懂这怎么做了,最后他提示用hash,我还是没法get。弄了半天,气氛很尴尬,最后只好算了。问了两个问题结束这轮。 到了这里楼主已经心灰意冷了,这是传说中的二轮游吧?于是呆坐在那等着被人带出去。等了一段时间居然进来一个蛮高层的国人经理,介绍她的team,介绍Bloomberg。然后问楼主简历上的经历。总体上这轮非常愉快,经理非常非常nice。 最后来了一个senior hire的HR,说是校招的HR不够用了他来顶。问了一些关于身份,和其它公司的面试情况,又讲了一堆Bloomberg的好处。 面完HR就结束这次onsite了。虽然撑到了四轮,但根据版上最近的Bloomberg面经的形势,觉得还是凶多吉少,因为第二轮实在太囧。不管怎样,moveon了。希望写的对大家有帮助。