阿里内推2016面试(终 总结).doc

孙彦晨阿里一面
项目,问了一个项目,是学术项目



list用过吗它是怎么实现的
list是C++标准模版库(STL,Standard Template Library)中的部分内容。实际上,list容器就是一个双向链表,可以高效地进行插入删除元素。使用list容器之前必须加上<vector>头文件:#include<list>;
hash_map用过吗它是怎么实现的
容器都有哪些
数组与链表的区别?
?用过单例模式吗?
叙述一下单例模式的过程
在单例模式下,用多线程会出现问题吗?
,C++中最讨厌delete,怎么解决?
引出智能指针加锁

用到乐观锁与悲观锁的知识点
悲观锁(Pessimistic Lock), 顾名思义,就是很悲观,每次去拿数据的时候都认为别人会修改,所以每次在拿数据的时候都会上锁,这样别人想拿这个数据就会block直到它拿到锁。传统的关系型数据库里边就用到了很多这种锁机制,比如行锁,表锁等,读锁,写锁等,都是在做操作之前先上锁。
乐观锁(Optimistic Lock), 顾名思义,就是很乐观,每次去拿数据的时候都认为别人不会修改,所以不会上锁,但是在更新的时候会判断一下在此期间别人有没有去更新这个数据,可以使用版本号等机制。乐观锁适用于多读的应用类型,这样可以提高吞吐量,像数据库如果提供类似于write_condition机制的其实都是提供的乐观锁。
两种锁各有优缺点,不可认为一种好于另一种,像乐观锁适用于写比较少的情况下,即冲突真的很少发生的时候,这样可以省去了锁的开销,加大了系统的整个吞吐量。但如果经常产生冲突,上层应用会不断的进行retry,这样反倒是降低了性能,所以这种情况下用悲观锁就比较合适。


问题:假设一个文件中有9亿条不重复的9位整数,现在要求对这个文件进行排序。
一般解题思路:
1、将数据导入到内存中
2、将数据进行排序(比如插入排序、快速排序)
3、将排序好的数据存入文件
难题:
一个整数为4个字节
即使使用数组也需要900,000,000 * 4byte =
对于32位系统,访问2G以上的内存非常困难,而且一般设备也没有这么多的物理内存
将数据完全导入到内存中的做法不现实
其他解决办法:
1、导入数据库运算
2、分段排序运算
3、使用bit位运算
解决方案一:数据库排序
将文本文件导入到数据库,让数据库进行索引排序操作后提取数据到文件
优点:操作简单
缺点:运算速度慢,而且需要数据库设备。
解决方案二:分段排序
操作方式:
规定一个内存大小,比如200M,200M可以记录(200*1024*1024/4) = 52428800条记录,我们可以每次提取5000万条记录到文件进行排序,要装满9位整数需要20次,所以一共要进行20次排序,需要对文件进行20次读操作
缺点:
编码复杂,速度也慢(至少20次搜索)
关键步骤:
先将整个9位整数进行分段,亿条数据进行分成20段,每段5000万条
在文件中依次搜索0~5000万,50000001~1亿……
将排序的结果存入文件
解决方案三:bit位操作
思考下面的问题:
一个最大的9位整数为999999999
这9亿条数据是不重复的
可不可以把这些数据组成一个队列或数组,让它有0~999999999(10亿个)元素
数组下标表示数值,节点中用0表示这个数没有,1表示有这个数
判断0或1只用一个bit存储就够了
声明一个可以包含9位整数的bit数组(10亿),一共需要10亿/8=120M内存
把内存中的数据全部初始化为0, 读取文件中的数据,并将数据放入内存。比如读到一个数据为341245909这个数据,那就先在内存中找到341245909这个bit,并将bit值置为1遍历整个bit数组,将bit为1的数组下标存入文件
?
内推孙婉君
阿里一面

;
(TCP较多,UDP少);
;
;
,UDP可能丢包,TCP保证数据顺序,UDP不保证。
、快速排序


封装继承多态
、多态、多继承优缺点
多重继承的优点就是一个类可以实现多个