字节跳动后端一面解析：疯狂拷打计算机基础

嗨～我是可拟雀，一个后端开发工程师，毕业于某985大学，目前供职于bat某大厂核心部门后端。每天分享最新面经答案，希望在大环境不好的当下能帮到你，让你多积累面试经验。免费分享个人学习2个月速通大厂路线和面经解析合集，需要请私信

1.问项目

2.Redis数据类型相关：sortedSet的实现；五种数据类型？

答：String（字符串）：这是Redis最基本的数据类型。你可以将String视为与Memcached相似的类型，每个key对应一个value。String类型是二进制安全的，可以存储字符串、整数或浮点数，其值的最大存储限制为512MB。String类型支持的操作包括设置值、获取值、增减操作等。

Hash（哈希）：Redis的Hash是一个键值对集合，其中每个键都对应一个值。Hash实际上是一个string类型的field和value的映射表，因此它特别适合用于存储对象。

List（列表）：Redis的List是简单的字符串列表，它按照插入顺序进行排序。你可以在其头部或尾部添加新的元素。

除了上述三种基本数据类型外，Redis还支持一些更高级的数据类型：

Set（集合）：Set是string类型元素的集合，并且集合中的元素是唯一的，没有重复值。

Zset（Sorted Set：有序集合）：这是string类型元素的集合，并且每个元素都会关联一个double类型的分数。Redis正是通过分数来为集合中的元素进行从小到大的排序。Zset的成员是唯一的，但分数可以重复。

此外，Redis还有一些特殊的数据类型或功能：

Bitmaps（位图）：这是一种位数组，其中每个二进制位代表一个布尔值。

HyperLogLog：这是一种基数算法，用于估计一个集合中不同元素的数量。

Geospatial（地理位置）：这是一种地理位置数据类型，用于存储地理位置信息和坐标。

Streams（流）：这是一种持久化的消息队列，用于存储和处理消息。

Modules（模块）：Redis支持动态加载模块，通过加载模块可以扩展Redis的功能，如添加新的数据类型、命令等。

关于 Sorted Set（有序集合），它实际上是 String 类型元素的集合，并且每个元素都会关联一个 Double 类型的分数。Redis 正是通过分数来为集合中的元素从小到大进行从小到大的排序。Sorted Set 的成员是唯一的，但分数(score)可以重复。

Sorted Set 的底层实现主要是利用了两种数据结构：跳表(Skip List)和哈希表(Hash)。其中哈希表是为了快速定位某个元素的分数，而跳表则是为了快速获取排序后的元素列表。

跳表(Skip List)：

跳表是一种可以随机化的数据结构，实质就是一种可以进行二分查找的有序链表。在链表的基础上，增加了多级索引，以提高查找的速度。跳表在 Redis 中主要用于实现 Sorted Set 数据类型，以支持快速的插入、删除和查找操作。

跳表的主要特点包括：

搜索效率高：跳表在查找、插入和删除操作上的时间复杂度都是 O(log n)，与平衡树相当。

实现简单：跳表相对于平衡树来说，实现起来要简单得多，而且其性能也不会因为数据的变化而发生退化。

空间复杂度低：相对于其他平衡树，跳表的空间复杂度较低。

在 Redis 中，Sorted Set 的实现结合了跳表和哈希表，其中哈希表用于存储每个元素和对应分数的映射关系，而跳表则用于存储元素的排序信息。这种组合方式使得 Redis 的 Sorted Set 在保证数据有序性的同时，也提供了高效的查找、插入和删除操作。

3.HashMap为什么不安全，如何改进，以及concurrentHashMap？

答：HashMap在Java中是一个非线程安全的哈希表实现。它不安全的主要原因在于其内部状态在并发修改时可能会变得不一致。具体来说，当多个线程同时对HashMap进行读写操作时，可能会出现以下问题：

数据不一致：在HashMap的扩容或重新哈希过程中，如果多个线程同时修改HashMap的状态，可能会导致元素丢失或数据错位。

死循环：在HashMap的某些实现版本中（例如JDK 1.7及之前），如果并发修改导致了HashMap的结构发生变化（如扩容），那么在迭代HashMap时可能会出现死循环。

为了改进HashMap的线程安全性，可以采取以下措施：

