华为云 BU 校招 Java 后端开发，一面、二面面经 // 不知道是个例还是整个华为，至少我面的这个部门给我的面试体验相当好，面试官会当场给我比较积极的反馈，面试结束后 5 分钟内就发短信通知通过。美中不足的是笔试后面还有很长很罗嗦的性格心理测评题，个人说实话比较反感这类测评以及行测题，但总之瑕不掩瑜。 一面二面自我介绍，聊了聊非科班毕业后的一些不相干的工作经历，坦陈自己缺乏项目经验，于是面试官后面就问了些八股文。运气还不错，面试官的引导技巧也很在线，卡壳的地方也能引导我回答出来。 Java基础 了解 Java 哪些数据结构？ 说说 HashMap 实现吧？ 了解一致性 Hash 吗？ 线程同步有什么需要注意的地方？设置锁，限制对资源的争夺。（多线程这块了解不多） 对 Java 的锁有什么认识吗？回答面试官对 Java 当中多线程不熟，锁的具体实现不了解，但是粗略了解一些操作系统涉及的锁的抽象原理，于是面试官让我从抽象的角度介绍锁。回答锁其实就是对某一种资源(某个对象、某个代码块)的分配限制，如果资源能分配若干份，锁就表现为信号量，如果资源是唯一的，锁就表现为二元互斥量。竞争中获 ...

虾皮新加坡后端开发，一面、二面（凉）面经 // 先把我写在牛客网面经 贴上，等有空了整理搬过来

用回溯 + DFS 搜索可能的解，用位运算优化空间复杂度 // 题目链接-来源：力扣（LeetCode） n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。 示例 1： 输入：n = 4输出：[[“.Q..”,”…Q”,”Q…”,”..Q.”],[“..Q.”,”Q…”,”…Q”,”.Q..”]]解释：如上图所示，4 皇后问题存在两个不同的解法。 思路：简化版的解数独。由于我们需要给出 n 皇后问题的所有解，因此考虑使用回溯 + DFS 的方法搜索每一个可能的解。暴力解的复杂度显然无法接受，我们每在棋盘放入一个皇后，就要维护一个冲突信息，记录与这个皇后相关的行、列、对角线，这样我们之后放置新的皇后时，就可以直接排除这些冲突的位置，即「剪枝」大大降低我们的解法复杂度。回溯时，我们需要用某种方式撤销掉与这个皇后相关的冲突信息，仿佛我们从未放置过它。本题各种 ...

快速幂模拟 pow(x,n) 幂函数实现 // 题目链接-来源：力扣（LeetCode） 给定一个字符串数组，将字母异位词组合在一起。可以按任意顺序返回结果列表。 字母异位词指字母相同，但排列不同的字符串。 示例 1: 输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]输出: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]] 思路：常规的 n 次累乘时间复杂度为 O(n)，我们考虑对其进行优化。容易发现，如果采用分治的方法，计算 pow(x, n) 时，只需将 pow(x, n / 2) 的结果进行平方… 即可在 O(logn) 的时间内完成计算。当然，分治过程中有许多细节要处理，比如 n 为奇数时，我们要先单独乘一次 x，让 n 变为偶数后才能继续分治。为了高效完成分治，考虑快速幂的实现。我们将 n 视为二进制数，每次以其最低位为参考，若最低位为 1，表示当前 n 为奇数，我们就在结果中乘上 x；然后不论奇偶，我们都将 x 平方，并将 n 右移继续处理下一位，这个操 ...

为字母异位词设置分配哈希值相同的数据结构 // 题目链接-来源：力扣（LeetCode） 给定一个字符串数组，将字母异位词组合在一起。可以按任意顺序返回结果列表。 字母异位词指字母相同，但排列不同的字符串。 示例 1: 输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]输出: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]] 思路：观察可以发现，我们需要提取字母异位词之间满足一定的「等价性」，我们需要提取出能够表达这个等价性的某一个等价特征，作为放在哈希表中作为 key，而 value 指向一个结果列表，才能依次归类这些字符串。我们可以提取出一种方便处理的等价特征，比如将字母异位词按字典序排序以后得到的字符串，一定相同，我们可以以这个字符串作为 key 来执行哈希查找，快速定位到应该存放的结果集当中。排序方法多种多样，比如可以将字符串转化为字符数组，然后对字符数组执行排序。当然，设字符串长度为 m，总字符串个数为 n，考虑排序的复杂度此方法的整体复杂度为 O(nmlogm)。我 ...

