2022届暑假实习微软面经总结

2月底投的简历，大部门是上海C+AI，3.12-14笔试，2小时3道英文算法题 

题目1：给定一个数组S代表每辆车的座位数，数组P代表以及坐在该车上的乘客数，求最少需要几辆车运送所有乘客 
排个序再贪心 

题目2：给定一个数组代表一堆石头的高度，青蛙只能从一个石头跳到高度大于等于该石头的相邻石头上，两只青蛙从同一个石头向相反方向跳，求两只青蛙之间的最远距离 
用dp求出每个石头从该石头出发的最大非递减子数组长度inc和在该石头结束的最大非递增子数组长度dec，最远距离则为max(inc[i]+dec[i]-1) 
题目3：一个由0和1组成的二维数组，两行n列，给出第一行、第二行以及每列元素的和，通过这些信息还原出数组内容 
先还原都为0和都为1的列，再根据剩下的两行的情况处理 

满分通过了笔试，大约一周后收到面试邀请，在3.29下午连续进行一二面 
微软的一二面是平行面，只要通过了其中一轮就可以，有些部门会先发一面邀请，挂了再给二面机会，C+AI则是直接发出两面的邀请 

一面： 

中文自我介绍 
问项目 
三次握手和四次挥手 
hashmap和红黑树 
算法题：给定一个整数数组，求出该整数数组能拼接得到的最大整数 
这道题的核心思路是把整数按照”字典序“排序，所以把所有数都可以当作字符串处理，这个排序的关键是处理一个数字是另一个数字的前缀的情况 
举个例子，59应该放在591前面，而596又应该放在59前面 
但是当时脑子没转过弯来，写了一个及其丑陋的递归比较函数，如下 

	def cmp(a,b):
    if a>b:
        if len(a)>len(b) and a[:len(b)]==b:
            return cmp(a[len(b):],b)
        return True
    if a<b:
        if len(b)>len(a) and b[:len(a)]==a:
            return cmp(b[len(a):],a)
        return False
    return a>b
    
标准答案是这样： 

def cmp(a,b):
    return a+b>b+a
    
因为面试官不熟悉python，而且这个递归比较函数实在是很不直观，我花了很多时间解释代码并且测试正确性，整个面试就只做了这一道题，不知道一面评价如何 

二面： 

1.中文自我介绍 
2.线程调度的算法 
3.tcp和udp 
4.数据库的ACID 
5.c++的stl以及各种数据结构 

这一段问了特别多，从vector，list，map，unordered map一路问过去，数据结构和c++的具体实现都有涉及，我就从顺序表到红黑树都讲了 
八股文环节耗时有点久，这时面试已经过去快半个小时了，于是这一面也只有一道算法题旋转数组，需要新数组和原地旋转的两种都写了 

3.30收到lead面邀请，3.31lead面： 

中文自我介绍 
深挖实习内容，最终暴露了我之前的实习完全是curd的事实 
接下来可能算得上是传说中的系统设计题，给一个一元多项式，探讨各种储存这个多项式的方法 
我就从数组，链表，哈希表，二叉树之类的各种方法都讨论了一下，每提出一种方法都要和面试官探讨使用这个方法的优缺点，从储存空间，查找速度，修改等方面都要涉及，指针大小之类的的细节都要考虑到 
然后是写一个基于二叉树的多项式的类，要求实现初始化，加法乘法运算和打印结果的几个函数 

lead面面试完一周后4.7收到信息收集邮件，4.14收到offer 
