面试题整理
C++基础
另外一篇整理里面https://www.jianshu.com/p/9aae0e5dc21a
计算机网络基础TCP/IP
- 分层结构（4层），及对应的主要协议
应用层：HTTP(基于) DNS（域名解析协议，基于UPD）
传输层：TCP UPD（都基于IP数据报协议）
IP层：IP数据包协议、ICMP（IP层的附属协议,是介于IP层和TCP层之间的协议） - 封装和解封
封装：应用层数据->加头部封装成TCP段或UDP消息->加IP头封装成IP数据报->封装成帧
解封：逆过程，读取头部消息，去掉头部信息，剩下的交给上层。 - 数据校验
简单的校验和算法。 - TCP协议介绍
要点： - 流量控制和拥塞控制
流量控制：接收窗口rwnd，在tcp头部写入，告诉对方自己接受缓冲区的大小。发送方根据这个大小来决定发送多少数据【rwnd-未确认的】。
拥塞控制【启发式试探过程】：慢启动（起点比较小指数增加）和拥塞避免已经很大了，慢慢增加。 - TCP的11种状态
题目形式：介绍一下TCP三次握手，4次挥手，11中状态。
要点：画图介绍10种状态，再说明CLOSING状态的特殊性
客户端<====================> 服务器端
开始阶段==================== listen（服务器的调用listen函数）
发送SYN（SYN_SEND）------------>接收后进入SYN_RCV状态（半开）
ESTABLISHED<-------------------------发送SYN，并确认
题目形式：为什么建立连接要三次握手，断开链接要四次握手。
三次握手是因为要建立全双工可靠链接，最少需要三次握手。两次不行，是防止已过期的连接再次传到被连接的主机。四次可以，但是效率低了。
四次挥手：一份请求断开链接，只是表示自己不再发送数据，但对方的数据不一定发完了，所以要能够接受对方的数据，处于半关闭状态。
- SYN攻击
说一下syn flood 攻击。【百度面试】
https://www.nowcoder.com/discuss/1922
原理：伪造SYN连接，占满半开连接队列，真正的服务被拒绝。
解决方法：1、释放不活动的连接。2、延迟分配TCB。3、使用SYN Proxy防火墙
- TCP的TIME_WAIT状态
题目形式：介绍一下TIME_WAIT状态，为什么要有TIME_WAIT状态，有什么影响，如何解决。
要点：解释一下TIME_WAIT，可以画图，后面三问也是作为回答的要点
TIME_WAIT: 主动关闭连接的一方，收到对方发送的FIN后，响应对方并进入TIME_WAIT状态，等待2MSL时间，如果没有再结束到数据，主动方进入CLOSED状态。
原因：1）确保可靠连接关闭（对方关闭），如果对方没有收到FIN的响应报文（丢失）会重传FIN报文，而主动方是CLOSED状态，被动方会收到RST消息。2）接收并丢弃迟到的段，TIME_WAIT状态会占用端口，不会被其他连接使用。报文的最大生存期是2MSL，可以保证该链接所有数据再网络中消失。不会出现新的连接接收到老的数据。
影响：TIME_WAIT会占用端口，服务器端马上重启会失败。客户端如果短连接多，会占用大量端口，导致没有可用端口。
解决：设置socket选项SO_REUSEADDR，或修改内核参数，地址重用。客户端短连接改为长链接。
- UDP和TCP的区别
要点：链接vs无连接 可靠vs不可靠（无序，丢失，重复） 流vs消息 流量控制和拥塞控制 效率
TCP：有连接的可靠的字节流协议
UDP：无连接的数据报协议 - UDP实现可靠传输
要点：应用层模拟实现TCP【确认重传，序列编号】
系统编程
- 多进程fork
题目形式：介绍一下fork函数。
要点：子进程，关系，区别，返回值，文件描述符，写时复制
fork函数作用是创建一个子进程，父进程中的返回值是子进程的pid，子进程返回值是0，放回-1表示创建失败。可以根据返回值区分是父进程和子进程。
内核创建新的PCB结构
子进程是父进程的一个副本【代码段，数据段，堆，栈等支援】。子进程拥有复制父进程的文件描述符，在内核中指向相同的file结构，引用计数器加一。
子进程拥有自己的地址空间（虚拟地址），但开始时指向相同的物理地址，通过写时复制（copy-on-write）方式提高效率。在没有exec调用的情况下共享代码段。
- 多进程exec调用
题目形式:介绍exec调用，并比较exec和fork
exec（系列函数有6个）不创建新的进程，而是替换当前进程的内容（虚拟内存的内容）。【删除已存在的用户区域->映射私有区域->映射共享区域->设置程序计数器】
fork函数的内容在上面。f
比较：fork函数创建新的进程（产生新的pid），并且生成一个父进程副本。exec不创建新的进程（pid不变），替换内容。fork和exec配合使用运行一个新的程序。两个函数的返回都很特殊，成功时，fork返回两次，exec不返回。
- 多进程clone
题目形式：介绍clone，比较clone和fork
clone函数提供参数，选择复制父进程的哪些资源。【意义在于实现线程】
int clone(int (*fn)(void *), void *child_stack, int flags, void *arg)
/*
fn就是即将创建的线程要执行的函数，stack是线程使用的堆栈。
再来看一下clone和pthread_create的区别：linux中的pthread_create最终调用clone。
*/
- 多进程僵尸进程
题目形式：介绍一下僵死进程，产生原因，影响，如何避免。
要点：wait，wait_pid，信号，init进程
1）父进程退出子进程还在运行，会产生孤儿进程，孤儿进程由init进程收养，没有危害。
2）子进程退出后，释放了资源但是还是有些资源无法释放【进程id，退出状态，运行时间等】，需要等父进程调用wait或wait_pid获取子进程状态后回收处理，进入僵死状态。如果子进程退出后，父进程没有调用wait或wait_pid，则子进程进程描述符会一直留在系统中，称为僵死进程。僵死进程占用进程描述符，而系统的集成描述符是有限的，僵死进程可导致系统进程描述符可用而无法创建新进程。
处理方式：1）捕获SIGCHLD信号并忽略 SIG_IGN。2）sig_handler函数中调用wait，wait_pid 3）调用两次fork函数，第一次创建子进程，子进程再创建子进程并退出，父进程wait子进程回收资源，孙进程成为孤儿进程，退出后由init进程回收。4）父进程退出是调用wait
题目形式：进程间通信的方式，【说说信号量，消息队列，共享内存...】比较各种通信方式
要点：几种通信方式特点，对比，应用场景，限制
消息传递：管道和FIFO、消息队列
同步：互斥锁和条件变量、读写锁、信号量
共享内存。
管道
FIFO
管道-------------FIFO------------消息队列
半双工---------半双工----------（全双工？）
亲缘进程------任意进程-------任意进程
数据流---------数据流----------消息
顺序读取------顺序读取-------随机读取
无边界---------无边界----------有边界【有特点结构】
无优先级------无优先级-------有优先级
进程相关------进程相关-------独立
同步：【进程】信号量、【线程】互斥锁和条件变量、读写锁、自旋锁（忙等待）
信号量（semaphore）: 与已经介绍过的 IPC 结构不同，它是一个计数器。信号量用于实现进程间的互斥与同步，而不是用于存储进程间通信数据。
共享内存（Shared Memory），指两个或多个进程共享一个给定的存储区。
特点
- 共享内存是最快的一种 IPC，因为进程是直接对内存进行存取。
- 因为多个进程可以同时操作，所以需要进行同步。
- 信号量+共享内存通常结合在一起使用，信号量用来同步对共享内存的访问
五种通讯方式总结
1.管道：速度慢，容量有限，只有父子进程能通讯
2.FIFO：任何进程间都能通讯，但速度慢
3.消息队列：容量受到系统限制，且要注意第一次读的时候，要考虑上一次没有读完数据的问题
4.信号量：不能传递复杂消息，只能用来同步
5.共享内存区：能够很容易控制容量，速度快，但要保持同步，比如一个进程在写的时候，另一个进程要注意读写的问题，相当于线程中的线程安全，当然，共享内存区同样可以用作线程间通讯，不过没这个必要，线程间本来就已经共享了同一进程内的一块内存
网络编程
- 五种I/O模式
阻塞模式，非阻塞模式，IO复用，信号IO，异步IO
阻塞模式：挂起等待
非阻塞模式：忙等待
设置为非阻塞模式的几种方式：
创建时指定
int s = socket(AF_INET, SOCK_STREAM | SOCK_NONBLOCK, IPPROTO_TCP);
API调用
fcntl(sockfd, F_SETFL, fcntl(sockfd, F_GETFL, 0) | O_NONBLOCK);
ioctl(sockfd, FIONBIO, 1); //1:非阻塞 0:阻塞
accep4函数返回，设置flags为SOCK_NONBLOCK
int accept4(int sockfd, struct sockaddr *addr, socklen_t *addrlen, int flags);
I/O复用：select/poll，epoll
信号I/O：注册信号，信号处理
异步I/O：buf传递给内核，有数据时，填充buf发送消息，通知时数组已经准备好，不需要再拉取数据
- select poll和epoll的比较
回答要点：1.文件描述符个数限制 2.效率（轮询和回调对比）3.epoll数据结构（红黑树和队列） - epoll两种模式LT和ET
题目形式：比较epoll边沿触发和水平触发
要点：EL只通知一次（非阻塞），LT可能通知多次（阻塞和非阻塞）
EL模式下，描述符从未就绪状态变为就绪状态时，内核通知进程，并从就绪队列中移除。只支持非阻塞模式（不是不能用阻塞模式，而是会有问题）。【数据不处理完，不会再次被通知，所以需要在处理EL中，循环读取数据，直到发生EAGIN（表示暂无数据可读）或返回值小于要读取的长度（表示读完），阻塞模式在这个时候就会出问题，没有数据可读，会一直等待，而无法执行其他操作，非阻塞模式会立即返回，让进程可以处理其他事件】
LT是默认模式，支持阻塞和非阻塞模式两种模式。和select/poll一样，有数据直接读就行，不需要一定读完，因为下一次还会通知。
效率对比：EL通知一次，效率更高，但对程序员要求更高。TL会多次通知，效率相对低，当编程简单，不易出错。
- 惊群效应
题目形式：介绍惊群效应，影响，解决方法。
要点：条件满足多个线程被唤醒只有一个能得到资源，需要调度线程开销大， 解决方法：只会唤醒等待队列上的第一个进程或线程
惊群现象（thundering herd）就是当多个进程和线程在同时阻塞等待同一个事件时，如果这个事件发生，会唤醒所有的进程，但最终只可能有一个进程/线程对该事件进行处理，其他进程/线程会在失败后重新休眠，这种性能浪费就是惊群。
Nginx中使用mutex互斥锁解决这个问题，具体措施有使用全局互斥锁，每个子进程在epoll_wait()之前先去申请锁，申请到则继续处理，获取不到则等待，并设置了一个负载均衡的[算法]-当某一个子进程的任务量达到总设置量的7/8时，则不会再尝试去申请锁）来均衡各个进程的任务量。
linux系统使用
- GCC编译选项
- GDB命令
- 常用命令
题目形式：说一下你熟悉的linux命令
要点：不太会的不要说，防止被抓住深问。
数据结构和算法
- 树
树被问到的可能性很高，线性结构太简单，图比较复杂不好问，树种类多应用广（数据库，STL都可能问到）。
题目形式：
介绍一下红黑树，比较红黑树和AVL。（前面可能问着STL的map和set，然后就转到红黑树了）
介绍字典树
比较B树和B+树（数据库索引必问）
红黑树：平衡二叉查找树。操作时间复杂度是logn。满足5个特点：
1）节点非即黑
2）根黑
3）叶黑（叶子节点是空节点，虚拟节点）
4）路径红不连（红节点的子节点不能为红节点）
5）路径黑相等（任意节点到所有根节点上的路径）
- 套路算法（TOP K，洗牌算法，）
问题很套路，答案也很套路，看过可能就知道，不看想破脑袋的题目。
问题形式：从20亿个数字的文本中，找出最大的前100个。
要点：堆排序，大小维护，数据替换
维护一个大小为100的小顶堆，堆中数据都比顶大，如果新数据比顶下，则丢弃，如果比顶大，替换顶部数据，并调整堆。复杂度为nlogm，这里的m是100。
题目形式：有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。
要点：哈希，堆排序，大小设计
1）1G数据的文件哈希到1024个小文件中，每个文件大小平均为1M。概率上有一半的会超过1M，还有继续切分，不如一开始就去2048的大小，这样每个文件大小大约为0.5M，还有个别超过1M的继续处理到小于1M。（这样相同的词在同一个文件中）
2）对小文件统计词频。方法可用hash_map，或者排序（hash效率更高些），将其写入文件。
3）剩下的就是上一题的过程。
题目形式：假如每天有10亿次的QQ登录记录，实际只有6亿个不同的人登录。如何找出这6一个QQ号。【来源牛客网面经】
要点：简单计算分析，hash分文件，文件内记录去重
10亿条数据，一条数据去10byte（QQ号11位了），简单计算一下大小：约为10G，全部放入内存不现实。将QQ号hash到10个小文件（hash算法可以简单的mod10），每个文件平均为1G，1G的数据可以用hash表去重，写入输出文件。
#数据库
+ 数据库事务理解
事务的4个特点
>1）原子性（要么都做，要么不做，不会存在做部分）
2）一致性
3）隔离性
4）**持久性**这一条没记住
+ MySQL数据库的存储引擎
题目形式：介绍一下MySQL的存储，优缺点和应用场景。
InnoDB：支持事务，默认存储引擎。
MyISAM：不支持事务，效率高。支持FullText索引。
Memory：在内存中，效率高。适用查找频繁，基本不变的数据。
