Bloomberg OnSite 1/12 两轮游

原帖地址:一亩三分地

第一次发帖,发一下Bloomberg的onSite吧。

Bloomberg的电面是很久以前了所以我也不记得了。我是1月12号onsite面的,具体的流程大家在其他面经里也可以看到,所以我就直接进入主题说说面经吧。

第一轮,只有一个人面我,他应该是欧洲人,有口音,有点难听懂他说话。他先问我“Why Bloomberg”。然后问我一些C++的基础题。比如给你一个class C,里面没有任何implementation,然后有一个function foo里面先是C{}, 然后print “Hello”, 在main里call foo,问我要怎么样才能print: “Hi Hello World”,不能修改function foo,只能改class。我就说用constructor and destructor。然后他说如果foo里面的C{}变成C c = new C(); 问我现在会print什么。我说现在会print “Hi Hello” 因为没有delete c 所以destructor没有被用到,然后他问了我这两个不同implementation是怎么用memory的,比如stack还是heap. 然后就正式做题了。
第一题:因为我刷题只刷了一半,不知道这道题在leetcode上有没有。给我一个Tree,这个tree的每一个node可以有很多children,每一个node只有一个pointer指向它的parent,和平常熟悉的tree不一样,平常的tree都是parent有pointer指向children. 他先让我把TreeNode的definition写出来,然后让我做一个function,input是一个数组和一个int,数组里面存的是这个tree的所有的node, int存的是target。要我在这个tree里找到target然后return这个target node的所有的children。我开始就说用BFS,解释了一下,面试官说这个方法可以做到,不过太慢了,要N^2,问我有没有更快的方法,我想了想,他给我了一点提示,然后想出用hashmap,key存node, value存这个node的直系children的数组。这样再用BFS,就能达到O(N)了。
第二题:Server Attack的题目。说你只有一个function,用这个function来察觉有没有在攻击服务器。这个function return bool, 每次有一个server request这个function都会被call. 然后告诉我这个function will return true如果在5秒内有10次以上的request。这个题我一开始给出的方法是用一个time和count来看,每5秒更新一次time并重设count为0. 但是面试官指出这个方法对于这种情况不行: {0 1 2 3 4 5.5 5.5 5.5 5.5 5.5 5.5}。在这种情况下我的function会给false 但是其实应该是true,因为我的function会在第一个5.5上reset。然后我就纠结了半天,面试官给了一些提示,最后才想出用一个window卡住10个request 然后每一次只看头和尾的时间差,如果是小于5秒就证明有server attack。这个window用queue来做。因为时间到了,所以面试官让我解释一下我的算法,没有写代码,然后第一轮结束。
.鏈枃鍘熷垱鑷point3acres璁哄潧
第二轮,两个人进来了,一个美国大叔和一个印度小哥。此时我已经觉得上一轮答得不好了。不过就当给自己的锻炼,所以要乐观面对每一道题。
这一轮美国大叔先出题,又给了我一个tree,每一个node有pointer指向up, right, down。然后说每一个node都比自己上面的值大,比下面的值小,最后右边的值比自己的值大,也比所有自己下面的值要大。他给我画了个example,所以这样比较好懂。他先给了我1到9,让我把这10个数字放进他画的tree里面。然后问我如果写算法要怎么把1到n放入tree里面。我解释完,他让我写一个function来print所有的node, in order。然后我写迅速写了一个recursive的方法,蛮简单的,一遍就过。然后他问我那iterative呢,我说每个node的上面用stack, 下面用queue,他说上面确实要用stack,但是下面真的需要queue么。我想了想,说不需要,用那个stack也能做到,然后再解释了一下,他表示满意。
第二题是印度小哥出的system design的题,就是让我做一份web browser,里面会存k个访问最多的网页,依次序展示出来,问我怎么做。我就想到了用min heap和hashmap来做,hashmap来存所有的网页和改网页被访问的次数,min heap的大小就是k,最顶上的是访问最少的,每次一个网页被访问,都会update min heap和hashmap。最后谈了谈时间复杂度,第二轮就完了。

然后等了20分钟,就被HR请出去了。个人还是有点失落。但是回想一下,应该是栽在第一轮了,其实server attack那道题我在面经里面见过,当时还会做,不过忘了。以后的教训就是面经要看的再多一些,并且继续刷题!希望对各位有帮助!