Bloomberg R&D 3.20日面试游记

whuwangyi 发表于 2014-3-23 01:54
首先感觉LZ分享，祝LZ好运！

runner那题描述得不太清楚，每个人的位置都只升不降么？但是如果runner的位 ...

对于Runner这题：用堆固然可以每次取得最大元素，但是堆（C++中）是不提供对堆内部元素的update方法的，只有top和push,pop三个操作。当runner的位置更新了之后，如何操作堆呢？至少在C++中，这需要nlogn才能完成。或者Java中直接存在堆的更新方法？

whuwangyi 发表于 2014-4-18 22:41
我之前的疑问是这里是否有个每个runner的位置只升不降的前提。我不知道这里的位置是只的排名还是指的物理 ...

这个题在Bloomberg面试中出现多次，还可能以20支股票和价格为背景，所以无法假设值只升不降，这样的话该用什么数据结构合适呢？如果只有单一的数字的话，以数字为key用set即可（set也是自动有序的，同时提供增删改查）。问题在于题目中的背景不能保证值unique，所以只能用multiset，如此则还要解决键值重复的问题。对此有什么更好的办法吗？

whuwangyi 发表于 2014-4-21 09:41
Java的话可以用TreeMap，是根据key排序的HashMap。如果每个时刻平均更新的runner个数为n个，则需要O(nlog ...

以<股票代号, 股价>为例，在TreeMap中如果根据Key排序的话，这个Key是什么呢？如果是股票代号的话，显然无法返回股价最高的K个，如果是股价的话，当出现相同股价的情况如何处理？会覆盖掉前一个数据么？

每次所有runner更新的话，不久意味着数据完全无序么？对此求topK需要nlogn排序吧，线性怎么做到？

whuwangyi 发表于 2014-4-23 00:02
嗯，谢谢提醒，之前想错了，这题不是简单用个TreeMap就可以解决的，我把key和value弄反了。

我觉得可以 ...

我也是这么想的，BST+hash，不过在C++中直接用set即可。set在C++里是基于RBTree实现的，比自己做的好，而且直接提供查找删除等一众功能。使用的时候直接往里面放key和value的pair并保持和hash同步即可。

binary search 那个时间 logn-1 不就是logn嘛。。。。

whuwangyi 发表于 2014-4-21 09:41
Java的话可以用TreeMap，是根据key排序的HashMap。如果每个时刻平均更新的runner个数为n个，则需要O(nlog ...

treemap 是rbtree 吧，我觉得是可以用treemap的，根据value排序改一下comparator就可以了吧。