一亩三分地论坛

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

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

Bloomberg Intern 校园面试 Final Rounds

[复制链接] |试试Instant~ |关注本帖
堕落的猴子 发表于 2015-4-9 04:02:51 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 实习@Bloomberg - 校园招聘会 - 校园招聘会 |Pass其他

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

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

x
2015暑假Intern,已定F家,纯分享面经。
土木转行所以细节可能粗糙,请谅解。

感想:
1,依然是校园面试。一开始说是一轮面试,看来面得不错,直接给了hiring manager面和HR面(就在隔壁小房间等着)。
2,依然很多design相关题,类似我第一轮的面试,有兴趣的可以搜搜看。

一轮:
1,两个面试官,都是之前来过学校info session还有hackathon的,所以聊了下这些东西。

2,给一个string,删除所有重复字符,任意字符包括空格都算。. from: 1point3acres.com/bbs

基础肯定是用HashSet来存字符。先说了个用stringbuilder一路append的做法,然后被告知不需要返回,就直接逐个字符打印了。

3,一个数组作为输入,输出是给用户看的histogram,纵坐标表示以0 ~ k -1, k ~ 2k - 1如此划分的不同区间内的元素数。假设现在用户可以直接拖动一个slider来调整k的大小,试问如何优化这个操作的时间和空间。

一开始说每次用户给个新k值都暴力扫描原数组,答可以。问如何优化扫描速度。
然后说先排序数组,然后做N/k次二叉扫描,搜索数组里最小的大于等于k-1, 2k-1, 3k-1的数组的index,返回的值就是可以用来划分的index(让二叉搜索的失败返回值不是-1而是low指针就可以),然后histogram就是index1, index2-index1, index3-index2这样。问如何继续优化,假设最大数字不是很大。
于是想到counting sort里的那个辅助数组C,C[i]记录小于或者等于i的原数组的元素的数量。扫描一次原数组,然后不需要二叉搜索,直接读取C里面的k-1, 2k-1, 3k-1等等的值就可以了。问如何优化空间,假设最大数字很大。
于是想到用interval tree优化空间,不过牺牲了查询速度,这个部分讨论一下思路就结束了。

4,数组里有一堆数字,除了一个出现奇数次,其他都是偶数次。找到那个奇数次的。

就是single number,会问你如何检查输入数组是对的,比如全部是偶数,比如有两个奇数。这个拿第一次出来的结果回去再扫一次数组统计这个结果的出现次数验证之就可以了。

二轮:
1,上来就自我介绍说是Hiring Manager,手下无数实习生。然后开场一个为什么Bloomberg。然后介绍了几个主要大组问兴趣。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
.1point3acres缃
2,一些和Linux有关的基础知识,比如directory是怎么manage的呀,文件系统是怎么样的呀,为什么用inode呀。

3,大design题,设计一个给investment banker用的目标公司新闻推送系统。

前端有注册,用户选择公司列表,实时更新相关公司新闻的呈现。中间有连接的维持方式(就是存一大堆sockets)和网路负载的优化。后端有新闻推送的收集,大量用户为目标的及时推送,服务器稳定性,用户信息的验证和推送的过滤机制。总之主要技术就是分布式,消息队列,Websocket,缓存服务器,备用服务器,也可以进一步用一些其他技术来优化比如storm和kafka。总之见仁见智,多主动和他交流,能想到的酷炫技术词都可以甩出来。最后答得他挺满意的,说我的设计基本就是BB在用的设计,虽然我都搞不清我的设计到底是啥了囧。

HR面:.鐣欏璁哄潧-涓浜-涓夊垎鍦
1,HR就在隔壁的隔壁等着。没啥问题,就是随便聊下为啥bloomberg,暑假的目标(这不肯定intern嘛),pending offer等等。然后稍微催了下,说会尽快给结果。

总的来说还是很愉悦的面试,应该offer妥了。
祝大家都有好运。.鏈枃鍘熷垱鑷1point3acres璁哄潧
houqingniao 发表于 2015-4-9 04:50:44 | 显示全部楼层
恭喜lz,lz转行还这么强悍。赞一个
回复 支持 反对

使用道具 举报

