《大众点评网试题及海量数据扩展知识积累》由会员分享，可在线阅读，更多相关《大众点评网试题及海量数据扩展知识积累（13页珍藏版）》请在金锄头文库上搜索。
1、 肖龙肖龙答案整理如下：答案整理如下： /* 思路：创建两组桶，用于存放52个字母（假设字符串全部由字母组成），每个桶代表一个 字母，其中有一个值，出现一个字母则对应的值加一。最后两组桶比较每个桶的值便能得 知字符串是否相等。 */ #include #include /* 给代表对应字母的桶赋值 */ void loadStr(int bucket52, char str32) int tempStr = 0; for(int i = 0; i = x) j-; r*i = rj; while(*i =t.len) v=i-t.len; /*返回匹配模式串的首字符下标*/ else v=-1
2、; /*返回丌匹配标志*/ return v; 操作：操作：代码来自严蔚敏书本代码来自严蔚敏书本 【1】快速排序代码 【2】KMP模式匹配代码 问题2：综合搜索了一些面试题目，觉得用堆算法比较好。我记得高分笔记堆排序那张介绍了下，比较适合这种场景。 答案整理如下：答案整理如下： 根据特定的场景，采用巧妙的算法搭配合适的数据结构，才能达到最佳的效果。基于这条 设计原则，为了寻求最高的效率，我们综合考虑影响查询的若干前置因素。比如海量数据是否 建立了索引，海量数据分布在 N 台电脑中，查询记录的重复性，IO 的开销等。 对于题设已知条件，可以认为隐含了该系统使用了缓存或负载均衡机制，那么查询出来的
3、 数据如果是重复的，就会使用缓存中的记录，于是分 2 种情况讨论 : (1)重复的数据比较多，可能对于所有的 query，一次性就可以加入到内存了。比如虽然有 一千万个 Query， 但是由于重复度比较高， 因此事实上只有 100 万的 Query， 每个 Query 10Byte。 可以采用 hashMap 建立数据字典，统计每个 query 出现的次数，然后用最小堆排序取出前 10 个 最大的积分可以了。 (2)重复的数据比较少， 可以考虑将数据字典放在硬盘上面或者分布式计算， 采用 map-reduce 过程， 首先将数据按照范围划分到不同机器， 让数据划分后可以一次性读进内存， 实际就
4、是 map。 这样得出结果之后，各个机器拿出最大的前 10 个积分汇总。然后，选出汇总的数据中最大的前 10 个积分，实际就是 reduce 过程。当然，外排序也会消耗大量的 IO。当然，分布式计算也是 一个外排序的归并过程，将不同的子文件逐渐处理，然后进行一个合并。 参考资料 http:/ 面试题目-大数据量海量数据处理 （重要重要文字截图说明文字截图说明） http:/ ORACLE SQL性能优化(全) http:/ 原创 mysql数据库千万级别数据的查询优化和分页测试 http:/ 1-十道海量数据处理面试题 （重要文字截图说明）（重要文字截图说明） http:/ 教你如何迅速秒杀99%的海量数据处理面试题 http:/ 微软面试100题系列by_July (这些资源你可以好好看下，100个微软算法) (还有好多相关算法文档可以看看) http:/ 当今世界最受人们重视的十大经典算法 其它丌重要的文章参考： http:/ 如何构建千万用户级别如何构建千万用户级别 后台数据库架构设计的思路后台数据库架构设计的思路 http:/ 数据库太大有什么优化技术数据库太大有什么优化技术 http:/ 主题：主题：oracle大数据量（千万界别）怎么优化查询，分区。大数据量（千万界别）怎么优化查询，分区。 http:/ 海量数据库的查询优化和分页算法
