攒人品系列--百度C++一面

大家好，我是阿Q。

经常关注我的小伙伴可能会发现我昨天发了一篇用ACM解*客题，但是后来又不见这个文章了。（细心的同学可能会发现我给大家分享的面经的手撕算法都是ACM模式的。）

我为什么会删呢，，今天上午想了一下，等我把这些题目写的差不多了就放到知识星球上。

并不是每个人都能看到，一切都在筹备中，所以说该怎么做你懂，这些东西对你来说一定是有益的。

ps：小伙伴们，微信公众号又改版了，如果没有星标，公号文章就会渐渐沉底，我们可能长久失联。给阿Q一个星标，让我们每天都能见面。

今天攒人品系列的百度C++一面，分享给大家~

来源：

https://www.nowcoder.com/feed/main/detail/5e3e69f409eb4264a3f6e76ff489abfe

自我介绍+闲聊了一会，为什么选择C++编程 

1. 定义和用途：TCP是一种基于连接的、可靠的传输层协议，用于在网络上传输数据。它提供了一种点对点的、面向连接的通信方式，确保数据的可靠性、顺序传输和错误检测与恢复。TCP是互联网协议套件中的一部分，用于可靠地传输数据，例如网页、电子邮件、文件传输等。
2. 工作原理：TCP通过建立连接、数据传输、确认和错误处理等机制来实现可靠的数据传输。它使用三次握手来建立连接，通过序列号和确认号来跟踪和确认数据的传输顺序。如果数据包丢失或损坏，TCP会自动重传，以确保数据的完整性和可靠性。

1. 定义和用途：RPC是一种通信协议和编程模型，用于在不同的计算机上执行远程过程调用。它允许一个程序在远程计算机上请求另一个程序执行特定的函数或过程，就像本地函数调用一样。RPC通常用于分布式系统中，使不同的计算机能够协作完成任务。
2. 工作原理：RPC允许一个程序（客户端）调用另一个程序（服务器）上的函数，而不必了解底层的网络通信细节。当客户端发起RPC请求时，它会将请求参数打包并发送到服务器，服务器执行相应的函数，然后将结果返回给客户端。RPC框架负责处理通信、序列化和反序列化等底层细节。

1. 层次不同：TCP是一种传输层协议，主要负责数据传输和可靠性。RPC是一种应用层协议和编程模型，用于实现远程过程调用。
2. 用途不同：TCP用于传输数据，而RPC用于实现分布式系统中的远程通信。
3. 抽象程度不同：TCP是一种低层次的协议，涉及网络通信的细节。RPC提供了更高层次的抽象，使程序能够像调用本地函数一样调用远程函数。
4. 实现方式不同：TCP是一个通用的协议，可以用于各种应用。RPC通常是基于特定的编程框架或库实现的，例如，gRPC、Apache Thrift、CORBA等。

1. 协议设计目标不同：
1. HTTP协议：HTTP是一种通用的协议，设计用于传输超文本和数据。它是一种文档传输协议，通常用于请求和传输HTML页面、图像、CSS、JavaScript等资源。HTTP的主要设计目标是使文档在不同的计算机和浏览器之间能够共享和呈现。
2. RPC协议：RPC协议专门设计用于远程过程调用，它的主要目标是允许应用程序在不同的计算机上调用远程函数或方法，实现分布式计算和通信。
2. 数据传输方式不同：
1. HTTP协议：HTTP是一种请求-响应协议，通常用于请求某种资源（如网页或文件）并接收相应的响应。HTTP的通信模式是基于文档交换的，它使用HTTP请求方法（GET、POST等）来传递数据。
2. RPC协议：RPC是一种远程调用协议，它允许客户端应用程序像调用本地函数一样调用远程函数。RPC通常用于传递参数和调用远程函数，并返回结果。
3. 应用场景不同：
1. HTTP协议：HTTP主要用于构建Web应用，浏览器通过HTTP与Web服务器通信，请求和获取Web资源。它通常用于在浏览器和Web服务器之间传输HTML、CSS、JavaScript等资源。
2. RPC协议：RPC通常用于构建分布式应用程序，它使不同的计算机上的应用程序能够协同工作。RPC允许应用程序之间进行函数调用，以实现更复杂的分布式计算任务。
4. 性能和效率考虑：
1. HTTP协议：HTTP协议通常使用文本（如JSON、XML）来表示数据，这增加了数据的传输开销。对于某些场景，特别是在大规模的分布式系统中，HTTP的性能和效率可能不够高。
2. RPC协议：RPC协议通常使用二进制格式来传输数据，这减少了数据传输的开销，提高了性能和效率。RPC框架通常还提供了更多的功能，如参数序列化和反序列化、错误处理等。

