用字符串模拟乘法 // 题目链接-来源：力扣（LeetCode） 给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。 示例 1: 输入: num1 = “2”, num2 = “3”输出: “6” 思路：因为输入是字符串的形式，直观地思考可以采用模拟竖式的形式，对两个数分别从低位向高位按位作乘法，存储当前位的结果和进位结果进入一个结果数组。考虑如下情形，我们计算 123 * 456，index 0 1 2num1 1 2 3num2 4 5 6 ... (6* 2) 1 2 (5* 3) 1 5 当计算 123 * 456 的时候，我们要计算 123 * 6，123 * 5， 123 * 4，然后分别错位累加，需要多次考虑进位，保存中间结果。我们可以对上述算法进行优化，简化我们的判断逻辑。我们用一个 res[] 数组存储结果，易知 res[] 的长度最多为两乘数长度之和 len1 + len2，最少为 len1 + len2 - 1，res[0] 对应结果的最高 ...

将大块问题分解成小块问题 // 题目链接-来源：力扣（LeetCode） 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 示例 1： 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]输出：6解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 思路：如果把每一块相连的雨水作为一个整体来考虑，时间复杂度显然是不可接受的。我们尝试按每一列来考虑雨水容量。对于任意一根柱子，其所在位置能否存放雨水，取决于其本身的高度以及「左侧最高柱子高度」以及「右侧最高柱子高度」当中的较小者（木桶原理）。于是我们需要为每一根柱子存储其「左侧最高柱子高度」以及「右侧最高柱子高度」，显然，这两个高度都能在 O(n) 时间求出，以「左侧最高柱子高度」（记为MaxLeft[i]）为例，MaxLeft[i] = max(MaxLeft[i - 1], height[i - 1])。维护了 MaxLeft 和 MaxRigh ...

用已有空间构建哈希表 // 题目链接-来源：力扣（LeetCode） 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。 示例 1： 输入：nums = [1,2,0]输出：3 思路：本题题目要求空间复杂度为 O(1)，如果不限制空间复杂度，只要将大小满足 [1, n] 区间内的数组元素存入哈希表。再遍历 [1, n] 区间，第一个不在哈希表中的整数即为所求答案。 考虑空间复杂度为常数，如果仍要使用哈希表的方法，我们只能考虑利用数组原有的空间。由于我们只需定位 [1, n] 区间内的每个元素，而数组长度恰为 n，因此我们只需实现一种 [1, n] 到 数组下标[0, n - 1] 一一对应的映射方法作为我们的哈希算法。这里为了简便起见，可以令 hash(x) = x - 1。接着我们考虑遍历数组，将 [1, n] 范围内的元素全部交换到哈希算法对应的下标位置；而对这个范围以外的元素，我们只需跳过不作考虑即可。显然，交换后的元素仍可能处于 [1, n] 范围内，我们需 ...

场景设计校招面经整理、热身 // 1. 用户登录系统： 表结构设计 为了支持多种方式用户登录，并且隔离敏感数据（如密码），防止接口暴露而泄露，我们需要分表 将用户的一些非敏感信息集合在一个 Profile 表中，字段如下： user_id（主键） | name | birthday | … 用户名和密码单独维护在一个 LocalAuth 表中，字段如下： user_id（主键） | userName | password 其他 OAuth 协议登录方式可以集成在一张 OAuth 表中，因为一个用户可能对应多种认证登录方式，不能再以 user_id 作为主键，改用一个自增 id，字段如下： id（主键） | user_id | oauth_name（比如 weibo、qq 等） | oauth_id | oauth_access_token | oauth_expires 其他登录方式类似，可以新建一个表，单独存储该种登录所需的相关信息，所有表均通过 user_id 关联到 Profile 表中 认证实现过程 用户选择任意一种登录方式（用户名密码、第三方 OAuth、HTTP A ...

计算机网络基础知识校招面经整理、热身 // 计算机网络基础知识TCP 和 UDP 区别：TCP 是面向连接的运输层协议通过三次握手、四次挥手等机制建立和拆除连接，只能一对一通信通过重传、流量控制、拥塞控制等机制实现可靠的数据传输面向字节流，将应用层传递来的数据视为无差别的字节流首部 20-60 字节 UDP 是无连接的运输层协议支持多对多交互通信不保证数据可靠到达。面向报文，将应用层传递来的报文直接加上首部后发送首部仅 8 字节 TCP 建立连接后，发送方发送一个包，接收端在收到包之前出现故障，会发生什么：这类故障的题目，抓住 2 个重点：一、端口是否关闭，若端口关闭，会返回 RST 报文，发送方收到后自行关闭连接。二、数据包是否到达接收方，接收方能否发送应答报文，应答报文能否发送回发送方。其中任何一环出问题，发送方会重传报文直到次数超限关闭连接、或者直到报文成功送达。 进程挂了接收端进程关闭后，通信的端口随之关闭，不处于监听状态，则接收端向发送端返回一个 RST 报文，发送方收到这个报文后直接关闭自己的连接。 服务器宕机发送端发送的报文无回应，会超时重传直到超出次数限制，默认 ...

