腾讯云后端开发一面

来源：https://www.nowcoder.com/feed/main/detail/ca235c30abc9455897a577c62de61cbf

1、讲一下hashmap的原理？

哈希表的原理基于哈希函数，用于将键映射到特定的存储位置，以便快速访问数据。

基本原理：

哈希函数：哈希表的核心是哈希函数，它接受一个键作为输入并生成一个固定大小的哈希码（或哈希值）。这个哈希码通常是一个整数，它可以用来确定存储位置。
存储数组：哈希表内部通常包括一个固定大小的数组，通常是连续的内存空间。数组的大小通常会大于哈希表中的元素数量，以避免碰撞（后面会解释）。
哈希冲突：由于哈希函数将不同的键映射到相同的位置，可能会发生哈希冲突。哈希表需要解决这些冲突，常见的方法包括链地址法（Chaining）和开放地址法（Open Addressing）。
- 链地址法：在数组的每个位置存储一个链表（或其他数据结构），具有相同哈希码的键被存储在同一位置的链表中。
- 开放地址法：在碰撞发生时，继续寻找下一个可用的位置。这可能涉及线性探测、二次探测等策略。
存储和检索：存储时，哈希表使用哈希函数计算键的哈希码，然后找到相应的存储位置，将键-值对存储在那里。检索时，哈希表使用相同的哈希函数找到存储位置，并返回与键关联的值。
性能：哈希表的性能通常非常出色，因为它允许常量时间复杂度的存储和检索操作，即 O(1)。这是因为哈希函数通常能够将键均匀地映射到数组的不同位置。
调整大小：当哈希表的负载因子（已存储元素数量与数组大小之比）超过某个阈值时，通常需要调整数组的大小，以避免性能下降。这通常包括创建新的更大数组，重新哈希存储的元素，并将其放入新数组中。

2、http常见状态码？

1xx（信息性状态码）：服务器正在处理请求，需要进一步操作。
- 100 Continue：客户端应继续发送请求。用于确认客户端的请求已被服务器接收，可以继续发送请求正文。
- 101 Switching Protocols：服务器已经理解客户端的请求，需要切换协议以完成请求。
2xx（成功状态码）：请求被成功接收、理解和接受。
- 200 OK：请求成功，服务器返回的数据在响应正文中。
- 201 Created：请求已经被服务器成功处理，并且创建了新的资源。
- 204 No Content：服务器成功处理请求，但没有返回响应体，通常用于 DELETE 请求。
3xx（重定向状态码）：需要进一步操作以完成请求。
- 301 Moved Permanently：资源被永久移动到新的 URL。客户端应使用新的 URL 发起请求。
- 302 Found：资源被临时移动到新的 URL。客户端应继续使用原始 URL。
- 304 Not Modified：资源未被修改，可以使用缓存的版本。
4xx（客户端错误状态码）：客户端发送了错误的请求或无法完成请求。
- 400 Bad Request：请求中存在语法错误。
- 401 Unauthorized：需要身份验证，未提供有效凭据。
- 403 Forbidden：服务器拒绝了请求。
- 404 Not Found：请求的资源未找到。
5xx（服务器错误状态码）：服务器在尝试处理请求时发生了错误。
- 500 Internal Server Error：服务器遇到了意外错误。
- 502 Bad Gateway：充当网关或代理的服务器收到来自上游服务器的无效响应。
- 503 Service Unavailable：服务器暂时不可用，通常是因为超载或维护。

3、http和https的区别？

