x******0 发帖数: 178 | 1 统计最近30分钟google的top 10 searched keywords -- getTop10InLast30mins(),需
要经常调用。 |
t********e 发帖数: 344 | 2 distributed count + min heap? |
x******0 发帖数: 178 | 3 minheap 是肯定的。
我当时说需要对每个keyword 维护一个circular array,大小可以是30,记录每分钟的
search数目。
但是这样的话每分钟都要为每个keyword update这个array,而且minheap也要update。
可以进一步优化,根据log只用update那些在heap里的keyword 和上一分钟search过的
keyword。
貌似interviewer还是不满意,说这样存储的cost还是可以优化。
【在 t********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : distributed count + min heap?
|
t********e 发帖数: 344 | 4 "根据log只用update那些在heap里的keyword 和上一分钟search过的keyword。"
你是说上30分钟?
继续优化可以approximate吗?例如只存top 100k keywords in all time |
o***g 发帖数: 2784 | 5
这个太夸张了
【在 x******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : minheap 是肯定的。 : 我当时说需要对每个keyword 维护一个circular array,大小可以是30,记录每分钟的 : search数目。 : 但是这样的话每分钟都要为每个keyword update这个array,而且minheap也要update。 : 可以进一步优化,根据log只用update那些在heap里的keyword 和上一分钟search过的 : keyword。 : 貌似interviewer还是不满意,说这样存储的cost还是可以优化。
|
x******0 发帖数: 178 | 6 30分钟只是个参数,可以是1分钟,5分钟。。。
【在 t********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : "根据log只用update那些在heap里的keyword 和上一分钟search过的keyword。" : 你是说上30分钟? : 继续优化可以approximate吗?例如只存top 100k keywords in all time
|
x******0 发帖数: 178 | 7 当然可以搞个moving average。。。我说了以后,貌似对方也不满意
【在 o***g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 这个太夸张了
|
m*****n 发帖数: 2152 | 8 有个想法,你可以试试。
不用array,用linked list,
每个keyword维护linked list,
有的keyword如果每分钟都会出现,就是30个nodes(假设最长30),每个node存的是前
n分钟的总数,不是第n分钟的次数。
有的keyword不是每分钟都会出现,就小于30个nodes。
linked list可以滚动没问题。
从说明来看,这个function一般是getTop10inLast30, 10, 5, 1 几个特殊时间的数
,不是1-30都有。
在更新linked list的时候(时间复杂度 < 30*O(n) ),可以对这几个特殊时间建堆,只
要4个 10个element的minheap。 应该是< 4*log10*O(n)的时间复杂度。
【在 x******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 统计最近30分钟google的top 10 searched keywords -- getTop10InLast30mins(),需 : 要经常调用。
|
x******0 发帖数: 178 | 9 谢谢!这个想法很好。
只不过那个interviewer总是觉得我每个keyword用了太多storage,moving average又
不对,百思不得其解。。
【在 m*****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 有个想法,你可以试试。 : 不用array,用linked list, : 每个keyword维护linked list, : 有的keyword如果每分钟都会出现,就是30个nodes(假设最长30),每个node存的是前 : n分钟的总数,不是第n分钟的次数。 : 有的keyword不是每分钟都会出现,就小于30个nodes。 : linked list可以滚动没问题。 : 从说明来看,这个function一般是getTop10inLast30, 10, 5, 1 几个特殊时间的数 : ,不是1-30都有。 : 在更新linked list的时候(时间复杂度 < 30*O(n) ),可以对这几个特殊时间建堆,只
|
b*****c 发帖数: 1103 | |
|
|
o***g 发帖数: 2784 | 11 你没搞懂,我为什么说太夸张了
我的理解你选择的数据集有问题,我理解是你要对所有的数据集做这个操作。包括在这
一分钟里没有被搜索的关键词也要做这个操作。如果你真是这么想的就太夸张了,如果
面试官也这么认为的就糟糕了。数据集没选对,后面怎么算都不行啊
【在 x******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 当然可以搞个moving average。。。我说了以后,貌似对方也不满意
|
b*****c 发帖数: 1103 | |
x******0 发帖数: 178 | 13 你说的对,我刚开始是说对所有的做操作。后来面试官一质疑,我就马上改过来,只对
被搜索的keyword做这个操作。但是他还是觉得我统计这些keyword的方法太expensive。
貌似这个面试feedback还不错,但是肯定没有达到面试官心中的optimal。应该是差不
远了。
【在 o***g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你没搞懂,我为什么说太夸张了 : 我的理解你选择的数据集有问题,我理解是你要对所有的数据集做这个操作。包括在这 : 一分钟里没有被搜索的关键词也要做这个操作。如果你真是这么想的就太夸张了,如果 : 面试官也这么认为的就糟糕了。数据集没选对,后面怎么算都不行啊
|
W*********y 发帖数: 481 | |
o***g 发帖数: 2784 | 15 我不知道面试官要的是啥,也许他有非常牛逼的算法之类的。
但是我想从工程师的角度说说这种问题。不是教授角度。
在你心中这些关键词集合是个什么样子?一些随机的字符串?想成这样是不够的。
一共在google被搜索过的关键词的数量级肯定不是M,往上高个3到6个数量级都是非常
可能的。在一分钟内被搜索过的关键词,多数是长尾(long tail)的,少数是重复次
数很高的。这些长尾的关键词有些甚至几周几个月才被搜索一次。长尾关键词占总搜索
次数比却是很小的。30分钟之内,为什么不是5分钟10分钟,可能5分钟10分钟的所有关
键词操作一下是能搞定的,但是30分钟内,很多关键词其实只出现过1次2次。因为只要
前10个,所以,这些长尾的就可以不用计算直接忽略掉。如果要前1000个10000个,忽
略的关键词还真得谨慎点儿,前10个的话,很多都可以忽略掉。
下面是我能想到的3个方法
1. 专业的学术术语,这个开销比较大,需要查字典,不太实用
2. 搜索结果小于多少就可以忽略了
3. 关键词长度,大于多少字符就可以忽略了。50肯定是没问题的,20我觉得都可以一
试。
第三个是最简单最有效的,不用其他资源就可以。
这种东西严谨么?肯定是不严谨的,但是是有效的。这东西也没法拿出来说,但实际大
家都在用。
expensive。
【在 x******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你说的对,我刚开始是说对所有的做操作。后来面试官一质疑,我就马上改过来,只对 : 被搜索的keyword做这个操作。但是他还是觉得我统计这些keyword的方法太expensive。 : 貌似这个面试feedback还不错,但是肯定没有达到面试官心中的optimal。应该是差不 : 远了。
|
U***A 发帖数: 849 | |
x******0 发帖数: 178 | 17 赞一个
【在 o***g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我不知道面试官要的是啥,也许他有非常牛逼的算法之类的。 : 但是我想从工程师的角度说说这种问题。不是教授角度。 : 在你心中这些关键词集合是个什么样子?一些随机的字符串?想成这样是不够的。 : 一共在google被搜索过的关键词的数量级肯定不是M,往上高个3到6个数量级都是非常 : 可能的。在一分钟内被搜索过的关键词,多数是长尾(long tail)的,少数是重复次 : 数很高的。这些长尾的关键词有些甚至几周几个月才被搜索一次。长尾关键词占总搜索 : 次数比却是很小的。30分钟之内,为什么不是5分钟10分钟,可能5分钟10分钟的所有关 : 键词操作一下是能搞定的,但是30分钟内,很多关键词其实只出现过1次2次。因为只要 : 前10个,所以,这些长尾的就可以不用计算直接忽略掉。如果要前1000个10000个,忽 : 略的关键词还真得谨慎点儿,前10个的话,很多都可以忽略掉。
|
z****e 发帖数: 54598 | 18 可以建一级cache,二级cache,三级cache……
【在 o***g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我不知道面试官要的是啥,也许他有非常牛逼的算法之类的。 : 但是我想从工程师的角度说说这种问题。不是教授角度。 : 在你心中这些关键词集合是个什么样子?一些随机的字符串?想成这样是不够的。 : 一共在google被搜索过的关键词的数量级肯定不是M,往上高个3到6个数量级都是非常 : 可能的。在一分钟内被搜索过的关键词,多数是长尾(long tail)的,少数是重复次 : 数很高的。这些长尾的关键词有些甚至几周几个月才被搜索一次。长尾关键词占总搜索 : 次数比却是很小的。30分钟之内,为什么不是5分钟10分钟,可能5分钟10分钟的所有关 : 键词操作一下是能搞定的,但是30分钟内,很多关键词其实只出现过1次2次。因为只要 : 前10个,所以,这些长尾的就可以不用计算直接忽略掉。如果要前1000个10000个,忽 : 略的关键词还真得谨慎点儿,前10个的话,很多都可以忽略掉。
|
z****e 发帖数: 54598 | 19 不过大猩猩,我问你个问题
你这里面确定freq比较少的,比如过去30分钟只出现1次2次的这种
你如何界定?你要删不也要等到30分钟之后才删?
你还是要把这个term以及timestamp保留在内存结构或者某个db什么的里面呀
这题除了heap以外,我觉得就是一个hashmap用来统计次数
最后删除时候会遇到一个并发的问题,而且需要你保存log
这个log用linkedlist也未尝不可,但是每次删除log呢,是一个很费时间的过程
如果用当前thread,会导致整个thread被blocked,所以最好额外启动一个thread
统计完,去保存次数那个hashmap里面扣除你刚删除掉的那些terms的freq的时候
一定会遇到并发冲突的问题,所以需要用到concurrenthashmap
所以我上次就不认为从array开始弄有什么道理,你还不同意我
我觉得这题三个点回答出来
一个priorityqueue,就是min heap的实现
另外一个是concurrenthashmap,考并发
最后一个是timestamp,这个可以扯一下logic clock
最后拼凑起来,就很圆满了
【在 o***g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我不知道面试官要的是啥,也许他有非常牛逼的算法之类的。 : 但是我想从工程师的角度说说这种问题。不是教授角度。 : 在你心中这些关键词集合是个什么样子?一些随机的字符串?想成这样是不够的。 : 一共在google被搜索过的关键词的数量级肯定不是M,往上高个3到6个数量级都是非常 : 可能的。在一分钟内被搜索过的关键词,多数是长尾(long tail)的,少数是重复次 : 数很高的。这些长尾的关键词有些甚至几周几个月才被搜索一次。长尾关键词占总搜索 : 次数比却是很小的。30分钟之内,为什么不是5分钟10分钟,可能5分钟10分钟的所有关 : 键词操作一下是能搞定的,但是30分钟内,很多关键词其实只出现过1次2次。因为只要 : 前10个,所以,这些长尾的就可以不用计算直接忽略掉。如果要前1000个10000个,忽 : 略的关键词还真得谨慎点儿,前10个的话,很多都可以忽略掉。
|
o***g 发帖数: 2784 | 20 赵老师啊,我跟楼主只是在说面试官说楼主存储空间太大不满意的问题
界定?我原帖最后一段说了,这个不是严谨的方法。就是说只是一个粗略的方法。
方法我不是提了3个。忽略的意思是见到这个关键词就直接看下一个了,不给空间也不
做统计,就当没有这个词。根本没有保留多长时间的问题。
不严谨有时也有好处,记得几年前央视焦点访谈曝光谷歌搜索关键词提示涉黄。
那个提示词那么长,肯定是有人故意而为才顶上去的,如果把长关键词都忽略了,这事
儿也成不了。
就这个问题,其实还有很多地方需要考虑,而你提到的这些heap hashmap之类的在我来
看是最不重要的。
比如如何采集这些关键词,需要确定用户搜索的关键词都能采集到。这事儿其实就挺难
的。
我能想到的是,互联网上到处都有各级cache,如果某个cache中了,就直接返回了,这
个request都没有到服务器就返回了,你可能就没有得到这次搜索。第二个是,即便到g
家的服务器了,服务器也是遍布世界各地的。(各个城市搜索链接的服务器是不同的,
同一个关键词的返回结果可能是不同的哦!!!)在世界各地的这些数据怎么集中到一
起。
还有时间戳的问题,用户是12.999秒发出的搜索,到服务器是13.01秒,这个应该算在
12秒里还是13秒里?再说服务器时间都可能不完全一样。
如果只是做题的话,可能上面这些不用考虑,但是实际工作就需要考虑。我不知道如果
面试的时候提这些情况会不会加分。
我做了很多tracking report之类的工作,各个地方统计的数很难对的上,即便一天几
十个的都很难对的上。但是单个测试的时候总是通过的。
所以有了这些背景知识,最后统计的时候有些不严谨是不是也是可以接受的呢
【在 z****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不过大猩猩,我问你个问题 : 你这里面确定freq比较少的,比如过去30分钟只出现1次2次的这种 : 你如何界定?你要删不也要等到30分钟之后才删? : 你还是要把这个term以及timestamp保留在内存结构或者某个db什么的里面呀 : 这题除了heap以外,我觉得就是一个hashmap用来统计次数 : 最后删除时候会遇到一个并发的问题,而且需要你保存log : 这个log用linkedlist也未尝不可,但是每次删除log呢,是一个很费时间的过程 : 如果用当前thread,会导致整个thread被blocked,所以最好额外启动一个thread : 统计完,去保存次数那个hashmap里面扣除你刚删除掉的那些terms的freq的时候 : 一定会遇到并发冲突的问题,所以需要用到concurrenthashmap
|
|
|
i*******t 发帖数: 79 | 21 为什么是min heap不是max?
arraylist存(keyword,time,count, heap1 node, heap2 node)
hashmap存(keyword,index),或者用trie存index
一个max heap放index,以count为比较值
第二个max heap放index,以time为比较值。
每次接到一个keyword,更新这4个数据结构(先用trie或者map找到index)
每次调用的时候或者hashmap一定大的时候按照第二个heap,去掉所有的超时元素,更
新4个数据结构
【在 x******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : minheap 是肯定的。 : 我当时说需要对每个keyword 维护一个circular array,大小可以是30,记录每分钟的 : search数目。 : 但是这样的话每分钟都要为每个keyword update这个array,而且minheap也要update。 : 可以进一步优化,根据log只用update那些在heap里的keyword 和上一分钟search过的 : keyword。 : 貌似interviewer还是不满意,说这样存储的cost还是可以优化。
|
z****e 发帖数: 54598 | 22 不是,猩猩啊
你要等一个定长时间之后才能看出这个关键词出现的freq呢?
举个例子,当你看到克什米亚之后直接忽略,因为一般情况下这个词是低频词
那么万一短时间内这个克什米亚大量出现呢?
因为每次你都忽略,所以会导致你无法统计出这个关键词的freq
这样对于短时间内出现的热点会错过的呀
【在 o***g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 赵老师啊,我跟楼主只是在说面试官说楼主存储空间太大不满意的问题 : 界定?我原帖最后一段说了,这个不是严谨的方法。就是说只是一个粗略的方法。 : 方法我不是提了3个。忽略的意思是见到这个关键词就直接看下一个了,不给空间也不 : 做统计,就当没有这个词。根本没有保留多长时间的问题。 : 不严谨有时也有好处,记得几年前央视焦点访谈曝光谷歌搜索关键词提示涉黄。 : 那个提示词那么长,肯定是有人故意而为才顶上去的,如果把长关键词都忽略了,这事 : 儿也成不了。 : 就这个问题,其实还有很多地方需要考虑,而你提到的这些heap hashmap之类的在我来 : 看是最不重要的。 : 比如如何采集这些关键词,需要确定用户搜索的关键词都能采集到。这事儿其实就挺难
|
c*******y 发帖数: 98 | 23 我去,这就是senior和new grad的区别所在了,new grad除非是脑补天才根本不可能答
的这么迪奥。
【在 o***g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 赵老师啊,我跟楼主只是在说面试官说楼主存储空间太大不满意的问题 : 界定?我原帖最后一段说了,这个不是严谨的方法。就是说只是一个粗略的方法。 : 方法我不是提了3个。忽略的意思是见到这个关键词就直接看下一个了,不给空间也不 : 做统计,就当没有这个词。根本没有保留多长时间的问题。 : 不严谨有时也有好处,记得几年前央视焦点访谈曝光谷歌搜索关键词提示涉黄。 : 那个提示词那么长,肯定是有人故意而为才顶上去的,如果把长关键词都忽略了,这事 : 儿也成不了。 : 就这个问题,其实还有很多地方需要考虑,而你提到的这些heap hashmap之类的在我来 : 看是最不重要的。 : 比如如何采集这些关键词,需要确定用户搜索的关键词都能采集到。这事儿其实就挺难
|
o***g 发帖数: 2784 | 24 你看我propose的忽略长度是多少,50呢,这个还需要看一下统计数据,我估计看完之
后,20也可以。你给的克什米亚才4个字符长度啊。
我说这个不严谨了,就是理论上有漏的可能性。但是这种可能出现的概率是极低的,即
便一年有一次,又有什么关系呢
退一万步讲,如果world cup 2014 final game这个能进前10,那我想world cup final
一定比那个更多。你不会错过这种信息的。
【在 z****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不是,猩猩啊 : 你要等一个定长时间之后才能看出这个关键词出现的freq呢? : 举个例子,当你看到克什米亚之后直接忽略,因为一般情况下这个词是低频词 : 那么万一短时间内这个克什米亚大量出现呢? : 因为每次你都忽略,所以会导致你无法统计出这个关键词的freq : 这样对于短时间内出现的热点会错过的呀
|
z****e 发帖数: 54598 | 25 嗯,大猩猩的意思我大概明白了
但是query term一般指的是用户输入的关键字
其他的叫做co term,这种一般有query expansion的说法
比如world cup 2014 final game
真正输入的query term估计只有world cup两个,剩下的是系统自动expand的
比如crimea,然后系统会自动补足其他的co term,比如conflict这些
这里面文章很大,不仅仅是删掉long tail就好了的
而且你只删超过50个字符长的搜索,这个估计也不会有太大优化的作用
因为很少有人会输入超过20个或者50个字符长度的搜索酱紫
当然删除低频词是必需的,要不然内存会增长得很快
但是我觉得存最近30分钟得数据
也是必需的
所以一读一写,这里就自然涉及读写冲突问题,这就是为什么会说到concurrent处理
而且query log本身是很重要的一个query expansion的来源
其实真正query expansion,比如crimea->crimea conflict
这种都是通过mining log得到的,所以有些低级和原始,为学术界所不齿
但是用得比较多
final
【在 o***g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你看我propose的忽略长度是多少,50呢,这个还需要看一下统计数据,我估计看完之 : 后,20也可以。你给的克什米亚才4个字符长度啊。 : 我说这个不严谨了,就是理论上有漏的可能性。但是这种可能出现的概率是极低的,即 : 便一年有一次,又有什么关系呢 : 退一万步讲,如果world cup 2014 final game这个能进前10,那我想world cup final : 一定比那个更多。你不会错过这种信息的。
|
s******s 发帖数: 89 | 26 比较认同赵大牛的方法。
用一个HashMap 来记得current minute 的
Keywords 和它的出现次数。用 一个Queue of
size of 30 (因为30 分钟,也可以是60分钟)
来记录 每一分钟的map,构成 一个动态
leaking buffle Queue,这样就可以精确
算出last 30 minutes, 60 minutes, 24 hours
freq Top K keywords.
【在 z****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 嗯,大猩猩的意思我大概明白了 : 但是query term一般指的是用户输入的关键字 : 其他的叫做co term,这种一般有query expansion的说法 : 比如world cup 2014 final game : 真正输入的query term估计只有world cup两个,剩下的是系统自动expand的 : 比如crimea,然后系统会自动补足其他的co term,比如conflict这些 : 这里面文章很大,不仅仅是删掉long tail就好了的 : 而且你只删超过50个字符长的搜索,这个估计也不会有太大优化的作用 : 因为很少有人会输入超过20个或者50个字符长度的搜索酱紫 : 当然删除低频词是必需的,要不然内存会增长得很快
|
c****l 发帖数: 1280 | |
a***n 发帖数: 623 | 28 我去。。。感叹一下这种题目不是欺负new grad么。。。
其实每个词平时都是有词频统计的,比如fukujima这个词平时是铁定进不了top10的。
这题目一个大小为10的minheap肯定要,然后再搞个pool装一些最近n分钟突然频率暴涨
的词就可以了,比如fukujima地震那半小时这个词频肯定异常暴涨。
然后每个词每分钟统计出来可以和平时的词频对比一下,如果区别不大又是长尾词就丢
了,否则进二级pool,如果在二级pool里统计发现累加前30分钟的次数已经高于heap
top的次数了则进heap。 |
s***m 发帖数: 5 | |