百度2015校园招聘软件开发笔试题及答案

简单题（本题共30分）

请简述Tcp-ip的3次握手以及4次挥手过程？并解释为何关闭连接需要4次挥手(10分)

详细答案参见TCP/IP协议三次握手与四次握手流程解析

1. TCP三次握手、四次挥手过程如下:

   

   通常情况下，一个正常的TCP连接，都会有三个阶段:1、TCP三次握手; 2、数据传送; 3、TCP四次挥手

   • SYN: (同步序列编号,Synchronize Sequence Numbers)该标志仅在三次握手建立TCP连接时有效。表示一个新的TCP连接请求。
   • ACK: (确认编号,Acknowledgement Number)是对TCP请求的确认标志,同时提示对端系统已经成功接收所有数据。
   • FIN: (结束标志,FINish)用来结束一个TCP回话.但对应端口仍处于开放状态,准备接收后续数据。

2. 四次挥手的原因：

   这是因为服务端的LISTEN状态下的SOCKET当收到SYN报文的建连请求后，它可以把ACK和SYN（ACK起应答作用，而SYN起同步作用）放在一个报文里来发送。但关闭连接时，当收到对方的FIN报文通知时，它仅仅表示对方没有数据发送给你了；但未必你所有的数据都全部发送给对方了，所以你可以未必会马上会关闭SOCKET,也即你可能还需要发送一些数据给对方之后，再发送FIN报文给对方来表示你同意现在可以关闭连接了，所以它这里的ACK报文和FIN报文多数情况下都是分开发送的。

3. 不能两次握手连接的原因：

   3次握手完成两个重要的功能，既要双方做好发送数据的准备工作(双方都知道彼此已准备好)，也要允许双方就初始序列号进行协商，这个序列号在握手过程中被发送和确认。

   现在把三次握手改成仅需要两次握手，死锁是可能发生的。作为例子，考虑计算机S和C之间的通信，假定C给S发送一个连接请求分组，S收到了这个分组，并发送了确认应答分组。按照两次握手的协定，S认为连接已经成功地建立了，可以开始发送数据分组。可是，C在S的应答分组在传输中被丢失的情况下，将不知道S是否已准备好，不知道S建立什么样的序列号，C甚至怀疑S是否收到自己的连接请求分组。在这种情况下，C认为连接还未建立成功，将忽略S发来的任何数据分组，只等待连接确认应答分组。而S在发出的分组超时后，重复发送同样的分组。这样就形成了死锁。

4. SYN攻击

   在三次握手过程中，服务器发送SYN-ACK之后，收到客户端的ACK之前的TCP连接称为半连接(half-open connect).此时服务器处于Syn_RECV状态.当收到ACK后，服务器转入ESTABLISHED状态.

   Syn攻击就是 攻击客户端 在短时间内伪造大量不存在的IP地址，向服务器不断地发送syn包，服务器回复确认包，并等待客户的确认，由于源地址是不存在的，服务器需要不断的重发直 至超时，这些伪造的SYN包将长时间占用未连接队列，正常的SYN请求被丢弃，目标系统运行缓慢，严重者引起网络堵塞甚至系统瘫痪。

   Syn攻击是一个典型的DDOS攻击。检测SYN攻击非常的方便，当你在服务器上看到大量的半连接状态时，特别是源IP地址是随机的，基本上可以断定这是一次SYN攻击.在Linux下可以如下命令检测是否被Syn攻击

   netstat -n -p TCP | grep SYN_RECV

   一般较新的TCP/IP协议栈都对这一过程进行修正来防范Syn攻击，修改tcp协议实现。主要方法有SynAttackProtect保护机制、SYN cookies技术、增加最大半连接和缩短超时时间等.但是不能完全防范syn攻击。