安全性：
- HTTP： HTTP 是一种不安全的协议，数据在传输过程中是明文的，容易被中间人攻击者截获和窥视。
- HTTPS： HTTPS 使用 SSL/TLS（Secure Sockets Layer/Transport Layer Security）协议来加密数据传输，从而提供安全性。数据在传输时经过加密，使其难以被窃取或篡改。
端口：
- HTTP： HTTP 默认使用端口 80 进行通信。
- HTTPS： HTTPS 默认使用端口 443 进行通信。
URL 前缀：
- HTTP： HTTP 的 URL 以 "http://" 开头。
- HTTPS： HTTPS 的 URL 以 "https://" 开头。
证书要求：
- HTTP： HTTP 不需要服务器端的数字证书。
- HTTPS： HTTPS 要求服务器端具有有效的 SSL/TLS 数字证书，以便客户端验证服务器的身份。这可以防止中间人攻击。
数据传输方式：
- HTTP： HTTP 数据传输是明文的，没有加密保护。
- HTTPS： HTTPS 数据传输经过加密，保护数据的机密性和完整性。
速度：
- 由于 HTTPS 需要加密和解密数据，因此与 HTTP 相比，它可能会稍微减慢数据传输速度。然而，现代的硬件和协议优化已经减小了这一差距，使 HTTPS 在大多数情况下仍然能够提供良好的性能。

4、CA证书了解吗？

什么是 CA 证书？

CA 证书是由 CA 颁发的数字证书，用于验证公共密钥基础设施（PKI）中的实体身份。它包含有关实体（通常是服务器或客户端）的信息，如名称、公共密钥、有效期和签名。

CA 的角色：
- 根 CA（Root CA）：根 CA 是最高级别的 CA，它自签名并用于签署下级 CA 的证书。根 CA 的公共密钥被广泛分发，以便客户端可以验证下级 CA 的证书。
- 中间 CA（Intermediate CA）：中间 CA 是由根 CA 签发的 CA 证书，它们可以用于签署终端实体（服务器或客户端）的证书。它们构成了 CA 层次结构中的中间层。
- 终端实体：终端实体可以是服务器、客户端或其他网络设备，它们使用由 CA 颁发的证书来验证其身份，并进行安全通信。
证书验证：

当客户端与服务器之间建立安全连接时，客户端会验证服务器的证书。这个验证包括以下步骤：

客户端检查服务器证书的签名是否可以通过根 CA 的证书验证。
客户端检查证书中的有效期以确保它仍然有效。
客户端检查证书中的主体名称（通常是服务器的域名）是否与客户端尝试连接的主机名匹配。

如果服务器证书通过验证，客户端将与服务器建立安全连接。

用途：

CA 证书广泛用于 Web 安全（HTTPS）、电子邮件加密（S/MIME）、虚拟专用网络（VPN）、数字签名等领域。它们确保了通信的机密性、完整性和身份验证。

著名的 CA：

一些著名的 CA 包括 Comodo、Symantec（现在属于 DigiCert）、GlobalSign、Let's Encrypt 等。

5、Http2.0的优势？

多路复用（Multiplexing）： HTTP/2 支持多路复用，允许在单个连接上同时传输多个请求和响应。这消除了在传统的 HTTP/1.x 中可能出现的串行请求的瓶颈问题，提高了并发性和响应速度。
二进制分帧（Binary Framing）： HTTP/2 使用二进制格式的帧，而不是文本格式的消息，这使得协议的解析更加高效。这有助于减小传输的开销，并提高了数据传输的效率。
头部压缩（Header Compression）： HTTP/2 使用 HPACK 压缩算法来减小请求和响应头部的大小。这减少了带宽的占用，特别是对于包含重复头部的请求，如 Cookie。
服务器推送（Server Push）： HTTP/2 允许服务器在客户端请求之前主动向客户端推送资源。这提高了网页加载速度，减少了往返请求的数量，因为服务器可以预测客户端可能需要的资源。
流优先级（Stream Prioritization）： HTTP/2 支持为流设置优先级，使客户端和服务器可以更好地管理资源分配。这有助于确保重要资源的及时传输。
单一连接： HTTP/2 通过一个单一的持久连接处理多个请求，而不需要为每个请求都建立新的连接，从而减少了连接建立和管理的开销。
支持加密：虽然加密在 HTTP/1.x 中是可选的，但在 HTTP/2 中，加密是强制性的。这提高了数据传输的安全性和隐私。
兼容性： HTTP/2 的设计允许它在现有的基础设施上平稳地演进，因此它可以与 HTTP/1.x 兼容。这意味着即使服务器和客户端不支持 HTTP/2，它们仍然可以继续使用 HTTP/1.x 进行通信。