Redis 基础知识校招面经整理、热身 // 1. Redis的数据结构：Redis 的数据库的基本单元是一个个「键值对」，键值对由「对象」组成， 具体是后述 5 种对象之一。键值对中的键一定是字符串对象，可以认为是这个键值对的「名字」键值对中的值可以是任意类型的某个具体的对象，可以认为是这个键值对的「本体」。 Redis 还有许多基本的数据结构如 简单动态字符串（SDS）、双端链表（linkedlist）、字典（dict）、跳跃表（skiplist）、压缩列表（ziplist）、整数集合（intset） 等，由这些数据结构的一种或多种（作为编码方式等），Redis 可以实现我们数据操作的基本单元「对象」。 2. Redis的各对象底层结构：所有redis的对象都由一个 redisObject 结构表示，有如下几个与数据有关的字段：unsigned type // 类型（如 String、List、Hash等）unsigned encoding // 编码方式（底层数据结构的实现方式）void *ptr; // 指向底层数 ...

MySQL基础知识校招面经整理、热身 // 1. 聚簇索引和普通索引：聚簇索引指其 B+ 树的叶子节点包含了指向数据的指针。查询聚簇索引时，只需顺着该指针即可访问到数据。普通索引指叶子节点处的索引项只是存储了某个聚簇索引的索引值，而非直接指向数据。查询普通索引时，还需额外回表 1 次，通过查到的索引值查找该聚簇索引，最终获得数据。MySQL中 InnoDB 主键索引一定为聚簇索引，不设主键的话第一个唯一索引字段即为聚簇索引，没有唯一索引字段的话，使用隐藏字段自增主键作为聚簇索引。由于聚簇索引在一张表中最多创建一个，所以其余索引为普通索引。 2. 普通索引和聚簇索引是单独存在表还是另外开一个表：不太确定这题要问什么。尝试从叶子结点的结构来回答。 聚簇索引的叶子结点是指向了该结点值所在的数据行的，也就是说指向了原数据表。 普通索引的叶子节点则是指向了一个新表，表中存储了当前索引值对应的所有主键值。从这个角度来说，普通索引确实创建了一个新表，而聚簇索引没有（直接在原数据表的基础上以主键构建索引） 3. HashMap 和 B 树有何异同，为什么数据库一般使用b树来当索引：相同：好像没 ...

数据结构基础知识校招面经整理、热身 // 1. 红黑树、B+ 树、B 树、二叉搜索树： 二叉搜索树：又称 BST，是为了实现在 O(logn) 时间内完成对有序集合中的元素完成一次查找，而设计的数据结构。 B树：二叉搜索树在最坏情况下，如果元素按顺序插入，会失去平衡退化为链表，查找的效率为 O(n)，为了解决这个平衡问题，引入 AVL 树、 B 树。B树中的元素会优先填满每层的结点，达到最大值以后分裂，分裂时会调整父节点和其他子节点，实现平衡。同时 B 树的一层可以设定允许容纳多个节点，进一步降低树高。 红黑树： B 树的一个缺点在于其插入、删除节点时的分裂逻辑较为复杂，对大量写操作不友好。为了解决这个问题，引入红黑树。红黑树是某棵确定的 2-3 B树的另一种表现形式（或者说，给定一种旋转规则（LL、LR、RR旋转），则一棵红黑树唯一地映射着一棵 2-3 B 树，反之亦然）。其某个红结点与其父节点（一定为黑色）可以视为对应的 2-3 B 树的某一个结点的2个元素。至此，我们将 B 树的结点分裂规则，转化为了红黑树的旋转规则，大大简化了判断逻辑。 B+ 树： B 树的另一缺点在于，对 ...

自定义哈希算法充分利用原数组空间 // 题目链接-来源：力扣（LeetCode） 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。 示例 1： 输入：nums = [1,2,0]输出：3 思路：假设不限制空间复杂度，本题显然可以用普通的哈希表存储所有元素，然后从 1 开始遍历正整数，直到找到第一个不发生冲突的正整数即为答案。现在要求 O(1) 空间复杂度，我们考虑如何充分利用原数组空间，螺蛳壳里做道场。我们总共有 n 个元素，并且有长度为 n 的数组空间，并且 n 个元素当中，会有 /[0,n] 个元素或者小于等于 0、或者大于 n（n 个不相同的正整数若均小于等于 n，则最小未出现的元素为 n + 1， 否则，答案一定在 (0,n]之间），不在我们考虑之列，也就是说，我们的数组空间是完全够用的，经过充分的交换之后，可以把所有处于 (0,n] 之间的元素哈希到合适的位置上。（理论上，这里有无数种哈希算法，比如 Hash(x) = (x + a) % n， ...

回溯遍历可能选项，二分法加快效率，39题的变式 // 题目链接-来源：力扣（LeetCode） 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用一次。 注意：解集不能包含重复的组合。  示例 1: 输入: candidates = [10,1,2,7,6,1,5], target = 8,输出:[[1,1,6],[1,2,5],[1,7],[2,6]] 思路：此题完全可以沿用上一题的模板。我们先对数组排序，之后二分地找到最大的小于等于 target 的数，从这个数开始向下回溯递归地进行 DFS搜索。只需注意，上题的每个元素是无限量的，而本题中的元素有限。为了不漏掉重复的元素，同时不重复考虑重复的元素，我们只需在每次递归当中，在循环每次要进入下层递归前，判断当前循环考虑的元素是否与前一次循环重复，重复则略过即可。时间复杂度：O(2^n * n) 其中 2^n 是指元素个数为 n 的集合所对应的幂集中的元素数量。空间复杂 ...