外部同步：通过在访问HashMap的代码块外部添加同步锁，可以确保同一时间只有一个线程能够修改HashMap。这种方法简单但效率较低，因为它会阻塞其他线程的访问，即使它们只是进行读操作。

Map<K, V> map = Collections.synchronizedMap(new HashMap<K, V>());

// 或者使用synchronized块

synchronized(map) {

    // 访问map的代码

}

使用线程安全的替代方案：Java提供了Hashtable和Collections.synchronizedMap等线程安全的Map实现，但这些实现通常性能较低，因为它们在每次访问时都需要获取锁。

更好的解决方案是使用ConcurrentHashMap，它是Java并发包（java.util.concurrent）中的一个线程安全的哈希表实现。ConcurrentHashMap通过分段锁（在JDK 1.7及之前）或CAS（Compare-and-Swap）操作和同步控制（在JDK 1.8及之后）来实现高效的并发读写。它允许多个线程同时读写ConcurrentHashMap的不同部分，从而大大提高了并发性能。

ConcurrentHashMap的主要改进点包括：

分段锁（在JDK 1.7及之前）：将HashMap内部划分为多个段（Segment），每个段都有自己的锁。这样，当多个线程访问不同的段时，它们可以并行执行，而不会产生锁竞争。

CAS操作和同步控制（在JDK 1.8及之后）：利用无锁算法和CAS操作来减少锁的使用，同时保持了线程安全性。在扩容或重新哈希时，采用了一种更加复杂的算法来确保并发修改的正确性。

4.TCP报文的结构?

答：

TCP报文主要由两部分组成：TCP报头和TCP数据。TCP报文是TCP传输的数据单元。以下是TCP报文结构的一些关键组件：

源端口（Source Port）：16 bits，标识数据发送端的应用层程序。源端口和IP层解析出来的IP地址标识报文的发送地，同时也确定了报文的返回地址。

目的端口（Destination Port）：16 bits，标识数据接收方的应用层程序。这个对端端口号表明了该数据报是发送给接收方计算机的具体的一个应用程序。

序列号（Sequence Number）：32 bits，标识数据发送方所发出数据的编号。在TCP传送的流中，每一个字节都有一个序号，这个序号确保了TCP传输的有序性。例如，一个报文段的序号为300，此报文段数据部分共有100字节，则下一个报文段的序号为400。

确认序号（ACK）：指明下一个期待收到的字节序号，表明该序号之前的所有数据已经正确无误地收到。确认号只有当ACK标志为1时才有效。

报头长度（Header Length）：4 bits，标识TCP报头的长度，单位是4字节。TCP报文的固定长度与IP报文一致，都是20字节，但TCP的报头长度范围为20~60字节。

此外，TCP报文还可能包含其他字段，如窗口大小（一个16比特位的字段）等，这些字段有助于TCP实现其可靠传输和流量控制的功能。

总的来说，TCP报文结构的设计使得TCP协议能够可靠地、有序地传输数据，同时支持各种网络环境和应用需求。

5.输入URL会发生什么？

答：从后端开发工程师的角度来看，有以下的过程：

DNS解析：

首先，浏览器会向DNS服务器发送请求，将输入的URL解析为对应的IP地址。这是因为网络中的设备通常是通过IP地址进行通信的，而URL中的域名则是一种更便于人类记忆和使用的形式。

建立TCP连接：

一旦获得了IP地址，浏览器就会尝试与服务器建立TCP连接。TCP是一种面向连接的、可靠的、基于字节流的传输层通信协议。通过三次握手过程，浏览器和服务器之间建立起一个可靠的通信通道。

发送HTTP请求：

在TCP连接建立后，浏览器会构造一个HTTP请求报文，并通过TCP连接发送给服务器。这个HTTP请求报文包含了请求的方法（如GET、POST等）、请求的URL路径、请求头（包含了各种元数据，如浏览器类型、用户代理等）以及请求体（对于POST请求来说）。

服务器接收并处理请求：

服务器在接收到HTTP请求后，会由其后端应用（通常是Web服务器软件，如Nginx、Apache等）来处理这个请求。后端应用会根据请求的URL路径来查找对应的处理程序或资源。这通常涉及到路由处理，即根据URL的不同部分来调用不同的代码或模块。

执行后端逻辑：

一旦找到了对应的处理程序，后端应用就会执行相应的逻辑代码。这可能包括从数据库中查询数据、执行计算任务、调用其他服务或API等。这些操作可能会根据请求的具体内容而有所不同。

