一亩三分地论坛

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

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

Bloomberg Oniste

[复制链接] |试试Instant~ |关注本帖
dydcfg 发表于 2016-10-1 04:31:52 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Bloomberg - 网上海投 - Onsite |Otherfresh grad应届毕业生

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

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

x
第一轮国人GG和国人姐姐
1.给一个单词字典和一个没有分词过的句子,求一个合法的分词结果.
2.anagram
第二轮白人小哥和黑人小哥
3.给一个2D矩阵,代表地图.每个国家有自己的编号,在地图上是连续的块.给一个初始坐标,求该坐标所属国家,如果要建立一个围墙把这个国家围起来需要多长的围墙?
4.design一个Client-Server系统,用于处理股票信息,可以返回用户订阅的股票里更新频数最多的K只股票.
第三轮HR,英国口音的白人小哥
第四轮,Manager,非常和善,开心地谈笑风生然后做了一道题:
5.First Unique Character

求offer求加米. more info on 1point3acres.com



补充内容 (2016-10-4 05:08):
拿到offer啦,感觉他家动作好快!

评分

5

查看全部评分

 楼主| dydcfg 发表于 2016-10-10 05:37:53 | 显示全部楼层
zpinthehouse 发表于 2016-10-5 23:03
就是说本来股票A的freq是6,已经是top K了,现在又增加了一次变成7,这个时候heap要重新heapify。。可是 ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
这个其实不用立即去更新.比如你给的例子里,如果A是TopK但是不在堆顶,然后A从6->7,这个时候不用去更新A的值.当后面由于新的值加入后导致A上升到栈顶的时候,再去更新A的值.也就是先把A pop出来,然后push进去新的A值.
回复 支持 1 反对 0

使用道具 举报

cicean 发表于 2016-10-1 14:38:48 | 显示全部楼层
我去,第一题word break II
第二题 number of island 变形 找周长 BFS
第五题???excuse me         
387        First Unique Character in a String  . more info on 1point3acres.com

这这这 。 这真的是BB 么?????
回复 支持 反对

使用道具 举报

 楼主| dydcfg 发表于 2016-10-1 22:45:12 | 显示全部楼层
cicean 发表于 2016-10-1 14:38
我去,第一题word break II
第二题 number of island 变形 找周长 BFS . 1point3acres.com/bbs
第五题???excuse me         

第五题也就是Manager出着玩的,不过他是做系统优化的所以对着程序问了很多底层优化=。=比如CPU预测流pipeline啥的。。。最后一轮纯娱乐面
回复 支持 反对

使用道具 举报

cicean 发表于 2016-10-1 23:16:43 | 显示全部楼层
我觉得考操作系统基础知识,确实比刷题都难。一个想不到就挂了。楼主确实厉害…看来manager 问的都是比较深层次的问题。之前面微软最后一轮被问线程和锁,很多操作系统的知识。完全不记得了,上课也没好好听。
回复 支持 反对

使用道具 举报

 楼主| dydcfg 发表于 2016-10-2 01:47:59 | 显示全部楼层
cicean 发表于 2016-10-1 23:16
我觉得考操作系统基础知识,确实比刷题都难。一个想不到就挂了。楼主确实厉害…看来manager 问的都是比较深 ...

木有木有,那些知识面前看看就可以了
回复 支持 反对

使用道具 举报

sherry900629 发表于 2016-10-2 03:06:00 | 显示全部楼层
没刷过题的默默走开。。。谢谢楼主。。。
回复 支持 反对

使用道具 举报

cicean 发表于 2016-10-2 05:19:58 | 显示全部楼层
dydcfg 发表于 2016-10-2 01:47
木有木有,那些知识面前看看就可以了

CPU 预测流 pipeline 是啥?完全不知道啊。赶快翻出OS 教科书再看一遍。.鐣欏璁哄潧-涓浜-涓夊垎鍦
系统底层优化是指程序执行时候,CPU 占用率,内存占用率的优化么? 不太懂,有没有什么具体资料可以参考的。
回复 支持 反对

使用道具 举报

 楼主| dydcfg 发表于 2016-10-2 09:31:34 | 显示全部楼层
cicean 发表于 2016-10-2 05:19.鐣欏璁哄潧-涓浜-涓夊垎鍦
CPU 预测流 pipeline 是啥?完全不知道啊。赶快翻出OS 教科书再看一遍。
系统底层优化是指程序执行时候 ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
CPU会有指令的pipeline,然后像遇到if这样的分支命令预测错了会有惩罚重新加载pipeline.不过都是纯聊天的=。=manager喜欢这些话题
回复 支持 反对

