第一次笔试:
1. Buddy System 怎么进行内存的分配.
解答:
在Linux内核中,空闲内存管理的基本单位是页面(x86/x86-64 CPU定义的页面),即以页面为单位来管理物理内存(kmalloc等slab/slub机制,是比页面更小的细分)。
Linux内核管理的每个内存空闲块都是2的幂次方个页面,幂次方的大小为order。把1个空闲页面的放在一起、2个空闲页面(物理地址连续)放在一起、4个空闲页面(物理地址连续)放在一起 ... ... 2^(MAX_ORDER-1)个页面(物理地址连续)放在一起。空闲页面组织,如下图所示。 
伙伴系统(Buddy System)在理论上是非常简单的内存分配算法。它的用途主要是尽可能减少外部碎片(external fragmentation),同时允许快速分配与回收物理页面。为了减少外部碎片,连续的空闲页面,根据空闲块(由连续的空闲页面组成)大小,组织成不同的链表(或者orders)。
这样所有的2个页面大小的空闲块在一个链表中,4个页面大小的空闲块在另外一个链表中,以此类推。注意,不同大小的块在空间上,不会有重叠。下图为空闲页面的分配示意图
2. 函数f参数0和1的概率分别为p和1-p,利用f构造一个函数,可以等概率的返回0和1
解答:
两种方法:
方法1: 运行函数f两次, 输出结果及概率为: P(00)=p^2, P(11)=(1-p)^2, P(01)=p*(1-p), P(10)=(1-p)*p
可以发现产生01和10的概率是相等的, 所以可以定义新函数为g, 当输出为01的时候g输出0, 当输出为10的时候, g输出1.
方法2:
设g(x)=f(x)>0?0:1; 刚g(x)以概率 1-p 生成0.
所以f(x),g(x)同时生成0的概率为p(1-p)等于同时生成1的概率.
得等概率随机数
function g(x){
int v=f(x)+g(x);
if(v==0){
return 0; //1.f(x)g(x)同时为0
else if(v==2){
return 1; //2.f(x)g(x)同时为1
}else{
g(x); //3.f(x)g(x)一个为0一个为1,重新生成随机数
}
}
上面第3步的概率为p^2+(1-p)^2
3. 上台阶问题:每次只能上1或2阶, 给出N时可以采用的方式总数.
f(1)=1, f(2)=2,
f(N)=f(N-1)+f(N-2)
这是斐波那契数列.
4. 一个整数数组是无界的, 里面包含正数和负数,也包括重复的元素,给定一个整数K,如何得到K的索引值.
5. 整数数组是无序的,并且都是正数, 如何找到不连续整数的最大和.
6. 最长递增子序列问题
7. 一些术语:
这是3种垃圾回收的方法.
reference counting : 引用计数
stop_and_copy: 该算法的提出是为了克服句柄的开销和解决堆碎片的垃圾回收。它开始时把堆分成 一个对象 面和多个空闲面，程序从对象面为对象分配空间，当对象满了，基于coping算法的垃圾 收集就从根集中扫描活动对象，并将每个活动对象复制到空闲面（使得活动对象所占的内存之间没有空闲洞），这样空闲面变成了对象面，原来的对象面变成了空闲面，程序会在新的对象面中分配内存。
一种典型的基于coping算法的垃圾回收是stop-and-copy算法，它将堆分成对象面和空闲区域面，在对象面与空闲区域面的切换过程中，程序暂停执行。
mark_and_sweep: tracing算法是为了解决引用计数法的问题而提出，它使用了根集的概念。基于tracing算法的垃圾收集器从根集开始扫描，识别出哪些对象可达，哪些对象不可达，并用某种方式标记可达对象，例如对每个可达对象设置一个或多个位。在扫描识别过程中，基于tracing算法的垃圾收集也称为标记和清除（mark-and-sweep）垃圾收集器。
第二次笔试:
1. 使用UDP协议的应用.
基于UDP的应用层协议有DHCP BOOTP TFTP RADIUS SNMP NTP HTTP-s SLP SSL
2. STATE设计模式.
解析：
State模式主要解决的是在开发中时常遇到的根据不同的状态需要进行不同的处理操作的问题，而这样的问题，大部分人是采用switch-case语句进 行处理的，这样会造成一个问题：分支过多，而且如果加入一个新的状态就需要对原来的代码进行编译。State模式采用了对这些不同的状态进行封装的方式处 理这类问题，当状态改变的时候进行处理然后再切换到另一种状态，也就是说把状态的切换责任交给了具体的状态类去负责。同时，State模式和 Strategy模式在图示上有很多相似的地方，需要说明的是两者的思想都是一致的，只不过封装的东西不同：State模式封装的是不同的状态，而 Stategy模式封装的是不同的算法。
3. IPC方法
进程间通讯(IPC)方法主要有以下几种： 管道/FIFO/共享内存/消息队列/信号量
(1).管道中还有命名管道和非命名管道(即匿名管道)之分，非命名管道(即匿名管道)只能用于父子进程通讯，命名管道可用于非父子进程，命名管道就是FIFO，管道是先进先出的通讯方式
(2).消息队列是用于两个进程之间的通讯，首先在一个进程中创建一个消息队列，然后再往消息队列中写数据，而另一个进程则从那个消息队列中取数据。需要注意的是，消息队列是用创建文件的方式建立的，如果一个进程向某个消息队列中写入了数据之后，另一个进程并没有取出数据，即使向消息队列中写数据的进程已经结束，保存在消息队列中的数据并没有消失，也就是说下次再从这个消息队列读数据的时候，就是上次的数据！！！！
(3).信号量，它与WINDOWS下的信号量是一样的，所以就不用多说了
(4).共享内存，类似于WINDOWS下的DLL中的共享变量，但LINUX下的共享内存区不需要像DLL这样的东西，只要首先创建一个共享内存区，其它进程按照一定的步骤就能访问到这个共享内存区中的数据，当然可读可写
以上几种方式的比较：
(1).管道：速度慢，容量有限，只有父子进程能通讯
(2).FIFO：任何进程间都能通讯，但速度慢
(3).消息队列：容量受到系统限制，且要注意第一次读的时候，要考虑上一次没有读完数据的问题
(4).信号量：不能传递复杂消息，只能用来同步
(5).共享内存区：能够很容易控制容量，速度快，但要保持同步，比如一个进程在写的时候，另一个进程要注意读写的问题，相当于线程中的线程安全，当然，共享内存区同样可以用作线程间通讯，不过没这个必要，线程间本来就已经共享了同一进程内的一块内存
4. 反转单词顺序
5. 二叉树转换为双向链表.
6. 最长回文串.
7. 旋转数组的查找.
8. 直方图的最大面积:分治法, 单调栈.