上周五约了今天早上的面试。按时打过来了。
主要问了算法、网络和操作系统的东西。算法会的都讲错；操作系统把我怼惨了，几乎都PASS了，第一场就GG了。

1. 问一下基本情况

2. 介绍一下自己的项目

3. 打过ACM为什么选择做Java后台

4. 说一下建堆的时间复杂度（讲错）

说了是O（nlogn），面试官很惊讶，我吓死，就解释了下大概过程。遍历非叶子结点O（n），每个结点都要往下进行shiftdown操作O（logn），所以得到O（nlogn）。
结束后查了一下，是O（n），连最应该答出来的都凉凉了。原因在于只考虑了最差情况下的复杂度。1/2的结点只用简单的和下面比较，1/4的结点需要往下shiftdown一次，1/8的结点需要两次，1/16的结点需要三次...1/2^k的结点需要k次，k的大小大概是logn。
建堆复杂度证明

5. 了解背包吗，说一下动态规划的思想，用过几维的动态规划（没讲好）

之前没准备过，想到什么就说了下。
之后可能会这样答：动态规划的本质，是对问题状态的定义和状态转移方程的定义。动态规划是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。
还要复习下背包。
什么是动态规划

6. TCP的四次挥手

提到了四次挥手+等待2MSL（最长报文段寿命）。

7. TCP的报文结构（不会）

提到了首部。然后让我讲讲首部，我就抱歉不记得了。
TCP首部的前20个字节是固定的，包括了源端口、目的端口、序号、确认号、窗口大小等信息。

image

好像提到了TLS，我以为讲的是报文结构里面的东西，直接说不知道。忘了是https的东西，才刚看过，惨。

8. HTTP的报文结构（没讲全）

提到了只有响应头和请求头是不同的，然后讲了下响应头和请求头里面的东西，没讲全。其他结构（首部行，实体主体）基本相同。
请求头里面包含了：方法、URL和版本。（漏了说URL）
响应头里面包含了：版本、状态码和解释状态码的简单短语。

9. HTTP的状态码

讲了100、200、300、400、500。（讲的不够规范）
100：客户端应当继续发送请求。这个临时响应是用来通知客户端它的部分请求已经被服务器接收，且仍未被拒绝。客户端应当继续发送请求的剩余部分，或者如果请求已经完成，忽略这个响应。服务器必须在请求完成后向客户端发送一个最终响应。
200：请求已成功，请求所希望的响应头或数据体将随此响应返回。出现此状态码是表示正常状态。
300：被请求的资源有一系列可供选择的回馈信息，每个都有自己特定的地址和浏览器驱动的商议信息。用户或浏览器能够自行选择一个首选的地址进行重定向。
400：语义有误，当前请求无法被服务器理解。除非进行修改，否则客户端不应该重复提交这个请求。或者 请求参数有误。
500：服务器遇到了一个未曾预料的状况，导致了它无法完成对请求的处理。一般来说，这个问题都会在服务器端的源代码出现错误时出现。

10. UDP和TCP的区别

1. UDP无连接，TCP有连接。
2. UDP是尽最大努力的交付，TCP是保证可靠交付（好不容易到会的地方，就开始讲如何保证可靠性，讲了确认机制，超时重传，拥塞控制、流量控制，扯到一半面试官不给我讲了...）。
3. UDP是面向报文的，TCP是面向字节流的。
4. UDP可以是一对一、一对多、多对一、多对多通信，TCP是点对点通信。
5. UDP速度快，TCP速度慢（建立连接需要时间）。

11. UDP和TCP分别有什么用途

UDP：一般用于即时通信（QQ聊天 对数据准确性和丢包要求比较低，但速度必须快），在线视频（RTSP 速度一定要快，保证视频连续，但是偶尔花了一个图像帧，人们还是能接受的），网络语音电话（VoIP 语音数据包一般比较小，需要高速发送，偶尔断音或串音也没有问题）等等。
TCP：一般用于文件传输（FTP HTTP 对数据准确性要求高，速度可以相对慢），发送或接收邮件（POP IMAP SMTP 对数据准确性要求高，非紧急应用），远程登录（TELNET SSH 对数据准确性有一定要求，有连接的概念）等等。