5. 2MSL TIME_WAIT状态

   
   TIME_WAIT状态的存在有两个理由：（1）让4次握手关闭流程更加可靠；4次握手的最后一个ACK是是由主动关闭方发送出去的，若这个ACK丢失，被动关闭方会再次发一个FIN过来。若主动关闭方能够保持一个2MSL的TIME_WAIT状态，则有更大的机会让丢失的ACK被再次发送出去。（2）防止lost duplicate对后续新建正常链接的传输造成破坏。lost duplicate在实际的网络中非常常见，经常是由于路由器产生故障，路径无法收敛，导致一个packet在路由器A，B，C之间做类似死循环的跳转。IP头部有个TTL，限制了一个包在网络中的最大跳数，因此这个包有两种命运，要么最后TTL变为0，在网络中消失；要么TTL在变为0之前路由器路径收敛，它凭借剩余的TTL跳数终于到达目的地。但非常可惜的是TCP通过超时重传机制在早些时候发送了一个跟它一模一样的包，并先于它达到了目的地，因此它的命运也就注定被TCP协议栈抛弃。另外一个概念叫做incarnation connection，指跟上次的socket pair一摸一样的新连接，叫做incarnation of previous connection。lost duplicate加上incarnation connection，则会对我们的传输造成致命的错误。大家都知道TCP是流式的，所有包到达的顺序是不一致的，依靠序列号由TCP协议栈做顺序的拼接；假设一个incarnation connection这时收到的seq=1000, 来了一个lost duplicate为seq=1000, len=1000, 则tcp认为这个lost duplicate合法，并存放入了receive buffer，导致传输出现错误。通过一个2MSL TIME_WAIT状态，确保所有的lost duplicate都会消失掉，避免对新连接造成错误。

   该状态为什么设计在主动关闭这一方：
   （1）发最后ack的是主动关闭一方
   （2）只要有一方保持TIME_WAIT状态，就能起到避免incarnation connection在2MSL内的重新建立，不需要两方都有

   如何正确对待2MSL TIME_WAIT

   RFC要求socket pair在处于TIME_WAIT时，不能再起一个incarnation connection。但绝大部分TCP实现，强加了更为严格的限制。在2MSL等待期间，socket中使用的本地端口在默认情况下不能再被使用。若A 10.234.5.5:1234和B 10.55.55.60:6666建立了连接，A主动关闭，那么在A端只要port为1234，无论对方的port和ip是什么，都不允许再起服务。显而易见这是比RFC更为严格的限制，RFC仅仅是要求socket pair不一致，而实现当中只要这个port处于TIME_WAIT，就不允许起连接。这个限制对主动打开方来说是无所谓的，因为一般用的是临时端口；但对于被动打开方，一般是server，就悲剧了，因为server一般是熟知端口。比如http，一般端口是80，不可能允许这个服务在2MSL内不能起来。解决方案是给服务器的socket设置SO_REUSEADDR选项，这样的话就算熟知端口处于TIME_WAIT状态，在这个端口上依旧可以将服务启动。当然，虽然有了SO_REUSEADDR选项，但sockt pair这个限制依旧存在。比如上面的例子，A通过SO_REUSEADDR选项依旧在1234端口上起了监听，但这时我们若是从B通过6666端口去连它，TCP协议会告诉我们连接失败，原因为Address already in use.

操作系统的内存管理淘汰算法有哪些,请列出并简要说明？(10分)

进程运行时，若其访问的页面不在内存而需将其调入，但内存已无空闲空间时，就需要从内存中调出一页程序或数据，送入磁盘的兑换区。选择调出页面的算法就称为页面置换算法。好的页面置换算法应有较低的页面更换频率。

• 最佳（OPT）置换算法是理论算法，它将不再使用的页面换出，而实际中不能预知哪个页面不再使用，但是这个算法是最优算法，可以作为评测其他算法的性能。
• 先进先出(FIFO)置换算法优先淘汰最先进入内存中的页面。该算法实现简单，但算法跟内存的实际运行规律不符，不管该页面是否经常使用，这样就有可能导致缺页率增加，导致页面置换次数增加。
• 最近最少(LRU：least recently used)使用置换算法当需要淘汰某页，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。在这里采用一个页面集大小的栈存储最近访问的页面。页面按时间顺序压如栈中。如果被访问的页在栈中，则从栈中移出页面，压入栈顶。这样栈底记录离当前时间最近的一段时间内最久没有使用过的页。
• 最不经常使用(LFU:least frequently used)置换算法 LFU在需要淘汰某一页时，首先淘汰到当前时间为止、被访问次数最少的那一页。这只要在页面集中给每一页增设一个访问计数器即可实现。每当该页被访问时，访问计数器加1，而发生一次缺页中断时，则淘汰计数值最小的那一页，并将所有的计数器清零。
• 最近最不经常使用(NRU:not recently used)算法 NRU在需要淘汰某一页时，从那些最近一个时期内未被访问的页中任选一页淘汰。只要在页表中增设一个访问位即可实现。当某页被访问时，访问位置1。否则，访问位置0。系统周期性地对所有引用位清零。当需淘汰一页时，从那些访问位为零的页中选一页进行淘汰。如果引用位全0或全1，NRU算法退化为FIFO算法。

详解可参照:操作系统内存管理淘汰算法的实现 和 内存管理的页面置换算法有哪些

进行数据库设计时通常需要遵守哪些范式,请列举并说明?(10分)

设计关系数据库时，遵从不同的规范要求，设计出合理的关系型数据库，这些不同的规范要求被称为不同的范式，各种范式呈递次规范，越高的范式数据库冗余越小。

