一亩三分地论坛

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

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

新鲜的Bloomberg店面面筋

[复制链接] |试试Instant~ |关注本帖
simasy 发表于 2016-10-13 23:03:50 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 本科 全职@Bloomberg - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
楼主人在欧洲,申的London office
.1point3acres缃面试官小哥英音蜜汁好听啊!
45分钟的面试硬生生地扯到了80分钟。。。。一脸蒙蔽

-google 1point3acres一开始问了Why Bloomberg,介绍下你的暑假实习,说一说你遇到的最困难的地方,然后做题
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
题目就一道,不难,但是楼主还是写出了bug。。
Twin primes:
Given 0 < n < 1000
find the biggest prime pairs x < y <= n, and y - x = 2

Eg. twin_pair(50) => (41, 43)
twin_pair(5) => (3, 5)
twin_pair(2) => "Not found"

用sieve of Eratosthenes把小于等于n的prime都generate出来,然后从尾到头遍历就可以了。。。。然后就这么简单的程序我还写出了bug orz
. 鍥磋鎴戜滑@1point 3 acres
Follow up我都数不清有多少个了。。。

1. 如果用户经常call这个function怎么办? => pre compute. 1point3acres.com/bbs
2. 如果n的上限变成INT_MAX怎么办?=> 这个我感觉我答得不太好,感觉应该问用户需求的(比如能不能接受第一次时间很长,内存有多少之类的)。。。我说的是找一个bar,比如500, 所有n<500的话都generate prime numbers on the fly,如果更大的话就pre compute 所有然后以后用的时候就会快很多
3. 如果pre compute消耗的内存不能忍受怎么办? => cache, 于是开启了一个大坑。这个时候已经差不多40分钟了,我以为就差不多结束了。。。结果呵呵
4. 如果这个function要给用户用, 你会问用户一些什么问题? => 你的电脑可以接受多大的内存消耗(大的话就pre compute, 小的话on the fly);你可以接受一开始setup的时候要等比较长一会儿,但是之后运算挺快的吗(可以的话pre compute, 不可以on the fly)
5. 那cache还是会占内存啊,如果cache超了limit,先drop哪个结果 => LRU
6. (楼主用的python) python里你怎么implement一个LRU => OrderedDict, 一个类似于hash map但是同时记录你push进map的timestamp。结果小哥貌似没听过这玩意,说这我还真不知道,我每次都直接用builtin LRU(妈蛋刷LeetCode LRU那题的时候我如果直接用builtin LRU还练习个毛线啊)
7.你觉得OrderedDict是怎么implement的 => 我当时脑抽竟然忘了。。。好在过了一小会儿想起来了,Priority Queue + Dict
8. 对于priority queue, 如果我想随机删掉某一个entry,worst case? => O(n) 一开始脑抽答得O(lgn),后来想起来是按照timestamp做的heap,所以找一个value没办法用heap的查找方法
9. 那怎么加快这个查找过程呢? => auxillary hash_set to index,有点类似于SQL里的index,但是cost是更多的memory

中间还基本上把LRU那题scratch了一下

—————————————————————————————————————————————————————————————————————————

讲道理我觉得这比上来丢问题就做要好很多,如果没有那堆follow up就看我写的垃圾代码必挂无疑 orz

第一次发帖,求大米大米

求过求过俺还想去伦敦玩一趟
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
 楼主| simasy 发表于 2016-10-13 23:08:58 | 显示全部楼层
再加一个follow up...刚才忘了 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
问pq记录timestamp时会不会有问题?我一开始没get到点,后来他直接说了在multi thread的时候,才意识到想让我回答thread safety issue
=> Python 有notorious的GIC,所以multithread基本gg,我平常都是用multiprocess to get around,代价是fork process 比create thread更expensive. 如果不加锁的时候确实有可能出现两个entry有同样的timestamp。
回复 支持 反对

使用道具 举报

aiyawocao 发表于 2016-10-17 08:45:52 | 显示全部楼层
非常感谢楼主。
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-17 11:42:44 | 显示全部楼层
我比较old school, 用C++。. From 1point 3acres bbs
请问面试官问priority queue随机删掉某一个entry是只针对Python语言的吗?C++ standard library的priority queue都没有API允许删除任意位置的元素,只能pop顶端元素,甚至都没有iterator遍历(priority queue应该也是用heap实现的)
回复 支持 反对

使用道具 举报

elizabethxiazhi 发表于 2016-11-16 14:19:03 | 显示全部楼层
LZ怎么样了,求分享onsite信息哎谢谢LZ
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 02:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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