12. UDP实现可靠传输如何设计（不会）

讲了像TCP一样，但是面试官和我说UDP是无连接的，我就说不会了。他说这也没有一个标准的答案，回去自己查一下。

有连接和无连接区别：首先面向连接的通信具有数据的有序性，关心数据是否按序到达，接收方需要发送确认。 而面向无连接的通信不能保证接收数据的顺序与发送数据的顺序一致，只负责把分组封装好发出去，不关心接收方是否接收到。
需要在UDP之上封装实现超时重传（定时器）、有序接收和确认应答（seq和ack）还有滑动窗口（滑动窗口协议）等机制。
UDP实现可靠传输

13. 了解Socket编程吗（不会）

Java课上用过，忘得差不多了，就不给自己挖坑了。

14. 对分布式和大数据有了解吗（不会）

答了没了解过，但是准备完面试后会去学习。

15. 系统内核（不会）

忘了问题了，听到问题的时候懵了。

16. Linux文件结构（不会）

答了B树，面试官估计惊呆了，就跳过这个问题。

应该是要答Linux的文件目录吧。

Linux文件目录

17. 多个应用程序访问内存，但是内存很小，如何实现（提示虚拟内存，不会）

一开始没听清楚，说通过线程。后面讲清楚又不会了。

应用程序在运行之前没有必要全部装入内存，仅需将那些当前要运行的少数页面或段先装入内存便可运行，其余部分暂留在硬盘上。程序在运行时，若要访问的页已经调入内存，就继续执行下去；否则发出缺页中断请求，此时OS利用请求调页功能将它们调入内存，使进程能执行下去。如果内存已满，无法装入新的页，就要利用页面置换功能，将内存暂时不用的页调到硬盘上。这样便可使多个应用程序同时访问较小的内存空间。

虚拟内存需要请求调入功能和置换功能。实现方式分为请求分页系统和请求分段系统。

请求分页系统需要有请求页表机制、缺页中断机构和地址变换机构。

1. 请求页表机制

   
   
   请求页表
   
   

   （1）访问字段A：记录本页在一段时间内被访问的次数，或者记录最近已有多长时间未被访问。方便置换算法计算。
   （2）修改位M：标识该页在调入内存后是否被修改过。因为内存中每一页会在外存中保留一份副本，所以若在置换时未被修改，就不需要再将该页写回外存，以减少系统开销和启动磁盘的次数；若被修改，要写回外存保证外存的副本是最新的。

2. 缺页中断机构
   在指令执行期间产生和处理中断信号。一条指令在执行期间可能产生多次缺页中断。

3. 地址变换机构

   
   
   请求分页的地址变换过程

内存分配策略：

1. 固定分配局部置换。固定分配是指 为每个进程分配固定的数目的物理块（物理块里包含多个页）。局部置换是指 进程发生缺页，就从分配给该进程的页中选出一页换出，再调入一页，保证分配给该进程的内存空间不变。
2. 可变分配全局置换。可变分配指 进程运行期间，物理块可以适当增多或减少。全局置换指 进程发生缺页，将OS的一个空闲物理块分配给该进程，如果空闲物理块用完了，OS才从内存中选择一页调出。
3. 可变分配局部置换。

页面置换算法（LRU）

说明自己对于挺多知识只知道是什么，没有去挖掘为什么是这样的，内在有什么关联。

18. CPU那么快，内存那么慢，操作系统如何协调（不会）

提到了Cache，就不会了。

Cache介绍

19. 说我操作系统比较差，让我说说做过什么实验，然后就讲了银行家算法

20. 说说爬虫经历

21. 百度的每秒访问量大概是多少

开放性问题。没答好。讲了大概千万级别，说了下中国13亿人口，每秒在100个人里面应该会有1个人访问。挂了电话一查百度每天的访问量才几亿，惨。

22. 如果能实习的时间

23. 有什么问题想问

总结

这个面试官其实还是很好的，主要自己太菜了。对于很多知识都是一知半解，听过，但是深入一下就不会了。而且有些都是知道的，但是没答好，或者没认识到面试官是想问那个点。总的来说，自己还是太naive了，要多想想知识的内在联系，让它们串起来。