6、Http3.0了解吗？

底层传输协议： HTTP/3 基于 QUIC（Quick UDP Internet Connections）协议，而不是像 HTTP/2 一样基于 TCP 协议。QUIC 是 Google 开发的一种传输层协议，它结合了 TCP 和 TLS（Transport Layer Security）以提供更好的性能和安全性。
多路复用： HTTP/3 保留了 HTTP/2 中引入的多路复用功能，允许在单个连接上并行传输多个请求和响应。这有助于提高并发性和降低延迟。
头部压缩： HTTP/3 同样采用头部压缩，以减小请求和响应的头部大小，减少带宽的使用。
服务器推送：类似于 HTTP/2，HTTP/3 也支持服务器推送，使服务器能够预测客户端可能需要的资源，并主动将这些资源推送给客户端，以提高加载速度。
快速握手： QUIC 协议具有快速的连接建立和恢复机制，这减少了握手时延迟，特别有助于移动设备和不稳定网络的性能。
安全性： HTTP/3 的连接是通过 TLS 加密的，这提供了数据传输的安全性和隐私保护。
抗干扰性：由于 HTTP/3 使用 UDP 协议，它更具抗干扰性，可以更好地应对网络中的数据包丢失和重新排序等情况。
兼容性： HTTP/3 旨在与 HTTP/1.1 和 HTTP/2 兼容，因此现有的服务器和客户端可以逐渐过渡到 HTTP/3，而不会中断现有的应用程序。

7、UDP相对于TCP的优势？

低延迟： UDP 具有较低的通信延迟，因为它不涉及连接的建立和维护，也没有拥塞控制机制。这使得 UDP 适合需要实时性的应用，如音视频流媒体和在线游戏。
高吞吐量：由于没有 TCP 的复杂性（如拥塞控制和流量管理），UDP 允许在网络上以高速传输数据。这对于快速数据传输非常有利，如广播、多播和实时数据流。
简单： UDP 是一种轻量级协议，它的头部较小，不涉及复杂的状态管理。这使得 UDP 更容易实现和处理，适用于资源有限的嵌入式设备和传感器网络。
适用于无连接通信： UDP 是一种无连接协议，不需要建立和维护连接，因此适用于一次性的短期通信或状态不太重要的应用。
支持广播和多播： UDP 允许数据以广播（一对多）或多播（一对多）方式传输，这对于向多个接收者同时发送数据非常有用。
自定义数据包： UDP 允许应用程序自定义数据包的格式和内容，因此非常灵活，适用于各种不同的通信需求。

8、TCP三次握手讲一下？

第一次握手：
- 客户端向服务器发送一个带有SYN（同步）标志的数据包，表明客户端想要建立连接。
- 客户端选择一个初始的序列号（ISN，Initial Sequence Number），用于后续的数据传输。ISN 是一个随机数，通常是一个较大的值。
第二次握手：
- 服务器收到客户端的 SYN 数据包后，确认了这个请求，并向客户端发送一个带有 SYN 和 ACK（确认）标志的数据包。
- 服务器也选择了一个初始的序列号，通常是比客户端的 ISN 大1的值。这个序列号用于服务器向客户端传输数据。
第三次握手：
- 客户端收到服务器的 SYN-ACK 数据包后，向服务器发送一个确认（ACK）数据包，表明客户端也确认了连接的建立。
- 在这个数据包中，客户端也确认了服务器的初始序列号。

9、为什么必须是三次握手？

