一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 3425|回复: 49
收起左侧

Bloomberg Onsite - 2014 Software Developer(Entry Level)

[复制链接] |试试Instant~ |关注本帖
pc1000a 发表于 2014-4-21 04:29:58 | 显示全部楼层 |阅读模式

2014(4-6月) 码农类 硕士 全职@Bloomberg - 内推 - Onsite |Fail

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
来发个Bloomberg Onsite经验贴。本人跟大牛什么的不沾边儿,所有CS方面的知识都是自学的,虽然CE毕业的,但是最后才转的,以前的专业和上过的绝大部分课程都是Signal Processing, Communication,Information Theory等,所以也能给自学出家找CS工作的朋友一个参考吧。题目其实不太重要,因为面试官不同,再者高频题网上都有,所以说了也不大可能碰到一样的;还是多总结总结经验教训吧。

先说教训。。。战术上重视,战略上一定要藐视,即使很想去的公司,也要淡定,抱着信念“成了就成,不成大不了爷继续面下家,机会遍地都是,挂了1家还有另外n-1家公司的机会在那儿等着呢!”。我就是开始太重视这家公司,准备了很多,前一天晚上也看很晚,结果当天脑子很不清楚,再加上开局不顺有些紧张,简单的题都没发挥好。。。失败的事儿常有,但努力了却没发挥出自己的水平才是最让人遗憾的。

哦,语言方面给不用C++的朋友提个醒,Bloomberg用C++,但如果你申请的是有New Employee Training Program的那种,那么如果你的priority不是C++的话,大可不怎么管C++的东西。 他们会让你选择自己的language答题。。有可能后面一两轮会遇到C++的概念性的问题(不确定),但是总的来说不是个事儿,准备阶段不用花太多时间到C++语言上,重要的还是算法数据结构CS基础。

还有,申Bloomberg能赶上Campus Interview的话,难度比onsite简单很多,通过率也会高很多,因为大公司人员流动大,campus recruiting的时候一定是公司招人高峰期。
. 1point3acres.com/bbs
我面了第一轮就挂了。。(貌似公司也不想招人了,职位网上早就关闭,并且第一轮结束大部分candidate都出来了)所以大家觉得面试简单的话轻喷哈。。小心灵这会儿还受伤没缓过来呢

下面说流程。面试前公司的interview day routine就不说了。HR带着在公司闲逛,逛到差不多来了3个面试官跟我一起吃了点儿东西聊一聊,然后就去一个会议室开始了。三个面试官一个百人哥们儿很nice,一中国女同胞主要在旁边做记录,另一个一看就是美国学霸的哥们儿问东西喜欢抓住一点就使劲儿往深了挖,很aggressive,也是导致我紧张没发挥好的主要原因。。想想都是泪。
. visit 1point3acres.com for more.
上开先让介绍自己,然后就介绍讨论简历上的一个主要project。。讲了很久,对我列的主要的那个project问得很深细节很仔细,比一般公司都要仔细。。(也有可能跟面试官喜好有关)。我project用的是一个优化的算法解决的问题,那个problem最直观最傻的解法时间复杂度我只想过大概是n的好几次方,但是没仔细分析过。。临场学霸哥就开始使劲儿问到底是多少。。然后一紧张没答上来,开局不顺,给后面也挖了个坑,估计他觉得我算法复杂度分析巨shi吧,所以后面的东西算法复杂度使劲儿抠。。。本人没有系统地上过CS的课,复杂度分析方法虽然知道,但没怎么做过练习题,平时也没用过,大部分东西复杂度都是靠经验或者直接想能想出来的,所以遇到这种使劲儿抠复杂度分析的,只能给跪了。。所以上经验:CS的基础,复杂度之类的,一定要掌握,不要觉得写出来code就完了。大公司喜欢看员工CS方面的发展潜力,这也是个很好的考察点,虽然有些人会觉得很基础很简单。

