Bloomberg经典面经题讨论

经典高频的马拉松问题：

一个 track 上有很多 runners(runner 已经给的属性有 id 和 name)，还有很多 check points(已给属 性为 distance:距离终点的距离，和 id)，check points 可以检测到哪个 runner 跑过它.

1. 实时更新 top k 的选手<

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

inkedlist， 有谁知道这种解法是什么意思吗？

欢迎大神们来讨论！！感谢！！




补充内容 (2017-10-23 00:28):
或者建一个checkpoint的array,然后每有一个runner过了当前checkpoint，就将runner从上一个checkpoint删除，然后加入到当前checkpoint.  显示排名的时候，就从array的后面开始找top K ？

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

这个题目不就是LFU吗....每次过checkpoint就是过相当于增加了一个频率，没看出来哪儿不一样，求大神指点

huzhouwjj 发表于 2018-1-30 06:48
可能是我菜，欢迎纠正！
我不理解，为什么double-linkedlist里的删除/更新是O(1)? 不应该是先去search你要 ...

其实就是LFU的变种，每个checkpoint维护一个linkedhashset，插入删除就可以O(1)了。

讨论有加米！ 欢迎讨论！！！

我使用的第二种方法，然后过了

补充内容 (2017-10-23 01:33):
咦。。。看错了。。。不用每个sensor都维护一个linkedlist吧 只需要从头到尾 所有运动员排序的一个linkedlist就可以了吧~

这是LRU的变形吧，double linked list不断更新当前的runner顺序即可

EddieZ 发表于 2017-10-23 02:06
这是LRU的变形吧，double linked list不断更新当前的runner顺序即可

能再详细讲一下吗？比如一个runner先后过了checkpoint 1和checkpoint 2，应该怎么办呢？  而且top K是从后端开始找吗

用Heap不行么？

EddieZ 发表于 2017-10-23 02:06
这是LRU的变形吧，double linked list不断更新当前的runner顺序即可

嗯嗯  差不多就这个思路！

StellaYue00 发表于 2017-10-23 01:31
我使用的第二种方法，然后过了

补充内容 (2017-10-23 01:33):

您的意思是 一个doubly linkedlist + 一个排序Linkedlist？

tabrisjayson 发表于 2017-10-24 23:40
用Heap不行么？

heap好像不是面试官想要的答案

westcoastboy 发表于 2017-10-25 01:51
您的意思是 一个doubly linkedlist + 一个排序Linkedlist？

就是用的一个double linkedlist + Hashmap~