初始化序列号（ISN）的同步：在握手的过程中，客户端和服务器都要选择一个初始的序列号（ISN），用于后续的数据传输。如果只有两次握手，而没有第三次握手，那么双方无法同步彼此的 ISN，这可能导致不可靠的连接和数据传输。
避免旧连接的问题：三次握手可以防止已经终止的连接请求被误认为是新连接的请求。如果只有两次握手，旧的请求可能会被错误地视为新连接，从而导致混乱和错误的数据传输。
确认连接的双方：三次握手确保了连接的双方都已经同意建立连接。在第一次握手时，客户端表明它想要建立连接；在第二次握手时，服务器确认了请求并表明它也愿意建立连接；最后，在第三次握手时，客户端再次确认了连接。这确保了双方都明确表示了他们的意愿。
安全性：三次握手可以防止恶意或未经授权的连接请求。只有在三次握手完成后，双方才会建立连接。如果只有两次握手，可能会容易受到连接重放攻击等安全问题的影响。

10、mysql的两种引擎？

InnoDB：InnoDB是MySQL默认的存储引擎，它支持事务、行级锁、外键约束和崩溃恢复能力。它是一个强大的存储引擎，适用于大多数应用场景，特别是那些需要数据完整性和高并发性能的应用。
MyISAM：MyISAM是另一种MySQL存储引擎，它不支持事务，而是以表级锁为基础工作。MyISAM在一些特定用途下仍然有用，例如用于只读或很少更新的数据表，因为它可以提供较快的读取性能。然而，由于其不支持事务和崩溃恢复，它不适用于需要数据完整性和高并发性能的应用。

11、B+树和B树的区别？

结构：
- B树（B-tree）：B树是一种多路搜索树，它的内部节点可以拥有多个子节点，通常用于磁盘存储系统，以减少磁盘I/O次数。B树的所有节点都存储数据，而叶子节点之间有指针连接，形成一个有序的链表。这使得B树在范围查询时比B+树更高效。
- B+树（B+ tree）：B+树也是一种多路搜索树，但它的叶子节点保存了所有数据，而内部节点只用于索引目的。叶子节点之间同样有指针连接，形成一个有序的链表。B+树适用于范围查询，因为数据仅存在于叶子节点，范围查询可以直接在叶子节点上进行。
应用场景：
- B树：由于B树的内部节点也存储数据，它适用于需要随机访问的场景，如文件系统和数据库的索引结构。B树对于范围查询的性能较差。
- B+树：B+树适用于需要范围查询和顺序访问的场景，如数据库管理系统中的索引结构。B+树的叶子节点形成了有序链表，因此范围查询的效率较高。此外，B+树通常比B树更适合磁盘存储系统，因为它减少了I/O操作，提高了性能。

12、Redis的缓存击穿讲一下？

Redis的缓存击穿是一种缓存失效的情况，它通常发生在一个非常热门的缓存键（通常是常用的键）在某个时间点失效，然后在此时突然有大量的并发请求尝试访问该键。由于缓存失效，每个请求都需要查询数据库或其他数据源以重新填充缓存，这会导致数据库负载急剧上升，甚至可能导致数据库宕机或性能急剧下降。

一些缓存击穿的典型情况：

一个非常热门的缓存键，例如用户的会话信息、热门商品信息等，在某个时间点过期或被删除。
在缓存失效后，大量并发请求同时访问该键，触发大量的数据库查询。
数据库负载急剧上升，可能导致性能下降，响应时间增加，甚至导致数据库宕机。

缓存击穿的解决方案：

设置合适的缓存过期时间：确保缓存键的过期时间不是太短，以减少热门数据的频繁失效。
使用互斥锁（Mutex）：在缓存失效时，使用互斥锁来保护数据库查询操作，只允许一个线程或请求进行查询，其他线程等待结果或直接返回相同的结果。
预加载：在缓存键失效之前，使用定时任务或后台线程进行预加载，将缓存重新填充，以避免在缓存失效时才触发数据库查询。
带有过期时间的分布式锁：使用分布式锁来确保只有一个节点执行数据库查询，其他节点等待结果。此方法适用于分布式环境中。
使用缓存穿透保护：在缓存中设置一个不存在的键的占位符，以防止无效的查询访问数据库。
使用快速失败策略：当缓存失效时，直接返回一个默认值，而不是触发数据库查询，以减轻数据库负载。

