面经｜微软暑期实习｜一面｜萌新体验大厂面试（已凉）

11897

2022.03.09

发布于未知归属地

微软一面 - 2022.3.7 GG

自我介绍
- 我有点草率，就单一点讲太多了，也没有跟面试官互动
- 大概几分钟吧，面试官也比较干脆，于是说，那就上题目？
- 然后就开始写题了……
三门问题
- 面试官本意是想让我写随机模拟
- 哪知道我直接用古典概型给他求精确概率，应该给他整无语了
- 个人感觉应该很扣分吧，没有 get 到他的点，就自顾自己的写了一堆代码，会不会觉得我不擅长沟通😫
- 所以加考了个求 $π$

class Solution {
public:
    bool choose(vector<int> doors, int id) {
        return (doors[id] == 1);
    }

    bool newChoose(vector<int> newDoors) {
        int i = 0;
        if (newDoors[i] == -1)i++;
        return (newDoors[i] == 1);
    }
};

int test1() {
    Solution sol = Solution();
    vector<int> doors1{1, 0, 0};
    vector<int> doors2{0, 1, 0};
    vector<int> doors3{0, 0, 1};
    int cnt = 0;
    if (sol.choose(doors1, 1)) cnt++;
    if (sol.choose(doors2, 1)) cnt++;
    if (sol.choose(doors3, 1)) cnt++;
    printf("P1=%lf\n", cnt / 3.0);

    cnt = 0;
    vector<int> newDoors1_1{1, 0, -1};
    vector<int> newDoors1_2{1, -1, 0};
    vector<int> newDoors2_1{-1, 1, 0};
    vector<int> newDoors2_2{0, 1, -1};
    vector<int> newDoors3_1{-1, 0, 1};
    vector<int> newDoors3_2{0, -1, 1};
    if (sol.newChoose(newDoors1_1)) cnt++;
    if (sol.newChoose(newDoors1_2)) cnt++;
    if (sol.newChoose(newDoors2_1)) cnt++;
    if (sol.newChoose(newDoors2_2)) cnt++;
    if (sol.newChoose(newDoors3_1)) cnt++;
    if (sol.newChoose(newDoors3_2)) cnt++;
    printf("P2=%lf\n", cnt / 6.0);
}

利用随机函数，求 $π$
- 思路倒是好想，也给面试官分享了才开始写的
  - 构造一个 $1 \times 1$ 的正方形，内切一个 $\frac{1}{4}$ 圆
  - 在正方形内，随机一个坐标，模拟多次
  - 统计，使用频率来模拟概率，求出 $P (圆内) = \frac{π}{4}$
  - 进一步求出 $π$
- 面试时没搞清 C++ 自带函数 $rand()$ 的返回值的范围，写出了 $bug$
- $rand() \in [0, RAND_MAX]$
- 面试时，由于对随机生成数取了模数 $N = 1 e 6$ 大于了 $RAND_MAX = 65536$
- 所以，其随机数范围不是 $[0, N)$
- 最后也没能 Debug 出来，故 GG
话说为什么面完就秒想通？？？下面是正确代码

int main() {
    srand((unsigned) time(NULL));
    int N = 1e7, cnt = 0, R = 1e6;
    for (int i = 0; i < N; i++) {
        double a = (1.0 * rand() / RAND_MAX);
        double b = (1.0 * rand() / RAND_MAX);
        if (a * a + b * b < 1.0) cnt++;
    }
    printf("%lf", (4.0 * cnt) / N);
    return 0;
}

微软二面 - 2022.3.9 补试

自我介绍
- 这次详细些了（大概相互问答有十几分钟？忘记看时间了），面试官小哥哥好温柔
- 我没有扎很深在某个点过多的介绍了，主要是总体先介绍自己
- 然后让面试官提感兴趣的点，再展开
- 个人特点，接触编程早，中学，大学也仍然参加竞赛
- 项目经验少
做题部分
- 这个面试官喜好面试者手K代码（免编译，不用自动补全，静态Debug）
- 其实对我来说没啥问题，但还是紧张的
问题一（lower_bound()）二分查找，对于排序的数组（小到大），求下边界
- 由于一开始紧张，头脑一片空白，条件写反好几次
- 然后面试官引导我手动 debug, 跑样例
- 最后终于改对了🤣，不晓得会不会印象分掉得比较多
- 然后问的问题是关于这个函数的一些隐藏 bug 和修改建议
  - 空数组
  - 数组长度接近 int 上限
  - 优化，找到下边界，提前返回
  - 数组不包含目标元素
  - 后面两个是面试官引导我，我才想到的🤣
  - 位运算会快一点，面试官说，然后顺手改了，小哥哥很喜欢优化呀😁同道中人

    int lower_bound(vector<int>&arr,int target){
        int n=arr.size();
        if(n==0){
            return -1;
        }
        int l=0,r=arr.size()-1;
        while(l<r){
            int mid=l+((r-l)>>1);
            if(arr[mid]==target && arr[mid-1]!=target && mid-1>=0) return mid;
            if(arr[mid]>=target)r=mid;
            else l=mid+1;
        }
        if(arr[l]==target)
            return l;
        return -1;
    }

问题二剑指 Offer 58 - I. 翻转单词顺序
- 基于时间关系，没写代码但是说了思路
- 栈实现
- 空间优化，原地实现，翻转两次
- 时间复杂度：均为 $O (N)$
- 空间复杂度：
  - 栈 $O (N)$
  - 两次翻转 $O (1)$

后记

革命尚未成功，同志仍需努力