微软(苏州)实习生面试经验

面试时间是19年12月初,一共三轮电话面试,每轮至少两个算法题,第三轮是leader面,前两轮单纯的做题,第三轮在开始做题之前聊了几分钟的天。

下面记录一下面试的过程,其实和网上记录的差不多,就是一直做题。但这毕竟是我第一次正式的面试,还是做点记录纪念一下。

一面

第一个题是“Z字形打印二叉树”,给定一颗树,先打印根节点,从第二行开始先从左到右,再从右到左打印。第一次面试真的有点紧张,刚开始敲键盘的时候手都在抖。这个题其实是《剑指offer》上比较经典的题目了,还好我之前刷了一遍。所以在草稿纸上简单画了一下,就思路就比较清晰,给定两个栈,分别交替存储每层的节点。给面试讲了一下大致思路之后,就开始写代码了,为避免沉默的尴尬,一边写一边给面试官讲具体的思路。具体的代码可以参考牛客网-剑指offer-z字形打印二叉树,这里就不写了。

做完之后面试官让我计算一下复杂度,因为每个元素分别入栈和出栈一次,时间复杂度是O(N)。栈里存储的元素也不会超过N,所以空间复杂度也是O(N)。复杂度的计算感觉要求不是很严格,给出答案后面试官就没说什么,然后继续下一题。

第二题,图相关,找到最大的好友圈。给定N个club,每个club里有人员的ID,找出其中最大的好友圈。什么算好友圈呢, 举个例子比较容易理解:

有3个club,其中每个club拥有的会员如下:

clubI: [1, 2, 3]

clubII: [2, 3, 4]

clubIII: [5, 6, 7]

因为2和3都属于club1和club2,所以1,2,3,4都属于同一个圈子。最大的好友圈数量就是4。

看到这个题的第一反应是深度优先遍历(DFS),要做DFS的话,肯定得用字典,每个key对应一个list,然后遍历就好了。但是怎么设计key和list,还没想好。因为不想让面试陷入太长的尴尬期,就决定开始写。最初的想法是以人员ID作为key,club作为list,遍历每个人拥有的club id,再根据该id遍历该club下的人数,累加起来。但后来发现这种思路的复杂度太高,写起来也比较麻烦,大概写到一半后,面试觉得这样复杂度太高了,让我先停一下,让我算算这样做的复杂度,我估计了一下,没想好,反正就是很高。面试官让我再换个思路,想个简单一点的,我突然脑洞一开,觉得,我把他们每个club当个集合,求下并集和交集不就行了吗?如果两个集合有交集,那就合并,没有交集就不合并,代码很简洁,感觉几行就能写完。突然为自己的脑洞鼓掌....但是面试官又问,这样做的时间复杂度呢?最差的情况每两两集合做交集,这一步复杂度为O(N^2),再求并集,至少O(N^3)。O(N^3)实在太高了,面试官又让我想想简单一点的,但是时间快到了,然后面试官就直接开始指引我了,把每个人的ID当作图的节点,用领接表来表示从一个点到另一个点可达,已经遍历了的点就标记一下,直到所有的点都被标记。面试官最后让我说这个算法的复杂度,我算了算,O(N),确实好多了,代码也不用写了。

最后再问了问面试官部门的业务,然后就结束了。从头到尾面试官都挺和蔼的,感觉很不错。

二面

一面和二面是没有关系的,反正就是换个人来做题。其实我的二面应该是一面,但因为第一天把他放鸽子了,所以HR在第二天重新安排了面试。

感觉比上一个面试官要严肃一点,一来就直接做题,还说,“我们搞快点,尽量在45分钟内结束。”(HR定的是一个小时)。第一个完全没见过,叫格雷码(Gray Code,后来发现leetcode上有原题),传入一个N,要求返回第N行的格雷码。格雷码是这样的:

2: 00 01 11 10

