字节跳动后端暑期实习最新面经解析：回归基础，方为大道

嗨～我是可拟雀，一个后端开发工程师，毕业于某985大学，目前供职于bat某大厂核心部门后端。每天分享最新面经答案，希望在大环境不好的当下能帮到你，让你多积累面试经验。******************************

一面 1h
1. 布隆过滤器原理
答：布隆过滤器（Bloom Filter）是一种空间效率极高的概率型数据结构，它利用位数组和一系列哈希函数，以较小的空间代价和较大的概率来检测一个元素是否属于某个集合。

其核心原理如下：

位数组：布隆过滤器使用一个位数组作为底层存储结构。每个位都可以是0或1，表示该位置是否被“占用”。

哈希函数：布隆过滤器使用多个独立的哈希函数。当向过滤器中添加一个元素时，这些哈希函数会计算出多个索引值，并将位数组中对应的位设置为1。

添加元素：对于每个待添加的元素，布隆过滤器会利用所有的哈希函数计算出多个索引值，并将这些索引对应的位数组中的位置设为1。

查询元素：为了判断一个元素是否存在于集合中，布隆过滤器同样会利用哈希函数计算出多个索引值，并检查这些索引对应的位是否都为1。如果所有位都为1，那么过滤器认为该元素可能存在（但可能存在误报，即实际上元素并不在集合中）。如果有任何一位为0，那么过滤器可以确定该元素一定不存在。

需要注意的是，布隆过滤器存在以下特点：

误报率：由于哈希冲突的存在，布隆过滤器可能会错误地认为某个不在集合中的元素是存在的，这称为误报或假阳性。但布隆过滤器不会误报不存在的元素为存在，即不存在假阴性。误报率可以通过增加位数组的大小或使用更多的哈希函数来降低。

不支持删除：布隆过滤器不支持从集合中删除元素。一旦一个元素被添加到过滤器中，其对应的位就会被设置为1，并且无法再被撤销。尝试删除元素可能会导致其他元素的误报率增加。

尽管存在这些限制，但布隆过滤器因其高效的空间利用率和快速的查询速度，在许多场景中都得到了广泛应用，如缓存穿透、垃圾邮件过滤、网页黑名单系统等。

2. 回表、覆盖索引？
答：
回表：

回表是数据库中一种查询优化方式，通常出现在使用非聚集索引进行查询的场景中。非聚集索引与数据行分开存储，它包含一个指向数据行的指针。当使用非聚集索引进行查询时，数据库引擎首先通过该索引找到匹配的行，然后使用行指针到表中查找相应的行数据。这个额外的查找操作就被称为“回表”。回表操作的代价较高，因为它需要额外的IO操作，增加了查询的开销，特别是在大型数据表中这种开销更为明显。

为了优化查询性能，可以考虑将经常需要查询的列包含在非聚集索引中，这样数据库引擎在索引中就能找到所需的所有信息，无需再进行回表操作。但需要注意的是，回表操作并不适用于使用聚集索引的查询，因为聚集索引包含了整个表的数据，查询时无需再回到表中查找数据。

覆盖索引：

覆盖索引是一个包含了查询语句所需的所有数据的索引。它不仅能够提供索引的搜索能力，还可以完全覆盖查询需求，避免了回表操作。在覆盖索引中，索引本身包含了查询语句中涉及的所有字段，因此数据库引擎可以仅通过索引就获取到所需的所有信息，无需再额外去查找数据行。这减少了I/O消耗，提高了查询效率。

覆盖索引是数据库性能优化的一个重要策略，但在使用过程中需要根据具体场景权衡选择，以达到更好的性能优化效果。

3. 无序数组的中位数？
4. 差分题目？
5. UDP 实现和 TCP 实现？
答：

连接性：UDP是无连接的协议，它不需要在传输数据之前建立连接。发送端只需将数据封装在UDP数据报中，然后发送给接收端。与此不同，TCP是面向连接的协议，在发送数据之前，需要先通过三次握手协议建立连接，确保数据传输的正确性。

可靠性：TCP协议保证数据传输的可靠性，它通过一系列机制（如确认应答、超时重传等）确保数据能够准确、有序地到达接收端。而UDP协议则不保证数据的可靠性，它只负责将数据发送出去，不关注数据是否到达接收端，也不保证数据的顺序性。

传输效率：UDP协议通常具有更高的传输效率，因为它不需要进行连接建立和断开等额外操作，且没有复杂的流量控制和拥塞控制机制。TCP协议虽然保证了数据的可靠性，但也因此引入了更多的开销，导致传输效率相对较低。

报文大小：UDP的报文首部只有8个字节大小，而TCP的报文首部有20个字节。这也在一定程度上影响了两种协议的传输效率和应用场景。

