t*****e
发帖数: 53 | 1 Assume the data cannot fit in memory. You can provide either exact or
approximate solutions. Please provide more details about your solution. |
i***h
发帖数: 12655 | 2 近似：
内存有多少用多少， 每个记录出现次数
当新的记录进来， 内存不够了， 踢掉最少最老的记录
精确：
用外部文件存结果？ |
b*******d
发帖数: 750 | 3 哥也被问到这道题了，略有不同，给出了incoming query的distribution的曲线，qps
是几千这样子。这个system有三个api：
1）getTopTenMillionInPastHour()
2) isInTopTenMilionInPastHour()
3) notifyWhenJoinOrRemovedFromTopTenMillionInPastHour()
自己来architect系统，定义service能提供数据的精度。
我当时给的是个多台机器的架构。我觉得是旧data每秒钟都在产生（任何当前时间进行
的api call，准确来说，1小时零1秒前的数据都是旧的，对算top10millioninPastHour
没有意义），但几乎没有任何系统在一秒钟内可以purge掉这么多的旧数据，所以就要
定义一个精度。比如，semantics是“我能保证给结果是精确的，但是有个最多20分钟
的delay”，或者“我不能保证结果是100%精确的，但是我能最新的query能够实时的反
应在结果中，并且返回的结果和真值有90%的重合”。
其实就是说consistency，availability，partition/sharding， 只能选两样。 |
w****x
发帖数: 2483 | 4
比如找top 10 queries, 把大文件hash分成200个小文件, 每个小文件可以放入内存.
每个小文件取top 5 queries, 从1000个query中找出前10个, 除非很巧, 基本可以得出
top 10
【在 t*****e 的大作中提到】
: Assume the data cannot fit in memory. You can provide either exact or
: approximate solutions. Please provide more details about your solution.
|
N**n
发帖数: 832 | 5 大神你还没回答我你从哪儿找到的800道题呢
【在 w****x 的大作中提到】
:
: 比如找top 10 queries, 把大文件hash分成200个小文件, 每个小文件可以放入内存.
: 每个小文件取top 5 queries, 从1000个query中找出前10个, 除非很巧, 基本可以得出
: top 10
|
t*****e
发帖数: 53 | 6 踢掉最少最老的记录
But those queries might showed again in the future? they might be in the
list of top 10 queries.
【在 i***h 的大作中提到】
: 近似：
: 内存有多少用多少， 每个记录出现次数
: 当新的记录进来， 内存不够了， 踢掉最少最老的记录
: 精确：
: 用外部文件存结果？
|
t*****e
发帖数: 53 | 7 Can you explain more detail about your system? Particularly, how you can get
the 90% accuracy?
qps
top10millioninPastHour
【在 b*******d 的大作中提到】
: 哥也被问到这道题了，略有不同，给出了incoming query的distribution的曲线，qps
: 是几千这样子。这个system有三个api：
: 1）getTopTenMillionInPastHour()
: 2) isInTopTenMilionInPastHour()
: 3) notifyWhenJoinOrRemovedFromTopTenMillionInPastHour()
: 自己来architect系统，定义service能提供数据的精度。
: 我当时给的是个多台机器的架构。我觉得是旧data每秒钟都在产生（任何当前时间进行
: 的api call，准确来说，1小时零1秒前的数据都是旧的，对算top10millioninPastHour
: 没有意义），但几乎没有任何系统在一秒钟内可以purge掉这么多的旧数据，所以就要
: 定义一个精度。比如，semantics是“我能保证给结果是精确的，但是有个最多20分钟
|