3: 000 001 011 010 110 111 101 100

4: 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000

他和二进制很相像,但是每次只变化一位。

完全没见过这种题(刷的题比较少),真的有点紧张,一开始想从二进制入手,但想了想没思路,于是就想单纯的找规律。看了一会,终于看出规律来了,比如3是由在2的格雷码前面先加个0,再把2反转一下加个1,提炼出来就是G(N + 1) = (0 + G(N)) +(1 + R(G(N)),R表示反转列表。发现规律后就很好写代码了。为了方便,这题直接用python。

first = ["00", "01", "11", "10"]
    dp = {}
    dp[2] = first
    def grayCode(n):
        if n in dp:
            return dp[n]
        else:
            temp = list(map(lambda x: "0" + x, grayCode(n - 1))) + 
                        list(map(lambda x: "1" + x, grayCode(n - 1).reverse()))
            dp[n] = temp
            return dp[n]

之后照例面试官让我讲一下复杂度,如果以N表示位数的话,时间复杂度就是O(N * 2 ^ N),因为反转字符串需要花费2^N,空间复杂度是O(2^N)。这个时间复杂度挺吓人的,但是面试官也没说啥,就继续下一个问题。

由于时间问题,第二个问题面试官没有让我写代码了,只是说下思路和计算复杂度就行。问题是,给定一个整数数组,求子数组的数量,要求子数组的元素个数大于等于2,且顺序不能变。比如[1,2,3,4,5], [1, 2]或[1,3]是他的子数组,但是[2,1]不是。所以不能是简单的排列组合。

我的思路是等差数列的求和,

比如个数为2的时候,计算公式: F(2) = (n - 1) + (n - 2) + (n - 3) + ... +2 + 1 = (n / 2) * (n - 1)

个数为3的时候, 递归,取出第一个元素后,对剩下的子数组又重复上面的计算。

这里感觉不是很严谨,还没有仔细验证,面试官就开始问下一个问题,求所有子数组中的递增子数组中长度最长的数组。

这里想了很久,没有想好,因为面试官先让我算子数组的个数,我潜意识里就以为是已经得到了所有子数组,要比较他们的长度和是否递增。最终还是没有想到解决方案,面试官说没事,面试就这样吧,语气也很友好。到面试快结束的时候才反应过来,其实没必要管所有子数组,只需要在原数组中查找最长的递增子数组就好了,但是具体怎么做也没思路,然后面试就结束了。

后来在leetcode上查了一下,有一个用动态规划的o(N^2)的解法,有个只需要O(NlogN)的解法要用到线段树,就直接放弃了,这里只贴下DP的解法吧:

class Solution(object):
    def findNumberOfLIS(self, nums):
        N = len(nums)
        if N <= 1: return N
        lengths = [0] * N #lengths[i] = longest ending in nums[i]
        counts = [1] * N #count[i] = number of longest ending in nums[i]

        for j, num in enumerate(nums):
            for i in xrange(j):
                if nums[i] < nums[j]:
                    if lengths[i] >= lengths[j]:
                        lengths[j] = 1 + lengths[i]
                        counts[j] = counts[i]
                    elif lengths[i] + 1 == lengths[j]:
                        counts[j] += counts[i]

        longest = max(lengths)
        return sum(c for i, c in enumerate(counts) if lengths[i] == longest)

三面

一二面结束之后就收到了三面的邀请,过了一天就开始三面。网上查的情况大多是三面只做一个题,结果我还是做了两个题。因为终面,面试官是个Leader,感觉得到他很有水平。一开始有个英文的自我介绍,因为有了一面时自我介绍的惨痛教训,所以这里稍微准备了一下,说得比较流利,结果面试官马上就开始英文问问题,聊聊为什么喜欢微软啊,还有项目啥的。没多久我就表示不行了,能不能说中文,他说OK,然后就切换到中文。

然后开始做题,和前两次在线编辑不一样的是,这一次做题让我打开本地的编辑器,他通过远程桌面看我做题。他问我平时用什么语言,我说C++和Python,他就让我用C++,于是我就打开了VSCode。

第一个题目是,写一个函数,验证输入的字符串是否是IPv4。IPv4的要求是有4段,每一段的数字在区间[0,255]内。这个题是蛮简单的,但是他要求我不能用任何STL的函数,string都不行,连字符串转int的方式也要自己写。但是写完之后还让我举出需要用到的测试用例,在不断举例的过程中,发现自己代码里存在着好多bug,最终改了好久,终于改完了。

bool judgeIPV4(char* s) {
    if (!s) return false;
    int digit = -1;
    count = 0;
    while (*s != '\0') {
        if (*s >= '0' && *s <= '9' && digit == -1) {
            digit = 0;
        }
        if (*s >= '0' && *s <= '9' && digit != -1) {
            int temp = *s - '0';
            digit = digit * 10 + temp;
            if (digit > 255) {
                return false;
            }
        } 
        else if(digit == '.') {
            if (digit < 0) {
                return false;
            }
            count += 1;
            if (count > 3) return false;
            digit = -1;
        } else {
            return false;
        }
        s++;
    }
    if (count != 3 || digit < 0) return false;
    return true;
}

这个题从算法上来说比较简单,但是需要考虑的情况很多,好多次我说我觉得没问题了,他还是让我再看看,果然还是有bug。。。最后一个bug是超过int范围了的问题。虽然磕磕碰碰了很久,但是最终还是完成了,又开始下一题。

我刚听到下一题的时候我内心是崩溃的,不是说好的三面只面一个题吗???结果还好,第二题是我见过的,真的是运气好。题目是给定前序遍历和中序遍历,重建二叉树。这个题的核心是知道前序遍历的第一个节点是root,中序遍历中在root之前的节点属于左子树,root之后的属于右子树。

#include<iostream>
#include<vector>
using namespace std;
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x): val(x), left(NULL), right(NULL) {}
};