目前关系数据库有六种范式：第一范式（1NF）、第二范式（2NF）、第三范式（3NF）、巴斯-科德范式（BCNF）、第四范式(4NF）和第五范式（5NF，还又称完美范式）。

• 第一范式 所有的域都应该是原子性的，即数据库表的每一列都是不可分割的原子数据项，而不能是集合，数组，记录等非原子数据项。即实体中的某个属性有多个值时，必须拆分为不同的属性。在符合第一范式（1NF）表中的每个域值只能是实体的一个属性或一个属性的一部分。简而言之，第一范式就是无重复的域。
• 第二范式要求实体的属性完全依赖于主关键字。所谓完全依赖是指不能存在仅依赖主关键字一部分的属性，如果存在，那么这个属性和主关键字的这一部分应该分离出来形成一个新的实体，新实体与原实体之间是一对多的关系。为实现区分通常需要为表加上一个列，以存储各个实例的唯一标识。简而言之，第二范式就是在第一范式的基础上属性完全依赖于主键。
• 第三范式 在1NF基础上，任何非主属性不依赖于其它非主属性[在2NF基础上消除传递依赖]

详细讲解参见数据库范式

算法与程序设计题(本题共45分)

寻找一个简单链表的中项,如果存在两个则返回前一个.请给出算法描述并给出代码(15分)

分析:可以借助于两个指针，快慢指针，快指针一次走两步，慢指针一次走一步，当快指针走到尾端时，慢指针即指向中项位置。空间复杂度为0（1）时间复杂度为O(n).

struct ListNode
{
    struct ListNode *next;
    int key;
};

ListNode* getMID(ListNode* head)
{
    if (NULL == head)return NULL;
    ListNode *first = head;
    ListNode *second = head;
    while(NULL != second->next)
    {
        if(NULL == second->next->next)break;
        first = first->next;
        second = second->next->next;
    }
    return first;
}

拓展：借助快慢指针，可以判断单向链表中是否有环，依据就是如果有环，快指针与慢指针总会相遇

在由N个正数的集合S中:找出最大元素C,满足C=A+B,其中A,B都是集合S中元素.请给出算法描述、代码与时间复杂度分析(15分)

算法步骤:

1. 首先对集合进行排序,从小到大排序,可以选择排序算法较快的快速|归并|堆排序, n∗log(n) 复杂度
2. 找最大满足条件的元素C。两层循环，外层循环从大到小依次寻找C。内层循环，分别从头尾向中间寻找元素A B,是的 C = A + B，找到后即跳出两层循环。时间复杂度 O(n2) 。

程序复杂度为 O(n2)

int FindSum(int A[],int n){
    sort(A,A+n);

    int left,right,sum;

    for(int i = n - 1;i >= 2;--i){
        left = 0,right = i - 1;

        while(left < right){
            sum = A[left] + A[right];
            if(sum == A[i]){
                return A[i];
            }
            else if(sum > A[i]){
                --right;
            }
            else{
                ++left;
            }
        }
    }
    return -1;
}

使用堆栈(Stack)来模拟队列(FIFO)功能,要求数据必须存储在堆栈内部.需要实现enqueue(入栈),dequeue(出栈),isEmpty(判空)三个功能,并给出单元测试.(15分)

思路：两个堆栈实现队列
s1为入栈的，s2为出栈的
1. 入队列：直接压入s1即可
2. 出队列：如果s2不为空，把s2中的栈顶元素直接弹出；否则，把s1的所有元素全部弹出压入s2中，再弹出s2的栈顶元素.

stack<int> A;
stack<int> B;
//入队
void enqueue(int value[],int len)
{
    for (int i = 0; i < len; i++)
    {
        A.push(value[i]);
    }
    if (B.empty())
    {
        while(!A.empty())
        {
            B.push(A.top());
            A.pop();
        }
    }
}
出队
void dequeue()
{
    while(!B.empty())
    {
        B.pop();
        //其他操作
    }    
    while(!A.empty())
    {
        B.push(A.top());
        A.pop();
    }
    while(!B.empty())
    {
        B.pop();
        //其他操作
    }
}
//判断是否为空
bool isEmpty()
{
     return (A.empty() && B.empty());
}

拓展：通过队列实现栈

两个队列A与B，两个队列指针，指针qQueue指向一个非空队列(当然如果A、B都是空的话，指向其一），指针tmp始终指向另外一个空队列
1. 入栈: 直接进入qQueue指向的队列；
2. 出栈: qQueue指向的队列是否为空，非空时，将其指向的队列数据移动pop到tmp指向的队列，获取最后一个数据即可，交换qQueue与tmp。

详细讲解参见两个栈实现队列 两个队列实现栈

系统设计题(本题共25分)

手机推送服务设计,在各个手机端应用都有一定的云控制能力,可以再某些情况下云端发送各种数据或者命令道手机端,例如发送一个强制升级的命令或者手机app配置变换的数据包,以及发送一个信息给特定人群(某个地区)
请设计一个以长链接为主的云端控制服务,为了聚焦主要问题,可以忽略掉低速手机网络(例如:2g网络)手机终端等因素\用户登录的需求.服务需要承担定向、定量的推送需求,在设计中要尽量高的吞吐能力和容错能力。
需要完成
a)基本的模块视图
b)链接管理主要设计思路。单台机器承担更多链接，但是链接多了后管理链接(链接中断、链接查找)都会出现性能瓶颈，请尝试给出思路。
c)尝试给出提高容错能力(避免因为某台物理机器或者某个机器上的程序挂掉导致整个系统不可用)的思路

后续分析…

参考：

• http://www.cnblogs.com/newpanderking/p/3972280.html
• 深入浅出TCP协议的2MSL TIME_WAIT状态
• Linux中TCP连接过程简介