2022年4月16日——360暑期实习笔试

360的暑期实习笔试试题算是我做过的所有暑期实习笔试题中比较特殊的，因为选择题从题量（分值占比）到覆盖面到难度都超过其他大厂的暑期实习笔试题。

选择题

选择题一共 40 道，涵盖了：机器学习基础、深度学习基础、C++基础、python基础、线性代数、概率论、基础数据结构和算法，算是综合性比较强的。而且难度也不算低，整个40道选择题也花了差不多1个小时，而且其中还有一部分忘了都不会做，就瞎选了。

编程题

大致的题目意思解读出来就是求解正向和反向的最大的连续递增子序列的问题，比较基本的动态规划问题。

题目大致意思是，给定一个长度为 N 的数组，现在有 M 次操作，每一次都将数组的前 n 个数进行升序或者降序排列，问最终的数组的值是多少。（N最大为 10^5，M 最大为 10^5）

例子：

输入：

5 2 // 5个数，2组操作 
3 2 4 5 1 // 原始数组值 
0 3 // 0 代表升序，前3个数升序，得到 2 3 4 5 1 
1 2 // 1 代表降序，前2个数降序，得到 3 2 4 5 1

输出：

3 2 4 5 1

暴力法时间复杂度 O(M*N\log N) 超时，只过了 9% 的数据。

因为时间充足，我做了两轮改进；

改进 1：

基于单调队列的改进，其实根据题目的意思可以知道，如果后的操作操作的范围比前面操作的范围要大的话，其实前面的操作带来的影响完全会被摸除，所以其实我们只需要保留有效的操作就行了。使用单调递减的队列只保留下有效的操作。

#include<bits/stdc++.h>

using namespace std;

int main() {
    int N, M, t, x, lt;
    cin >> N >> M;
    int vec[N], ops[N], indices[N];
    deque<int> Deque;
    for(int i = 0; i < N; ++i)
        cin >> vec[i];
    // 保证单调队列中的操作范围递减
    for(int i = 0; i < M; ++i) {
        cin >> ops[i] >> indices[i];
        while(!Deque.empty() && indices[Deque.back()] <= indices[i])
            Deque.pop_back();
        Deque.push_back(i);
    }
    lt = -1;
    while(!Deque.empty()) {
        int idx = Deque.front();
        Deque.pop_front();
        // 如果连续两次操作相同，后一次不会对结果有影响，进一步优化
        if(ops[idx] == lt)
            continue;
        else {
            if(ops[idx] == 0)
                sort(vec, vec + indices[idx], less<int>());
            else
                sort(vec, vec + indices[idx], greater<int>());
            lt = ops[idx];
        }
    }
    for(int i = 0; i < N; ++i)
        cout << vec[i] << ' ';
    return 0;
}

上面的代码其实在最坏的情况下，时间复杂度依然是 O(M*N\log N)，但是已经通过全部的用例了，看来没有测试到极限。

因为时间充足，我继续基于问题的特点做了优化，最终时间复杂度理论上可以降低到 O(N\log N), 也就是只需要一次排序。

改进 2：

#include<bits/stdc++.h>

using namespace std;

int main() {
    int N, M, t, x;
    cin >> N >> M;
    // 增加 tmp
    int vec[N], ops[N], indices[N], tmp[N];
    deque<int> Deque;
    for(int i = 0; i < N; ++i) {
        cin >> vec[i];
        tmp[i] = vec[i];
    }
    // 先通过一轮单调栈，保存好有效的操作 
    for(int i = 0; i < M; ++i) {
        cin >> ops[i] >> indices[i];
        while(!Deque.empty() && indices[Deque.back()] <= indices[i])
            Deque.pop_back();
        Deque.push_back(i);
    }
    // 只做范围最大的一次排序
    int idx = Deque.front();
    Deque.pop_front();
    if(ops[idx] == 0)
        sort(tmp, tmp + indices[idx], less<int>());
    else
        sort(tmp, tmp + indices[idx], greater<int>());
    // s 记录其实点，e 记录终止点，我们保证数据是按照 s 到 e 的顺序排序的
    int s = indices[idx] - 1, e = 0, last_ops = ops[idx], last_idx = indices[idx], ptr = s;
    while(!Deque.empty()) {
        idx = Deque.front();
        Deque.pop_front();
        // 上次操作之后固定不变的部分
        int nums = last_idx - indices[idx];
        while(nums--) {
            vec[ptr] = tmp[s];
            ptr--;
            if(s > e)
                s--;
            else
                s++;
        }
        // 如果两次操作不一样，则交换起始点和终止点
        if(ops[idx] != last_ops)  swap(s, e); 
        last_idx = indices[idx];
        last_ops = ops[idx];
    }
    int nums = abs(s - e) + 1;
    while(nums--) {
         vec[ptr] = tmp[s];
            ptr--;
            if(s > e)
                s--;
            else
                s++;
    }
    for(int i = 0; i < N; ++i)
        cout << vec[i] << ' ';
    return 0;
}

希望能进面试，早点拿到暑期实习 offer 吧，不然又要 emo 了；

今年太难了，目前已经有快手、小红书、网易云音乐三家简历直接给我挂了。

#春招##实习##笔试题目##笔经##360公司#