工程建设标准网站,网站制作背景图片,二级学院网站建设报告,wordpress只在首页显示1. TOP K 算法
有10个⽂件#xff0c;每个⽂件1G#xff0c;每个⽂件的每⼀⾏存放的都是⽤户的 query#xff0c;每个⽂件的 query 都可能重复。要求你按照 query 的频度排序。
方法1#xff1a; 顺序读取10个⽂件#xff0c;按照 hash(query)%10 的结果将 query 写⼊到…1. TOP K 算法
有10个⽂件每个⽂件1G每个⽂件的每⼀⾏存放的都是⽤户的 query每个⽂件的 query 都可能重复。要求你按照 query 的频度排序。
方法1 顺序读取10个⽂件按照 hash(query)%10 的结果将 query 写⼊到另外 10 个⽂件记为中。这样新⽣成的⽂件每个的⼤⼩⼤约也 1G假设 hash 函数是随机的。找⼀台内存在 2G 左右的机器依次对⽤hash_map(query, query_count)来统计每个 query 出现的次数。利⽤快速/堆/归并排序按照出现次数进⾏排序。将排序好的 query 和对应的 query_cout 输出到⽂件中。这样得到了 10 个排好序的⽂件记为。对这 10 个⽂件进⾏归并排序内排序与外排序相结合。 方法2 与⽅案 1 类似但在做完 hash分成多个⽂件后可以交给多个⽂件来处理采⽤分布式的架构来处理⽐如 MapReduce最后再进⾏合并。
2. 不重复的数据
在 2.5 亿个整数中找出不重复的整数注内存不⾜以容纳这 2.5 亿个整数。 解答 1⽅案 1采⽤ 2-Bitmap每个数分配 2bit00 表示不存在01 表示出现⼀次10 表示多次11 ⽆意义进⾏共需内存 2^32 * 2bit1 GB 内存还可以接受。然后扫描这 2.5 亿个整数查看 Bitmap 中相对应位如果是 00 变 0101 变 1010 保持不变。所描完事后查看 bitmap把对应位是 01 的整数输出即可。 2⽅案 2也可采⽤与第 1 题类似的⽅法进⾏划分⼩⽂件的⽅法。然后在⼩⽂件中找出不重复的整数并排序。然后再进⾏归并注意去除重复的元素。
3. 判断数据是否存在
给 40 亿个不重复的 unsigned int 的整数没排过序的然后再给⼀个数如何快速判断这个数是否在那 40 亿个数当中 1⽅案 1oo申请 512M 的内存⼀个 bit 位代表⼀个 unsigned int 值。读⼊ 40 亿个数设置相应的 bit 位读⼊要查询的数查看相应 bit 位是否为 1为 1 表示存在为 0 表示不存在。
4. 重复最多的数据
有⼀千万条短信有重复以⽂本⽂件的形式保存⼀⾏⼀条有重复。请⽤5分钟时间找出重复出现最多的前 10 条。 解答 1分析 常规⽅法是先排序在遍历⼀次找出重复最多的前 10 条。但是排序的算法复杂度最低为 nlgn。 2可以设计⼀个 hash_table, hash_mapstring, int依次读取⼀千万条短信加载到 hash_table 表 中并且统计重复的次数与此同时维护⼀张最多 10 条的短信表。 这样遍历⼀次就能找出最多的前 10 条算法复 杂度为 O(n)。