13、布隆过滤器的具体实现原理？

布隆过滤器（Bloom Filter）是一种用于快速检查一个元素是否属于一个集合的概率型数据结构。它以极低的内存消耗和快速的查询速度而闻名。

具体实现原理：

初始化：首先，创建一个长度为m的位数组（通常用比特位表示，0或1）。初始时，所有位都被置为0。
哈希函数：选择k个不同的哈希函数，每个哈希函数可以将输入元素映射到位数组中的一个位置。这些哈希函数应该足够分散，以减小冲突的可能性。
插入元素：当要插入一个元素时，对该元素应用每个哈希函数，得到k个哈希值。然后，将位数组中这k个位置的位都设置为1。
查询元素：当要查询一个元素是否存在时，同样对该元素应用每个哈希函数，得到k个哈希值。然后检查位数组中这k个位置的位是否都为1。如果有任何一个位置的位为0，那么该元素肯定不在集合中。如果所有位置的位都为1，那么该元素可能存在于集合中，但不能确定。
误判率：布隆过滤器存在一定的误判率，这是由于哈希函数的不完美性和位数组长度等因素造成的。可以通过选择合适的位数组大小和哈希函数数量来控制误判率。

优点：

布隆过滤器可以高效地检查一个元素是否属于集合，通常比线性搜索要快得多。
布隆过滤器内存消耗较低，适用于大规模数据集的去重和查询。

缺点：

布隆过滤器有一定的误判率，不能保证100%的准确性。
布隆过滤器无法删除已插入的元素，因为删除一个元素可能影响其他元素的判断。

注意：布隆过滤器通常用于需要快速判定元素存在性的场景，例如缓存、爬虫去重、拼写检查等。要控制误判率，需要谨慎选择哈希函数和位数组大小，以适应具体应用需求。

14、如果有用户恶意访问不存在的记录怎么办？可采取措施：

限制请求频率：实施访问频率限制，例如使用令牌桶或漏桶算法，以确保用户不能过快地发送请求。这可以帮助减轻恶意用户对系统的冲击。
实施验证码：对于一些敏感操作或需要频繁访问的接口，要求用户进行验证码验证，以确保访问的合法性。这可以防止自动化的爬虫和恶意请求。
IP封锁：监测并识别频繁访问不存在记录的IP地址，然后将这些IP地址列入黑名单，暂时禁止它们的访问。这是一种针对具体恶意用户的应对措施。
日志和监控：定期检查服务器日志，特别是针对不存在记录的请求。通过分析日志，可以识别异常或恶意行为，并采取相应的措施。
身份验证和授权：确保用户必须经过身份验证，且只能访问他们有权限访问的记录。这可以通过访问控制列表（ACL）或基于角色的访问控制来实现。
自动封禁机制：实施自动封禁机制，可以根据一定的规则和阈值来检测异常或恶意请求，并自动封禁涉及的用户或IP地址。
错误处理：为不存在的记录返回一个合理的错误响应，而不是空白或默认页面。这可以减少用户的困惑和误解。
持续改进安全策略：不断更新和改进安全策略，以适应不断变化的威胁和攻击。保持安全策略的灵活性是重要的。

15、如果这个数据又存在于db中呢？

访问控制：确保只有经过授权的用户可以访问敏感数据。使用身份验证和授权机制来验证用户的身份，以确定他们是否有权访问特定数据。
记录恶意行为：监控和记录用户的恶意行为，包括频繁的非法访问或异常的数据访问模式。这些记录可以用于安全审计或作为证据，以便采取法律行动。
防火墙和WAF：使用Web应用程序防火墙（WAF）或其他网络安全工具来检测和阻止恶意请求。WAF可以识别和拦截常见的攻击，如SQL注入、跨站脚本（XSS）等。
限制访问频率：限制用户的访问频率，以减少恶意用户对系统的冲击。这可以通过令牌桶、漏桶算法或类似的速率限制机制来实现。
错误处理：为非法请求返回适当的错误响应，而不是泄漏过多信息。不要返回详细的错误消息，以防止信息泄漏。
数据加密：在数据库中存储敏感数据时，使用适当的加密来保护数据的安全。即使数据被恶意获取，也难以解密。

