数据结构与算法面试系列-04
数据结构与算法面试系列-04
1. 红黑树（一）之 原理和算法详细介绍
R-B Tree简介
R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。
红黑树的特性:
1）每个节点或者是黑色，或者是红色。
2）根节点是黑色。
3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
4）如果一个节点是红色的，则它的子节点必须是黑色的。
5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
注意：
A) 特性3）中的叶子节点，是只为空（NIL或null）的节点。
B) 特性5），确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。
2. ⼆叉树与红⿊树有什么区别？
欢迎大家关注微信公众号： Java精选 ，专注分享前沿资讯，BATJ 大厂面试题解读，架构技术干货，微服务、高可用等架构设计，10年开发老兵帮你少走弯路，欢迎各领域程序员交流学习！
此类面试题只能在微信小程序： Java精选面试题 ，查阅全部内容，感谢支持！
3. 描述一下什么是 B 树？
B树也称B-树，它是一颗多路平衡查找树。我们描述一颗B树时需要指定它的阶数，阶数表示了一个结点最多有多少个孩子结点，一般用字母m表示阶数。当m取2时，就是我们常见的二叉搜索树。
一颗m阶的B树定义如下：
1）每个结点最多有m-1个关键字。
2）根结点最少可以只有1个关键字。
3）非根结点至少有Math.ceil(m/2)-1个关键字。
4）每个结点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。
5）所有叶子结点都位于同一层，或者说根结点到每个叶子结点的长度都相同。
上图是一颗阶数为4的B树。在实际应用中的B树的阶数m都非常大（通常大于100），所以即使存储大量的数据，B树的高度仍然比较小。每个结点中存储了关键字（key）和关键字对应的数据（data），以及孩子结点的指针。我们将一个key和其对应的data称为一个记录。但为了方便描述，除非特别说明，后续文中就用key来代替（key, value）键值对这个整体。在数据库中我们将B树（和B+树）作为索引结构，可以加快查询速速，此时B树中的key就表示键，而data表示了这个键对应的条目在硬盘上的逻辑地址。
4. 三个字符串如何验证其中字符串由另外两个字符串交错组成？
欢迎大家关注微信公众号： Java精选 ，专注分享前沿资讯，BATJ 大厂面试题解读，架构技术干货，微服务、高可用等架构设计，10年开发老兵帮你少走弯路，欢迎各领域程序员交流学习！
此类面试题只能在微信小程序： Java精选面试题 ，查阅全部内容，感谢支持！
5. 【腾讯】一千万条短信，有重复，以文本文件保存，请用五分钟时间，找出重复出现最多的前10条。
一、问题解析
对于本题来说，某些面试者想用数据库的办法实现，首先将文本导入数据库，再利用select 语句的方法得出前10个短信。但实际上用数据库是绝对满足不了5分钟解决这个条件的。这是因为1千万条短信即使1秒钟导入1万条(这已经算是很快的数据导入了)，5分钟才3 百万条，即便真的能在5分钟内录完1千万条，也必须先建索引，否则SQL语句在5 分钟内肯定得不出结果。但对1千万条记录建索引，在5 分钟内也不能完成。所以用数据库的办法不行。
这种类型的题之所以会出现，这是因为互联网公司每时每刻需要处理由用户产生的海量数据/日志，所以海量数据的题现在很热，互联网公司招聘时基本上都会考。重点考查求职者的数据结构设计与算法基本功。
二、正确方法
方法1：用哈希表的方法
可以将1千万条短信分成若干组，进行边扫描边建散列表的方法。第一次扫描，取首字节、尾字节、中间任意两字节作为Hash Code，插入到hash table中，并记录其地址、信息长度和重复次数。同hash code 且等长就疑似相同，比较一下。相同记录只加1次进hash table,但将重复次数加1。一次扫描以后，已经记录各自的重复次数，进行第二次hash table 的处理。用线性时间选择可在O（n）的级别上完成前10 条的寻找。分组后每组中的top10 必须保证各不相同，可用hash 来保证，也可直接按hash值的大小来分类。
方法2：采用从小到大排序的办法
根据经验，除非是群发的过节短信，否则字数越少的短信，出现重复的概率越高。建议从字数少的短信开始找起，比如一开始搜个字的短信，找出重复出现的top10并分别记录出现次数，然后搜两个字的，以此类推。对于对相同字数的比较长的短信的搜索，除了hash之类的算法外，可以选择只抽取头、中和尾等几个位置的字符进行粗判，因为此种判断方式是为了加快查找速度，但未必能得到真正期望的top10，因此，需要做标记，如此搜索一遍后，可以从各次top10结果中找到备选的top10，如果这次top10中有刚才做过标记的，则对其对应字数的所有短信进行精确搜索，以找到真正的topl0并再次比较。
方法3：采用内存映射办法
首先，1千万条短信按现在的短信长度将不会超过1GB 空间，使用内存映射文件比较合适，可以一次映射（如果有更大的数据量，可以采用分段映射），由于不需要频繁使用文件I/O和频繁分配小内存，这将大大提高了數据的加载速度。其次，对每条短信的第i（i 从0到70）个字母按ASCII码进行分组，也就是创建树。i是树的深度，也是短信第i个字母。
该问题主要是解决两方面的内容，一是内容加载，二是短信内容的比较。采用文件内存映射技术可以解决内容加载的性能问题（不仅仅不需要调用文件I/O函数，而且也不需要每读出一条短信都要分配一小块内存），而使用树技术可以有效地减少比较的次数。
6. 100w 个数中找出最大的 100 个数？
欢迎大家关注微信公众号： Java精选 ，专注分享前沿资讯，BATJ 大厂面试题解读，架构技术干货，微服务、高可用等架构设计，10年开发老兵帮你少走弯路，欢迎各领域程序员交流学习！
此类面试题只能在微信小程序： Java精选面试题 ，查阅全部内容，感谢支持！