使用道具 举报

zpinthehouse 发表于 2016-10-5 08:23:46 | 显示全部楼层
恭喜楼主!能请教一下第四题,求前K个股票是怎么做的么?多谢楼主。。
回复 支持 反对

使用道具 举报

Roisterer 发表于 2016-10-5 09:48:58 | 显示全部楼层
恭喜楼主! 同问第四题
回复 支持 反对

使用道具 举报

 楼主| dydcfg 发表于 2016-10-5 11:42:37 | 显示全部楼层
Roisterer 发表于 2016-10-5 09:48
恭喜楼主! 同问第四题
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
我是用size=K的小根堆加hashMap做的,小根堆维护了前K频繁的股票.不过注意的是要维护堆顶的元素的频数是最新的.然后更新的时候看看那只股票的频数是否大于了堆顶元素并且不在堆里,满足的话就pop然后压入新元素.另外一个解法我觉得可以用红黑树,key=频数,val=list<stock>,然后再用一个hashMap做映射.输出的话直接逆中根序遍历搞搞输出K个就行了.
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-10-5 12:01:23 | 显示全部楼层
dydcfg 发表于 2016-10-5 11:42
我是用size=K的小根堆加hashMap做的,小根堆维护了前K频繁的股票.不过注意的是要维护堆顶的元素的频数是最 ...

请问楼主, 堆是最小堆嘛, 堆顶元素正好是更新第K频繁的股票?
回复 支持 反对

使用道具 举报

 楼主| dydcfg 发表于 2016-10-5 12:18:15 | 显示全部楼层
小A要当码农 发表于 2016-10-5 12:01
请问楼主, 堆是最小堆嘛, 堆顶元素正好是更新第K频繁的股票?
. 1point 3acres 璁哄潧
是的,最小堆.
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-10-5 12:20:25 | 显示全部楼层

多谢楼主~
回复 支持 反对

使用道具 举报

zpinthehouse 发表于 2016-10-5 23:01:25 | 显示全部楼层
dydcfg 发表于 2016-10-5 11:42.鐣欏璁哄潧-涓浜-涓夊垎鍦
我是用size=K的小根堆加hashMap做的,小根堆维护了前K频繁的股票.不过注意的是要维护堆顶的元素的频数是最 ...

感谢楼主。。有一个小问题,如果update的时候股票已经在堆里,是不是只要重新heapify就可以,这样是logK的复杂度?红黑树的想法很赞。。多谢!!
回复 支持 反对

使用道具 举报

zpinthehouse 发表于 2016-10-5 23:03:53 | 显示全部楼层
zpinthehouse 发表于 2016-10-5 23:01
感谢楼主。。有一个小问题,如果update的时候股票已经在堆里,是不是只要重新heapify就可以,这样是logK ...

就是说本来股票A的freq是6,已经是top K了,现在又增加了一次变成7,这个时候heap要重新heapify。。可是比如说java的priorityqueue,不能实现这个功能。。所以如果这道题会要求实现最小堆么?
回复 支持 反对

使用道具 举报

monosky 发表于 2016-10-6 05:32:04 | 显示全部楼层
恭喜楼主!第3题跟我面的题目一样
回复 支持 反对

使用道具 举报

cicean 发表于 2016-10-7 02:48:57 | 显示全部楼层
楼主第四题, 4.design一个Client-Server系统,用于处理股票信息,可以返回用户订阅的股票里更新频数最多的K只股票..1po
能用top k frequent elements bucket sort 的解法么?
回复 支持 反对

使用道具 举报

cicean 发表于 2016-10-7 02:51:15 | 显示全部楼层
dydcfg 发表于 2016-10-2 09:31
CPU会有指令的pipeline,然后像遇到if这样的分支命令预测错了会有惩罚重新加载pipeline.不过都是纯聊天的= ...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
楼主,我不会聊OS 咋办啊,我只会backend 和 数据库。一问OS 进程和多线程,就挂了, 不知道怎么补,看了一遍OS 数,还是不知道讲的是个啥,非常苦恼。
回复 支持 反对

使用道具 举报

cicean 发表于 2016-10-7 03:10:36 | 显示全部楼层
dydcfg 发表于 2016-10-1 22:45
第五题也就是Manager出着玩的,不过他是做系统优化的所以对着程序问了很多底层优化=。=比如CPU预测流pipel ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
楼主在明确下第一题,是要一个合理的分词组合,还是要多个组合? word break I 是一个 II 是所有解。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 02:58

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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