具体问题

  • 编程题：链表加法
    与这个题目类似：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函数计算，而查找时那个位置的元素已被移除。

    存疑