r****m
发帖数: 70 | 1 Design an architecture to find out top 5 shared links in Linkedin in the
past 5 mins/1 hour/1 day/1 week/1 month/1 year.
除了map-reduce，还有上面其他的方法吗，求指点 |
z****e
发帖数: 54598 | 2 讨论过不少次了
其实这是一个多线程的题
我第一感觉是用hashmap做
后来看得古德霸等牛人的说法
貌似hashmap是共识
然后就是产品的各种bla bla bla了
看你熟悉什么就上什么了 |
g***9
发帖数: 159 | |
r****m
发帖数: 70 | |
c*******2
发帖数: 60 | 5 对于这样的题, 我想问一下, 比如说是显示过去一小时某某东西的时候,
假设现在是 09:00, 那么就显示 08:00--09:00之间的;
然后等到 09:01的时候呢? 是显示 08:01--09:01还是09:00-09:01之间的呢?
上面我是用的"分"做最小单位, 如果换成"秒"或者"毫秒"呢? |
a***y
发帖数: 50 | |
A******g
发帖数: 612 | 7 感觉就是一个sql statement...
【在 z****e 的大作中提到】
: 讨论过不少次了
: 其实这是一个多线程的题
: 我第一感觉是用hashmap做
: 后来看得古德霸等牛人的说法
: 貌似hashmap是共识
: 然后就是产品的各种bla bla bla了
: 看你熟悉什么就上什么了
|
l*****t
发帖数: 2019 | 8 有link么？
【在 z****e 的大作中提到】
: 讨论过不少次了
: 其实这是一个多线程的题
: 我第一感觉是用hashmap做
: 后来看得古德霸等牛人的说法
: 貌似hashmap是共识
: 然后就是产品的各种bla bla bla了
: 看你熟悉什么就上什么了
|
y**********u
发帖数: 6366 | 9 你确定你没有在误导人吗？
【在 z****e 的大作中提到】
: 讨论过不少次了
: 其实这是一个多线程的题
: 我第一感觉是用hashmap做
: 后来看得古德霸等牛人的说法
: 貌似hashmap是共识
: 然后就是产品的各种bla bla bla了
: 看你熟悉什么就上什么了
|
k*********6
发帖数: 738 | 10 这个是不是用rolling window啊？具体怎样加新的扔掉旧的呢？ |
|
|
i********s
发帖数: 22 | 11 感觉上这个应该是个olap engine的设计题目；类似快速求sum之类的；
按照时间窗口保存top K link & count，按照时间窗口做merge即可； |
g**e
发帖数: 6127 | 12 偶像终于出现了
【在 y**********u 的大作中提到】
: 你确定你没有在误导人吗？
|
n*******1
发帖数: 145 | 13 用一个circle 时间做tag 然后指针旋转 删除数据添加数据 更新最大值 只想到这个了 |
z****e
发帖数: 54598 | |
z****e
发帖数: 54598 | 15 存在db里太浪费了
【在 A******g 的大作中提到】
: 感觉就是一个sql statement...
|
z****e
发帖数: 54598 | 16 最早以前我不确定
最早有人问的时候，就有人说过circle，我就感觉应该是hashmap
还说过了比hashtable快十倍的说法，懒得继续找了
后来又有人问
我看了古德霸和这位牛人的说法，我确定了，应该是没有错
priorty queue等不是不行，但是并发时候效率堪忧，锁得太多
这个牛人做message的，举的大部分例子都是message
可能在twitter，我猜的
所以对于它给出的答案，我会认真阅读
发信人: rtscts (syslink), 信区: JobHunting
标 题: Re: most clicked urls in the last 5 mins, 1hr, 24 hrs?
发信站: BBS 未名空间站 (Fri Aug 9 18:44:21 2013, 美东)
这个是经典的stream processing问题。
Server把url扔到后端，后端有数个server或者process,最简单的方法就是hash url然
后决定按hashcode把url扔到那个server或者process （modulo就可以了）,这个
process就把url累计count一下，然后把url:count这个pair 扔到后一级的process或者
server，后一级的server把url:count存到一个concurrent hashmap里。一个thread 大
概每10秒钟把这个map扫一遍，给出前10名。
这是很粗略的方法，讲究一些的可以加各种花里胡哨的东西上去。
知道twitter storm吗？就是干这个的。http://storm-project.net/ 阿里巴巴和淘宝都在用，估计那个主要开发者Xu Mingming也是淘宝的。 竞争对手是Apache S4,但是S4明显不是对手。
【在 y**********u 的大作中提到】
: 你确定你没有在误导人吗？
|
z****e
发帖数: 54598 | 17 现在大部分计算机精确不到ms
也不是不行，但是需要定制，real time的领域跟大部分web系统不是一回事
linkedin用不到那么精确
【在 c*******2 的大作中提到】
: 对于这样的题, 我想问一下, 比如说是显示过去一小时某某东西的时候,
: 假设现在是 09:00, 那么就显示 08:00--09:00之间的;
: 然后等到 09:01的时候呢? 是显示 08:01--09:01还是09:00-09:01之间的呢?
: 上面我是用的"分"做最小单位, 如果换成"秒"或者"毫秒"呢?
|
z****e
发帖数: 54598 | |
z****e
发帖数: 54598 | |
z****e
发帖数: 54598 | 20 你上次问我的aop的问题
也没什么很fancy的部分
无非用spring aop或者aspectj做几个拦截器
然后生成log，扔在nosql里面
然后查找起来方便，这样可以分离log代码和主代码
这也是aop的本意，然后查找时候可以用hadoop或者scala
这样就不需要用蛋疼的grep了
【在 l*****t 的大作中提到】
: 有link么？
|
g*****g
发帖数: 34805 | 21 我给个分布式设计，过面试应该够了。
每个share产生一个event，发给一个dispatch cluster，这个cluster干的活就是根据
url算个hash出来，分配给下一个count cluster，所以相同的url会发给同一个结点处
理。count cluster上每个结点需要一个存一个根据时间排列的queue，每个dispatch
event会产生一个当前时间的+1 job和5分钟后的-1 job。queue可以用诸如Cassandra
DB time based UUID实现，scheduled excutor可以用Java的
ScheduledExecutorService实现。这个结点可以用ConcurrentSkipListMap 维护所有
link count并快速获得top 5 link。count cluster是最大的一个cluster，比如说有
1000个结点。
接下来如果count cluster很大，可以有一个aggregation cluster，干的事情是周期性
poll (比如说每5秒) count cluster 的一部分获得所有top 5排序并保存top 5
snapshot。比如说10个结点，每个结点管10个count node。最上层的结点会有所有
linkedin link的top 5。当然你会让多个结点在最上面，query这个cluster即可。
dispatch 10
count 1000
aggregation 10
query 10
至于5分钟，1年啥的，维护不同的queue就够了。不支持任意时间的top 5。 |
