具体问题
-
编程题：链表加法
与这个题目类似：add-two-numbers，但是给出的两个数和计算的结果是正向的：链表头部就是最高位，尾部才是个位。
譬如135+25=160：
input：
1->3->5
2->5
output:
1->6->0
当时思路：直接使用两个栈来存储两个链表，再每次从栈顶取元素相加。
面试官：能否只使用一个栈实现？
一个栈+递归？？
存疑。
TCP、UDP区别
| 协议 | 是否面向连接 | 传输可靠性 | 传输形式 | 传输速率 | 所需资源 |
| :----: | ---- | ---- | ---- | ---- | ---- |
|TCP| 面向连接 | 可靠 | 字节流 | 慢 | 多 |
|UDP| 不面向连接 | 不可靠 | 数据报文段 | 快 | 少 |UDP最大数据报文长度
UDP最大数据报文长度=IP数据报的最大报文长度(65535字节)-IP首部(20字节)-UDP首部(8字节)介绍
TCP拥塞控制
慢开始、拥塞避免、快重传、快恢复。内核态与用户态的区别
权限不同
内核态：可以执行特权指令和非特权指令。
用户态：仅能执行非特权指令。
百度百科：特权指令
常见的特权指令有以下几种:
（1）有关对I/O设备使用的指令 如启动I/O设备指令、测试I/O设备工作状态和控制I/O设备动作的指令等。
（2）有关访问程序状态的指令 如对程序状态字（PSW）的指令等。
（3）存取特殊寄存器指令 如存取中断寄存器、时钟寄存器等指令。
（4）其他指令。
- 内核态与用户态如何切换
用户态->内核态：
切换过程中会用到 访管指令（非特权指令，因为需要在用户态使用）
- 系统调用，即用户程序要求操作系统的服务
- 中断
- 异常
- 用户程序企图执行特权指令
内核态->用户态：
中断返回指令（特权指令，因为只能在内核态调用）
介绍
TIME_WAIT状态
等待时间：2*MSL。
原因：确保连接的被动结束方（简称B）能够收到主动结束方（简称A）的ACK报文。
如果B没收到，则会重新发送FIN报文。丢失ACK的传输时间加上重发FIN传输的时间约为2*MSL。局域网内不同设备发送消息的冲突如何处理
主要考点：CSMA/CD协议
载波监听：不管在发送前，还是发送中，每个主机都必须不停地检测信道。
碰撞检测：边发送边监听。
当检测到冲突时，就立即停止发送，面的继续进行无效的发送，白白浪费网络资源，然后等待一段随机时间后再次发送。
使用 截断二进制指数退避 算法来确定重传时间：
每次从离散的整数集合中随机取一个数，记为
r。重传推后的时间就是r倍的争用期。
参考：
- 百度百科：截断二进制指数退避
- 《计算机网络》第七版 谢希仁编著
介绍
HashMap的数据结构
数组、链表、红黑树。如何设计一个支持并发的
HashMap
参考ConcurrenHashMap和SynchronizedHashMap的实现。除了链表和红黑树，还可以如何处理
Hash冲突
公共溢出区、再哈希、顺序寻址（线性探测、二次探测、伪随机数）。使用再哈希处理哈希碰撞时，查找时如何区分使用的哪一个哈希算法
当时回答的是，依次与每一个Hash算法计算的哈希值所在位置存储的数据进行equals比较，直到找到 或者 所有hash函数都比较完且不存在。
不存在的判定条件应该是所有hash函数都比较完，而不应该是某一个hash值所在位置为空就停止：有可能为空的位置在当前查找的元素插入时存在，所以发生冲突继续使用后续的hash函数计算，而查找时那个位置的元素已被移除。
存疑
介绍一下原子类
对原子类的操作都具有原子性，即不可再拆分。原子操作的实现原理
