dropbox一道题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

dropbox一道题

dropbox一道题# JobHunting - 待字闺中

f*l2015-08-28 07:08

1 楼

给出一堆log, 里面有photo id和访问时间, 还有一个iterator, 能够按照photoId
和访问时间iterate, 问如何输出top m的访问photo
followup: 如何存储这些log, 来支持方便的retrieve 这些信息.
哪位大神能给个思路吗？谢谢！

t*r2015-08-28 07:08

2 楼

先遍历一遍存成哈希表再用heap?
存在内存或缓存里 Id : list of acces time

H*s2015-08-28 07:08

3 楼

如果iterator可以按photoid排序，那一个heap就可以，
否则用hashmap存photoid和count
如果单机内存不够放整个hashmap，可以考虑用distributed memory cache，比如
memcache或者redis.
存数据的时候最好用photoid shard到不同的小文件中，这样计算的时候不需要存整个
photoid的空间，可以把计算top m的工作distribute到多台机器上计算，最后merge。
也可以用mapreduce

g*u2015-08-28 07:08

4 楼

log是已经写好的，还是还在不停写，要给出当前top m?
不管怎么样，都得知道每个photo的frequency，然后根据frequency做partial sort取
top m。楼主，这题是不是这意思呢？各位聪明的小白兔们说说看。

【在 f*********l 的大作中提到】

: 给出一堆log, 里面有photo id和访问时间, 还有一个iterator, 能够按照photoId
: 和访问时间iterate, 问如何输出top m的访问photo
: followup: 如何存储这些log, 来支持方便的retrieve 这些信息.
: 哪位大神能给个思路吗？谢谢！

f*l2015-08-28 07:08

5 楼

不太清楚，我也是从网上看的这道题目。应该是给定的一堆log，stream的情况也可以
讨论一下哈

【在 g*****u 的大作中提到】

: log是已经写好的，还是还在不停写，要给出当前top m?
: 不管怎么样，都得知道每个photo的frequency，然后根据frequency做partial sort取
: top m。楼主，这题是不是这意思呢？各位聪明的小白兔们说说看。