1. 通用性：HTTP是一种通用的应用层协议，几乎所有计算机和操作系统都支持它。因此，使用HTTP作为RPC的传输协议可以实现跨平台和跨语言的通信，使不同的系统能够相互通信。
2. 防火墙友好：HTTP通常使用标准的HTTP端口（如80和443），这使得HTTP RPC能够穿透大多数防火墙和代理服务器，从而更容易地进行跨网络通信。
3. 可扩展性：HTTP支持各种HTTP方法（GET、POST、PUT、DELETE等），可以使用不同的HTTP方法来表示不同的RPC操作，使RPC框架具有灵活的扩展性。
4. 安全性：HTTP可以与SSL/TLS一起使用，提供安全的加密通信，保护数据的机密性和完整性。这对于处理敏感信息的RPC通信非常重要。
5. 已有基础设施：大多数现代编程语言和开发框架都提供了HTTP客户端和服务器库，这些库可以轻松地用于构建HTTP RPC的客户端和服务器。
6. 适应性：HTTP是一种文本协议，但它可以与各种数据格式（如JSON、XML、二进制等）一起使用，因此可以根据需要选择适当的数据格式进行RPC通信。
7. RESTful风格：使用HTTP作为RPC的传输协议还可以采用RESTful风格的设计，将RPC操作映射到HTTP的资源和方法上，使RPC接口更具可理解性和可维护性。

1. 客户端请求锁：当客户端需要获取锁时，它会在锁节点下创建一个临时顺序子节点（例如，/locks/lock-0001
   ）。子节点的名称是按照一定规则生成的，通常包括客户端的标识符。
2. 获取当前锁的竞争者：客户端获取锁的过程中，首先获取锁节点下的所有子节点，并按照顺序对它们进行排序，以确定客户端的锁请求的顺序。
3. 检查是否获取锁：客户端检查自己创建的子节点是否是当前最小的子节点。如果是最小的子节点，表示客户端成功获取了锁，可以执行其需要的操作。否则，客户端等待，直到它的子节点成为最小的。
4. 释放锁：当客户端完成了对共享资源的操作后，它删除自己创建的子节点，这会触发ZooKeeper通知其他等待锁的客户端。这些客户端会重新检查自己的子节点是否成为最小的，以决定是否获取锁。

