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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: "根据log只用update那些在heap里的keyword 和上一分钟search过的keyword。"
: 你是说上30分钟？
: 继续优化可以approximate吗？例如只存top 100k keywords in all time
|
x******0
发帖数: 178 | 7 当然可以搞个moving average。。。我说了以后，貌似对方也不满意
【在 o***g 的大作中提到】
:
: 这个太夸张了
|
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 的大作中提到】
: 统计最近30分钟google的top 10 searched keywords -- getTop10InLast30mins(),需
: 要经常调用。
|
x******0
发帖数: 178 | 9 谢谢！这个想法很好。
只不过那个interviewer总是觉得我每个keyword用了太多storage，moving average又
不对，百思不得其解。。
【在 m*****n 的大作中提到】
: 有个想法，你可以试试。
: 不用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 的大作中提到】
: 当然可以搞个moving average。。。我说了以后，貌似对方也不满意
|
b*****c
发帖数: 1103 | |
x******0
发帖数: 178 | 13 你说的对，我刚开始是说对所有的做操作。后来面试官一质疑，我就马上改过来，只对
被搜索的keyword做这个操作。但是他还是觉得我统计这些keyword的方法太expensive。
貌似这个面试feedback还不错，但是肯定没有达到面试官心中的optimal。应该是差不
远了。
【在 o***g 的大作中提到】
: 你没搞懂，我为什么说太夸张了
: 我的理解你选择的数据集有问题，我理解是你要对所有的数据集做这个操作。包括在这
: 一分钟里没有被搜索的关键词也要做这个操作。如果你真是这么想的就太夸张了，如果
: 面试官也这么认为的就糟糕了。数据集没选对，后面怎么算都不行啊
|
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 的大作中提到】
: 你说的对，我刚开始是说对所有的做操作。后来面试官一质疑，我就马上改过来，只对
: 被搜索的keyword做这个操作。但是他还是觉得我统计这些keyword的方法太expensive。
: 貌似这个面试feedback还不错，但是肯定没有达到面试官心中的optimal。应该是差不
: 远了。
|
U***A
发帖数: 849 | |
x******0
发帖数: 178 | 17 赞一个
【在 o***g 的大作中提到】
: 我不知道面试官要的是啥，也许他有非常牛逼的算法之类的。
: 但是我想从工程师的角度说说这种问题。不是教授角度。
: 在你心中这些关键词集合是个什么样子？一些随机的字符串？想成这样是不够的。
: 一共在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 的大作中提到】
: 我不知道面试官要的是啥，也许他有非常牛逼的算法之类的。
: 但是我想从工程师的角度说说这种问题。不是教授角度。
: 在你心中这些关键词集合是个什么样子？一些随机的字符串？想成这样是不够的。
: 一共在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 的大作中提到】
: 我不知道面试官要的是啥，也许他有非常牛逼的算法之类的。
: 但是我想从工程师的角度说说这种问题。不是教授角度。
: 在你心中这些关键词集合是个什么样子？一些随机的字符串？想成这样是不够的。
: 一共在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 的大作中提到】
: 不过大猩猩，我问你个问题
: 你这里面确定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 的大作中提到】
: 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 的大作中提到】
: 赵老师啊，我跟楼主只是在说面试官说楼主存储空间太大不满意的问题
: 界定？我原帖最后一段说了，这个不是严谨的方法。就是说只是一个粗略的方法。
: 方法我不是提了3个。忽略的意思是见到这个关键词就直接看下一个了，不给空间也不
: 做统计，就当没有这个词。根本没有保留多长时间的问题。
: 不严谨有时也有好处，记得几年前央视焦点访谈曝光谷歌搜索关键词提示涉黄。
: 那个提示词那么长，肯定是有人故意而为才顶上去的，如果把长关键词都忽略了，这事
: 儿也成不了。
: 就这个问题，其实还有很多地方需要考虑，而你提到的这些heap hashmap之类的在我来
: 看是最不重要的。
: 比如如何采集这些关键词，需要确定用户搜索的关键词都能采集到。这事儿其实就挺难
|
c*******y
发帖数: 98 | 23 我去，这就是senior和new grad的区别所在了，new grad除非是脑补天才根本不可能答
的这么迪奥。
【在 o***g 的大作中提到】
: 赵老师啊，我跟楼主只是在说面试官说楼主存储空间太大不满意的问题
: 界定？我原帖最后一段说了，这个不是严谨的方法。就是说只是一个粗略的方法。
: 方法我不是提了3个。忽略的意思是见到这个关键词就直接看下一个了，不给空间也不
: 做统计，就当没有这个词。根本没有保留多长时间的问题。
: 不严谨有时也有好处，记得几年前央视焦点访谈曝光谷歌搜索关键词提示涉黄。
: 那个提示词那么长，肯定是有人故意而为才顶上去的，如果把长关键词都忽略了，这事
: 儿也成不了。
: 就这个问题，其实还有很多地方需要考虑，而你提到的这些heap hashmap之类的在我来
: 看是最不重要的。
: 比如如何采集这些关键词，需要确定用户搜索的关键词都能采集到。这事儿其实就挺难
|
o***g
发帖数: 2784 | 24 你看我propose的忽略长度是多少，50呢，这个还需要看一下统计数据，我估计看完之
后，20也可以。你给的克什米亚才4个字符长度啊。
我说这个不严谨了，就是理论上有漏的可能性。但是这种可能出现的概率是极低的，即
便一年有一次，又有什么关系呢
退一万步讲，如果world cup 2014 final game这个能进前10，那我想world cup final
一定比那个更多。你不会错过这种信息的。
【在 z****e 的大作中提到】
: 不是，猩猩啊
: 你要等一个定长时间之后才能看出这个关键词出现的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 的大作中提到】
: 你看我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 的大作中提到】
: 嗯，大猩猩的意思我大概明白了
: 但是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 | |
