彭博昂赛

czcbangkai 发表于 2017-12-4 15:58
谢谢楼主回复~ 再问下股票那道题complexity要求是怎么样的呢?

没有要求，我直接说“既然要频繁更新、频繁获取top K，所以对这两个操作都要求非常快”，然后直接给了最优解。 其实也是因为只剩下十五分钟才开始第二题，没时间绕弯子。。

qifu1001 发表于 2017-12-5 00:26
恭喜楼主拿到offer
楼主，topK stock那个能讲下为什么用 hashMap + treeSet么
我想直接将hashMap 转成 li ...

我不太懂java... 但是我猜你用list的话，排序是要nlogn的吧，这样复杂度有点高。   treeset可以const时间访问到旧的<Name, share> pair, 然后删除，然后insert 新的<Name, share> pair (O(logn).  然后排序的话，因为treeset本身是有序的（花费了logn来插入新的元素），所以每次想获取top K的时候是O(1)。    也就是说，更新value是logN的操作，获取top K是const的操作。    你看一看list能不能达到这样的复杂度

白菜3383 发表于 2017-12-5 04:37
我不太懂java... 但是我猜你用list的话，排序是要nlogn的吧，这样复杂度有点高。   treeset可以const时间 ...

多谢楼主，突然发现自己想复杂了, TreeSet可以直接解决

白菜3383 发表于 2017-12-4 13:57
直接最优解

兄弟是拿到offer了嘛？恭喜恭喜！
请问一下打算去嘛？我也是前几天收到的offer，如果打算去的话可否加个微信聊一聊？

求问一下why bb怎么答的？

lz,那个第二轮hashmap + set，我没想明白怎么做。。是用hashmap存stockName跟share，然后set直接存share，需要找top k 的时候，去hashmap里找value为set里top k的？感觉这样也很慢啊。。。

补充内容 (2017-12-8 16:42):
还有，priority_queue为什么不行？每次只需要把min的将新的input比较就好了啊。。

wangsiwei 发表于 2017-12-8 00:51
兄弟是拿到offer了嘛？恭喜恭喜！
请问一下打算去嘛？我也是前几天收到的offer，如果打算去的话可否加个 ...

好的  私信你了

YHYbrilliant123 发表于 2017-12-8 01:02
求问一下why bb怎么答的？

这个问题我觉得当时临场发挥的很好哈哈，给你参考一下：

考虑一个公司有很多方面因素，比如1.这个公司主要侧重工作方向是什么、用什么技术、是否和我的兴趣匹配，2.公司文化，3. 以及同事都是什么样的人等等。
对于第一点，我很喜欢金融方面的东西，还有投资啊、股票、基金甚至比特币什么的。在之前准备面试问题的时候我碰到过一个问题，给你一组数据代表每天的股价，让你找出一个策略获得最大收益。我当时想现实生活中我要是有这种能力就好了，后来我发现这不正是BB在做的嘛，分析数据，预测市场，非常有趣！另一方面，说回老本行，我是一个swe，BB的engineering文化非常有名，不像传统的金融公司。
第二点有关公司文化，我之前看过一段Michael Bloomberg的采访，他说员工不应该被等级或者title来区分，所以bb的公司结构很扁平化，team精简，这对于我一个fresh man很友好。
第三点，我听说BB的员工当中有两三个人在C++委员会里，那BB不就相当于“Game definer”，和这些大牛一起工作当然学到的就更多！

当时描述的比这个还详细，每一点都“声情并茂”，哈哈感觉把面试官吹得也很高兴

844587076 发表于 2017-12-8 16:40
lz,那个第二轮hashmap + set，我没想明白怎么做。。是用hashmap存stockName跟share，然后set直接存share， ...

priority_queue单纯把min pop出去的话会有问题的。 比如现在pq里有这些元素{<A, 100>, <B, 200>, <C,300>}，其中ABC都是股票的名字。  现在有人又交易了300 share的B，于是B总共加起来变成500了，单纯把最小的pop的话会变成{<B,200>, <C,300>, <B,500>}有重复。   用hashmap的作用就是记录每一个股票当前的交易量。 set的作用是，先找到旧的<B,200>，删掉，然后插入<B,500>, 并且保证插入、删除等等操作始终都是有序的