豌豆荚面试题

1. 字节对齐
现代计算机中内存空间都是按照byte划分的，从理论上讲似乎对任何类型的变量的访问可以从任何地址开始，但实际情况是在访问特定类型变量的时候经常在特定的内存地址访问，这就需要各种类型数据按照一定的规则在空间上排列，而不是顺序的一个接一个的排放，这就是对齐。
对齐的作用和原因：各个硬件平台对存储空间的处理上有很大的不同。一些平台对某些特定类型的数据只能从某些特定地址开始存取。比如有些架构的CPU在访问 一个没有进行对齐的变量的时候会发生错误,那么在这种架构下编程必须保证字节对齐.其他平台可能没有这种情况，但是最常见的是如果不按照适合其平台要求对 数据存放进行对齐，会在存取效率上带来损失。比如有些平台每次读都是从偶地址开始，如果一个int型（假设为32位系统）如果存放在偶地址开始的地方，那 么一个读周期就可以读出这32bit，而如果存放在奇地址开始的地方，就需要2个读周期，并对两次读出的结果的高低字节进行拼凑才能得到该32bit数 据。显然在读取效率上下降很多。
2.虚函数原理
虚函数是为了实现多态。多态的实现需要虚函数和动态绑定技术。实现方式：基类使用虚函数；
子类覆盖该函数；用一个基类的指针或引用只想子类对象，在运行的过程中，通过查找该对象的虚函数表实现多态。虚函数表在每个对象最开始的地方。
3.函数指针
int(f)(int) 函数指针
int(f[10])(int) 函数指针数组
4.编译器和连接器和加载器的问题
编译器和汇编器创建了目标文件（包含由源程序生成的二进制代码和数据）。链接器
将多个目标文件合并成一个，加载器读取这些目标文件并将它们加载到内存中（在一个集成
编程环境中
一个目标文件包含五类信息。
● 头信息：关于文件的整体信息，诸如代码大小，翻译成该目标文件的源文件名称，
和创建日期等。
● 目标代码：由编译器或汇编器产生的二进制指令和数据。
● 重定位信息：目标代码中的一个位置列表，链接器在修改目标代码的地址时会对它
进行调整。
● 符号：该模块中定义的全局符号，以及从其它模块导入的或者由链接器定义的符号。
● 调试信息：目标代码中与链接无关但会被调试器使用到的其它信息
5. select, poll 和epoll的原理和区别
在Linux Socket服务器短编程时，为了处理大量客户的连接请求，需要使用非阻塞I/O和复用，select、poll和epoll是Linux API提供的I/O复用方式
（1）select 函数监视的文件描述符分3类，分别是writefds、readfds、和exceptfds。调用后select函数会阻塞，直到有描述副就绪（有数据 可读、可写、或者有except），或者超时（timeout指定等待时间，如果立即返回设为null即可），函数返回。当select函数返回后，可以 通过遍历fdset，来找到就绪的描述符。
select目前几乎在所有的平台上支持，其良好跨平台支持也是它的一个优点。select的一 个缺点在于单个进程能够监视的文件描述符的数量存在最大限制，在Linux上一般为1024，可以通过修改宏定义甚至重新编译内核的方式提升这一限制，但 是这样也会造成效率的降低。
（3）不同与select使用三个位图来表示三个fdset的方式，poll使用一个 pollfd的指针实现。
pollfd结构包含了要监视的event和发生的event，不再使用select“参数-值”传递的方式。同时，pollfd并没有最大数量限制（但是数量过大后性能也是会下降）。 和select函数一样，poll返回后，需要轮询pollfd来获取就绪的描述符。
从上面看，select和poll都需要在返回后，通过遍历文件描述符来获取已经就绪的socket。事实上，同时连接的大量客户端在一时刻可能只有很少的处于就绪状态，因此随着监视的描述符数量的增长，其效率也会线性下降。
（3）主要是epoll_create,epoll_ctl和epoll_wait三个函数。epoll_create函数创建epoll文件描述符，参数size并不是限制了epoll所能监听的描述符最大个数，只是对内核初始分配内部数据结构的一个建议。返回是epoll描述符。-1表示创建失败。epoll_ctl 控制对指定描述符fd执行op操作，event是与fd关联的监听事件。op操作有三种：添加EPOLL_CTL_ADD，删除EPOLL_CTL_DEL，修改EPOLL_CTL_MOD。分别添加、删除和修改对fd的监听事件。epoll_wait 等待epfd上的io事件，最多返回maxevents个事件。
在 select/poll中，进程只有在调用一定的方法后，内核才对所有监视的文件描述符进行扫描，而epoll事先通过epoll_ctl()来注册一 个文件描述符，一旦基于某个文件描述符就绪时，内核会采用类似callback的回调机制，迅速激活这个文件描述符，当进程调用epoll_wait() 时便得到通知。
epoll的优点主要是一下几个方面：
a. 监视的描述符数量不受限制，它所支持的FD上限是最大可以打开文件的数目，这个数字一般远大于2048,举个例子,在1GB内存的机器上大约是10万左 右，具体数目可以cat /proc/sys/fs/file-max察看,一般来说这个数目和系统内存关系很大。select的最大缺点就是进程打开的fd是有数量限制的。这对 于连接数量比较大的服务器来说根本不能满足。虽然也可以选择多进程的解决方案( Apache就是这样实现的)，不过虽然linux上面创建进程的代价比较小，但仍旧是不可忽视的，加上进程间数据同步远比不上线程间同步的高效，所以也 不是一种完美的方案。
b. IO的效率不会随着监视fd的数量的增长而下降。epoll不同于select和poll轮询的方式，而是通过每个fd定义的回调函数来实现的。只有就绪的fd才会执行回调函数。
c. 支持电平触发和边沿触发（只告诉进程哪些文件描述符刚刚变为就绪状态，它只说一遍，如果我们没有采取行动，那么它将不会再次告知，这种方式称为边缘触发）两种方式，理论上边缘触发的性能要更高一些，但是代码实现相当复杂。
d. mmap加速内核与用户空间的信息传递。epoll是通过内核于用户空间mmap同一块内存，避免了无畏的内存拷贝。
6.stl的sort是如何实现的
STL的sort()算法，数据量大时采用Quick Sort，分段递归排序，一旦分段后的数据量小于某个门槛，为避免Quick Sort的递归调用带来过大的额外负荷，就改用Insertion Sort。如果递归层次过深，还会改用Heap Sort。
为什么是Insertion Sort，而不是Bubble Sort。
选择排序(Selection sort)，插入排序(Insertion Sort)，冒泡排序(Bubble Sort)。这三个排序是初学者必须知道的三个基本排序方式，且他们速度都不快 – O(N^2)。选择排序就不说了，最好情况复杂度也得O(N^2)，且还是个不稳定的排序算法，直接淘汰。
可冒泡排序和插入排序相比较呢？
首先，他们都是稳定的排序算法，且最好情况下都是O(N^2)。那么我就来对他们的比较次数和移动元素次数做一次对比（最好情况下），如下：
插入排序：比较次数N-1，移动元素次数2N-1。
冒泡排序：比较次数N-1，无需移动元素。(注：我所说的冒泡排序在最基本的冒泡排序基础上还利用了一下旗帜的方式，即寻访完序列未发生数据交换时则表示排序已完成，无需再进行之后的比较与交换动作）
那么，这样看来冒泡岂不是是更快，我可以把上述的final_insertion_sort()函数改成一个final_bubble_sort()，把每个子序列分别进行冒泡排序，岂不是更好？
事实上，具体实现时，我才发现这个想法错了，因为写这么一个final_bubble_sort()，我没有办法确定每个子序列的大小，可我还是不甘心呐，就把bubble_sort()插在introsort_loop()最后，这样确实是每个子序列都用bubble_sort()又排序了一次，可是测试结果太惨了，由此可以看书Bubble Sort在“几近排序但尚未完成”的情况下是没多少改进作用的。
为什么不直接用Heap Sort
堆排序将所有的数据建成一个堆，最大的数据在堆顶，它不需要递归或者多维的暂存数组。算法最优最差都是O(NlogN)，不像快排，如果你人品够差还能恶化到O(N^2)。当数据量非常大时（百万数据），因为快排是使用递归设计算法的，还可能发出堆栈溢出错误呢。
那么为什么不直接用Heap Sort？或者说给一个最低元素阈值（__stl_threshold)时也给一个最大元素阈值（100W），即当元素数目超过这个值时，直接用Heap Sort，避免堆栈溢出呢？
对于第一个问题，我测试了一下，发现直接用Heap Sort，有时还没有Quick Sort快呢，查阅《算法导论》发现，原来虽然Quick和Heap的时间复杂性是一样的，但堆排序的常熟因子还是大些的，并且堆排序过程中重组堆其实也不是个省时的事。
7.c++11中引入的各种新特性
8. linux的线程同步原语
9.linux查看一个进程打开了哪些句柄
lsof
10. linux下得内存泄露
vargrind检查内存泄露