构造HTTP响应：

后端应用在处理完请求后，会构造一个HTTP响应报文。这个响应报文包含了状态码（表示请求的处理结果，如200表示成功，404表示未找到等）、响应头（包含了各种元数据，如内容类型、缓存控制等）以及响应体（包含了实际返回给浏览器的数据，如HTML页面、JSON数据等）。

发送HTTP响应并关闭连接：

后端应用通过TCP连接将HTTP响应报文发送回浏览器。发送完成后，TCP连接可能会被关闭（对于短连接来说），或者保持打开状态以便后续的请求（对于长连接或HTTP/2的流连接来说）。

浏览器解析并渲染响应：

浏览器在接收到HTTP响应后，会解析响应报文中的HTML、CSS和JavaScript等内容，并根据这些内容来渲染页面。如果响应中包含了图片、视频等其他资源，浏览器还会发送额外的HTTP请求来获取这些资源。

在整个过程中，后端开发工程师主要负责编写和维护后端应用代码，确保它能够正确地处理各种HTTP请求并返回合适的响应。同时，他们还需要关注性能优化、安全性、可扩展性等方面的问题，以确保后端系统的稳定性和高效性。

6.TCP为什么要三次握手？

答：

确认通信双方的可达性：客户端和服务器可以通过握手过程验证对方的IP地址和端口是否可达，从而确保双方之间的网络连接正常。

确认对方的接收能力：通过握手过程，客户端和服务器可以交换彼此的初始序列号。这样，每个数据包都可以按序发送和接收。这种确认和同步机制保证了数据的可靠传输。

避免过期的连接请求：在网络状况复杂或较差的情况下，发送方可能会连续发送多次建立连接的请求。三次握手的过程可以防止过期的连接请求被错误地接受。只有在握手过程中完成了三次确认，才能建立有效的连接。

具体来说，三次握手的过程如下：

SYN：客户端发送一个SYN包到服务器，并进入SYN_SEND状态，等待服务器确认。

SYN+ACK：服务器收到SYN包，必须确认客户的SYN（ACK=客户序列号+1），同时自己也发送一个SYN包，即SYN+ACK包，此时服务器进入SYN_RECV状态。

ACK：客户端收到服务器的SYN＋ACK包，向服务器发送确认包ACK(ACK=服务器序列号+1），此包发送完毕，客户端和服务器进入ESTABLISHED状态，完成三次握手。

完成三次握手后，客户端与服务器开始传送数据。这样，TCP就建立了一个可靠的连接，确保了数据的可靠传输，避免了不必要的数据丢失和错误。

7.操作系统缺页中断，页面置换算法有哪些？

答：操作系统缺页中断：

缺页中断是一种特殊的中断，当程序试图访问已映射在虚拟地址空间中，但是并未加载到物理内存中的一个分页时，由硬件产生的中断。简单来说，当要访问的页面不在主存（物理内存）中，操作系统需要将其调入主存后再进行访问，这一过程就称为缺页中断。

页面置换算法：

在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则会产生缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存中选择一个页面将其移出内存，以便为即将调入的页面让出空间。用来选择淘汰哪一页的规则就叫做页面置换算法。

页面置换算法有多种，其中一些常见的包括：

最佳置换算法（OPT）：

原理：每次选择淘汰的页面将是以后不再使用，或者在最长时间内不再被访问的页面。

问题：实际上，只有在进程的执行过程中才可以知道接下来会访问的页面，操作系统对接下来要访问的页面是不能进行预判的，因此该算法是不能被实现的。但最佳页面置换算法可以用于对可实现算法的性能进行衡量比较。

先进先出置换算法（FIFO）：

原理：每次选择淘汰的页面是最早进入内存的页面。

实现：把调入内存的页面按照先后顺序放入队列，当需要进行换出页面时，将队头页面换出。

除了上述两种算法外，还有最近最少使用（LRU）置换算法、时钟（CLOCK）置换算法等多种算法，它们各自有不同的实现原理和应用场景。选择哪种页面置换算法取决于具体的应用需求和系统环境。

8.手撕二叉搜索树的删除。较为简单的题目。

总的来说，面试很注重基础知识的考察。

原文传送门

免费专栏地址，每日更新，欢迎订阅