16、场景题1：10000个数找最大的100个数，给出时间和空间复杂度？

可以使用堆（Heap）数据结构来实现。

具体思路：

初始化一个最小堆（Min Heap）数据结构，其大小为100。最小堆是一种特殊的二叉树，其中每个节点的值都小于或等于其子节点的值，根节点是堆中的最小值。
遍历10000个数，对于每个数，执行以下操作：
- 如果堆的大小小于100，直接将该数插入堆中。
- 否则，如果该数大于堆顶元素（堆中最小的元素），则将堆顶元素弹出，然后将该数插入堆中。
最终，堆中的100个元素即为10000个数中的最大100个数。

时间复杂度：

遍历10000个数，每次插入或删除操作的时间复杂度为O(log(100))，即O(log(1))，因为堆的大小是常数100。总的时间复杂度为O(10000 * log(1))，即O(10000)。

空间复杂度分析：

堆的空间复杂度为O(100)。

再给出其它解决思路，供大家参考：

快速排序变种（如快速选择）：这种方法是使用快速排序的变种算法，通常称为快速选择。它选择一个枢轴元素，将数组分为两部分，一个部分包含大于枢轴的元素，另一个部分包含小于枢轴的元素。如果枢轴的索引等于100，那么枢轴元素就是第100大的元素，以及枢轴右边的元素都是前100大的元素。这种方法具有平均时间复杂度为O(n)。
分治法：将10000个数分成多个子数组，每个子数组的大小为n/100，其中n是数组的大小。然后，对每个子数组执行快速选择以找出该子数组中的前100个最大元素。最后，合并所有子数组中的前100个元素，得到最大的100个数。
分桶法：将10000个数分为多个桶，每个桶包含n/100个元素。然后，在每个桶中找出最大的100个元素。最后，合并这些桶中的前100个元素，得到最大的100个数。
部分排序：对数组的前100个元素执行排序算法，通常可以使用快速排序或归并排序。这样，前100个元素即为最大的100个数。这种方法适用于只需要找出前k个最大数的情况。

17、场景题2：40亿个qq号，有两种状态，如何在O(1)的时间复杂度找到某个qq号的状态？

要在O(1)的时间复杂度内找到某个qq号的状态，可以使用位图排序（Bitmap Sort）的思想。位图排序是一种基于位操作的高效排序和查询技术，适用于问题中的二进制状态数据，比如这里的qq号状态。

位图表示状态：首先，将所有的qq号状态信息表示为一个位图，其中每个qq号对应一个位。假设我们有40亿个qq号，那么需要40亿个位，可以使用一个很大的位图来表示。
初始化位图：将位图初始化为全0，表示初始状态下，所有qq号的状态都是一种状态。这个初始化过程只需遍历一次位图，时间复杂度为O(N)，其中N是位图的大小。
设置状态：要设置某个qq号的状态，只需在位图中将对应qq号的位设置为1或0，分别表示两种状态。这个操作是O(1)的，因为它只涉及到一个位的设置或清除。
查询状态：要查询某个qq号的状态，只需查看位图中对应qq号的位是1还是0。这个操作也是O(1)的，因为它只涉及到一个位的查看。

位图排序的核心思想是用位来表示状态信息，通过位操作来设置和查询状态，因此能够在O(1)的时间复杂度内实现。但需要注意，位图的大小可能非常大，需要足够的内存来存储位图。此外，位图排序适用于二进制状态信息，如果状态信息不仅包含两种状态，还包含更多状态，可以考虑使用多个位图来表示。

给个代码理解：

C++

#include <iostream>
#include <vector>
#include <bitset>

