计算机网络
https://leetcode-cn.com/circle/discuss/3f6ftQ/
- TCP/UDP 对比
- TCP 面向连接的,可靠的,以字节流形式传输的,适用于要求通讯数据可靠的场景。
- UPD 无连接的,不可靠的,以数据报文段形式传输,适用于对通讯速度要求高的场景。
TCP 如何保证可靠:
- 校验和
- 流量控制:滑动窗口来实现
- 拥塞控制:慢启动; 拥塞避免;快重传快恢复;
- ARQ协议:a. 停止等待ARQ协议 (发送完分组后等待确认) b. 连续ARQ协议 (发送方维护一个窗口,窗口内连续发送;接收方累计确认,对按序到达的最后一个分组做确认)
- 超时重传
- TCP 三次握手
- 客户端向服务器端发送一个带有SYN标志的数据包,表示请求建立连接
- 服务端向客户端发送一个带有SYN+ACK 标志的数据包
- 客户端向服务端发送一个带有ACK标志的数据包
- 其中带有SYN标志的数据包,不包含数据,但是占用一个序列号
- 带有ACK标志的数据包,确认号是收到的SYN标志的序列号+1
- TCP如何拥塞控制
- 忙开始:拥塞窗口从小到大慢慢指数倍增加
- 拥塞避免:超过上限之后,拥塞窗口按照线性增长
- 快重传,快恢复:发送方连续收到3个重复的确认后,提前重传
慢开始:刚开始建立连接的时候,发送窗口大小为1,然后逐步增加窗口的大小,如每次加倍。
拥塞避免:当发送窗口达到一个门限值之后,窗口大小不再每次加倍,而是每次+1,减缓窗口增大速度。
快重传: 快重传算法规定,发送方只要一连收到三个重复确认就应当立即重传对方尚未收到的报文段,而不必继续等待设置的重传计时器时间到期,这是因为此时网络状况良好,可以立即重传。
快恢复:执行“乘法减小”算法将发送窗口门限值减半,以门限值为起点(而非0值),然后执行拥塞避免算法。
- tcp time-wait状态
- 防止主动关闭端的ACK报文段丢失,导致被动关闭段无法关闭连接的情况;被动关闭端没有收到ACK,会重传FIN报文,否则被动关闭方会停留在半关闭状态。
- 允许旧的重复报文在网络中消失,防止新连接收到旧连接的延迟的报文而导致错误
[
](https://blog.csdn.net/u010039418/article/details/80628490)
操作系统
进线程区别和通信优劣势对比
https://haicoder.net/note/opsys-interview/opsys-interview-process-thread-difference.html
- 进程是资源分配的基本单位,
- 线程是运行调度的基本单位,是进程的一个运行实体,一个进程可以有多个线程,线程可以共享进程的内存空间
- 进程通信:
- 管道
- 信号量
- 消息队列
- 套接字
- 共享内存
ipc - 共享内存实现原理
- 先创建共享内存,再将共享内存映射到每个进程中。
select/epoll 区别和触发方式区别 (select、poll和epoll的区别和 IO多路复用模型讲解)
- https://www.cnblogs.com/aspirant/p/9166944.html
- select 只知道有I/O 事件发生了,却不知道是哪几个流,只能无差别轮询
- poll 和select没有本质区别,但没有最大连接数限制,基于链表来存储
- epoll 可以理解为event poll,epoll 会将哪个流发生了什么事件告诉我们,epoll 实际上是事件驱动,对发生的事件进行轮询。
进程调度算法
- 先来先服务
- 短作业优先 (对长作业不友好)
- 时间片轮转
- 多级反馈队列调度算法 (有多级队列,优先级递减,执行时间片递增)
- 最高优先级
页面置换算法
- 最佳页面置换算法 (理想状态,评估的依据)
- 先进先出置换算法 (选择内存中驻留时间很长的页面进行置换)
- 最近最久未使用置换算法 (选择最长时间没有被访问页面进行置换)
- 时钟页面置换算法 (页面保存在环形链表中,发生缺页中断后,遇到的访问位为1的修改为0,遇到0,直接淘汰)
- 最不常用置换算法 (选择访问次数最少的页面淘汰)
磁盘调度算法
- 先来先服务 (寻道时间过长)
- 最短寻道时间优先 (可能会产生某些请求饥饿,磁头在一小块区域来回移动)
- 扫描算法 (磁头在一个方向移动,再调转方向)(磁道中间部分比较占便宜,磁道响应频率存在差异)
- 循环扫描算法 (按照相同的方向扫描)(磁道相应频率相对平均)
段表 页表
死锁和必要条件
算法
- 算法题手写一个快排、归排,并对比分析优劣
快速排序
归并排序
- 手写BST的插入、查找、删除
https://leetcode-cn.com/circle/discuss/q1iaUL/
智力题
1.自我介绍
2.操作系统
2.1 进程和线程
2.2 进程通信
2.3 进程调度
2.4 段表 页表
2.5 死锁和必要条件
3.计网
3.1 ARP协议
3.2 TCP UDP的区别
3.3 DNS协议
3.4 TCP的滑动窗口
3.5 输入URL的后续全过程
4.数据结构
4.1 算法的四大特性—>空间复杂度和时间复杂度
4.2 队列和栈
4.3 HashMap的实现(顺便答一下冲突处理)
4.4 深度优先和广度优先
4.5 中序遍历是深度优先还是广度优先
4.6 冒泡排序的原理 空间复杂度和时间复杂度
5.算法
5.1 一天内分钟和时钟能相遇几次(口述就行)
5.2 链表去除重复结点
作者:面经熊
链接:https://leetcode-cn.com/circle/discuss/zSpznY/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。