Glassdoor上一道bb的题

wcsoswto

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

Design question about web traffic

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

lor="#404040">谁知道如果constant time得到top-10。

33847682

是lfu么？

myangelasuka

heap啊 recording是logn heap.pop() is O(1)

wcsoswto

myangelasuka 发表于 2017-1-5 12:39
heap啊 recording是logn heap.pop() is O(1)

那record怎么constant time啊？

myangelasuka

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

laiguojiuhao

因为是top 10不是top k嘛，维护一个大小为10的最小堆，记录次数就用哈希表，每次hit之后和堆顶元素比较就行了

tcui

这题应该是用double linked list吧，可以参考LC上的All-O-One data structure 那题