微软暑期实习笔试分享

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

Graph from the example 1 with chosen vertices marked.

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

Graph from the example 2 with chosen vertices marked.

// 本质上就是图中任意相连两点的度的和中的最大值
// 时间复杂度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;
}
#微软##笔经##C++工程师#
全部评论
1 3题跟我的一样
点赞 回复
分享
发布于 2021-03-30 09:20

相关推荐

12 53 评论
分享
牛客网
牛客企业服务