Skip to main content

面试笔记

1. 计算机网络​

http tcp 和 ip都在第几层？

  1. HTTP 属于应用层
  2. TCP 属于传输层
  3. IP 属于网络层

OSI 七层模型：

  1. 物理层（Physical Layer）：硬件接口，负责物理信号传输。
  2. 数据链路层（Data Link Layer）：提供节点间的可靠传输（如以太网）。
  3. 网络层（Network Layer）：负责路由和寻址（如 IP 协议）。
  4. 传输层（Transport Layer）：提供端到端的通信（如 TCP 和 UDP）。
  5. 会话层（Session Layer）：：管理会话控制和数据交换。
  6. 表示层（Presentation Layer）：负责数据的格式化、加密和解密。
  7. 应用层（Application Layer）：用户直接交互的协议和服务（如 HTTP、FTP）。

TCP 三次握手​

TCP 是面向连接的、可靠的传输层协议，在通信双方正式开始数据传输前，必须确定彼此的收发能力和初始化序列号（Sequence Number），以确保数据能被可靠地传输并重组。

“三次握手”可以确保双方都知道对方可以正常收发数据，并且能够交换起始序列号，为后续数据传输做准备。

  1. Client -> Server：发送 SYN 包（SYN = 1，Seq = x）

    • 客户端向服务器发送一个带有 SYN 标志的数据包，请求建立连接。
    • 同时指定一个初始序列号 Seq = x（用来标识数据包的顺序）。
    • 在该阶段，客户端处于 SYN_SEND 状态。

  2. Server -> Client：发送 SYN+ACK 包（SYN = 1, ACK = 1，Ack = x+1，Seq = y）

    • 服务器收到客户端的 SYN 包后，如果同意建立连接，则向客户端发送一个带有 SYN+ACK 标志的数据包。
    • 服务器的包中也会包含自己的初始序列号 Seq = y。
    • ACK 确认号（Ack = x+1）表示“已收到客户端的 SYN 序列号 x，并期望下一个数据从 x+1 开始”。
    • 在该阶段，服务器处于 SYN_RCVD 状态。

  3. Client -> Server：发送 ACK 包（ACK = 1，Ack = y+1）

    • 客户端收到服务器的 SYN+ACK 包后，必须再发送一个确认包 ACK。
    • 其中 Ack = y+1，表示“已收到服务器的序列号 y，并期望下一个数据从 y+1 开始”。
    • 在该阶段，客户端处于 ESTABLISHED 状态。
    • 该包发送完毕后，客户端进入 ESTABLISHED（连接已建立）状态，服务器在收到 ACK 后也进入 ESTABLISHED 状态。

TCP 四次挥手​

TCP 连接是全双工的，即双方都可以同时发送和接收数据。当一方没有数据要发送时，可以单方面关闭发送通道（即发送 FIN），但另一方可能还在继续发送数据，所以需要分两步：

  1. 先由主动关闭方发送 FIN 表示“我这边没有数据要发了”。
  2. 然后再由被动关闭方发送 FIN 表示“我也没有数据要发了”。

因此，断开连接往往需要四次挥手来确保双方都同意关闭各自的发送通道。

  1. 主动关闭方（Client） -> 被动关闭方（Server）：发送 FIN 包（FIN = 1，Seq = u）

    • 当客户端确定不再发送数据了，会发送 FIN 包给服务器，表示“我已经没有数据要发送了，之后你发给我的数据我仍然可以接收”。
    • 此时客户端处于 FIN_WAIT_1 状态。

  2. 被动关闭方（Server） -> 主动关闭方（Client）：发送 ACK 包（ACK = 1，Ack = u+1）

    • 服务器收到 FIN 后，发送 ACK 包进行确认，表明“我知道你不发数据了”。
    • 这时服务器仍可能有数据要发送（双工的另一方向还没关闭）。
    • 客户端收到这个 ACK 后，进入 FIN_WAIT_2 状态，等待服务器发送 FIN。
    • 服务器处于 CLOSE_WAIT 状态。

  3. 被动关闭方（Server） -> 主动关闭方（Client）：发送 FIN 包（FIN = 1，Seq = v）

    • 当服务器也发送完它要发的数据后，决定关闭连接，就会发送 FIN 包给客户端。
    • 服务器进入 LAST_ACK 状态，等待客户端的最后一个 ACK。

  4. 主动关闭方（Client） -> 被动关闭方（Server）：发送 ACK 包（ACK = 1，Ack = v+1）

    • 客户端收到服务器的 FIN 包后，发送 ACK 进行确认，Ack = v+1。
    • 此时客户端进入 TIME_WAIT 状态，等待可能还会在网络中滞留的重复 FIN 包。
    • 服务器在收到 ACK 后，就进入 CLOSED 状态。
    • 当客户端在 TIME_WAIT 状态（默认 2 * MSL 时间）结束后，也会进入 CLOSED 状态，至此连接完全关闭。

2. 排序算法​

排序算法的稳定性：当待排序序列中存在相等的元素时，排序前后这些相等元素的相对位置保持不变。

实际意义：在对复杂对象排序时很重要。比如先按成绩排序学生，再按年龄排序，如果使用不稳定排序算法，第二次排序会打乱第一次排序的相对顺序。

选择排序​

遍历一边数组，找到数组中的最小值，然后和数组中的第一个元素交换位置，接着在剩下的数组中继续找最小值，和数组中的第二个元素交换位置，以此类推，直到数组中所有元素都排序完成。

时间复杂度：

O(n2)O(n^2)

空间复杂度：

O(1)O(1)

选择排序不是稳定的排序算法。交换过程会打乱相等元素的相对位置。

冒泡排序​

时间复杂度：

O(n2)O(n^2)

空间复杂度：

O(1)O(1)

比起选择排序拥有了稳定性

插入排序​

时间复杂度：

O(n2)O(n^2)

空间复杂度：

O(1)O(1)

插入排序的效率和输入数组的有序度有很大关系，如果输入数组已经有序，或者仅有个别元素逆序，那么插入排序的内层 for 循环几乎不需要执行元素交换，所以时间复杂度接近 O(n)O(n)

对比插入排序和冒泡排序，插入排序的综合性能应该要高于冒泡排序。

快速排序​

时间复杂度：

O(nlogn)O(nlogn)

空间复杂度：

O(logn)O(logn)

快速排序是不稳定排序算法

归并排序​

时间复杂度：

O(nlogn)O(nlogn)

空间复杂度：

O(n)O(n)

归并排序是稳定排序算法