TreeNode *rebuiltTree(vector<int> pre, vector<int> mid) {
    if (pre.size() == 0) return NULL;
    TreeNode *root = new TreeNode(pre[0]);
    vector<int> left_pre, right_pre, left_mid, right_mid;
    bool flag = false;
    for (int i = 0; i < mid.size(); i++) {
        if(pre[0] == mid[i]) {
            flag = true;
            continue;
        }
        if(!flag) {
            left_pre.push_back(pre[i + 1]);
            left_mid.push_back(mid[i]);
        } else {
            right_pre.push_back(pre[i]);
            right_mid.push_back(mid[i]);
        }
    }
    root->left = rebuiltTree(left_pre, left_mid);
    root->right = rebuiltTree(right_pre, right_mid);
    return root;
}
写完之后,他让我想想这个代码里存在的bug。我举了三种,首先是如果节点值超过了int的范围,第二是递归中占用的内存超过 了堆的限制,第三是如果有重复的元素。。。他问我有重复的元素咋办,我说那就没有办法重建了啊,他笑了笑说就这样吧,这也是一个待验证的问题。

面试结束后不久就收到了hr电话,通过了


#微软##实习##C++工程师##面经#
全部评论
中文还是英文
点赞 回复
分享
发布于 2020-02-19 23:38
微软实习给多少钱一个月 还有就是大佬你是怎么准备算法的
点赞 回复
分享
发布于 2020-02-19 23:45
百信银行
校招火热招聘中
官网直投
大佬,你这是暑期实习?还是春招实习?
点赞 回复
分享
发布于 2020-02-20 05:13
恭喜大佬!
点赞 回复
分享
发布于 2020-02-20 10:48
楼主请问无法用英语交流的话能投微软吗😅
点赞 回复
分享
发布于 2020-02-20 14:10
这也太强了吧
点赞 回复
分享
发布于 2020-02-20 16:44
楼主面的是苏州还是北京
点赞 回复
分享
发布于 2020-02-20 20:51
好友圈那个咋做呀,不太会图,求大佬分享下
点赞 回复
分享
发布于 2020-02-21 00:00
电话面试咋做算法求问
点赞 回复
分享
发布于 2020-02-21 00:05
微软面试只做题不问其他的吗?
点赞 回复
分享
发布于 2020-02-21 23:40
lz写的好详细!谢谢!
点赞 回复
分享
发布于 2020-03-13 06:24
其实ip那个题可以用scanf输入,scanf("%d.%d.%d.%d",&a,&b,&c,&d);  这样输入就可以直接判断abcd了
点赞 回复
分享
发布于 2022-04-08 16:00

