字节跳动 Java 面试题精选——算法与数据结构「跳槽面试必备」
方法 1：快慢指针法 2.设两个工作指针 p、q，p 总是向前走，但 q 每次都从头开始走，对于每个节点，看 p 走的步数是否和 q 一样。比如 p 从 A 走到 D，用了 4 步，而 q 则用了 14 步。因而步数不等，出现矛盾，存在环。
==============================================================================
二叉搜索树：(Binary Search Tree 又名：二叉查找树，二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树： 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉搜索树。
红黑树是一棵二叉搜索树，它在每个结点上增加一个存储位来表示结点的颜色，可以是 RED 或 BLACK。通过对任何一条从根到叶子的简单路径上各个结点的颜色进行约束，红黑树没有一条路径会比其他路径长出 2 倍，所以红黑树是近似平衡的，使得红黑树的查找、插入、删除等操作的时间复杂度最坏为 O(log n)，但需要注意到在红黑树上执行插入或删除后将不在满足红黑树性质，恢复红黑树的属性需要少量(O(log n))的颜色变更(实际是非常快速的)和不超过三次树旋转(对于插入操作是两次)。虽然插入和删除很复杂，但操 作时间仍可以保持为 O(log n) 次。具体如何保证？引出红黑树的 5 个性质。
红黑树的 5 个性质：满足以下五个性质的二叉搜索树
每个结点或是红色的或是黑色的
根结点是黑色的
每个叶结点是黑色的
如果一个结点是红色的,则它的两个子结点是黑色的
对于每个结点,从该结点到其后代叶结点的简单路径上,均包含相同数目的黑色结点
插入操作：
由于性质的约束，插入的结点都是红色的。插入时性质 1、3 始终保持。破坏性质 2 当且仅当当前插入结点为根节点。变一下颜色即可。如果是破坏性质 4 或 5，则需要旋转和变色来继续满足红黑树的性质。下面说一说插入的几种情况，约定当前插入结点为 N，其父结点为 P，叔叔为 U，祖父为 G
情形 1：树空，直接插入违反性质 1，将红色改黑。
情形 2：N 的父结点为黑，不必修改，直接插入
从情形 3 开始的情形假定 N 结点的父结点 P 为红色，所以存在 G，并且 G 为黑色。且 N 存在一个叔叔结点 U，尽管 U 可能为叶结点。
情形 3：P 为红，U 为红（G 结点一定存在且为黑）这里不论 P 是 G 的左孩子还是右孩子；不论 N 是 P 的左孩子还是右孩子。
首先把 P、U 改黑，G 改红，并以 G 作为一个新插入的红结点重新进行各种情况的检查，若一路检索至根节点还未结束，则将根结点变黑。
情形 4：P 为红，U 为黑或不存在（G 结点一定存在且为黑），且 P 为 G 的左孩子，N 为 P 的左孩子（或者 P 为 G 的右孩子，N 为 P 的右孩子，保证同向的）。 P、G 右旋并将 P、G 变相反色。因为 P 取代之前黑 G 的位置，所以 P 变黑可以理解，而 G 变红是为了不违反性质 5。
情形 5：P 为红，U 为黑或不存在，且 P 为 G 的左孩子，N 为 P 的右孩子（或 P 为 G 的右孩子，N 为 P 的左孩子，保证是反向的），对 N，P 进行一次左旋转换为情形 4
删除操作比插入复杂一些，但最多不超过三次旋转可以让红黑树恢复平衡。
其他
黑高从某个结点 x 出发(不含 x)到达一个叶结点的任意一条简单路径上的黑色结点个数称为该结点的黑高。红黑树的黑高为其根结点的黑高。
一个具有 n 个内部结点的红黑树的高度 h<=2lg(n+1)
结点的属性(五元组):color key left right p
动态集合操作最坏时间复杂度为 O(lgn)
===================================================================================
数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。
数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。
B 树：
为了描述 B-Tree，首先定义一条数据记录为一个二元组[key, data]，key 为记录的键值，对于不同数据记录，key 是互不相同的；data 为数据记录。那么 B-Tree 是满足下列条件的数据结构：
d 为大于 1 的一个正整数，称为 B-Tree 的度。用来表示每个结点包含的关键字个数的上界和下界。可以证明 h<=logd((N+1)/2)
h 为一个正整数，称为 B-Tree 的高度。
每个非叶子节点由 n-1 个 key 和 n 个指针组成，其中 d<=n<=2d。
每个叶子节点最少包含一个 key 和两个指针，最多包含 2d-1 个 key 和 2d 个指针，叶节点的指针均为 null 。
所有叶节点具有相同的深度，等于树高 h。
key 和指针互相间隔，节点两端是指针。
一个节点中的 key 从左到右非递减排列。
所有节点组成树结构。
每个指针要么为 null，要么指向另外一个节点。
如果某个指针在节点 node 最左边且不为 null，则其指向节点的所有 key 小于 v(key1)，其中 v(key1)为 node 的第一个 key 的值。
如果某个指针在节点 node 最右边且不为 null，则其指向节点的所有 key 大于 v(keym)，其中 v(keym)为 node 的最后一个 key 的值。
如果某个指针在节点 node 的左右相邻 key 分别是 keyi 和 keyi+1 且不为 null，则其指向节点的所有 key 小于 v(keyi+1)且大于 v(keyi)。
由于 B-Tree 的特性，在 B-Tree 中按 key 检索数据的算法非常直观：首先从根节点进行二分查找，如果找到则返回对应节点的 data，否则对相应区间的指针指向的节点递归进行查找，直到找到节点或找到 null 指针，前者查找成功，后者查找失败。
一个度为 d 的 B-Tree，设其索引 N 个 key，则其树高 h 的上限为 logd((N+1)/2)，检索一个 key，其查找节点个数的渐进复杂度为 O(logdN)。从这点可以看出，B-Tree 是一个非常有效率的索引数据结构。
B+树：
B-Tree 有许多变种，其中最常见的是 B+Tree，例如 MySQL 就普遍使用 B+Tree 实现其索引结构。
B+树是 B 树的变形，它把所有的 data 都放在叶子结点中，只将关键字和子女指针保存于内结点，内结点完全是索引的功能。
与 B-Tree 相比，B+Tree 有以下不同点：
每个节点的指针上限为 2d 而不是 2d+1。
内节点不存储 data，只存储 key；叶子节点存储 data 不存储指针。
一般在数据库系统或文件系统中使用的 B+Tree 结构都在经典 B+Tree 的基础上进行了优化，增加了顺序访问指针。
在 B+Tree 的每个叶子节点增加一个指向相邻叶子节点的指针
例如图 4 中如果要查询 key 为从 18 到 49 的所有数据记录，当找到 18 后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率。
为什么 B 树（B+树）？
一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘 I/O 消耗，相对于内存存取，I/O 存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘 I/O 操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘 I/O 的存取次数。
这涉及到磁盘存取原理、局部性原理和磁盘预读。
先从 B-Tree 分析，根据 B-Tree 的定义，可知检索一次最多需要访问 h 个节点。数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次 I/O 就可以完全载入。为了达到这个目的，在实际实现 B-Tree 还需要使用如下技巧：
每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个 node 只需一次 I/O。
B-Tree 中一次检索最多需要 h-1 次 I/O（根节点常驻内存），渐进复杂度为 O(h)=O(logdN)。一般实际应用中，出度 d 是非常大的数字，通常超过 100，因此 h 非常小（通常不超过 3）。
综上所述，用 B-Tree 作为索引结构效率是非常高的。
而红黑树这种结构，h 明显要深的多。由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性，所以红黑树的 I/O 渐进复杂度也为 O(h)，效率明显比 B-Tree 差很多。
至于 B+Tree 为什么更适合外存索引，原因和内节点出度 d 有关。
由于 B+Tree 内节点去掉了 data 域，因此可以拥有更大的出度，拥有更好的性能。
**
==================================================================================
第一：简单介绍 一致性哈希算法是分布式系统中常用的算法。比如，一个分布式的存储系统，要将对象存储到具体的节点上，如果采用普通的 hash 方法，将数据映射到具体的节点上，如 key%N，N 是机器节点数。
考虑到比如一个服务器 down 掉，服务器结点 N 变为 N-1，映射公式必须变为 key%(N-1)
访问量加重，需要添加服务器结点，N 变为 N+1，映射公式变为 hash(object)%(N+1)
当出现 1,2 的情况意味着我们的映射都将无效，对服务器来说将是一场灾难，尤其是对缓存服务器来说，因为缓存服务器映射的失效，洪水般的访问都将冲向后台服务器。
第二点：hash 算法的单调性
Hash 算法的一个衡量指标是单调性，单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。
评论