看到很多人都不了解北美的公司，简单谈谈 Amazon 吧。

Amazon 的老板是出了名的抠（富有），每年的 PIP 名额（可以理解为裁员）将近 10%。公司发展策略就是裁老人招新人，能保证最低的用人成本，所以看起来一直在招人。

但是今年经济受疫情影响，很多公司都在缩招，强势扩招的 Amazon 反而成为了很多人的选择。

谈谈面试，Amazon 的 coding 不会太难，一般 2-4 轮 VO 就能上岸，非常看重 BQ 。感兴趣的可以去找《 Amazon 经典 BQ 120 题》，我这里也有一份资料。

贡献一个面经：

给定一个含不同整数的集合，返回其所有的子集。

• 子集中的元素排列必须是非降序的，解集必须不包含重复的子集。

在线做题地址:LC17

样例 1：

输入：[0] 输出： [   [],   [0] ] 

样例 2：

输入：[1,2,3] 输出： [   [3],   [1],   [2],   [1,2,3],   [1,3],   [2,3],   [1,2],   [] ] 

解题思路

• 这道题我们需要使用 dfs+回溯的方法来进行求解。

算法

• 将数组进行升序排列。
• 定义一个递归方法 dfs，参数有：当前子集 subset，当前子集长度 k，返回结果 res 。 将当前子集添加到 res 中。 从 k 到 len(nums)-1 遍历索引 i 。 将 nums[i] 添加到当前子集 subset 。 进行下一层的递归搜索，继续向子集中添加元素，这时 k 要加一。 * 从 subset 中删除 nums[i]进行回溯。

举例分析

• 假设 nums = [1, 2, 3]，递归树如图所示。树每深一层，子集的长度就加一。每个节点都是满足条件的子集，需要记录到结果 res 中。

复杂度分析

• 时间复杂度：O(n∗2n)，其中 n 为 nums 的长度。生成所有子集，并复制到输出集合中。
• 空间复杂度：O(n∗2n)，其中 n 为 nums 的长度。存储所有子集，共 n 个元素，每个元素都有可能存在或者不存在。

public class Solution {     /**      * @param nums: A set of numbers      * @return: A list of lists      */     public List<List<Integer>> subsets(int[] nums) {         List<List<Integer>> res = new ArrayList<>();         // 排序         Arrays.sort(nums);         // dfs 搜索         Deque<Integer> subset = new ArrayDeque<>(nums.length);         dfs(nums, 0, subset, res);         return res;     }     private void dfs(int[] nums, int k, Deque<Integer> subset, List<List<Integer>> res) {         // 当前组合存入 res         res.add(new ArrayList<>(subset));         // 为 subset 新增一位元素         for (int i = k; i < nums.length; ++i) {             subset.addLast(nums[i]);             // 下一层搜索             dfs(nums, i + 1, subset, res);             // 回溯             subset.removeLast();         }     } } 

大佬有話說 (0)