大众点评网试题及海量数据扩展知识积累.pdf

肖龙肖龙答案整理如下 答案整理如下 思路 创建两组桶 用于存放52个字母 假设字符串全部由字母组成 每个桶代表一个 字母 其中有一个值 出现一个字母则对应的值加一 最后两组桶比较每个桶的值便能得 知字符串是否相等 include include 给代表对应字母的桶赋值 void loadStr int bucket 52 char str 32 int tempStr 0 for int i 0 i strlen str i tempStr str i A bucket tempStr 1 对比两组桶中同下标的值 void cmp int bucket 1 52 int bucket 2 52 for int i 0 i 52 i if bucket 1 i bucket 2 i printf 字符串丌相等 n return printf 字符串相等 n int main int bucket 1 52 0 int bucket 2 52 0 char str 1 32 char str 2 32 printf 输入第一组字字母 n gets str 1 printf 输入第二组字字母 n gets str 2 if strlen str 1 strlen str 2 printf 字符串丌相等 getchar return 1 loadStr bucket 1 str 1 loadStr bucket 2 str 2 cmp bucket 1 bucket 2 getchar 问题问题1 1 简单搜索的资料找找感觉简单搜索的资料找找感觉 qksort r s k 1 qksort r k 1 t void qkpass listType r int s t i i s j t rp r s x r s key while i j while i x j r i r j while i j r i key x i r j r i r i rp KMP模式匹配算法 void GetNext SqString t int next int j k j 0 k 1 next 0 1 while j t len 1 if k 1 t data j t data k k为 1戒比较的字符相等时 j k next j k else k next k int KMPIndex SqString s SqString t int next MaxSize i 0 j 0 v GetNext t next while i s len 返回匹配模式串的首字符下标 else v 1 返回丌匹配标志 return v 操作 操作 代码来自严蔚敏书本代码来自严蔚敏书本 1 快速排序代码 2 KMP模式匹配代码 问题2 综合搜索了一些面试题目 觉得用堆算法比较好 我记得高分笔记堆排序那张介绍了下 比 较适合这种场景 答案整理如下 答案整理如下 根据特定的场景 采用巧妙的算法搭配合适的数据结构 才能达到最佳的效果 基于这条 设计原则 为了寻求最高的效率 我们综合考虑影响查询的若干前置因素 比如海量数据是否 建立了索引 海量数据分布在 N 台电脑中 查询记录的重复性 IO 的开销等 对于题设已知条件 可以认为隐含了该系统使用了缓存或负载均衡机制 那么查询出来的 数据如果是重复的 就会使用缓存中的记录 于是分 2 种情况讨论 1 重复的数据比较多 可能对于所有的 query 一次性就可以加入到内存了 比如虽然有 一千万个 Query 但是由于重复度比较高 因此事实上只有 100 万的 Query 每个 Query 10Byte 可以采用 hashMap 建立数据字典 统计每个 query 出现的次数 然后用最小堆排序取出前 10 个 最大的积分可以了 2 重复的数据比较少 可以考虑将数据字典放在硬盘上面或者分布式计算 采用 map reduce 过程 首先将数据按照范围划分到不同机器 让数据划分后可以一次性读进内存 实际就是 map 这样得出结果之后 各个机器拿出最大的前 10 个积分汇总 然后 选出汇总的数据中最大的前 10 个积分 实际就是 reduce 过程 当然 外排序也会消耗大量的 IO 当然 分布式计算也是 一个外排序的归并过程 将不同的子文件逐渐处理 然后进行一个合并 参考资料 面试题目 大数据量海量数据处理 重要重要文字截图说明文字截图说明 ORACLE SQL性能优化 全 原创 mysql数据库千万级别数据的查询优化和分页测试 1 十道海量数据处理面试题 重要文字截图说明 重要文字截图说明 教你如何迅速秒杀99 的海量数据处理面试题 微软面试100题系列by July 这些资源你可以好好看下 100个微软算法 还有好多相关算法文档可以看看 当今世界最受人们重视的十大经典算法 其它丌重要的文章参考 如何构建千万用户级别如何构建千万用户级别 后台数据库架构设计