校招面试编程题范文

《校招面试编程题范文》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、校招面试编程题范文　　　　1、海量日志数据提取出某日访问百度次数最多的那个IP　　　　首先是这一天并且是访问百度的日志中的IP取出来逐个写入到一个大文件中注意到IP是32位的最多有个2^32个IP同样可以采用映射的方法比如模1000把整个大文件映射为1000个小文件再找出每个小文中出现频率最大的IP(可以采用hashmap进行频率统计然后再找出频率最大的几个)及相应的频率然后再在这1000个最大的IP中找出那个频率最大的IP即为所求　　　　或者如下阐述：　　　　算法思想：分而治之+Hash　　　　1.IP地址最多有2^32=4G种取值情况所以不能完全加载到内存中处

2、理;　　　　2.可以考虑采用“分而治之”的思想按照IP地址的Hash(IP)24值把海量IP日志分别存储到1024个小文件中这样每个小文件最多包含4MB个IP地址;　　　　3.对于每一个小文件可以构建一个IP为key出现次数为value的Hashmap同时记录当前出现次数最多的那个IP地址;　　　　4.可以得到1024个小文件中的出现次数最多的IP再依据常规的排序算法得到总体上出现次数最多的IP;　　　　2、搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来每个查询串的长度为1255字节　　　　假设目前有一千万个记录(这些查询串的重复度比较高虽然总数是

3、1千万但如果除去重复后不超过3百万个一个查询串的重复度越高说明查询它的用户越多也就是越热门)请你统计最热门的10个查询串要求使用的内存不能超过1G　　　　典型的TopK算法还是在这篇文章里头有所阐述　　　　文中给出的最终算法是：　　　　第一步、先对这批海量数据预处理在O(N)的时间内用Hash表完成统计(之前写成了排序特此订正July、xx.04.27);　　　　第二步、借助堆这个数据结构找出TopK时间复杂度为N‘logK　　　　即借助堆结构我们可以在log量级的时间内查找和调整/移动因此维护一个K(该题目中是10)大小的小根堆然后遍历300万的Query分别和

4、根元素进行对比所以我们最终的时间复杂度是：O(N)+N’*O(logK)(N为1000万N’为300万)ok更多详情请参考原文　　　　或者：采用trie树关键字域存该查询串出现的次数没有出现为0最后用10个元素的最小推来对出现频率进行排序　　　　3、有一个1G大小的一个文件里面每一行是一个词词的大小不超过16字节内存限制大小是1M返回频数最高的100个词　　　　方案：顺序读文件中对于每个词x取hash(x)P00然后按照该值存到5000个小文件(记为x0,x1,…x4999)中这样每个文件大概是200k左右　　　　如果其中的有的文件超过了1M大小还可以按照类似的方

5、法继续往下分直到分解得到的小文件的大小都不超过1M　　　　对每个小文件统计每个文件中出现的词以及相应的频率(可以采用trie树/hashmap等)并取出出现频率最大的100个词(可以用含100个结点的最小堆)并把100个词及相应的频率存入文件这样又得到了5000个文件下一步就是把这5000个文件进行归并(类似与归并排序)的过程了　　　　4、有10个文件每个文件1G每个文件的每一行存放的都是用户的query每个文件的query都可能重复要求你按照query的频度排序　　　　还是典型的TOPK算法解决方案如下：　　　　方案1：　　　　顺序读取10个文件按照hash(q

6、uery)的结果将query写入到另外10个文件(记为)中这样新生成的文件每个的大小大约也1G(假设hash函数是随机的)　　　　找一台内存在2G左右的机器依次对用hashmap(query,querycount)来统计每个query出现的次数利用快速/堆/归并排序按照出现次数进行排序将排序好的query和对应的querycout输出到文件中这样得到了10个排好序的文件(记为)　　　　对这10个文件进行归并排序(内排序与外排序相结合)　　　　方案2：　　　　一般query的总量是有限的只是重复的次数比较多而已可能对于所有的query一次性就可以加入到内存了这样我们

7、就可以采用trie树/hashmap等直接来统计每个query出现的次数然后按出现次数做快速/堆/归并排序就可以了　　　　方案3：　　　　与方案1类似但在做完hash分成多个文件后可以交给多个文件来处理采用分布式的架构来处理(比如MapReduce)最后再进行合并　　　　5、给定a、b两个文件各存放50亿个url每个url各占64字节内存限制是4G让你找出a、b文件共同的url?　　　　方案1：可以估计每个文件安的大小为5G×64=320G远远大于内存限制的4G所以不可能将其完全加载到内存中处理考虑采取分而治之的方法　　　　遍历文件a对每个url求取hash(ur

8、l)00然