1. 基于数据库：可以使用关系型数据库（如MySQL或PostgreSQL）来实现分布式锁。具体做法是在数据库中创建一个锁表，每个客户端尝试插入一条记录作为锁，如果插入成功则表示获取了锁，否则等待。释放锁时，客户端删除相应的记录。数据库提供了事务支持，可以确保锁的一致性。但是这种方法的性能可能较差，因为它涉及到数据库操作。
2. 基于缓存：使用分布式缓存系统（如Redis或Memcached）来实现分布式锁。在缓存中设置一个键值对，键表示锁的名字，值可以是唯一的标识符。客户端尝试设置这个键值对，如果设置成功则获取了锁，否则等待。释放锁时，客户端删除键值对。缓存系统通常具有高性能和低延迟，适合实现分布式锁。
3. 基于分布式协调服务：除了ZooKeeper，还可以使用其他分布式协调服务来实现分布式锁，如Etcd或Consul。这些工具提供了类似ZooKeeper的分布式锁机制，允许客户端协调并竞争获取锁。
4. 基于文件系统：使用分布式文件系统（如HDFS）或网络文件系统（NFS）来实现分布式锁。客户端尝试在文件系统中创建一个锁文件，如果创建成功则获取了锁，否则等待。释放锁时，客户端删除锁文件。这种方法需要确保文件系统的一致性。
5. 基于消息队列：使用分布式消息队列（如Apache Kafka或RabbitMQ）来实现分布式锁。客户端发送请求到消息队列中，如果请求被处理则获取了锁，否则等待。释放锁时，客户端撤回请求。这种方法可以实现分布式锁，同时支持分布式任务处理。
6. 基于分布式算法：一些分布式算法，如Chubby（Google的锁服务）或Raft（一致性协议），可以用于实现分布式锁。这些算法通常需要复杂的实现和配置，适合大规模分布式系统。

1. 获取锁：当一个客户端想要获取锁时，它可以使用SETNX
   命令来尝试在Redis中设置一个特定的键（代表锁）。如果键不存在，则SETNX
   命令会将键设置为当前客户端，并返回1，表示锁已获取。如果键已存在，则表示锁已被其他客户端持有，无法获取锁，SETNX
   命令返回0。

SETNX lock_key my_client_id

1. 设置锁的超时时间：为了防止锁被无限期持有（例如，如果获取锁的客户端崩溃而没有释放锁），可以使用EXPIRE
   命令来设置锁的超时时间。这会在一段时间后自动释放锁。

EXPIRE lock_key lock_timeout

1. 释放锁：当客户端完成了对共享资源的操作后，它可以使用DEL
   命令来删除锁键，从而释放锁。

DEL lock_key

• 死锁：如果获取锁的客户端在设置锁的超时时间之前崩溃，那么锁可能会永远不会被释放。
• 锁重入：该简单实现不支持锁的重入，即同一个客户端不能多次获取同一个锁。
• 锁的争用：由于竞争锁时只有一个客户端能够成功，其他客户端需要不断地尝试获取锁，可能会导致锁的争用。

1. 字符串操作：
SET：设置键的值。
GET：获取键的值。
INCR：将键的值增加1。
DECR：将键的值减少1。

2. 列表操作：Redis的列表数据结构是基于双向链表实现的，常见的列表命令包括：
LPUSH：将一个或多个值插入到列表的左侧（头部）。
RPUSH：将一个或多个值插入到列表的右侧（尾部）。
LPOP：从列表的左侧移除并返回一个元素。
RPOP：从列表的右侧移除并返回一个元素。
LRANGE：获取列表中指定范围内的元素。

3. 集合操作：Redis的集合数据结构是无序不重复的元素集合，常见的集合命令包括：
SADD：将一个或多个元素添加到集合中。
SREM：从集合中移除一个或多个元素。
SMEMBERS：获取集合中的所有元素。

4. 哈希操作：Redis的哈希数据结构是键值对的集合，常见的哈希命令包括：
HSET：设置哈希中的字段值。
HGET：获取哈希中指定字段的值。
HDEL：删除哈希中的一个或多个字段。
HGETALL：获取哈希中所有字段和值。

5. 有序集合操作：Redis的有序集合数据结构是一个有序的元素集合，常见的有序集合命令包括：
ZADD：将一个或多个元素添加到有序集合中，并指定分数。
ZREM：从有序集合中移除一个或多个元素。
ZRANGE：按分数范围获取有序集合中的元素。

• LPUSH
  是用于向列表的左侧（头部）插入一个或多个值的命令。
• 列表是Redis中的一种有序数据结构，可以存储多个元素，每个元素都有一个索引。
• 插入新元素时，新元素将成为列表的第一个元素，而原有元素将向后移动，索引加1。
• LPUSH
  命令的语法如下：

