百度电面-----搜索词汇排名前十------我的灵感。

easyhaohao

浏览: 13611 次
性别:
来自: 上海

最近访客更多访客>>

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

论坛发帖

百度面试多线程

百度给我同学的一个电面试题，

如何统计搜索词汇的前十名。

最近看了HASHMAP的源码实现相关文章，

受到启发。

觉得可以用HASHSET实现

将所有关键字记录进HASHSET

关键字类

大概如下


class MyKeyWord
{ 
String keyWord;
int counts;
}

每次counts+1;

并且设定一个阀值VALVE1当超过多少时就将此对象添加进一个

LIST里（此LIST用于记录COUNTS较大的关键字），

对LIST 做排序，排序可以考虑用多线程归并排序

对LIST 也设定一个阀值，当LIST中的元素个数大于阀值时，

提高VALVE1的值，并重新调整删除LIST中阀值小于新阀值的元素。

以上纯属胡言乱语。。哈哈哈哈

分享到：

由读书遇瓶颈---------延伸下去的-------- ...

2011-05-18 13:14
浏览 997
评论(17)
论坛回复 / 浏览 (17 / 11985)
分类:编程语言
查看更多

17 楼抛出异常的爱 2011-05-23

ansjsun 写道

百度没天的搜索词估计有几千万..几个亿..如果用hash我觉得不行啊..java的hash支持大小也就是几十万...我觉得多少需要点人工参与的..人工筛选一个范围...维护一个词表再统计..否则我觉得搜索..为什么..肯定是第一了...

当然如果有能力..可以对当天..搜索top10做一个统计..从中发现新词..然后加入到词表中...

如果对搜索框再次分词的话．
应该还木有几个亿
中文比Ｅ文的总词量少些．．．

16 楼云中苍月 2011-05-23

一楼二楼说的是同一个意思。
正解！

15 楼 ansjsun 2011-05-23

14 楼 jcs7575 2011-05-22

fflover 写道

easyhaohao 写道


class MyKeyWord
{ 
String keyWord;
int counts;
}

说实话感觉不如堆排序,
这个当时我想的是hash+堆排序.但是后来我才知道,其实搜索的时候就像是访问数据库,有一个很大的cache,搜索的时候搜索引擎首先进行分词,然后在查询cache,逻辑组合查询结果,所以我们可以从cache里面选取命中率最高的排序就可以了.. 这样的话可以减少很多不必要的的排序.

这个题目可以延伸的，比如文件超大的情况，就要考虑切分文件，用hash了

13 楼 jcs7575 2011-05-22

用小顶堆，不是大顶

melanlife 写道

维护一个大顶堆

12 楼 fflover 2011-05-19

其实我现在倒觉得这个选出十大热门关键字并不是精确的,并没有真正的统计一天的所有结果,而只是统计了cache系统中一段时间中命中率最高的十个关键字,cache系统有自己的替换、淘汰机制。

11 楼 fflover 2011-05-19

easyhaohao 写道


class MyKeyWord
{ 
String keyWord;
int counts;
}

10 楼 easyhaohao 2011-05-19

<div class="quote_title">LeoChowComtop 写道</div>
<div class="quote_div">
<div class="quote_title">easyhaohao 写道</div>
<div class="quote_div">百度给我同学的一个电面试题， 如何统计搜索词汇的前十名。 最近看了HASHMAP的源码实现相关文章， 受到启发。 觉得可以用HASHSET实现 将所有关键字记录进HASHSET 关键字类 大概如下 <pre name="code" class="java">class MyKeyWord
{
String keyWord;
int counts;
}

</pre>
 每次counts+1; 并且设定一个阀值VALVE1当超过多少时就将此对象添加进一个 LIST里（此LIST用于记录COUNTS较大的关键字）， 对LIST 做排序，排序可以考虑用多线程归并排序 对LIST 也设定一个阀值，当LIST中的元素个数大于阀值时， 提高VALVE1的值，并重新调整删除LIST中阀值小于新阀值的元素。 以上纯属胡言乱语。。哈哈哈哈</div>
 
 
 
考察的只是大数据量排序？
我觉的关键点不在这， SE 这么大范围，高并发的被调用，不考虑下资源同步问题，如何保证准确度和效率？
极少跟帖，求赐教
</div>
 额，我只是看了HASHMAP的相关文章然后胡言乱语的。。<img src="/images/smiles/icon_biggrin.gif" alt="">

9 楼 LeoChowComtop 2011-05-19

<div class="quote_title">easyhaohao 写道</div>
<div class="quote_div">百度给我同学的一个电面试题， 如何统计搜索词汇的前十名。 最近看了HASHMAP的源码实现相关文章， 受到启发。 觉得可以用HASHSET实现 将所有关键字记录进HASHSET 关键字类 大概如下 <pre name="code" class="java">class MyKeyWord
{
String keyWord;
int counts;
}

</pre>
 每次counts+1; 并且设定一个阀值VALVE1当超过多少时就将此对象添加进一个 LIST里（此LIST用于记录COUNTS较大的关键字）， 对LIST 做排序，排序可以考虑用多线程归并排序 对LIST 也设定一个阀值，当LIST中的元素个数大于阀值时， 提高VALVE1的值，并重新调整删除LIST中阀值小于新阀值的元素。 以上纯属胡言乱语。。哈哈哈哈</div>
 
 
 
考察的只是大数据量排序？
我觉的关键点不在这， SE 这么大范围，高并发的被调用，不考虑下资源同步问题，如何保证准确度和效率？
极少跟帖，求赐教

8 楼 shaka 2011-05-19

晕，看来各大公司这面试题和解决办法也是抄来抄去

7 楼 lwjlaser 2011-05-19

melanlife 写道

维护一个大顶堆

用反堆了

6 楼 lwjlaser 2011-05-19

大小为10的最小堆

5 楼 bao231 2011-05-19

这个场景是否可以用 部分快速排序实现呢，通常如果数据量很大的话，可以考虑部分快速排序。

4 楼 cloud21 2011-05-19

pouyang 写道

抛出异常的爱写道

生成一个10个长的MyKeyWord数组
一个第10名点击次数与位置指针
一个hashBag
每加一个词看一下是否大于第10名点击次数
大于的话放入数组第10名

之后一次遍历找到点击次数最小的位置与值修正指针

抛哥说得不错，看了那么多抛哥的回帖，总感觉抛哥的文笔不是很达意，即不是很清晰明了，但说的总是非常正确。

嗯，用MAP最合适了，抛哥说的很明确了，变动位置，整体修正。

3 楼 pouyang 2011-05-18

抛出异常的爱写道

抛哥说得不错，看了那么多抛哥的回帖，总感觉抛哥的文笔不是很达意，即不是很清晰明了，但说的总是非常正确。

2 楼 melanlife 2011-05-18

维护一个大顶堆

1 楼抛出异常的爱 2011-05-18

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论