小红书一面、二面、HR面、offer

一面

一面面试官主要询问了简历上的内容，比较有趣的两个题是这个

bagging和boosting在参数选择上有什么不同：
- Bagging方法不需要特别关注参数选择，因为它使用随机采样自所有训练样本中进行有放回地重复采样，构建多个基学习器。每个基学习器都是独立的，并行地进行训练。因此，每个基学习器使用的参数都是原始数据集上的默认参数或经验选择的参数。
- Boosting方法对参数的选择相对较为重要，因为它是通过逐步优化基学习器来提升整体性能的。训练过程中，每个基学习器的训练都会受到前一个基学习器的影响。通常，Boosting方法会选择一些关键参数，如学习率（learning rate）、树的深度（tree depth）、迭代次数等。这些参数可以根据数据集和任务的特点进行调整，以获得更好的性能。

编程题：计算n的阶乘结果有多少个零：

#include <iostream>

// 计算 n 的阶乘结果中有多少个零
int countTrailingZeros(int n) {
    int count = 0;

    // 计算因子中 5 的个数
    for (int i = 5; n / i >= 1; i *= 5) {
        count += n / i;
    }

    return count;
}

int main() {
    int n;
    std::cout << "请输入一个整数 n：";
    std::cin >> n;

    int zeros = countTrailingZeros(n);
    std::cout << n << " 的阶乘结果中有 " << zeros << " 个零。" << std::endl;

    return 0;
}

二面

二面面试官看了简历觉得和面试岗位匹配度不够高，所以没怎么问简历上的内容，写了三道题。

编程题：实现数组最长的递增子序列

解法1：动态规划，时间复杂度 $O(n^2)$

#include <iostream>
#include <vector>
#include <algorithm>

int LongestIncreasingSubsequence(const std::vector<int>& nums) {
    int n = nums.size();
    std::vector<int> dp(n, 1);

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = std::max(dp[i], dp[j] + 1);
            }
        }
    }

    return *std::max_element(dp.begin(), dp.end());
}

int main() {
    std::vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    int longest = LongestIncreasingSubsequence(nums);
  
    std::cout << "数组的最长递增子序列长度为: " << longest << std::endl;

    return 0;
}

解法2：二分法+动态规划时间复杂度为 $O(nlogn)$

#include <iostream>
#include <vector>
#include <algorithm>

int LongestIncreasingSubsequence(const std::vector<int>& nums) {
    int n = nums.size();
    std::vector<int> dp(n, 0);
    int length = 0;

    for (int i = 0; i < n; i++) {
        int left = 0, right = length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (dp[mid] < nums[i]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        dp[left] = nums[i];
        if (left == length) {
            length++;
        }
    }

    return length;
}

int main() {
    std::vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    int longest = LongestIncreasingSubsequence(nums);

    std::cout << "数组的最长递增子序列长度为: " << longest << std::endl;

    return 0;
}

第一种解法不难，直接就写出来了，但是面试官说要更优的时间复杂度，那也就只剩下那个打扑克牌的排序方法，还是需要背一下的。

编程题：滑动窗口最大值

#include <iostream>
#include <vector>
#include <deque>

std::vector<int> slidingWindowMax(const std::vector<int>& nums, int k) {
    std::vector<int> result;
    std::deque<int> window;

    for (int i = 0; i < nums.size(); i++) {
        // 移除窗口外的元素
        if (!window.empty() && window.front() == i - k)
            window.pop_front();

        // 保持窗口内元素降序排列
        while (!window.empty() && nums[i] > nums[window.back()])
            window.pop_back();

        // 将当前元素索引加入窗口
        window.push_back(i);

        // 当窗口完全覆盖k个元素时，将窗口内的最大值加入结果
        if (i >= k - 1)
            result.push_back(nums[window.front()]);
    }

    return result;
}

int main() {
    std::vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;

    std::vector<int> result = slidingWindowMax(nums, k);

    std::cout << "滑动窗口最大值：" << std::endl;
    for (int val : result) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}

这个题一开始没有理解面试官想要我写什么，给我举得例子是CNN里面的MaxPooling操作，不过要我实现一维的。沟通了半天才发现就是滑动窗口最大值的题，双端队列解决了。然后又问最大堆或者最小堆能不能解决，怎么构建最大堆，时间复杂度怎么计算之类的问题了。