LPUSH key value [value ...]

• 其中，key
  是列表的键名，value
  是要插入的一个或多个值。

1. 拥塞窗口（Congestion Window）：拥塞控制的核心是拥塞窗口（也称为CWND）。拥塞窗口表示可以发送到网络上的未确认数据量。发送方根据拥塞窗口的大小来控制发送数据的速率。初始时，拥塞窗口通常很小，然后随着时间逐渐增大，直到达到网络的容量限制。
2. 拥塞避免算法（Congestion Avoidance Algorithm）：TCP使用拥塞避免算法来调整拥塞窗口的大小。该算法的核心思想是，在网络不发生拥塞时，拥塞窗口应该逐渐增大，以利用网络带宽。当网络出现拥塞时，拥塞窗口应该逐渐减小，以减轻拥塞。
3. 慢启动算法（Slow Start Algorithm）：慢启动是TCP拥塞控制的一部分，用于在连接刚开始时探测网络的容量。在慢启动阶段，拥塞窗口从一个小的值开始，然后每个往返时间（Round-Trip Time，RTT）内，拥塞窗口大小会翻倍，因此数据传输速率呈指数增长。
4. 拥塞检测算法（Congestion Detection Algorithm）：TCP使用拥塞检测算法来监测网络拥塞的发生。当发送方发现丢失数据包或接收到重复的 ACK 时，它可能会认为网络发生了拥塞，因此会降低拥塞窗口的大小。
5. 快速重传和快速恢复（Fast Retransmit and Fast Recovery）：当发送方连续收到三个重复的 ACK 时，它会认为某个数据包已丢失，并执行快速重传，尽早重新发送丢失的数据包。快速恢复算法用于在发生拥塞后恢复数据传输，它将拥塞窗口减小到一定程度，并在稍后逐渐增大。
6. 超时和重传（Timeout and Retransmission）：如果数据包在一段时间内未收到确认，发送方将认为数据包已丢失，并执行超时和重传操作，即重新发送未确认的数据包。
7. 队列管理和排队策略：在路由器和交换机等网络设备中，采用不同的排队策略来处理传入的数据包，例如，先进先出（FIFO）、优先级队列、随机早期丢弃（RED）等。这些策略也可以影响网络的拥塞情况。

1. 数据块大小不固定：如果发送端发送的数据块大小不固定，接收端不容易确定何时接收到一个完整的数据块。
2. 发送速度和接收速度不匹配：如果发送端以较快的速度发送数据，而接收端以较慢的速度接收数据，可能导致多个数据块被一次性接收。
3. 操作系统缓冲区：操作系统的网络缓冲区可能会导致数据在发送端积累，然后一次性发送到接收端，造成粘包。
4. Nagle算法：Nagle算法是TCP的一种算法，用于将小数据块合并成更大的数据块以减少网络流量。这可能导致数据块被合并，进一步增加了粘包的风险。
5. 并发接收：如果多个线程或进程同时从同一连接读取数据，它们可能会交错地接收到数据块，造成粘包问题。

1. Wireshark：Wireshark是一个流行的网络协议分析工具，可以用于捕获和分析网络数据包。使用Wireshark可以查看实际传输的数据包，以确定是否存在粘包问题。
2. 日志记录：在程序中添加详细的日志记录，包括发送和接收的数据块以及时间戳。这可以帮助您分析数据的接收顺序和大小。
3. 数据分隔符：如果可能的话，可以在数据中添加特定的分隔符，以帮助接收端识别数据块的边界。例如，在文本通信中，可以使用换行符或其他特殊字符作为分隔符。
4. 流量控制：考虑使用流量控制机制，如消息长度前缀或特殊标记，以明确指示每个数据块的大小。
5. 调整发送端和接收端：可以尝试调整发送端和接收端的处理逻辑，以更好地处理数据块的边界情况。