miraclebingo 发表于 2015-4-9 10:51:00 | 显示全部楼层
恭喜lz!lz能否说说第三题怎么用interval tree优化空间呢?如果叶子节点的单位节点,空间还是需要2N-1吧?
回复 支持 反对

使用道具 举报

miraclebingo 发表于 2015-4-9 10:59:45 | 显示全部楼层
第四题里面如果输入是奇数次的数是0,且只有0,那么怎么区分这是输入全部是偶数次,还是只有0是奇数次呢
回复 支持 反对

使用道具 举报

 楼主| 堕落的猴子 发表于 2015-4-9 13:20:48 | 显示全部楼层
miraclebingo 发表于 2015-4-9 10:59. more info on 1point3acres.com
第四题里面如果输入是奇数次的数是0,且只有0,那么怎么区分这是输入全部是偶数次,还是只有0是奇数次呢

噢?这个corner case面试官都没问到呢。

不过你xor完了,拿到0,然后直接统计数组里有几个0就好了吧。我说的第二步验证就是直接看这个结果在数组里是不是的确符合我们的条件。
回复 支持 反对

使用道具 举报

 楼主| 堕落的猴子 发表于 2015-4-9 13:25:42 | 显示全部楼层
miraclebingo 发表于 2015-4-9 10:51
恭喜lz!lz能否说说第三题怎么用interval tree优化空间呢?如果叶子节点的单位节点,空间还是需要2N-1吧?

严格来说应该是用tree来优化空间+搜索。其实我一开始想到的是直接链表,然后每次去链表里找区间边缘的位置,不过这样就是O(n)了。用树的话就是O(logn),不过其实就和我第二个办法很接近了。
回复 支持 反对

使用道具 举报

miraclebingo 发表于 2015-4-9 14:07:36 | 显示全部楼层
堕落的猴子 发表于 2015-4-9 13:20. visit 1point3acres.com for more.
噢?这个corner case面试官都没问到呢。

不过你xor完了,拿到0,然后直接统计数组里有几个0就好了吧。 ...

会不会有四个数都出现奇数次,但是xor是0呢?比如输入是0,1,2,4,7,结果得到0,而且回头统计数组里0也正好出现奇数次,但是输入是不符合条件的?
回复 支持 反对

使用道具 举报

 楼主| 堕落的猴子 发表于 2015-4-9 15:22:11 | 显示全部楼层
miraclebingo 发表于 2015-4-9 14:07
会不会有四个数都出现奇数次,但是xor是0呢?比如输入是0,1,2,4,7,结果得到0,而且回头统计数组里0 ...

有道理,这个等于是前面几个corner的混合。估计面试官都没想到这一层了。. visit 1point3acres.com for more.
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
这个corner还真不好解决,你有什么看法?
回复 支持 反对

使用道具 举报

miraclebingo 发表于 2015-4-10 02:29:37 | 显示全部楼层
堕落的猴子 发表于 2015-4-9 15:22
有道理,这个等于是前面几个corner的混合。估计面试官都没想到这一层了。

这个corner还真不好解决,你 ...

如果不要求空间的话,倒是可以hashset,出现第一次insert,出现第二次erase,最后如果size是1就是正确输入. 1point 3acres 璁哄潧
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
补充内容 (2015-4-10 02:29):
我觉得应该有更好的办法。。
回复 支持 反对

使用道具 举报

Fiona杀G 发表于 2015-4-10 02:43:52 | 显示全部楼层
噢居然在这里看到你,猴子
回复 支持 反对

使用道具 举报

 楼主| 堕落的猴子 发表于 2015-4-10 03:44:49 | 显示全部楼层
miraclebingo 发表于 2015-4-10 02:29
如果不要求空间的话,倒是可以hashset,出现第一次insert,出现第二次erase,最后如果size是1就是正确输 ...

是的,一开始我也是这么说,但是面试官追加问我能不能不用额外的空间完成检查。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
要么是他知道一个很屌的不用额外空间也能检查到异常输入的办法,要么就是他没意识到你说的这种corner case吧。
回复 支持 反对

使用道具 举报

 楼主| 堕落的猴子 发表于 2015-4-15 11:23:51 | 显示全部楼层
特地来更新下,今天被告知offer了。

所以我对于面试的一些分析和想法应该还是很有参考价值的,希望对大家有帮助。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 15:20

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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