当前位置:首页计算机类软件水平考试初级程序员->搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下

搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来,每个查询串的长度不超过255字节。假设目前有一千万个查询记录(重复度比较高,其实互异的查询串不超过三百万个;显然,一个查询串的重复度越高,说明查询它的用户越多,也就是越热门)。现要统计最热门的1 0个查询串,且要求使用的内存不能超过1GB。以下各方法中,可行且效率最高的方法是( )。

  • A.将一千万个查询串存入数组并进行快速排序,再统计其中每个查询串重复的次数
  • B.将一千万个查询串存入数组并进行堆排序,再统计其中每个查询串重复的次数
  • C.利用哈希表保存所有的查询串并记下每个查询串的重复次数,再利用小根堆选出重复次数最多的1 0个查询串
  • D.利用哈希表保存所有的查询串并记下每个查询串的重复次数,再利用大根堆选出重复次数最多的1 0个查询串
查看答案 纠错
答案: C
本题解析:

此题也是考查对基本算法的理解运用,首先快速排序方法是不适合于这种情况的,由于重复度比较高,因此事实上只有300万的Query,每个Query255Byte, 可以考虑把他们都放进内存中去,300万X255=765M,不会超过1G,因此可以用Hash_Map的思路。先对这批海量数据预处理(维护一个Key为Query字串,Value为该Query出现次数的HashTable,即hash_map(Query,Value),每次读取一个Query,如果该字串不在Table中,那么加入该字串,并且将Value值设为1;如果该字串在Table中,那么将该字串的计数加1即可。最终我们在O(N)的时间复杂度内用Hash表完成了统计;第二步、借助堆这个数据结构,找出Top K,时间复杂度为N‘logK。即借助堆结构,我们可以在log量级的时间内查找和调整/移动。因此,维护一个K(该题目中是10)大小的小根堆,然后遍历300万的Query,分别和根元素进行对比,采用最小堆这种数据结构代替数组,把查找目标元素的时间复杂度降到了0(logk),我们最终的时间复杂度是:O(N) + N*O(logK)。(N为1000万,N’为300万)。这是一道百度面试题。

更新时间:2021-11-22 18:49

你可能感兴趣的试题

单选题

(  )is the process of transforming information so it is unintelligible to anyone but the intended recipient.

  • A.Encryption
  • B.Decryption
  • C.Security
  • D.Protection
查看答案
单选题

As each application module is completed,it undergoes(  )to ensure that it operates correctly and reliably.

  • A.unit testing
  • B.integration testing
  • C.system testing
  • D.acceptance testing
查看答案
单选题

(  )algorithm specifies the way to arrange data in a particular order.

  • A.Search
  • B.Random
  • C.Sorting
  • D.Merge
查看答案
单选题

After analyzing the source code,(  )generates machine instructions that will carry out the meaning of the program at a later time.

  • A.an interpreter
  • B.a linker
  • C.a compiler
  • D.a converter
查看答案
单选题

(  )can help organizations to better understand the information contained within the data and will also help identify the data that is most important to the business and future business decisions.

  • A.Data processing system
  • B.Big Data analytics
  • C.Cloud computing
  • D.Database management
查看答案
单选题

浏览器开启无痕浏览模式后,(  )依然会被保存下来。

  • A.浏览历史
  • B.搜索历史
  • C.已下载文件
  • D.临时文件
查看答案
单选题

下列协议中,不属于TCP/IP协议簇的是(  )。

  • A.CSMA/CD
  • B.IP
  • C.TCP
  • D.UDP
查看答案
单选题

下列传输介质中,带宽最宽、抗干扰能力最强的是(  )。

  • A.双绞线
  • B.红外线
  • C.同轴电缆
  • D.光纤
查看答案
单选题

数控编程常需要用参数来描述需要加工的零件的图形。在平面坐标系内,确定一个点需要2个独立的参数,确定一个正方形需要(  )个独立的参数。

  • A.3
  • B.4
  • C.5
  • D.6
查看答案
单选题

某书的页码为1,2,3,...,共用数字900个(一个多位数页码包含多个数字),据此可以推断,该书最大的页码为(  )。

  • A.237
  • B.336
  • C.711
  • D.900
查看答案