1. 连接池工作原理：数据库连接池通常由连接管理器组成，其工作原理如下：
1. 初始化连接：在应用程序启动时，连接池会初始化一定数量的数据库连接，这些连接在池中处于空闲状态。
2. 连接请求：当应用程序需要与数据库交互时，它会从连接池中请求一个数据库连接。
3. 连接重用：如果池中有空闲的连接，则会将一个连接分配给应用程序，应用程序可以使用该连接执行数据库操作。
4. 连接释放：当应用程序完成数据库操作后，它将连接释放回池中，而不是关闭连接。
5. 连接维护：连接池会定期检查连接的状态，如果发现连接失效，则会关闭并重新创建连接，以确保连接的可用性。
2. 优点：使用数据库连接池有以下几个重要优点：
1. 性能提升：重用连接减少了每次连接建立和关闭的开销，提高了数据库操作的性能。
2. 资源管理：连接池可以限制并发连接数量，防止过多的连接导致数据库性能下降。
3. 连接复用：多个数据库操作可以共享同一个连接，减少了连接的创建和销毁次数，提高了数据库利用率。
4. 连接池监控：连接池通常提供监控和管理功能，允许管理员查看连接的状态、性能和资源利用情况。
3. 配置和参数：连接池通常允许配置参数，以满足不同应用程序的需求，包括最大连接数、最小连接数、连接超时时间、空闲连接的最大空闲时间等。
4. 连接池的类型：有多种不同类型的数据库连接池，包括：
1. JDBC连接池：针对Java应用程序的连接池，常见的实现包括Apache DBCP、C3P0、HikariCP等。
2. ORM框架连接池：某些对象关系映射（ORM）框架，如Hibernate，也提供自己的连接池。
3. 应用服务器连接池：一些应用服务器，如Tomcat，也提供了内置的连接池，用于管理数据库连接。
5. 注意事项：在使用数据库连接池时，需要注意以下几点：
1. 连接泄漏：必须确保在应用程序退出或释放连接时将连接返回到池中，否则可能导致连接泄漏。
2. 连接超时：如果连接池配置不当，可能会导致连接等待时间过长，影响性能。
3. 资源竞争：连接池可能引入资源竞争问题，需要合理配置连接池参数以避免竞争。

• 大量的缓存数据具有相同的过期时间，当这些数据同时过期时，会导致请求同时触发对后端存储的查询。
• 缓存服务器发生故障或重启，导致所有缓存数据被清除，然后需要重新加载。

1. 设置不同的过期时间：避免将所有缓存数据设置为相同的过期时间。可以采用随机化或分层的方式，使缓存数据的过期时间不完全一致，减少了同时失效的概率。
2. 使用热点数据预加载：对于关键的热点数据，可以在缓存数据即将过期时提前异步加载，以确保数据不会同时失效。
3. 备份缓存服务器：使用多个缓存服务器，并设置主备关系。当主缓存服务器故障时，备份服务器可以继续提供服务，避免缓存全部失效。
4. 限流和降级：实施请求限流和服务降级策略，以减少后端系统的压力。当缓存失效时，可以暂时限制请求的数量或降低某些请求的优先级。

• 请求查询一个不存在的键或非法的输入，导致缓存不命中。
• 恶意攻击者发送大量请求，试图穿透缓存并攻击后端系统。

1. 缓存空对象（Cache Null Values）：当查询结果为空时，仍然将该空结果缓存一段时间。这样，下次相同请求查询相同的数据时，缓存可以命中并返回一个空结果，而不会直接访问后端存储。
2. 布隆过滤器（Bloom Filter）：使用布隆过滤器来过滤掉无效或非法的请求，只允许合法的请求访问缓存。布隆过滤器可以快速判断一个键是否可能存在于缓存中。
3. 热点数据预加载：与缓存雪崩中的解决方法类似，可以预加载热点数据，确保即使请求穿透也不会直接查询后端存储。
4. 请求限制和防护：实施请求限制，例如限制来自同一IP的请求频率，以减轻恶意攻击的压力。

