自我介绍

毕业院校、项目经历、实习工作经历，简单介绍掌握的技能。

算法题

给定二叉树中指定节点和一个整数k，寻找距离指定节点距离为k的所有节点：

要求：时间复杂度 $O(n)$, 空间复杂度 $O(n)$

思路：如果给定节点为父结点，寻找距离其为 k 的节点可以直接用递归去查找，难点在于如何寻找给定节点父结点和兄弟节点中距离其为k的节点

问答环节

虚拟内存了解吗？使用虚拟内存有什么好处？

虚拟内存是计算机系统内存管理的一种技术。它使得应用程序认为它拥有连续的可用的内存，而实际上，它通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换。

1. 扩展内存容量：虚拟内存通过将部分数据存储在磁盘上（如HDD或SSD），扩展了物理内存（RAM）的容量。即使计算机的物理内存不足，也可以运行需要较大内存的应用程序，从而避免因内存不足导致程序无法运行的问题。
2. 多任务处理：虚拟内存允许多个程序共享计算机的物理内存。在实际使用中，每个程序认为自己有一个完整且独立的内存空间，而虚拟内存负责将这些内存请求映射到实际的物理内存或磁盘中。这种机制让操作系统可以运行多个程序，而不受物理内存容量的严格限制。
3. 内存隔离和安全性：虚拟内存为每个进程提供独立的虚拟地址空间，从而隔离进程间的内存访问。一个程序无法直接访问另一个程序的内存内容，防止程序之间的相互干扰，增强了系统的稳定性和安全性。
4. 灵活的内存管理：虚拟内存通过分页或分段机制，允许操作系统以更细粒度管理内存。内存页面可以按需加载到物理内存中，这种方式称为按需分页，提高了内存利用效率，避免了内存的浪费。
5. 更大的地址空间：通过虚拟内存，应用程序可以使用一个比物理内存更大的地址空间。这对于运行大型程序（如科学计算、数据库等）非常重要，因为程序可以利用虚拟内存进行更大规模的数据处理。
6. 简化开发工作：虚拟内存为程序开发提供了一种抽象，使程序员可以不用关心物理内存的具体布局和容量。程序员只需关注虚拟地址空间，而操作系统负责将虚拟地址映射到物理内存或磁盘位置。

计算机内存管理方式有哪几种？各自优缺点？

1. 页式内存管理

   概念：页式内存管理将内存分为固定大小的页面 (一般是4KB)，将进程的虚拟地址空间映射到物理内存的相应页框。

   优点：

   • 内存利用率高，内存以页为单位分配，消除了外部碎片；
   • 便于内存共享，多个进程共享同一页面，提高效率；
   • 按需加载，支持按需分页，只有在需要时才将页面加载至内存；
   • 实现方式较为直观，支持随机访问。

   缺点：

   • 由于页大小固定，最后一页未使用的部分可能会造成浪费，产生内部碎片；
   • 地址转换开销大，每次访问内存都需要通过页表进行地址转换，增加内存访问的时间；
   • 当进程虚拟地址空间较大的情况下，页表会占用较多的内存资源。

2. 段式内存管理

   概念：段式内存管理将程序划分为逻辑意义上的段，每个段具有不同的大小和属性，如代码段、数据段、堆栈段等。

   优点：

   • 逻辑结构清晰，每个段对应程序的逻辑模块，便于编程和管理；
   • 灵活性高，不同段可以有不同的大小，能更好适应程序的需求；
   • 便于共享和保护，可以对不同的段设置不同的权限，支持段的共享和保护；
   • 每个段的大小是按需动态分配的，减少了内部碎片的产生。

   缺点：

   • 内存分配和回收过程中，会产生外部碎片；
   • 地址转换复杂，短时管理需要段表进行地址转换，增加了复杂性；
   • 由于段的大小不固定，分配和回收内存可能需要更多时间。

3. 段页式内存管理

   概念：结合页式和段式管理的特点，首先将虚拟地址空间划分为若干段，每个段再进一步划分为固定大小的页。

   优点：结合了页式和段式的优点，支持段的逻辑划分，也支持按页分配内存。

   缺点：实现复杂，需要同时维护段表和页表，并且地址转换开销更大，内存访问需要两级地址转换，降低了访问速度。

选一种你熟悉的内存管理方式，简述其寻址过程？

这里我选的是页式内存管理。

1. 分解虚拟地址为页号（PN）和页内偏移量（PO）；

2. 查找页表，找到对应的物理页框号（FN）；

3. 检查页表项有效性，处理缺页情况；

4. 组合页框号和页内偏移量，计算物理地址；

5. 访问物理内存。

可以使用快表（TLB）优化地址转换过程。

TCP和UDP的区别以及各自的适用场景

TCP与UDP的基本区别，：

1. 基于有连接和无连接；
2. 系统占用资源多少；
3. UDP程序结构较为简单；
4. TCP面向字节流，UDP面向数据报；
5. TCP保证数据正确性，UDP可能丢包；
6. TCP保证数据顺序，UDP不保证。

