关于Top K实时排序的做法（BB/Bloomberg/彭博）经典题

最近刷面经经常看到BB家考这道题，实时更新top k成交量的stock
蠡口上有Top K Frequency的题，用HashMap统计频率再用TreeMap排序，但是非实时的

如果要求实时，LZ想就是需要取中间某时刻截面的临时数据再输入它们的意思吧。
LZ觉得还是用HashMap+TreeMap，每收到一个数据包，用一个update函数去更新，然后从TreeMap里面打印出top K。类似于LFU的做法。
时间复杂度是HashMap O(1)+TreeMap O(logn)

各位大神们还有没有更优化的做法呢，求赐教~~~

这种问题如果想回答得有深度的话会有很多trade-off要讨论，可以看看下面这些文章：

A Survey of Top-k Query Processing Techniques in Relational Database Systems
http://www.cs.umd.edu/~samir/498/topk.pdf

Efficient Computation of Frequent and Top-k Elements in Data Streams ⋆
http://www.cse.ust.hk/~raywong/comp5331/References/EfficientComputationOfFrequentAndTop-kElementsInDataStreams.pdf

Continuous Monitoring of Top-K Queries over Sliding Windows
http://ink.library.smu.edu.sg/cgi/viewcontent.cgi?article=1546&context=sis_research

感觉这题也可以变成系统设计考

magicsets 发表于 2018-5-5 10:17
这种问题如果想回答得有深度的话会有很多trade-off要讨论，可以看看下面这些文章：

A Survey of Top-k Q ...

Thank you so much! They are very helpful!

magicsets 发表于 2018-5-5 10:17
这种问题如果想回答得有深度的话会有很多trade-off要讨论，可以看看下面这些文章：

A Survey of Top-k Q ...

层主专业了！ 厉害！

magicsets 发表于 2018-5-5 10:17
这种问题如果想回答得有深度的话会有很多trade-off要讨论，可以看看下面这些文章：

A Survey of Top-k Q ...

非常感谢分享，对我很有帮助