1. 缓冲区节点（Buffer Node）：每个缓冲区节点是一个固定大小的内存块，用于存储数据。它包括数据区域和指向下一个节点的指针。
2. 链表结构（Linked List）：缓冲区节点通过链表结构连接在一起，形成一个链式缓冲区。链表的头指针指向第一个节点，而每个节点的尾指针指向下一个节点，直到最后一个节点，它的尾指针为空。

1. 添加数据（Append Data）：当需要将数据添加到链式缓冲区时，可以在链表的最后一个节点中添加数据。如果当前节点的数据空间不足，可以创建一个新节点，并将其链接到链表的尾部。
2. 读取数据（Read Data）：读取数据时，可以从链表的头部开始逐个节点读取数据，直到满足读取需求或遍历整个链表。
3. 释放缓冲区（Free Buffer）：当不再需要链式缓冲区时，需要释放它。这通常涉及遍历整个链表，释放每个节点的内存，并将节点从链表中移除。

链式缓冲区的主要优点包括：

• 动态扩展：可以动态增加节点，以适应不定长度的数据。
• 分散的数据：可以有效地处理分散的数据块，而无需将它们合并成一个连续的大块内存。
• 节省内存：由于每个节点的大小是固定的，因此可以更灵活地管理内存，不需要分配大块连续内存。

• 网络数据传输：用于管理接收或发送的数据块，以避免拷贝数据和提高性能。
• 文件系统：用于缓冲文件读取或写入操作，以降低磁盘IO的开销。
• 流式数据处理：用于处理实时数据流，如音视频流。

1. 快排：

#include <iostream>
#include <vector>


// 交换数组中两个元素的值
void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}


// 选择一个基准元素，并将数组分成两部分，返回基准元素的索引
int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[high]; // 选择数组的最后一个元素作为基准
    int i = low - 1; // i 表示小于基准的元素的最后一个位置


    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }


    swap(arr[i + 1], arr[high]);
    return i + 1; // 返回基准元素的索引
}


// 快速排序的递归函数
void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1); // 对左半部分排序
        quickSort(arr, pivotIndex + 1, high); // 对右半部分排序
    }
}


// 快速排序的入口函数
void quickSort(std::vector<int>& arr) {
    int low = 0;
    int high = arr.size() - 1;
    quickSort(arr, low, high);
}


int main() {
    std::vector<int> arr = {12, 4, 5, 6, 7, 3, 1, 15, 9, 2, 8};
    
    quickSort(arr);
    
    std::cout << "Sorted array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

1. 找到第一个重复元素的下标：

#include <iostream>
#include <vector>
#include <unordered_map>


// 找到数组中的第一个重复元素的下标
int findFirstDuplicate(std::vector<int>& nums) {
    std::unordered_map<int, int> seen; // 哈希表用于存储元素和它们的索引
    
    for (int i = 0; i < nums.size(); i++) {
        if (seen.find(nums[i]) != seen.end()) {
            // 如果当前元素已经在哈希表中出现过，返回它的索引
            return seen[nums[i]];
        } else {
            // 否则，在哈希表中记录当前元素和它的索引
            seen[nums[i]] = i;
        }
    }
    
    // 如果没有找到重复元素，返回-1
    return -1;
}


int main() {
    std::vector<int> nums = {2, 3, 1, 4, 2};
    
    int index = findFirstDuplicate(nums);
    
    if (index != -1) {
        std::cout << "第一个重复元素的下标是：" << index << std::endl;
    } else {
        std::cout << "数组中没有重复元素。" << std::endl;
    }
    
    return 0;
}

今天就给大家分享这么多吧，如果对你有帮助，你也可以去看看别的面经，同时也别忘了给阿Q一个免费的三连~