简历聊了二十分钟,然后第一题,其实就是Leetcode最新的一题Reverse Words in a String(http://oj.leetcode.com/problems/reverse-words-in-a-string/)的变种,那道题说的是,比如input一个句子"I Love you",output这个句子词序反转,即"You Love I"。Leetcode上input是一个string,让操作完还是返回个String。当时leetcode上做这题时,直接先扫一遍input string,把每个词存到一个List里面,花时间O(n);然后逆序把每个词输出拼接到一个StringBuffer上,并且加上隔开的空格,完事儿即生成了反转的一句话,时间同样O(n)。                       当时leetcode OJ一下就过了,也就没多想,因为需要处理整句话,所以时间O(n)也不能再往下降了吧。结果面试时,当然会要求给出更优化的解法 -- 时间没法优化了,空间优化呗:假如input is a char array instead of a string as a sentence,让原地进行反转操作。当时一下没想出来,后来在学霸哥引导下才一步步想出来,解法是,扫第一遍时,俩pointer,一头一尾往中间merge,每一步都交换头尾的char,即第一遍完了后,"I Love You"变为"uoY evoL I",花时间O(n);然后扫第二遍,step by step,找出每个单词的收尾index,然后用同样的方法反转这个单词,即"uoY evoL I" --> "You evoL I" --> "You Love I" --> "uoY evoL I" --> Done! 时间同样是O(n)。哦,有一点,写代码时注意很多special case怎么处理,一定要提出来,不然会觉得你分析不完整不仔细,比如句子收尾有没有空格啊,单词之间多个空格怎么处理啊,如果empty input或者input char array只有空格怎么办啊,之类的吧。   然后上经验教训:写leetcode时,不要觉得OJ通过就行了,一定要想想时间空间有没有更好的解法,注意,both时间&空间哈! 然后这里想吐槽一句:leetcode既然把这道题放到OJ了,那么把各个单词直接放到List的解法也太简单了吧,底下加个Follow Up给大家提个醒,空间上还有改进的空间多好。。
遇到我这种不爱没事儿坐那儿多想的小盆友,过了就高高兴兴地ctrl+w了。。。
-google 1point3acres
然后就没多少时间了,接下来追加了一个更简单的系统设计题,现在我想想都想把自己撞死。。题目说白了就是,我们有input data stream,每条entry都是一个公司的名字加上一个一个时间的股价,比如一共有n个公司吧,怎么输出某一时刻最高股价排名前k高的公司和他的最高股价,当然input公司能重复,output公司只能是唯一的。。说到这你是不是觉得这就完了。。?其实答案很简单,就是一个Map就完的事儿,比如用HashMap,Key是公司名字,Value是股价,每次有新entry时就往里放,若公司不存在就直接放,若公司存在,那么判断股价higher的话更新,not higher的话ignore就好了;最终对于value排序就好,比如写个自己comparator,然后用Collections里面的sort(List<T> list, Comparator<? super T> c)根据value进行降序排序,然后输出前k个entry就行。 时间Hash插入查询更新什么的都是O(1),排序基于比较的排序最低O(nlgn),所以总体最低O(nlgn)。     这就是解法,我的错误是,一直在想有没有更优化的算法,尝试了各种数据结构(甚至尝试使用他们的组合)等等。。但是根本就没往上述这个很简单的解法考虑,自然他们也觉得你没解决问题。。anyway, I was keeping confusing myself! 上经验:不管算法题还是设计题,先保证自己有个通过的解法(哪怕这个解法很简单),然后再说优化的事,其实这应该也就是正常的科技面试的节奏吧。.1point3acres缃

面到这就结束了,一个小时吧。。。我现在想想估计学霸哥觉得这孩子是个SB。。。没办法,随叫自己发挥成狗了呢。.鐣欏璁哄潧-涓浜-涓夊垎鍦

哦,追加一个经验:大家面试写code或者思路,不论白板还是纸上,一定要well organized,要清晰公正,思路结构明了,这样即使做不出来,也会让人觉得你有自己的思路,是在往正确的方向尝试。。。千万不要自己思路不清晰,写到纸上的更乱。。。面试官会看了会烦会懒得看的!code结构,变量名类名方法名要符合行业规范,不要瞎起名字,以为算法解决就行了。。好高分有时也占挺大比重的,尤其当你处于过于不过的边缘时!

哦,再废话一下追加一个经验,用recursive解题时要小心谨慎,因为弄不好容易出错,跳不出来或者循环嵌套不对,再有就是让你分析跟递归有关的复杂度,也不是太好弄,不如很多iterative解法能直接看出来。

哦了大概就这些吧。有挫折才会有进步,跪得彻底的大挫折更涨经验!keep working,再接再厉!帖子废话有点儿多,各位看官能看到这也算是挺有耐心了,为了准备面试付出了时间和经历,既然努力了总会有收获。Good luck to everyone!



补充内容 (2014-4-20 15:43):
哦,当然,第二题用HashMap无法对entry进行sort,因为是无序的,得像个另外的办法(比如用LinkedHashMap行不行?或者把各个entry都拽出来放到一个能sort的容器里呢。。)

评分

5

查看全部评分

maoyp 发表于 2014-4-21 10:21:49 | 显示全部楼层
感谢楼主分享, 我上个礼拜也是去B的onsite挂了

貌似是两轮Tech, 一轮manager, 这三轮每轮结束都会刷一些人, 我第二轮Tech后就被刷了. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

第二题的话, 同时用size是n的hashmap和size是k的minHeap如何?
回复 支持 反对

使用道具 举报

 楼主| pc1000a 发表于 2014-4-21 13:03:37 | 显示全部楼层

我当时也是用了Map+Heap的方法,但是感觉没说清。。。现在想想也能用这样做,但是会比较复杂,并且时间复杂度也不会比O(nlgn)再小了,因为heap插入什么的时间是lgn。。。并且刚刚觉得其实minHeap+Set就行了?
.鏈枃鍘熷垱鑷1point3acres璁哄潧
heap存在的意义在于保持前k的排序,Set在于判别这个公司是不是已经加入到heap里了。   -google 1point3acres

1, Heap: 可以让Heap里每个node都是个Entry<StockPrice, Company>,以StockPrice作为排序基准。
2, Set: 同时维护一个size也为k的Set,每个element都是存在于minHeap里的公司名字,为了后面对每一个新来的data stream里面的entry进行处理(更新或者添加删除)时,查询这个公司是不是已经存在于Heap里了。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
流程是,如果新来的entry的股价>minHeap.poll()的股价,那么必定有东西是需要更新的,所以查询这个新来entry的公司是不是存在于Set--如果存在,那么就根据这个股价,继续在Heap里面查找这个公司相应的entry(不同公司也可能有同一股价,所以有可能heap里不同的node的股价相同),然后更新;如果Set里面不存在这个新公司,则直接poll那个heap,然后把heap.poll()的公司从set里面删除,然后再分别添加新的。。

时间不可能比O(nlgn)低了。。貌似应该是O(n^2)。原因如下:. From 1point 3acres bbs

Set里面search的时间是O(1),Heap里面insert/delete的时间都是O(lgn),并且很麻烦的一点是,heap里面search的时间搞不好就直接O(n)了,因为Heap里左右孩子都是比parent大,而左右孩子大小又不确定,所以search要O(n)。。所以现在想想其实时间复杂度回比O(nlgn)高。。。应该是O(n^2)。所以涉及到search for any之类的都不用Heap。。。所以还是我帖子里说的方法最好,实现简单空间基本上最低,并且时间也到了lower bound了。。。

你觉得是这个意思吗?欢迎指正批评哈!. visit 1point3acres.com for more.

跟人聊聊后感觉思路清晰多了~~ BB挂了就算了,你到了第二轮比我好,我基本上相当于打酱油。。早知道挂得这么彻底就带上老婆去纽约玩几天了  都继续努力吧~


回复 支持 反对

使用道具 举报

maoyp 发表于 2014-4-21 20:42:34 | 显示全部楼层
pc1000a 发表于 2014-4-21 13:03 -google 1point3acres
我当时也是用了Map+Heap的方法,但是感觉没说清。。。现在想想也能用这样做,但是会比较复杂,并且时间复 ...

heap的size是k, 所以插入删除不是lgn, 而是lgk, 如果公司存在, 确实需要全部扫一遍, 那么复杂度是O(k)

k和n完全不一样, k往往是一个很小的数(比如top10, top100) 这样lgk基本就是常数级别了, 即使是k也还好. From 1point 3acres bbs
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
其实这类n多个海量数据里取top-k的题套路就是用heap, heap的size是k, 所以添加删除都是lgk

你这里需要额外考虑公司是否已经存在(额外用一个k-size的Set我也觉得挺好), 如果存在就需要整个搜一遍heap, 也没什么关系, 反正k很小, O(k)也无伤大雅

当然, 期待牛人给出更好答案
回复 支持 反对

使用道具 举报

 楼主| pc1000a 发表于 2014-4-22 02:35:33 | 显示全部楼层
maoyp 发表于 2014-4-21 07:42
heap的size是k, 所以插入删除不是lgn, 而是lgk, 如果公司存在, 确实需要全部扫一遍, 那么复杂度是O(k)

...

哦 对啊。。。我没想是n里面取k个。。分析还是太不仔细了
. visit 1point3acres.com for more.
这样的话,对于每一个新来的entry,最坏是O(k),那么一共有n条entry,所以最差O(kn),但是k一般都很小,所以一般performance会挺好。。是这个意思?.鐣欏璁哄潧-涓浜-涓夊垎鍦
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
n多个海量数据取top-k,哈哈,受教了~!
回复 支持 反对

使用道具 举报

maoyp 发表于 2014-4-22 04:43:55 | 显示全部楼层
一共有n条entry,所以最差O(kn)

这句话没太明白, 什么操作要动用全部n个entry?
回复 支持 反对

使用道具 举报

maoyp 发表于 2014-4-22 07:28:27 | 显示全部楼层
pc1000a 发表于 2014-4-22 02:35
哦 对啊。。。我没想是n里面取k个。。分析还是太不仔细了

这样的话,对于每一个新来的entry,最坏是O ...
. visit 1point3acres.com for more.
对于新来元素的插入, 如果公司已经在heap中, 就是O(k), 如果公司不在heap中, 就删除顶元素然后插入, O(lgk), 更新对应hashset的时间都是O(1)

要求输出top-k个entry时, 对heap内所有元素进行排序并输出, 复杂度是O(klgk), 也完全没问题(比O(nlgn)要好很多了)
-google 1point3acres
然后, 你说的需要O(kn)的是什么操作?
回复 支持 反对

使用道具 举报

 楼主| pc1000a 发表于 2014-4-22 10:10:10 | 显示全部楼层
maoyp 发表于 2014-4-21 18:28
对于新来元素的插入, 如果公司已经在heap中, 就是O(k), 如果公司不在heap中, 就删除顶元素然后插入, O(lg ...

我意思是,数据流中一共有n条数据(每条数据是公司+股价),那么我们必然要处理这n条数据;

然后最坏情况,对于每一条来的数据,公司都在那个HashSet里(当然第0到k-1条数据可以都不在Set里,因为此时Heap的size还没达到k,所以直接插入就行了),那么对于每一条数据都要搜遍整个Heap,heap里搜索的worst case是O(k);. From 1point 3acres bbs
. 1point3acres.com/bbs
所以基本上就是差不多O(nk)了。。。你觉得呢?
回复 支持 反对

使用道具 举报

maoyp 发表于 2014-4-22 11:40:34 | 显示全部楼层
pc1000a 发表于 2014-4-22 10:10
我意思是,数据流中一共有n条数据(每条数据是公司+股价),那么我们必然要处理这n条数据;

然后最坏情 ...

是这样啊, 那没错, 是O(kn)

不过这种题一般就是考虑单个操作的复杂度, 有多少次操作直接乘以操作次数就完了
回复 支持 反对

使用道具 举报

maoyp 发表于 2014-4-22 12:03:47 | 显示全部楼层
pc1000a 发表于 2014-4-22 10:10
我意思是,数据流中一共有n条数据(每条数据是公司+股价),那么我们必然要处理这n条数据;

然后最坏情 ...

有一个想法, 可以不用那个小的hashset.1point3acres缃

只需要稍加处理原来那个大的hashmap <company, price>, 就可以判断一个entry是否是top-k的
.1point3acres缃
如果这个entry不在heap中, 那么就把price乘以-1,使price为负数. 1point3acres.com/bbs

查询一个公司是否为top-k时, 如果其price是负数, 就不是top-k, 反之就是

总之就是充分利用hashmap,
回复 支持 反对

使用道具 举报

 楼主| pc1000a 发表于 2014-4-23 02:11:19 | 显示全部楼层
maoyp 发表于 2014-4-21 23:03 . visit 1point3acres.com for more.
有一个想法, 可以不用那个小的hashset. 鍥磋鎴戜滑@1point 3 acres
. 1point3acres.com/bbs
只需要稍加处理原来那个大的hashmap , 就可以判断一个entry是否 ...

哦 对啊 这样也行! 涨姿势了 哈哈
回复 支持 反对

使用道具 举报

孤笑客 发表于 2014-4-27 21:12:53 | 显示全部楼层
Reverse Words in a String,给的例子是How are you变成You are how么?
回复 支持 反对

使用道具 举报

 楼主| pc1000a 发表于 2014-4-28 07:43:37 | 显示全部楼层
孤笑客 发表于 2014-4-27 08:12
Reverse Words in a String,给的例子是How are you变成You are how么?

对 就是这样
回复 支持 反对

使用道具 举报

tmw507 发表于 2014-4-28 14:44:04 | 显示全部楼层
maoyp 发表于 2014-4-21 20:42
heap的size是k, 所以插入删除不是lgn, 而是lgk, 如果公司存在, 确实需要全部扫一遍, 那么复杂度是O(k)

...

HashMap+minheap, 就是build HashMap statistic against stream and time value constraint, 然后find largest top-k using size-k 的 minheap by scanning HashMap. 总体是O(nlog k).
回复 支持 反对

使用道具 举报

maoyp 发表于 2014-4-28 22:20:10 | 显示全部楼层
tmw507 发表于 2014-4-28 14:44
HashMap+minheap, 就是build HashMap statistic against stream and time value constraint, 然后find la ...
. 1point3acres.com/bbs
没错, 是这样, 不过很多面试都只是考虑单个操作的时间, 况且这里time value源源不断的进来, 数量远不止n, 这里n是公司的数量
回复 支持 反对

使用道具 举报

tmw507 发表于 2014-4-29 01:03:19 | 显示全部楼层
maoyp 发表于 2014-4-28 22:20
没错, 是这样, 不过很多面试都只是考虑单个操作的时间, 况且这里time value源源不断的进来, 数量远不止n, ...

我知道你的意思了。如果想支持任意时间点的查询,估计可以对每个公司store a (price,time) sequence ordered  by first time then price. 如果 price of t2 <= price of t1 就删除掉 price of t2, i.e., 只保留一个 按照time 和 price 都是递增的sequence: e.g. entry sequence {(20, 6), (15,2), (16,4), (17,1)} 只保留 {(17,1), (20,6)}. Maintain 这样的sequence 是 O(N^2) in time, O(N) in space, 假设N是total number of timestamps. 总的top-k查询是 O(n log N) in time, O(nN) in space.
回复 支持 反对

使用道具 举报

maoyp 发表于 2014-4-29 01:56:25 | 显示全部楼层
tmw507 发表于 2014-4-29 01:03
我知道你的意思了。如果想支持任意时间点的查询,估计可以对每个公司store a (price,time) sequence o ...

好别扭, 你把这个题想复杂了, 只需要考虑单个操作的时间, total number of timestamps 不用考虑, 考虑单个操作就好
回复 支持 反对

使用道具 举报

孤笑客 发表于 2014-4-29 08:02:23 | 显示全部楼层

那人叫Travis吗?
回复 支持 反对

使用道具 举报

 楼主| pc1000a 发表于 2014-4-29 10:02:15 | 显示全部楼层
孤笑客 发表于 2014-4-28 19:02
那人叫Travis吗?

忘了。。。哈哈 你也遇到这个题了?当时答好没?
回复 支持 反对

使用道具 举报

孤笑客 发表于 2014-4-29 10:52:38 | 显示全部楼层
pc1000a 发表于 2014-4-29 10:02
忘了。。。哈哈 你也遇到这个题了?当时答好没?
. from: 1point3acres.com/bbs
恩,我也遇过这个题,答好了,然后现在在这边上班 :)
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 08:38

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表