const size_t MAX_QQ_NUM = 4200000000;  // 最大的qq号数量
const size_t BITMAP_SIZE = MAX_QQ_NUM / 8;  // 位图的大小，每个qq号用一个位表示

std::vector<uint8_t> bitmap(BITMAP_SIZE);

// 设置qq号的状态
void setQQStatus(uint64_t qq, bool status) {
    if (qq > MAX_QQ_NUM) {
        std::cerr << "Invalid qq number." << std::endl;
        return;
    }

    size_t index = qq / 8;
    uint8_t bit = 1 << (qq % 8);

    if (status) {
        bitmap[index] |= bit;  // 设置位为1
    } else {
        bitmap[index] &= ~bit;  // 设置位为0
    }
}

// 查询qq号的状态
bool getQQStatus(uint64_t qq) {
    if (qq > MAX_QQ_NUM) {
        std::cerr << "Invalid qq number." << std::endl;
        return false;
    }

    size_t index = qq / 8;
    uint8_t bit = 1 << (qq % 8);

    return (bitmap[index] & bit) != 0;
}

int main() {
    // 示例：设置qq号100的状态为1
    setQQStatus(100, true);

    // 示例：查询qq号100的状态
    bool status = getQQStatus(100);
    std::cout << "QQ 100 Status: " << status << std::endl;

    // 示例：设置qq号200的状态为0
    setQQStatus(200, false);

    // 示例：查询qq号200的状态
    status = getQQStatus(200);
    std::cout << "QQ 200 Status: " << status << std::endl;

    return 0;
}

其实这个场景题更多的还是让大家理解并使用位图的，如果现在理解不是那么深刻的话，后边可以自己再看看相关的题目，加深印象。

18、算法题最大子数组的和？

动态规划方法：

动态规划的核心思想是利用已计算的子问题的解来求解更大的问题。在这里，我们可以定义一个动态规划数组 dp，其中 dp[i] 表示以 nums[i] 结尾的子数组的最大和。状态转移方程如下：

C++

dp[i] = max(nums[i], dp[i-1] + nums[i])

上面方程的意思是，对于第 i 个元素，它要么单独构成一个新的子数组，要么加入到之前的子数组中，取两者中的较大值。遍历整个数组，每次更新 dp[i]，最终 dp 数组中的最大值即为所求的最大和。

代码示例：

C++

#include <vector>
#include <algorithm>

int maxSubArray(std::vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;

    std::vector<int> dp(n); // 创建动态规划数组

    dp[0] = nums[0];
    int maxSum = dp[0]; // 记录最大和

    for (int i = 1; i < n; i++) {
        dp[i] = std::max(nums[i], dp[i - 1] + nums[i]);
        maxSum = std::max(maxSum, dp[i]);
    }

    return maxSum;
}

int main() {
    std::vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int result = maxSubArray(nums);
    std::cout << "Maximum Subarray Sum: " << result << std::endl;
    return 0;
}

贪心算法方法：

贪心算法的核心思想是维护一个当前连续子数组的和 currentSum 和一个最大子数组和 maxSum。遍历数组，每次考虑将当前元素加入到当前子数组中，或者从当前元素开始构建一个新的子数组。维护 maxSum 为遍历过程中的最大和。

代码示例：

C++

#include <vector>

int maxSubArray(std::vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;

    int maxSum = nums[0]; // 最大和
    int currentSum = nums[0]; // 当前连续子数组的和

    for (int i = 1; i < n; i++) {
        currentSum = std::max(nums[i], currentSum + nums[i]);
        maxSum = std::max(maxSum, currentSum);
    }

    return maxSum;
}

int main() {
    std::vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int result = maxSubArray(nums);
    std::cout << "Maximum Subarray Sum: " << result << std::endl;
    return 0;
}

补充 19、服务器负载高，如何排查？

服务器负载高可能由多种原因引起，包括CPU使用率高、内存不足、磁盘I/O繁忙、网络问题等。

可参考以下步骤：

