字节跳动服务端开发秋招一面

2024-11-12

自我介绍

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

算法题

给定二叉树中指定节点和一个整数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.