Q****a
发帖数: 296 | |
p*****2
发帖数: 21240 | 2 spark
【在 Q****a 的大作中提到】
: 这个怎么实现比较好，求大牛们指教
|
Q****a
发帖数: 296 | 3 二爷，面试中不能这么说吧。。。求个相关link吧，我记得以前看到过类似的问题，现
在一时搜不到了。。。
【在 p*****2 的大作中提到】
: spark
|
p*****2
发帖数: 21240 | 4 我觉得面试可以呀 如果真是项目实际问题 有轮子当然要用了
【在 Q****a 的大作中提到】
: 二爷，面试中不能这么说吧。。。求个相关link吧，我记得以前看到过类似的问题，现
: 在一时搜不到了。。。
|
f*******w
发帖数: 1243 | 5 同求好的idea，之前在版上也问过，在网上也没找着好的解法
我能想到的是用queue和hash来maintain time window，然后需要return的时候扫一遍
hash找top k...
时间和空间复杂度都很高 |
q********c
发帖数: 1774 | 6 stream processing典型应用，上kafka+storm或者spark.
【在 f*******w 的大作中提到】
: 同求好的idea，之前在版上也问过，在网上也没找着好的解法
: 我能想到的是用queue和hash来maintain time window，然后需要return的时候扫一遍
: hash找top k...
: 时间和空间复杂度都很高
|
f*******w
发帖数: 1243 | 7
用轮子是好，可是有时候面试官会问具体用什么数据结构实现啊
【在 q********c 的大作中提到】
: stream processing典型应用，上kafka+storm或者spark.
|
q********c
发帖数: 1774 | 8 那你就看看他们具体是怎么实现的。
【在 f*******w 的大作中提到】
:
: 用轮子是好，可是有时候面试官会问具体用什么数据结构实现啊
|
p********r
发帖数: 66 | 9 不知道数据量有多大，我们就当是内存存不下吧
1. 对数据进行划分，按照 hash(string) % k, 先处理一边文件，分成k个小文件 (对
同一个查询，分析一个小文件就能得到了)
2. 创建一个长度为n的 min-heap (n就是你要返回的最热门查询的个数)
3. 分析每一个文件，统计字符串对应的访问次数，可以用hashMap或者Trie树。
4. 根据统计结果更新min-heap
5. 排序 |
p********r
发帖数: 66 | 10 如果我去面Groupon可以这么回答吗？ 哈哈
【在 p*****2 的大作中提到】
: spark
|
|
|
p*****2
发帖数: 21240 | 11 可以 能做到这一步 已经比大多数人强了
【在 p********r 的大作中提到】
: 如果我去面Groupon可以这么回答吗？ 哈哈
|
f*******w
发帖数: 1243 | 12
这个是文件已经给好的解法
如果是real time stream就不能这样了啊
【在 p********r 的大作中提到】
: 不知道数据量有多大，我们就当是内存存不下吧
: 1. 对数据进行划分，按照 hash(string) % k, 先处理一边文件，分成k个小文件 (对
: 同一个查询，分析一个小文件就能得到了)
: 2. 创建一个长度为n的 min-heap (n就是你要返回的最热门查询的个数)
: 3. 分析每一个文件，统计字符串对应的访问次数，可以用hashMap或者Trie树。
: 4. 根据统计结果更新min-heap
: 5. 排序
|
m*****k
发帖数: 731 | |
p********r
发帖数: 66 | 14 这样的话，内存中得维持一个HashMap和min-heap 实时更新可以吗？
如果一个节点内存不够，还是使用相同的方法（hash(string) % k）把查询分配给多个
节点，每个节点用HashMap来统计
同时在主节点上维持一个min-heap
main node (min heap) -- node 1 (hashmap)
-- node 2 (hashmap)
...
-- node k (hashmap)
关键是处理同步问题，其它思路类似
【在 f*******w 的大作中提到】
:
: 这个是文件已经给好的解法
: 如果是real time stream就不能这样了啊
|
f*******w
发帖数: 1243 | 15
关键是不好更新
先不考虑内存不够的情况，光用hashmap和minheap是没法实现实时记录任意时刻前一个
小时的数据；你怎么删掉过期的数据？遍历一遍hash？
【在 p********r 的大作中提到】
: 这样的话，内存中得维持一个HashMap和min-heap 实时更新可以吗？
: 如果一个节点内存不够，还是使用相同的方法（hash(string) % k）把查询分配给多个
: 节点，每个节点用HashMap来统计
: 同时在主节点上维持一个min-heap
: main node (min heap) -- node 1 (hashmap)
: -- node 2 (hashmap)
: ...
: -- node k (hashmap)
: 关键是处理同步问题，其它思路类似
|
f*******w
发帖数: 1243 | |
c******f
发帖数: 243 | |
g*********e
发帖数: 14401 | 18 很好，下一个问题，请简单设计一下spark 写点schedule算法
【在 p*****2 的大作中提到】
: 我觉得面试可以呀 如果真是项目实际问题 有轮子当然要用了
|
k***g
发帖数: 166 | 19 土人路过，你们是肿么知道spark可以解决这类问题的？求link学习下，谢谢 |
p*****2
发帖数: 21240 | 20 多向好虫半海学习
赵策也行
【在 k***g 的大作中提到】
: 土人路过，你们是肿么知道spark可以解决这类问题的？求link学习下，谢谢
|
