3-27微软笔试

之前报名了ms的暑期实习，然而已经拿了阿里的offer，就拿笔试练练手，分享给大家，为秋招攒攒人品和经验

笔试成绩

微软的笔试成绩由以下两个方面组成：

• 正确性(Correctness)：你的算法得出的结果是否正确
• 性能表现(Performance)：你的算法的时间复杂度和空间复杂度是否最优

这场笔试总体来说不难，感觉在leetcode的easy~medium之间，贴上我的笔试评测结果：

Task1

求最大的非负数连续子序列之和

// online-algorithm，时间复杂度O(N)；空间复杂度O(1)
int solution(vector<int>& A) {
    // write your code in C++14 (g++ 6.2.0)
    int n = A.size();
    int i = 0;
    int max_sum = -1;
    int sum = 0;
    // 要求是连续非负子序列的和
    while (i < n) {
        // 如果遇到负数，则将当前的累计和sum清零，并到下一个数字重新计算累计和
        if (A[i] < 0) {
            i = i + 1;
            sum = 0;
            continue;
        }
        // 如果没遇到负数，则当前累计和sum加上当前遍历到的值A[i]，并顺便查看最大和max_sum是否要更新
        sum += A[i++];
        max_sum = max(max_sum, sum);
    }
    return max_sum;
}

Task2

题目有点长...本质上就是让你求图中任意相连两点的度的最大值

sample 1: A = [1,2,3,3], B = [2,3,1,4], N = 4, output = 4

sample 2: A = [1,2,4,5], B = [2,3,5,6], N = 6, output = 2

// 本质上就是图中任意相连两点的度的和中的最大值
// 时间复杂度O(M)，M为A or B数组的size；空间复杂度O(N)，N为节点总数
int solution(vector<int>& A, vector<int>& B, int N) {
    // write your code in C++14 (g++ 6.2.0)
    vector<int> degree(N + 1, 0);

    int M = A.size();
    for (int i = 0; i < M; i++) {
        degree[A[i]]++;
        degree[B[i]]++;
    }
    int result = 0;

    // 优化：只有M对节点是相连的
    for (int i = 0; i < M; i++) {
        result = max(result, degree[A[i]] + degree[B[i]] - 1);
    }

    return result;
}

Task3

给一个只由A, B, C, D组成的字符串，并且具备以下转换方式：

• 和B相邻的A，两者可以一起被删除
• 和D相邻的C，两者可以一起被删除

请问给你一个字符串S，使用上述规则直至字符串无法再进行任何转换，最终的字符串是什么？

思路：利用栈，新元素和栈顶元素符合上述条件的，则将栈顶元素pop出，否则push入新元素

// 时间复杂度O(N)，只需要遍历一遍字符串即可；空间复杂度O(N)，栈的容量要足够保存字符串的大小
string solution(string &S) {
    // write your code in C++14 (g++ 6.2.0)
    int n = S.size();
    if(n <= 1){
        return S;
    }

    string result = "";
    int i = 0;
    while(i < n) {
        if(result.empty()) {
            result.push_back(S[i]);
        } else if(S[i] == 'A' && result.back() == 'B') {
            result.pop_back();
        } else if(S[i] == 'B' && result.back() == 'A') {
            result.pop_back();
        } else if(S[i] == 'C' && result.back() == 'D') {
            result.pop_back(); 
        } else if(S[i] == 'D' && result.back() == 'C') {
            result.pop_back();
        } else {
            result.push_back(S[i]);
        }
        i++;
    }

    return result;
}