2022微软上海C+AI SWE暑期实习面经(已OC)

2022.2.21 微软上海C+AI 暑期实习正式批SWE

0.代码模板

先放一个我写算法题的cpp模板，面试的过程中我都是用这个模板来写的，里面还细分了各种题型专用的模板。

repo:https://github.com/Jiahui-Gu/CPPTemplate

一面（2022年2月21日上午11点）

1.聊天部分

面试官因为上一场面试迟到了20多分钟，这种其实是好事，因为面试官多少会带点歉意。

开头先自我介绍，我说到我之前在xx公司实习过，面试官追问我在那边实习感觉开心吗。

他说他面了很多人都在这个公司实习过，问我这个公司在什么位置。

问我本科是什么学校的，延伸出来是哪里人等等一系列问题。

聊的挺开心的，都快忘了是技术面试了。。。

最后问我刷LeetCode吗（可能因为我专业不是计算机），我说天天刷，昨天还打了周赛。

2. 算法题

我要发一个正整数，但是我键盘的一个数字键(2-9的其中一个数字)坏了，需要把这个正整数拆成两个正整数来发送，保证两数之和为先前的数字，同时拆分的两数都不包含坏数字，比如输入233，3坏了，应当返回222和11。

/*************************************************
Author: GuJiahui
Date: 2022-01-10
Description: CPPTemplate
*************************************************/

#include "base.h"
int main(){
    string s = "233";//输入数字
    char c = '3';//坏数字
    string add = "";//额外数字
    for(int i = 0; i < s.size(); i++){
        if(s[i] != c){
            if(add.size() != 0) add.push_back('0');
            continue;
        }
        s[i]--;
        add.push_back('1');
    }
    cout<<s<<endl;
    cout<<add<<endl;
    return 0;
}

3.反问

问了下部门的常用语言，面试官说基本用c#，不过面试对语言没要求。

其实才面了30分钟，但是因为面试官的迟到，已经要12点了，所以就没问了，大家都去吃饭吧。

二面（2022年2月22日上午11点）

1. 聊项目

开头先自我介绍，我说到我之前在xx公司实习过，之前实习参与了两个系统，问了我这两个系统的关联。

问了之前实习很多非技术的细节，估计是考察是否真的参与了项目（10分钟，还挺深入的）。

问我mq是如何工作的，之前公司mq的权限管理是咋样的（因为我简历里写了mq）。

2. 算法题

有效的数独https://leetcode-cn.com/problems/valid-sudoku/ 的改版，比原题要难一点点。

题目：给你一个长宽都为size的二维矩阵，矩阵的元素取值区间为[0,size]，其中0表示这里没有数，其他数字表示这里的数值，问这个二维矩阵是否满足数独的条件。

/*************************************************
Author: GuJiahui
Date: 2022-01-10
Description: CPPTemplate
*************************************************/

#include "base.h"
bool isValid(unordered_map<int, bool>& m, int num){
    if(num == 0) return true;
    if(m.find(num) != m.end()) return false;
    m[num] = true;
    return true;
}

int main(){
    int size = 9;//数独边长
    int smallLen = sqrt(size);//小方格边长
    if(smallLen * smallLen != size) return 0;

    vector<vector<int>> v = {};//输入的数独二维矩阵

    //每行是否符合规则
    for(int i = 0; i < v.size(); i++){
        unordered_map<int, bool> m;
        for(int j = 0; j < v[i].size(); j++){
            if(!isValid(m, v[i][j])) return 0;
        }
    }

    //每列是否符合规则
    for(int j = 0; j < v[0].size(); j++){
        unordered_map<int, bool> m;
        for(int i = 0; i < v.size(); i++){
            if(!isValid(m, v[i][j])) return 0;
        }
    }

    //每小格是否符合规则
    int raw = 0, col = 0;//小格的左上角点的坐标
    for(int i = 0; i < size; i++){
        unordered_map<int, bool> m;
        for(int dr = 0; dr < smallLen; dr++){
            for(int dc = 0; dc < smallLen; dc++){
                if(!isValid(m, v[raw+dr][col+dc])) return 0;
            }
        }
        col += smallLen;
        if(col >= size){
            col = 0;
            raw += smallLen;
        }
    }

    return 1;
}

问假设数独size=n的时空复杂度，答：时间最坏最好平均都是o( $n^2$ )，空间最好o(1)最坏o( $n$ )
ps:现在想想时间复杂度不太对，时间应该是最好o(1)，最坏o( $n^2$ )，不过当时面试官是肯定了我的答案的，估计他也没想到。

代码没跑，因为输入太难弄了，面试官肉眼debug

3.反问

Q: 我要面二面是一面没过吗？

A: 一面过没过都要二面，但只要过一个就能终面

Q：暑期实习hc有多少？
A：不知道

2022年2月23日上午12点收到终面邮件

三面（2022年2月25日上午10点）

面试官迟到10分钟，5分钟的时候打电话来说等他一会，为此还埋下了伏笔。。

1.项目（30分钟）

负责了哪些部分。

最困难的事。

以及一些细节。

项目问的时间太长了。。。

2.算法

算法题1

题目：给你nums数组，在其所有可能的全排列中，等概率返回一个。

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]中的一个

一开始没写出最优解(往蓄水池抽样想去了)，面试官说问可以原地吗？才写出了最优解

题解：

/*************************************************
Author: GuJiahui
Date: 2022-01-10
Description: CPPTemplate
*************************************************/

#include "base.h"

int main(){
    vector<int> num = {1,2,3,4};
    int lo = 0;
    while(lo < num.size()){//4
        int randIndex = rand(lo, nums.size())// rand函数返回[lo,nums.size())间的一个非负整数
        swap(nums[lo++], nums[randIndex]);
    }
    return 0;
}

Q:时空复杂度?

A:时间o(n)，空间o(1)

Q:如果这个函数是一个黑盒，你要如何证明它是等概率返回的？

A:测试一万次，看分布