搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来,每个查询串的长度不超过255字节。假设目前有一千万个查询记录(重复度比较高,其实互异的查询串不超过三百万个;显然,一个查询串的重复度越高,说明查询它的用户越多,也就是越热门)。现要统计最热门的1 0个查询串,且要求使用的内存不能超过1GB。以下各方法中,可行且效率最高的方法是( )。
此题也是考查对基本算法的理解运用,首先快速排序方法是不适合于这种情况的,由于重复度比较高,因此事实上只有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万)。这是一道百度面试题。
( )is the process of transforming information so it is unintelligible to anyone but the intended recipient.
As each application module is completed,it undergoes( )to ensure that it operates correctly and reliably.
( )algorithm specifies the way to arrange data in a particular order.
After analyzing the source code,( )generates machine instructions that will carry out the meaning of the program at a later time.
( )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.
浏览器开启无痕浏览模式后,( )依然会被保存下来。
下列协议中,不属于TCP/IP协议簇的是( )。
下列传输介质中,带宽最宽、抗干扰能力最强的是( )。
数控编程常需要用参数来描述需要加工的零件的图形。在平面坐标系内,确定一个点需要2个独立的参数,确定一个正方形需要( )个独立的参数。
某书的页码为1,2,3,...,共用数字900个(一个多位数页码包含多个数字),据此可以推断,该书最大的页码为( )。