请教一个面试题（已跪） - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>DataSciences - 数据科学

请教一个面试题（已跪）

请教一个面试题（已跪）# DataSciences - 数据科学

e*92015-07-26 07:07

1 楼

下面给了一个网站的访问记录。
要求是找出在10分钟内访问超过500次的robot。
写程序，说明为什么选择某个算法，讨论大数据情况下怎么样。
请问这样的问题都要考虑什么？谢谢！
Anonymous User ID TimeStamp Activity Count
223 9:45am 10
134 9:46am 12
134 9:50am 20
656 9:53am 100
223 9:55am 33
656 9:56am 312
223 10:03am 110
223 10:16am 312
134 10:20am 201
656 10:23am 180
223 10:25am 393
656 10:27am 312

N*G2015-07-26 07:07

2 楼

首先，需要一个缓存存最近10分钟的访问，即（user id， timestamp）pair，这是一
个滑动窗口，时间复杂度和读入一样，空间复杂度取决于最繁忙10分钟有多少访问
然后，建一个map，key是user id，value是这个user id最近10分钟的访问次数。读入
新访问，则对应value +1，然后处理已经过期的访问（>10分钟），将对应value -1。
每次读入均摊时间复杂度O(1)。空间复杂度=不同user个数。当然如果删除value=0的
map，空间复杂度=max(所有连续10分钟里出现不同user id的个数)

e*92015-07-26 07:07

3 楼

谢谢楼上！
应该说我的思路跟你的差不多。
我应该先写出来的。
有一个要说的是是看Activity Count总数超过500
是否还有其它要考虑的？
或许是我的程序风格不够好？
是否有高手愿意帮我看看？
私信给你
不想把程序贴上来了。。。
不胜感激！

Z*02015-07-26 07:07

4 楼

看看这个，Mining of Massive Datasets，
http://infolab.stanford.edu/~ullman/mmds/ch4.pdf
也许对你有帮助。
这个log是streaming？

d*62015-07-26 07:07

5 楼

思路差不多，具体细节有问题
假设这是一个stream的log
1. 你怎么判断那个访问已经过期？
2. 你怎么记录哪个10分钟的阶段访问超过500？
你只记录value显然无法解决第一个问题
第二个问题更麻烦，比如一个user在3分钟内就访问达到500次，那么往后7分钟的
stream继续进来，你要记录多少次？

【在 N******G 的大作中提到】

: 首先，需要一个缓存存最近10分钟的访问，即（user id， timestamp）pair，这是一
: 个滑动窗口，时间复杂度和读入一样，空间复杂度取决于最繁忙10分钟有多少访问
: 然后，建一个map，key是user id，value是这个user id最近10分钟的访问次数。读入
: 新访问，则对应value +1，然后处理已经过期的访问（>10分钟），将对应value -1。
: 每次读入均摊时间复杂度O(1)。空间复杂度=不同user个数。当然如果删除value=0的
: map，空间复杂度=max(所有连续10分钟里出现不同user id的个数)

m*g2015-07-26 07:07

6 楼

If the data is stored in a database, can't you do a SQL?
a1: current timestamp
a2: previous record within 10 mins window
SELECT a1.user_id, a1.TimeStamp as TimeStamp, SUM(a2.Activity_Count) as
visits_in_10mins
FROM activities a1
INNER JOIN activities a2
ON a1.TimeStamp BETWEEN a2.TimeStamp AND a2.TimeStamp + 10/(24*60)
AND a1.user_id = a2.user_id
GROUP BY a1.TimeStamp,a1.user_id
HAVING SUM(a2.Activity_Count) >= 500;

l*e2015-07-26 07:07

7 楼

如果是一个stream的话, create a ring buffer per user, size is 10, each slot
stores the visited count for 1 minutes. Expired slots will automatically be
overwritten.The total count of last 10 minutes for a user is the sum of the
ring buffer. Then use heap to get top-K.
Reference:
http://www.michael-noll.com/blog/2013/01/18/implementing-real-t

u*h2015-07-26 07:07

8 楼

1. 做一个dict, key 是 User ID,value 是一个 Queue
2. Queue 里的每一个node, 包含一个timestamp 和一个activity count.
3. 每次读取一行数据，根据user ID, 找到dict中的队列（如果是新ID,
那么就创建新队列）。把当前的timeStamp 和activity count加入队列。
根据当前的timeStamp，将10分钟以前的node踢出队列。队列计数，如果
大于500就汇报“机器人”。
4. 每隔n分钟，对dict进行一次清理：根据当前的timeStamp, 要求所有
dict中的队列都清理掉10分钟以前的node.
讨论： n 可以取值1-无穷大，如果内存小， n需要取比较小的值，如果内存
大， n可以取比较大的值。

【在 e********9 的大作中提到】

: 下面给了一个网站的访问记录。
: 要求是找出在10分钟内访问超过500次的robot。
: 写程序，说明为什么选择某个算法，讨论大数据情况下怎么样。
: 请问这样的问题都要考虑什么？谢谢！
: Anonymous User ID TimeStamp Activity Count
: 223 9:45am 10
: 134 9:46am 12
: 134 9:50am 20
: 656 9:53am 100
: 223 9:55am 33

e*92015-07-26 07:07

9 楼

谢谢大家的建议！
我是觉得他们故意题目出的不完善
比如没有日期光有小时和分钟
比如判断出一个ID在某个10分钟内是robot后还要怎么处理
我也做了些讨论。。。
还是不清楚他们到底要什么