血汗大厂 Amazon 的面经

看到很多人都不了解北美的公司,简单谈谈 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 中。

9ab04fdd-45a5-4bab-9407-92fa50628e2d.png

复杂度分析

  • 时间复杂度: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();
        }
    }
}
Click to rate this post!
[Total: 0 Average: 0]

相关文章

发表回复

您的电子邮箱地址不会被公开。