我要招人

去企业版

首页 > 试题广场 >

实现一个简化的搜索提示系统。给定一个包含了用户query的日

[问答题]

实现一个简化的搜索提示系统。给定一个包含了用户query的日志文件，对于输入的任意一个字符串s，输出以s为前缀的在日志中出现频率最高的前10条query。

由于是分布式系统，假设至少有26台机器，每个机器存储以26个字母开头的query日志文件（如机器1存的是a字母开头的，机器2存的是以b字母开头的……）

每个机器上维护着一张哈希表，对于每条query, 在哈希表表中存放其地址（哈希地址为链式的），并对其进行排序，按频率由高到低进行排序。

当用户进行搜索时，可以很快定位到某台机器，并根据哈希表，返回出现频率最高的前10条query。

提示：

1、可以预处理日志

2、假设query不超过10亿条，每个query不超过50字节。

3、考虑在大查询量的情况下如何实现分布式服务

牛客-007

（PS~ ：想到一种思路不知道行不行，写出来大家提提意见哈）

系统前台：

用JS监控input输入框的内容变化，用户输入或者删除字符（输入串的发生变化）就触发异步Javascript提交输入内容到后台，引发后台查询。然后再讲查询结果出现频率最高的前10条query展现给用户提示。

系统后台：

首先有26台服务器分别存储26个字母开头的query。所以首先要设计一个接收用户请求的服务器，这台服务器可以根据用户请求的首字母将查询请求分发给对应26台服务器中的一个（相当于查询请求的路由功能）。

然后就是这26台查询服务器如何设计的问题了。

假设query不超过10亿条，每个query不超过50字节。也就是query文件不超过50G，分在26台机器上也就是每台机器上的query文件不超过2G。

每个机器上维护着一张哈希表，对于每条query, 在哈希表表中存放其地址。收到每个query做hash运算可以找到query对应的地址。对应每个query存储两项信息，即query本身和被查询次数，也就是类似query:times这样的存储格式。

下面做预处理：26台机器都对自身存储的query进行遍历，分别找出a到z开头query出现频率最高的top10，这样的查询一次遍历就能找到，时间复杂度为O（N）。然后对找到的top10在内存中构建一个最小堆。其他非top10的query无需做排序处理。到这里预处理完成。

然后说查询过程，查询分为两类，

1，以给出搜索提示的异步Javascript提交的查询，这种查询直接返回最小堆中的10个query词条即可。

2，用户最终提交的查询（即用户输入完毕点击搜索按钮提交的查询），这种查询的query是用户最终查询的词条，这样的查询应该引起后台存储的对应query频率的变化。当一个query到达的时候，先用hash运算找到他的位置和对应的频率，hash操作时间复杂度是O(1),然后对应的次数+1，然后用这个+1的次数与最小堆中首个元素比较，如果大于最小堆首个元素，与最小堆中首个元素交换，然后最小堆做更新操作，保证最小堆的特性。否则不操作。这样最小堆中维护的10个query始终是这台机器上频率最高的，查询时返回这10个query词条即可。

编辑于 2015-03-30 21:21:05 回复(8)

牛客441326号

Trie树？

发表于 2016-04-02 11:04:50 回复(0)

牛客527850号

1. 利用所有query先构建一个trie树

2. 当来一个新query时，利用trie树进行检索，并以结束的节点为根进行前序搜索，得到所有所有包含前缀的字符串和对应数量，放到10个元素的最大堆里调整。

发表于 2018-01-18 19:52:47 回复(0)

7up

哈希表用来定位，大顶堆用来保证顺序，当需要更新的时候，通过哈希表迅速定位到大顶堆中query所在的节点，然后upHeap进行调整。

分布式服务的话，考虑采用分布式缓存、复制、负载均衡等策略吧...

发表于 2015-04-17 00:13:18 回复(0)

ThyBoox

1.每台机器的预处理

每台机器维护一张hash表,<key,value>=<query,times>，即表的键为每个query，值为query在本机器日志文件中出现的次数，这样用O(N)时间可以统计每个日志文件中每条记录出现的次数，其中N为日志文件的记录条数。

2.查询前台传过来的作为前缀的字符串s

根据字符串的首字母定位到对应的机器后，为了找出以s为前缀的top10，可以初始化一个最小堆，初始化方法是把hash表的前十个以s为前缀的记录填进最小堆，然后遍历剩余的hash表，如果当前的记录是以s为前缀，则用当前记录更新最小堆，否则继续下一条记录，直到把hash表遍历完，返回最小堆中的10条记录，时间复杂度为log10*N

缺点：为了找到以s为前缀的字符窜，把整个hash表都遍历了一遍，即比较每条记录是否以s开头，要是能把hash表的散列函数设计成和key的前缀有关就好了，这就就可以过滤掉很多条记录了。

为了解决上述缺点，Map可以选择TreeMap.

由于TreeMap是可以排序的，我们可以根据每条记录出现的频率对TreeMap进行降序排序，这样当需要找出以s为前缀的top10时，只需要找到前十个以s为前缀的记录就行了，因为TreeMap是降序的，后面就算还有以s为前缀的也进不了top10

发表于 2015-08-30 16:22:28 回复(0)

NSDaBen

搜索一般都不是即时的，即不会即时就搜索出网络上出现的新内容，也不会即时删除已经过是的内容。

日志就是一个文件，在这里就是被搜索的文件。

预处理就是有程序定时的去处理文件，按照常用的搜索关键字去完整的搜索文件，并建立索引文件，当用户搜索时，可以直接通过索引文件返回给用户。

分布式，就是拆分了，比如每个服务器分别处理不同的站点，或是一个文件中不同的区段，将处理的结果返回给主服务器，合并后返回给用户。

发表于 2015-05-18 23:37:29 回复(0)

黄小斜

1根据首字母hash到对应机器，每台机器的query表维护成一个大根堆，可返回频率最高的十条query。

2分布式：负载均衡，使用集群，使用缓存。

发表于 2017-04-03 16:53:12 回复(0)

提交观点

问题信息

哈希百度分布式系统设计

来自：腾讯2015春招后台开...

上传者：四只拖鞋

难度：

7条回答 315收藏 14623浏览

实现一个简化的搜索提示系统。给定一个包含了用户query的日

问题信息

热门推荐

相关试题