map是由什么实现的，你知道红黑树与AVL树的区别吗？

map底层采用红黑树。有人说自从红黑树出来之后，AVL树就被放进了博物馆，其实不然，在我看来，没有谁好谁坏，只有谁更适合。

AVL树中任何左右子树的高度差值不超过1，它是严格意义上的高度平衡树。查找、插入、删除在平均和最坏情况下的时间复杂度都是(log2 n)，增加和删除可能需要通过一次或多次旋转来重新平衡这个树。

红黑树的查询性能略微逊色于AVL树，因为他比AVL树会稍微不平衡最多一层，也就是说红黑树的查询性能只比相同内容的AVL树最多多一次比较，但是，红黑树在插入和删除上完爆AVL树，AVL树每次插入删除会进行大量的平衡度计算，而红黑树为了维持红黑性质所做的红黑变换和旋转的开销，相较于AVL树为了维持平衡的开销要小得多。

为什么像map、set都用红黑树实现，你有听过skip-list吗？

map、set的实现只是折衷了两者在search、insert以及delete下的效率。总体来说，RB-tree的统计性能是高于AVL的。理由如下：

1. 如果插入一个node引起了树的不平衡，AVL和RB-Tree都是最多只需要2次旋转操作，即两者都是O(1)；但是在删除node引起树的不平衡时，最坏情况下，AVL需要维护从被删node到root这条路径上所有node的平衡性，因此需要旋转的量级O(logN)，而RB-Tree最多只需3次旋转，只需要O(1)的复杂度。

2. 其次，AVL的结构相较RB-Tree来说更为平衡，在插入和删除node更容易引起Tree的unbalance，因此在大量数据需要插入或者删除时，AVL需要rebalance的频率会更高。因此，RB-Tree在需要大量插入和删除node的场景下，效率更高。自然，由于AVL高度平衡，因此AVL的search效率更高。

skip-list跳表的分析与实现

用过vector.reserve()吗，vector的数组是怎么增长的？

vector.reserver()增加了vector的capacity，但是它的size不会改变。它为vector预留空间，但在空间内并不真正创建元素对象，所以在没有添加新的对象之前，不能引用容器内的元素。加入新的元素时，要调用push_back()或insert()。

vector通过一个连续的数组存放元素，如果集合已满，在新增数据时，就要分配一块更大的内存，将原来的数据拷贝过来，释放之前的内存，最后插入新增的元素。不同的版本实现的扩容方式不同，SGI版本是以1.5倍扩容，PJ是以2倍扩容。

map-reduce了解过吗，能否简单说一下？

map和reduce简单来说，就是把一些数据通过map归类，通过reduce将同一类的数据进行处理。

map-reduce之所以有效基于两点：① 大而化小  ② 异而化同。这两点应对了大数据中的volume和variety的挑战。

假设我们手上有许多复杂数据，第一步就是分类，分类后的数据就会简化，这就是异而化同；第二步是分割，把数据切分成小块，这样就可以并发或批量处理，这就是大而化小。

回到map-reduce的概念上，map的工作就是切分数据，然后将它们分类，分类的方式就是输出key、value键值对，key对应类别。分类之后，reducer拿到的都是同类数据，这样处理就很容易了。

Linux中目录权限644代表什么意思，目录有可执行权限代表什么？

目录权限分别对应所有者、所属组、其他人的权限，在linux中：4-->read，2->write，1->execute，即读权限、写权限、可执行权限。644代表如下：

当我们进入一个目录时（普通用户），必须要有可执行权限。

了解awk、grep的用法吗，平时用gdb调试程序吗？

sed工具的使用方法     awk工具的使用方法     gdb多线程、多进程调试

如何实现TCP的拥塞控制、可靠传输？

TCP的可靠传输、拥塞控制、流量控制

数据库的ACID分别代表什么，原子性的定义？

Atomicity 原子性、Consistency 一致性、Isolation 隔离性、Durability 持久性。

原子性：用于标识事务是否完全地完成，一个事务的任何更新要在系统上完全完成，如果由于某种原因出错，事务不能完成它的全部任务，系统将返回到事务开始前的状态。