Amazon hackerrank 240 min 题目

据说发帖子可以攒人品，发一个刚刚的online code assignment

地里面找来的内推，10/16周一推得，周五收到了Most Popular Videos 的code assignment。今天做完和提交。
题目就是实时获取video的popular程度和排名，需要实现三个函数,

videoViewed(String videoId) - 观看video，每看一次view次数就会增加
getRanking(String video) 根据一个videoId，找到其排名，排名根据views的次数来排序
getTopVideos() - 得到前十排名

video大概数量为1 million，设计一个实现方案来存储和获取video，要求详细写明思考的过程，分析复杂度，必要时注释。

我用的方法就是类似LRU的实现，hashmap + doubly linkedlist，如果view的次数变动，那么就移动那个video 的linkedlist节点到相应的位置。

黓龙君 发表于 2017-10-25 06:00
getTopVideos() 是用 PriorityQueue 来实现吗? 如果只用 LinkedList + HashMap，那 getRanking(S ...

LinkedList就是有序的，里面记录rank，更新view的时候一起更新下，所以getRanking就直接是O(1)了。getTopVideos()直接从头取一次就行。

水果糖 发表于 2017-10-26 02:20
能详细说下么? 我不会并发。

1m 的库，按理说不大可能只有一个人去访问。

如果多个人同时访问了一个video，你要怎么处理？

比如有两个Thread同时call videoViewed("1") 这样

RightSoFar 发表于 2017-10-26 10:05
1m 的库，按理说不大可能只有一个人去访问。

如果多个人同时访问了一个video，你要怎么处理？

好的，谢谢。我给你发私信了，能加微信请教下这个问题么？

请问lz是实习还是ft？

msu_HIDDEN 发表于 2017-10-24 07:05
请问lz是实习还是ft？

fulltime，我是准备在职跳槽

LFU。紫薯

我上周末也做了这个，昨天催hr去看看，今天给我说他们没收到，但会再帮我查下。。。真是玄学公司服了

lyj87372517 发表于 2017-10-25 01:07
我上周末也做了这个，昨天催hr去看看，今天给我说他们没收到，但会再帮我查下。。。真是玄学公司服了

啊，是么，那我明天也再问下HR试试

getTopVideos() 是用 PriorityQueue 来实现吗? 如果只用 LinkedList + HashMap，那 getRanking(String video) 感觉要花 O(n) 的时间，有点太长了。在想怎么优化。

这种应该要考虑并发的吧。

RightSoFar 发表于 2017-10-25 15:59
这种应该要考虑并发的吧。

能详细说下么? 我不会并发。