监控系统资源：首先，使用系统监控工具来查看各种系统资源的使用情况，包括CPU使用率、内存使用率、磁盘使用率、网络带宽等。这可以帮助确定哪个资源导致了高负载。
查看进程信息：使用工具如top（Linux/Unix）或任务管理器（Windows）来查看哪些进程占用了大量资源。注意查看CPU和内存使用最高的进程。
检查日志：查看系统日志、应用程序日志和数据库日志，以查找任何异常或错误信息。日志中可能包含有关负载高的原因的线索。
性能分析工具：使用性能分析工具如perf、strace（Linux/Unix）或性能监视器（Windows）来深入分析进程的性能瓶颈，例如函数调用、系统调用、文件I/O等。
数据库查询分析：如果系统使用数据库，使用数据库性能分析工具来分析查询性能。检查慢查询日志和索引状态，以优化查询性能。
网络分析：使用网络分析工具如Wireshark来检查网络流量，寻找网络瓶颈和异常请求。检查是否有DDoS攻击或异常的网络流量。
应用程序代码：检查应用程序代码，特别是是否存在死循环、内存泄漏、不合理的资源使用等问题。
硬件问题：检查硬件健康状况，包括服务器的温度、风扇、硬盘状态等。硬件问题也可能导致负载高。
系统配置：检查系统配置是否合理，例如是否合适地配置了线程池、数据库连接池等参数。
升级和优化：根据分析的结果，对系统进行必要的升级和优化。这可能包括增加硬件资源、优化代码、增加缓存、调整配置等。
监控系统：在排查问题后，建立监控系统来定期检查服务器的性能，并实施警报机制，以便在未来发生问题时能够迅速采取行动。

20、TCP的流量控制讲一下？

工作原理：

滑动窗口机制： TCP 流量控制使用了滑动窗口机制。接收端维护一个接收窗口大小（Receiver Window Size），表示它还能接收多少字节的数据。这个窗口的大小会根据接收端的处理能力和可用缓冲空间而变化。
通告窗口大小：接收端会向发送端发送一个通告窗口大小（Advertised Window Size），告诉发送端它还能接收多少数据。通告窗口大小是动态调整的，根据接收端的情况和网络条件来确定。
发送端根据窗口大小发送数据：发送端根据接收端通告的窗口大小来确定可以发送多少数据。发送端会维护一个发送窗口，确保它只发送接收端可以容纳的数据量。
动态调整窗口大小：通告窗口大小可以根据接收端的缓冲区可用空间和网络条件来动态调整。如果接收端的缓冲区快满了，它会减小通告窗口大小，告诉发送端减缓发送速度；如果接收端有更多的可用空间，它会增大通告窗口大小，允许发送端发送更多数据。
避免过载： TCP 流量控制的关键目标是防止过载。通过定期更新通告窗口大小，TCP 确保发送端发送的数据不会超过接收端的处理能力和可用缓冲区大小。

微服务

文档

基础

腾讯云后端开发一面 ​

1、讲一下hashmap的原理？ ​

2、http常见状态码？ ​

3、http和https的区别？ ​

4、CA证书了解吗？ ​

5、Http2.0的优势？ ​

6、Http3.0了解吗？ ​

7、UDP相对于TCP的优势？ ​

8、TCP三次握手讲一下？ ​

9、为什么必须是三次握手？ ​

10、mysql的两种引擎？ ​

11、B+树和B树的区别？ ​

12、Redis的缓存击穿讲一下？ ​

13、布隆过滤器的具体实现原理？ ​

14、如果有用户恶意访问不存在的记录怎么办？ 可采取措施： ​

15、如果这个数据又存在于db中呢？ ​

16、场景题1：10000个数找最大的100个数，给出时间和空间复杂度？ ​

17、场景题2：40亿个qq号，有两种状态，如何在O(1)的时间复杂度找到某个qq号的状态？ ​

18、算法题 最大子数组的和？ ​

补充 19、服务器负载高，如何排查？ ​

20、TCP的流量控制讲一下？ ​