应用场景：由于UDP协议的高效性和无连接特性，它常被用于实时性要求较高、对数据传输可靠性要求不高的场景，如视频流传输、实时游戏等。而TCP协议则更适用于需要确保数据传输可靠性和顺序性的场景，如文件传输、网页浏览等。

6. LRU 和 LFU 的区别和实现
答：

LRU（Least Recently Used）和LFU（Least Frequently Used）是两种常见的缓存置换算法，它们的主要区别在于评估缓存对象被替换的标准不同。

LRU算法主要基于时间局部性原理，即如果一个数据在最近一段时间被访问过，那么将来被访问的可能性也很大。因此，LRU算法会淘汰最长时间未被使用的页面或数据。在LRU中，通常会使用一个双向链表来维护缓存数据的使用顺序，链表的头部表示最新使用的数据，尾部表示最旧的数据。每当有数据被访问时，该数据就会被移到链表的头部。当缓存已满且需要插入新数据时，LRU会从链表尾部选择最久未被使用的数据进行替换。

而LFU算法则主要基于频率局部性原理，即如果一个数据在最近一段时间被访问的次数很多，那么将来被访问的可能性也很大。因此，LFU算法会淘汰一定时期内被访问次数最少的页面或数据。LFU的每个数据块都有一个引用计数，当数据被访问时，其引用计数就会增加。所有数据块按照引用计数排序，具有相同引用计数的数据块则按照时间排序。当需要淘汰数据时，LFU会将已经排序的列表最后的数据块删除。

在实现上，LRU和LFU都需要维护一个数据结构来跟踪缓存中每个数据的使用情况。对于LRU，这通常是一个双向链表，而对于LFU，则需要一个能够记录引用计数的数据结构，如哈希表或优先队列。这两种算法在实现时都需要考虑如何高效地插入、查找和删除数据，以及如何在缓存满时选择合适的数据进行替换。

7. 虚拟内存？

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

虚拟内存的工作原理是将进程使用的内存分为多个页面（通常为4KB或8KB），每个页面都有一个唯一的虚拟地址。当进程需要访问某个页面时，操作系统会检查该页面是否已经在物理内存中，如果已经在内存中，则直接访问该页面；如果不在内存中，则操作系统会将该页面从磁盘上的虚拟内存中读取到内存中，并将其映射到进程的虚拟地址空间中。

虚拟内存不仅仅是简单地存放进程的一部分并且与内存可以互相交换，它还涉及到许多复杂的机制和算法，例如页面置换算法、页面预读技术、页面共享技术等，以提高系统的性能和效率。同时，虚拟内存也是操作系统中非常重要的一部分，它为多任务操作系统的正常运行提供了必要的支持。

8.os分页算法？

答：

OS分页算法是操作系统中用于管理内存的一种重要机制。分页的基本方法是将地址空间等分成某一个固定大小的页，每一页大小由硬件或操作系统来决定。进程的逻辑地址空间被分成若干个大小相等的页面，而物理内存空间也被分成与页大小相等的物理块或页框。当为进程分配内存时，以块为单位将进程中的页面装入物理内存中的块。

在分页机制下，物理内存空间是有限的，当所有物理页面都被占用时，操作系统需要选择某些页面进行置换，以便为新的页面腾出空间。这就涉及到了页面置换算法。

常见的页面置换算法包括FIFO（先进先出）算法、最佳置换算法和LRU（最近最少使用）算法等。

FIFO算法按照页面调入内存的先后顺序进行置换，最先调入内存的页面先被替换出去。

最佳置换算法选择在未来最长时间内不再被访问的页面进行替换。

LRU算法则选择最近最少使用的页面进行替换。

9. 函数调用与栈
答：
函数调用与栈的关系主要体现在函数调用的执行过程中。栈（Stack）是一种数据结构，它遵循后进先出（LIFO，Last In First Out）的原则，即最后进入栈的元素将最先被移除。在程序执行过程中，函数调用栈（或称为执行栈）用于存储函数调用时的相关信息，以确保函数能够正确地执行和返回。

当一个函数被调用时，以下操作通常会在函数调用栈上发生：

压栈（Push）：

函数调用者的下一条指令地址（即返回地址）被压入栈中。这样，当函数执行完毕后，程序可以返回到正确的位置继续执行。

函数的参数（如果有的话）也会被压入栈中，供函数内部使用。

函数的局部变量和运行时所需的其他信息也可能在栈上分配空间。

函数执行：

函数在栈顶开始执行。它可以访问其参数（从栈中读取）和局部变量（也在栈上分配）。

函数执行期间，可能会进行更多的函数调用，这些新的调用同样会压入栈中。

返回（Return）：

当函数执行完毕并准备返回时，它会从栈顶弹出，返回到之前保存的返回地址继续执行。

在返回过程中，函数可能返回一个值，这个值通常会被放置在某个特定的寄存器中，或者在某些情况下也可能被压入栈中，等待调用者读取。

清理栈：