分类处理实现高效地矩阵旋转，找规律 // 题目链接-来源：力扣（LeetCode） 给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。 你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。 示例 1： 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]输出：[[7,4,1],[8,5,2],[9,6,3]] 思路：我们可以将矩阵分组，方便我们进行旋转操作。我们发现每一次旋转操作，对于某一个位置的元素，只有与其相对应位置的另外 3 个元素是真正与其相关联的，我们可以一次性将这关联的四个位置「打包操作」（以示例 1 为例，不论我们旋转的角度是多少度，四个角落处永远都是被 1、3、7、9 四个数字占据，并且其相对位置不变，所以我们将其视为一个整体打包操作）。这样我们只需遍历 1/4 规模的矩阵元素，以其作为起始元素，每一个起始元素与其相关联的另外 3 个元素划为一组同一操作。为了对齐考虑，方便我们按数字规律查找关联元素，我们可以这样查找起始元素：显然，我 ...

用回溯 + DFS 搜索全排列（去重） // 题目链接-来源：力扣（LeetCode） 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。 示例 1： 输入：nums = [1,1,2]输出：[[1,1,2], [1,2,1], [2,1,1]] 思路：此题沿用 上一题 的模板即可。唯一的区别是，本题所给的数组中拥有重复元素，我们需要动用一点小技巧进行去重操作。首先将原数组排序，方便我们后续的比较。在每轮 dfs 查找数组中的每个元素时，我们用一个局部变量 prev 记录上一次访问过的元素，后续元素必须满足与 prev 不相同的条件我们才进行考虑。prev 的初始化可以选择一个不在值域中的数字，比如本题的值域是 [-10, 10]，我取 -11。其他代码与上一题完全一样。 时间复杂度：O(n * n!)空间复杂度：O(n) 实现：12345678910111213141516171819202122232425262728293031323334353637class Solution { public List<Lis ...

用回溯 + DFS 查找全排列 // 题目链接-来源：力扣（LeetCode） 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 示例 1： 输入：nums = [1,2,3]输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 思路：全排列的问题很直观，对于 nums 数组中的数字，我们可以用一个布尔型数组 visited[]将其标记为两类，一类是已经取到我们的结果集中的元素，另一类是尚未选择的元素。我们每次递归中，就按照一定的顺序（如，从后往前，或者从前往后，保证不遗漏即可），搜索 nums 中的尚未选择的元素，将其标为已选择（visited[i] 标记为 true），加入结果集，并在此基础上继续进行更深一层的 dfs。回溯发生在深层 dfs 返回之后，我们要恢复现场，将相关变量恢复为好像没有发生过本次 dfs 一样，包括从结果集中删除选择的元素（对于本题，即为结果列表最后一个元素），修改 visited[i]。递归中止的条件为结果集大小恰为 nums 的长度，表示 ...

贪心算法解决带长度参数的跳跃问题。 // 题目链接-来源：力扣（LeetCode） 给你一个非负整数数组 nums ，你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后一个位置。 假设你总是可以到达数组的最后一个位置。 示例 1: 输入: nums = [2,3,1,1,4]输出: 2解释: 跳到最后一个位置的最小跳跃数是 2。  从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。 思路：此题容易想到较为简单的 O(n²) 复杂度算法，我们用一个数组 jumps[] 记录第 i 格距离起点所需的跳步数。对于我们遍历到的第 i 格，其跳步数为 jumps[i]，我们维护 第 i 格之后的 nums[i] 格。显然，这些格子的跳步数至多为 jumps[i] + 1。设置初始条件为 jumps[0] = 0，最终返回 jumps[n - 1] 即可。以上做法，我们可能对每一个位置进行了多次更新，考虑能否优化到 O(n) 复杂度。我们用 jump 记录 ...

二维动态规划解决通配符匹配问题 // 题目链接-来源：力扣（LeetCode） 给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 ‘?’ 和 ‘*’ 的通配符匹配。 ‘?’ 可以匹配任何单个字符。‘*’ 可以匹配任意字符串（包括空字符串）。两个字符串完全匹配才算匹配成功。 说明: s 可能为空，且只包含从 a-z 的小写字母。p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。示例 1: 输入:s = “aa”p = “a”输出: false解释: “a” 无法匹配 “aa” 整个字符串。 思路：此题与 10.正则表达式匹配 相当类似，整体而言更加简单，我们可以借鉴其思路来破解本题。我们同样记 f(i, j) 为模式串的前 i - 1 个字符与字符串的前 j - 1 个字符的匹配情况。其中 f(0, j) 与 f(i, 0) 分别表示模式串或字符串为空串的情形。对于普通字符，f(i, j) 成立当且仅当 f(i - 1, j - 1) 成立，并且 s[j - 1] == p[i - 1]，即转移方程为 f(i, ...