快手社招一面算法原题

快手面试

最近收到一位读者的留言，是跟我吐槽「快手社招面试」的。

但是由于交谈内容太多东西需要脱敏，我打完马赛克之后，发现上下文都不连贯了。

遂罢。

但一转念，我想如果这真的是这个公司的普遍性问题，而非独立个例。

或许我能在社交媒体上找到其他人的案例？

于是我翻到了这样的帖子：

这位网友，能够进入面试，说明简历方面是符合要求的，大概率也与 HR 在商定面试时间时有过初步沟通。

因此，至少在初步的岗位匹配中，这位网友大概率是通过的，否则也不会进入面试环节。

结果却在面试中自我介绍结束后就被拒掉，这个确实不好理解。

帖子还带有「打工人在笑什么」这样 tag，我刚开始是真的不相信，以为就是纯恶搞调侃的。

但细看评论区，除了一如既往在幽默领域发挥稳定的神评网友以外，还是有不少网友表示有过类似经历的。

再看其他第一人称爆料的帖子：

这一位则是

...

还记得开头那个「刚自我介绍完就被问还有什么问题」的帖子，我提到了当中有一些很幽默的评论。

给大家分享其中一个：

...

回归主线。

我可没谈快手值不值得去，只是跟大家分享了，有网友反映过在快手面试遇到过的事儿。

如今这个行情，有面试机会，还是得去呀。

来一道「快手」一面算法原题。

题目描述

平台：LeetCode

题号：384

给你一个整数数组 nums，设计算法来打乱一个没有重复元素的数组。

实现 Solution class:

• Solution(int[] nums) 使用整数数组 nums 初始化对象
• int[] reset() 重设数组到它的初始状态并返回
• int[] shuffle() 返回数组随机打乱后的结果

示例：

输入
["Solution", "shuffle", "reset", "shuffle"]
[[[1, 2, 3]], [], [], []]

输出
[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

解释
Solution solution = new Solution([1, 2, 3]);
solution.shuffle();    // 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。例如，返回 [3, 1, 2]
solution.reset();      // 重设数组到它的初始状态 [1, 2, 3] 。返回 [1, 2, 3]
solution.shuffle();    // 随机返回数组 [1, 2, 3] 打乱后的结果。例如，返回 [1, 3, 2]

提示：

• 1<=nums.length<=2001 <= nums.length <= 2001<=nums.length<=200
• −106<=nums[i]<=106-10^6 <= nums[i] <= 10^6−106<=nums[i]<=106
• nums 中的所有元素都是 唯一的
• 最多可以调用 5×1045 \times 10^45×104 次 reset 和 shuffle

洗牌算法

共有 nnn 个不同的数，根据每个位置能够选择什么数，共有 n!n!n! 种组合。

题目要求每次调用 shuffle 时等概率返回某个方案，或者说每个元素都够等概率出现在每个位置中。

我们可以使用 KnuthKnuthKnuth 洗牌算法，在 O(n)O(n)O(n) 复杂度内等概率返回某个方案。

具体的，我们从前往后尝试填充 [0,n−1][0, n - 1][0,n−1] 该填入什么数时，通过随机当前下标与（剩余的）哪个下标进行值交换来实现。

对于下标 xxx 而言，我们从 [x,n−1][x, n - 1][x,n−1] 中随机出一个位置与 xxx 进行值交换，当所有位置都进行这样的处理后，我们便得到了一个公平的洗牌方案。

对于下标为 000 位置，从 [0,n−1][0, n - 1][0,n−1] 随机一个位置进行交换，共有 nnn 种选择；下标为 111 的位置，从 [1,n−1][1, n - 1][1,n−1] 随机一个位置进行交换，共有 n−1n - 1n−1 种选择 ... 且每个位置的随机位置交换过程相互独立。

Java 代码：

class Solution {
    int[] nums;
    int n;
    Random random = new Random();
    public Solution(int[] _nums) {
        nums = _nums;
        n = nums.length;
    }
    public int[] reset() {
        return nums;
    }
    public int[] shuffle() {
        int[] ans = nums.clone();
        for (int i = 0; i < n; i++) {
            swap(ans, i, i + random.nextInt(n - i));
        }
        return ans;
    }
    void swap(int[] arr, int i, int j) {
        int c = arr[i];
        arr[i] = arr[j];
        arr[j] = c;
    }
}

C++ 代码：

class Solution {
public:
    vector<int> nums;
    int n;
    Solution(vector<int>& _nums) : nums(_nums), n(_nums.size()) {}
    vector<int> reset() {
        return nums;
    }
    vector<int> shuffle() {
        vector<int> ans = nums;
        for (int i = 0; i < n; i++) {
            swap(ans[i], ans[i + rand() % (n - i)]);
        }
        return ans;
    }
};

Python 代码：

class Solution:
    def __init__(self, nums: List[int]):
        self.nums = nums
        self.n = len(nums)

    def reset(self) -> List[int]:
        return self.nums

    def shuffle(self) -> List[int]:
        ans = self.nums[:]
        for i in range(self.n):
            j = i + random.randint(0, self.n - i - 1)
            ans[i], ans[j] = ans[j], ans[i]
        return ans

TypeScript 代码：

class Solution {
    private nums: number[];
    private n: number;
    
    constructor(nums: number[]) {
        this.nums = nums;
        this.n = nums.length;
    }

    reset(): number[] {
        return this.nums.slice();
    }

    shuffle(): number[] {
        const ans: number[] = this.nums.slice();
        for (let i = 0; i < this.n; i++) {
            const j = i + Math.floor(Math.random() * (this.n - i));
            [ans[i], ans[j]] = [ans[j], ans[i]];
        }
        return ans;
    }
}

• 时间复杂度：O(n)O(n)O(n)
• 空间复杂度：O(n)O(n)O(n)

我是宫水三叶，每天都会分享算法题解，并和大家聊聊近期的所见所闻。

欢迎关注，明天见。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