阿里云一面(C++研发):2017-04-22

2017-08-20 14:25 阅读 692 次 评论 0 条

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 持久性。

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

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:阿里云一面(C++研发):2017-04-22 | 术与道的分享
分类:笔经面经 标签:, ,
1024do.com导航_术与道导航平台

发表评论


表情