UDP应用场景：实时场景，RIP路由表更新，DNS、SNMP等都是运行在UDP之上。

1. 面向数据报方式；
2. 网络数据大多为短消息；
3. 拥有大量client；
4. 对数据安全性没有特殊要求；
5. 网络负担重，但是对响应速度要求高。

总体来说，TCP与UDP的区别如下：

1. TCP面向连接（如打电话要先拨号建立连接）;UDP是无连接的，即发送数据之前不需要建立连接。
2. TCP提供可靠的服务。也就是说，通过TCP连接传送的数据，无差错，不丢失，不重复，且按序到达;UDP尽最大努力交付，即不保证可靠交付。
3. TCP面向字节流，实际上是TCP把数据看成一连串无结构的字节流;UDP是面向报文的。UDP没有拥塞控制，因此网络出现拥塞不会使源主机的发送速率降低（对实时应用很有用，如IP电话，实时视频会议等）。
4. 每一条TCP连接只能是点到点的;UDP支持一对一，一对多，多对一和多对多的交互通信。
5. TCP首部开销20字节;UDP的首部开销小，只有8个字节。
6. TCP的逻辑通信信道是全双工的可靠信道，UDP则是不可靠信道。

ps: UDP一般不说全双工、半双工，因为这些说法都是指面向连接才有的说法，而对于UDP这种不建立连接的传输协议，没有明确的全双工、半双工的说法。

TCP适用场景：

TCP 如何判断是否发生了拥塞？拥塞控制?

TCP拥塞判断机制：

1. 超时重传，超时未收到ACK；
2. 重复ACK，连续收到三个重复的ACK；
3. RTT增大，网络延迟显著上升；
4. 丢包率升高，丢包现象频繁发生；
5. ECN显式拥塞控制，通过网络设备显式告知拥塞。

TCP的四种拥塞控制算法：

1. 慢启动

   发送端在最初建立连接后，拥塞窗口值为1，接收方收到该报文后，将拥塞窗口的值变为2，每个传输轮次依次增加（指数方式增加），直至发生拥塞。

2. 拥塞避免

   每个传输轮次线性增加拥塞窗口值。

3. 快重传

   接收方收到未按需到达的报文段后，要求发送方重传之前的报文段，而不是等超时重传计数器超时再重传。

4. 快恢复

   发送方知道丢失了个别字段的报文段后，不启慢启动算法，执行快恢复算法，将拥塞窗口值修改为当前窗口的一般，开始执行拥塞避免算法。

三次握手和四次挥手是为了什么？

三次握手必要性：

1. 确保接收方/发送方通信能力正常；
2. 避免旧连接请求的干扰；
3. 同步初始序列号；
4. 确保双方对连接状态的理解一致。

四次握手必要性：

1. TCP是全双工通信协议，双方发送和接收的通道是独立的，因此连接的断开也需要分别关闭发送和接收通道
 	2. 确保全双工通信的每一方向都能独立关闭通道；
 	3. 保障数据完整传输，不丢失数据；
 	4. 避免资源泄露，确保连接彻底释放；
 	5. 增强协议的可靠性和健壮性。

进程间通信方式有哪几种？具体说说实现方式？

1. 匿名管道：只能在具有亲缘关系（父子进程）的进程间通信，单向通信。

   一个进程创建管道，使用 pipe 系统调用，生成一对文件描述符，一个文件描述符用于写入，另一个用于读取，数据以FIFO方式传递。

2. 有名管道：不要求进程有亲缘关系，支持双向通信。

   使用 mkfifo 创建一个命名管道文件，各个进程通过打开相同的命名管道文件来实现通信，数据在内核中传递，类似匿名管道。

3. 信号量：用于进程间同步，不能直接传输数据，适合解决共享资源的互斥和同步问题。

4. 消息队列：允许多个进程以消息为单位进行通信，消息具有标识和优先级。

   创建一个消息队列 msgget() ，进程通过消息队列向其他进程发送消息 mssgsnd()，接收进程通过消息队列接收消息 msgrcv(), 内核负责管理消息队列，确保消息按优先级或FIFO方式传递。

5. 共享内存：多个进程直接共享一块物理内存，是最快的IPC方式。

   创建或获取共享内存 shmget()，将共享内存附加到进程地址空间 shmat()，进程通过指针直接对共享内存进行读写。

6. 套接字：创建套接字socket进行你通信，支持不同主机或同一主机上的进程通信，支持TCP和UDP。

   创建套接字socket，通过 bond() 绑定地址、listen()监听 、accept() 接收连接实现服务端通信，客户端通过 connect() 连接服务端，双方通过 send() 和 recv() 进行数据交换。

7. 文件：通过文件系统进行间接通信，适合数据量大、时间要求不高的场景。

一个进程写入文件，另一个进程读取文件，文件内容可以多个进程共享，使用文件锁用于防止文件读写冲突。

反问

编程题有哪些思路？

部门技术栈

客户端开发主要是 Android 和 IOS，主要是Java、Swift 和 Object-C.