相关推荐

招聘对象:2025届毕业生(2024年11月-2025年10月毕业)招聘岗位:基础平台研发工程师,负责分布式查询引擎内核模块的架构设计、开发、测试、性能调优等工作。base地点:杭州/上海&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;阿里云表格存储是一款分布式结构化数据存储的多模型数据库,诞生于&nbsp;2009&nbsp;年阿里云成立时,在&nbsp;2014&nbsp;年正式商业化面向公共云提供服务,最主要特点是分布式、Serverless、按量付费、水平扩展和查询功能丰富等。历经&nbsp;10&nbsp;余年的打磨,目前已在阿里巴巴集团、阿里云公共云以及专有云内得到广泛应用,涵盖电商、金融风控、物联网、人工智能、大数据、社交媒体等不同业务领域,支撑钉钉、优酷、手淘、IoT、计算平台等多个内部核心&nbsp;BU&nbsp;和业务。&nbsp;&nbsp;&nbsp;&nbsp;表格存储丰富能力的背后,依赖底层的两大引擎:表格引擎和分布式查询引擎。分布式查询引擎团队近年来发展迅速,在&nbsp;Serverless、多租户隔离、稳定性、高性能、成本方面投入了大量精力,取得了不少成果,相对于业界开源产品在稳定性、安全、性能和成本方面都有很大优势,团队技术水平在业界属于前列。&nbsp;&nbsp;&nbsp;&nbsp;团队内的工作内容主要是分布式查询引擎内核的架构设计、开发等。团队有良好的新人培养机制,为实习生分配两位师兄,同时也会定期组织技术交流,讨论技术进展和相互学习。队内氛围融洽,沟通协作便捷高效,每个同学都能在有挑战的事物中挖掘自己的价值,期待志同道合的同学加入我们。岗位要求1.&nbsp;需要熟练掌握&nbsp;Java、C++、Rust&nbsp;语言中的至少一项,了解关键功能的实现最好。2.&nbsp;计算机类或者软件类专业,拥有扎实的计算机基础知识,包括计算机体系结构/网络/操作系统/数据库/并发编程等。3.&nbsp;以下内容为加分项,对其中一项或者多项熟悉甚好:&nbsp;&nbsp;a.&nbsp;对分布式系统/存储/高可用等领域有兴趣,或有相关的背景/经验,例如&nbsp;Elasticsearch、Lucene、HBASE、Cassandra、Clickhouse、Presto、Influxdb等等。&nbsp;&nbsp;b.&nbsp;了解分布式原理,例如CAP理论,RAFT、PAXOS等分布式一致性算法。&nbsp;&nbsp;c.&nbsp;学习过6.824/6.828/DDIA。&nbsp;&nbsp;d.&nbsp;参加过&nbsp;ACM-ICPC&nbsp;竞赛,获得过金牌或银牌。投递方式私戳&nbsp;or&nbsp;邮箱投递(pdf格式:姓名-学校-学历)&nbsp;#阿里云##阿里巴巴##实习##校招#
点赞 评论 收藏
转发
17 130 评论
分享
牛客网
牛客企业服务