自我介绍
毕业院校、项目经历、实习工作经历,简单介绍掌握的技能。
算法题
给定二叉树中指定节点和一个整数k,寻找距离指定节点距离为k的所有节点:
要求:时间复杂度 $O(n)$, 空间复杂度 $O(n)$
思路:如果给定节点为父结点,寻找距离其为 k 的节点可以直接用递归去查找,难点在于如何寻找给定节点父结点和兄弟节点中距离其为k的节点
问答环节
虚拟内存了解吗?使用虚拟内存有什么好处?
虚拟内存是计算机系统内存管理的一种技术。它使得应用程序认为它拥有连续的可用的内存,而实际上,它通常是被分隔成多个物理内存碎片,还有部分暂时存储在外部磁盘存储器上,在需要时进行数据交换。
- 扩展内存容量:虚拟内存通过将部分数据存储在磁盘上(如HDD或SSD),扩展了物理内存(RAM)的容量。即使计算机的物理内存不足,也可以运行需要较大内存的应用程序,从而避免因内存不足导致程序无法运行的问题。
- 多任务处理:虚拟内存允许多个程序共享计算机的物理内存。在实际使用中,每个程序认为自己有一个完整且独立的内存空间,而虚拟内存负责将这些内存请求映射到实际的物理内存或磁盘中。这种机制让操作系统可以运行多个程序,而不受物理内存容量的严格限制。
- 内存隔离和安全性:虚拟内存为每个进程提供独立的虚拟地址空间,从而隔离进程间的内存访问。一个程序无法直接访问另一个程序的内存内容,防止程序之间的相互干扰,增强了系统的稳定性和安全性。
- 灵活的内存管理:虚拟内存通过分页或分段机制,允许操作系统以更细粒度管理内存。内存页面可以按需加载到物理内存中,这种方式称为按需分页,提高了内存利用效率,避免了内存的浪费。
- 更大的地址空间:通过虚拟内存,应用程序可以使用一个比物理内存更大的地址空间。这对于运行大型程序(如科学计算、数据库等)非常重要,因为程序可以利用虚拟内存进行更大规模的数据处理。
- 简化开发工作:虚拟内存为程序开发提供了一种抽象,使程序员可以不用关心物理内存的具体布局和容量。程序员只需关注虚拟地址空间,而操作系统负责将虚拟地址映射到物理内存或磁盘位置。
计算机内存管理方式有哪几种?各自优缺点?
-
页式内存管理
概念:页式内存管理将内存分为固定大小的页面 (一般是4KB),将进程的虚拟地址空间映射到物理内存的相应页框。
优点:
- 内存利用率高,内存以页为单位分配,消除了外部碎片;
- 便于内存共享,多个进程共享同一页面,提高效率;
- 按需加载,支持按需分页,只有在需要时才将页面加载至内存;
- 实现方式较为直观,支持随机访问。
缺点:
- 由于页大小固定,最后一页未使用的部分可能会造成浪费,产生内部碎片;
- 地址转换开销大,每次访问内存都需要通过页表进行地址转换,增加内存访问的时间;
- 当进程虚拟地址空间较大的情况下,页表会占用较多的内存资源。
-
段式内存管理
概念:段式内存管理将程序划分为逻辑意义上的段,每个段具有不同的大小和属性,如代码段、数据段、堆栈段等。
优点:
- 逻辑结构清晰,每个段对应程序的逻辑模块,便于编程和管理;
- 灵活性高,不同段可以有不同的大小,能更好适应程序的需求;
- 便于共享和保护,可以对不同的段设置不同的权限,支持段的共享和保护;
- 每个段的大小是按需动态分配的,减少了内部碎片的产生。
缺点:
- 内存分配和回收过程中,会产生外部碎片;
- 地址转换复杂,短时管理需要段表进行地址转换,增加了复杂性;
- 由于段的大小不固定,分配和回收内存可能需要更多时间。
-
段页式内存管理
概念:结合页式和段式管理的特点,首先将虚拟地址空间划分为若干段,每个段再进一步划分为固定大小的页。
优点:结合了页式和段式的优点,支持段的逻辑划分,也支持按页分配内存。
缺点:实现复杂,需要同时维护段表和页表,并且地址转换开销更大,内存访问需要两级地址转换,降低了访问速度。
选一种你熟悉的内存管理方式,简述其寻址过程?
这里我选的是页式内存管理。
-
分解虚拟地址为页号(PN)和页内偏移量(PO);
-
查找页表,找到对应的物理页框号(FN);
-
检查页表项有效性,处理缺页情况;
-
组合页框号和页内偏移量,计算物理地址;
-
访问物理内存。
可以使用快表(TLB)优化地址转换过程。
TCP和UDP的区别以及各自的适用场景
TCP与UDP的基本区别,:
- 基于有连接和无连接;
- 系统占用资源多少;
- UDP程序结构较为简单;
- TCP面向字节流,UDP面向数据报;
- TCP保证数据正确性,UDP可能丢包;
- TCP保证数据顺序,UDP不保证。
UDP应用场景:实时场景,RIP路由表更新,DNS、SNMP等都是运行在UDP之上。
- 面向数据报方式;
- 网络数据大多为短消息;
- 拥有大量client;
- 对数据安全性没有特殊要求;
- 网络负担重,但是对响应速度要求高。
总体来说,TCP与UDP的区别如下:
- TCP面向连接(如打电话要先拨号建立连接);UDP是无连接的,即发送数据之前不需要建立连接。
- TCP提供可靠的服务。也就是说,通过TCP连接传送的数据,无差错,不丢失,不重复,且按序到达;UDP尽最大努力交付,即不保证可靠交付。
- TCP面向字节流,实际上是TCP把数据看成一连串无结构的字节流;UDP是面向报文的。UDP没有拥塞控制,因此网络出现拥塞不会使源主机的发送速率降低(对实时应用很有用,如IP电话,实时视频会议等)。
- 每一条TCP连接只能是点到点的;UDP支持一对一,一对多,多对一和多对多的交互通信。
- TCP首部开销20字节;UDP的首部开销小,只有8个字节。
- TCP的逻辑通信信道是全双工的可靠信道,UDP则是不可靠信道。
ps: UDP一般不说全双工、半双工,因为这些说法都是指面向连接才有的说法,而对于UDP这种不建立连接的传输协议,没有明确的全双工、半双工的说法。
TCP适用场景:
TCP 如何判断是否发生了拥塞?拥塞控制?
TCP拥塞判断机制:
- 超时重传,超时未收到ACK;
- 重复ACK,连续收到三个重复的ACK;
- RTT增大,网络延迟显著上升;
- 丢包率升高,丢包现象频繁发生;
- ECN显式拥塞控制,通过网络设备显式告知拥塞。
TCP的四种拥塞控制算法:
-
慢启动
发送端在最初建立连接后,拥塞窗口值为1,接收方收到该报文后,将拥塞窗口的值变为2,每个传输轮次依次增加(指数方式增加),直至发生拥塞。
-
拥塞避免
每个传输轮次线性增加拥塞窗口值。
-
快重传
接收方收到未按需到达的报文段后,要求发送方重传之前的报文段,而不是等超时重传计数器超时再重传。
-
快恢复
发送方知道丢失了个别字段的报文段后,不启慢启动算法,执行快恢复算法,将拥塞窗口值修改为当前窗口的一般,开始执行拥塞避免算法。
三次握手和四次挥手是为了什么?
三次握手必要性:
- 确保接收方/发送方通信能力正常;
- 避免旧连接请求的干扰;
- 同步初始序列号;
- 确保双方对连接状态的理解一致。
四次握手必要性:
1. TCP是全双工通信协议,双方发送和接收的通道是独立的,因此连接的断开也需要分别关闭发送和接收通道
2. 确保全双工通信的每一方向都能独立关闭通道;
3. 保障数据完整传输,不丢失数据;
4. 避免资源泄露,确保连接彻底释放;
5. 增强协议的可靠性和健壮性。
进程间通信方式有哪几种?具体说说实现方式?
-
匿名管道:只能在具有亲缘关系(父子进程)的进程间通信,单向通信。
一个进程创建管道,使用
pipe
系统调用,生成一对文件描述符,一个文件描述符用于写入,另一个用于读取,数据以FIFO方式传递。 -
有名管道:不要求进程有亲缘关系,支持双向通信。
使用
mkfifo
创建一个命名管道文件,各个进程通过打开相同的命名管道文件来实现通信,数据在内核中传递,类似匿名管道。 -
信号量:用于进程间同步,不能直接传输数据,适合解决共享资源的互斥和同步问题。
-
消息队列:允许多个进程以消息为单位进行通信,消息具有标识和优先级。
创建一个消息队列
msgget()
,进程通过消息队列向其他进程发送消息mssgsnd()
,接收进程通过消息队列接收消息msgrcv()
, 内核负责管理消息队列,确保消息按优先级或FIFO方式传递。 -
共享内存:多个进程直接共享一块物理内存,是最快的IPC方式。
创建或获取共享内存
shmget()
,将共享内存附加到进程地址空间shmat()
,进程通过指针直接对共享内存进行读写。 -
套接字:创建套接字socket进行你通信,支持不同主机或同一主机上的进程通信,支持TCP和UDP。
创建套接字
socket
,通过bond()
绑定地址、listen()
监听 、accept()
接收连接实现服务端通信,客户端通过connect()
连接服务端,双方通过send()
和recv()
进行数据交换。 -
文件:通过文件系统进行间接通信,适合数据量大、时间要求不高的场景。
一个进程写入文件,另一个进程读取文件,文件内容可以多个进程共享,使用文件锁用于防止文件读写冲突。
反问
编程题有哪些思路?
部门技术栈
客户端开发主要是 Android 和 IOS,主要是Java、Swift 和 Object-C.