y4oung's Studio.

微软面试

面经
Word count: 3.5kReading time: 13 min
2020/07/28 Share

北京微软E+D面试小记

最早投递还是4月份的时候，当时投递的是北京的Cloud+AI部门，因为是正式开始了summer intern，所以先走的笔试流程。题目比较变态，做了前两题，但也没有AC。最后理所当然地挂在了笔试上。当时发了一封邮件给我，问我要不要转岗到苏州CSS面试，查了一下这个职位主要以解决用户的技术问题为主，开发只是其中的一小部分。考虑到个人的技术提升空间，遂拒绝。

之后闲来无事，看到官网放出了E+D下面的MMX部门的移动开发岗位，于是又投递了一份简历。因为招聘答疑群里说不能再次投递相同类型的岗位（SWE），并没有多想。后来的某一天，接到了E+D这边打来的电话，问我要不要面试一下，欣然接受。

在4月底的某一天，连续安排了两轮平行面试。这两面的印象不是很深了，主要流程是自我介绍，一些简单的基础知识考察，然后就是算法题。

4月一面

第一题

题意：移动一个链表，按照input中的数字，将后n位的节点依次移动到链表头。

1
2
input: a->b->c->d->e 2
output: d->e->a->b->c

思路：这题比较简单，首先遍历一遍链表，计算长度，然后用输入的n除以链表长度去余，避免循环移动。然后用两个指针的移动来找倒数第n个节点的上一个节点。可以参考（剑指Offer第22题）。之后断开这两个节点的连接，将尾节点指向链表头即可。主要还是以考虑corner case为主。

第二题

这题是个偏实际问题的场景题，比如C++中有两种类型的注释，单行注释（//）和范围注释（/* */），给定一个代码文件，要求是把两种类型的注释全部删除。本质是个正则匹配问题吧。当时考虑的两种模式，一种是按行读取，去做字符匹配，遇到//就把当前该行从//开始的字符串都删除，这个不涉及到跨行问题。对于范围注释，如果遇到了就继续读下一行，直到匹配结束符为止。这里当时代码实现的时候，有很多的循环嵌套和判断，写的有点崩溃。具体原因好像是因为每次只读一行，然后同时又要进行删除操作。所以后面又思考了一下一次全部读入整个文件内容的方式，这里也存在文件过大的问题。耗了很长时间，没有很好的解决。

事后考虑了一下，这里可以用栈来存储吧，对满足条件的行依次压栈，最后统一来清除。也搜了一下解法，具体也没做记录，是个比较麻烦的事情，好像可以考虑用KMP算法或者有限状态机。

4月二面

二面紧接着一面进行，也是简单问了项目经历，然后就算法了。这次就写了一个题，时间上用的比较久。

给定一个数组，问数组中的元素两两组队能否构成倍数关系。

1
2
input：[1,2,3,6]
output: true

思路：没有去查最优解。我猜我的思路应该也不是。主要就是先升序排序，然后用twoSum的思路去做。用hashmap来存该元素和他的倍数，倍数作为key，在循环中依次去匹配数组元素。匹配成功就在hashmap中删除，遍历完后hashmap为空，则能满足要求。

主要是考虑了几个follow up，一是数组元素存在重复的问题，[1,1,2,2,3,6],对key-value的结构做了变更，value存储配对的对数。若大于1，则匹配成功一次就减1，为0时删除键值对。二是考虑负数存在的情况，这时候倍数关系要倒置。修改了两次代码，基本时间就差不多了。

这个根据我用的hashmap这个集合，面试官又追问了一下怎么解决哈希碰撞，以及链表过长的查询效率问题等等，简单说了下JDK1.8引入红黑树的思路。可能他想考察的是我的设计思路吧。

差不多就是这样的两面，个人感觉除了一面的注释删除问题没答好，其他都还算positive，后悔没有催一下hr更新进度，然后也不知道是他们忘发据信，还是什么原因，就没有消息了。

时间来到了7月，此时我已经在字节实习了两个月了。Microsoft官网投递的Action Center状态突然变了，又通知我继续面试。我以为是他们想起来了，打算三面，很是惊喜。没想到昨天一面的时候傻了。这又是一次平行面，restart from the beginning. 于是今天又结束了平行二面。很快地发来了thank you letter。
还是先记录一下内容。

7月一面（7.27）

两个题，基本都是剑指Offer原题或者比较类似的题。

第一题一开始是判断链表是否有环，快慢指针答完之后，follow up是计算环的长度。这个当时被自己的思维绕进去了，局限在剑指23题的思路上，一直在考虑两个节点走过的路径长度关系，证明环外长度和相遇节点到换入口节点长度的相等。虽然给出了思路，但是面试官觉得过于复杂。经过提醒，在假定有环的条件下，让慢节点再走一圈记录长度即可。一个注意点是考虑节点值的重复，所以要判断节点是否相等。

第二题是原题了，就是旋转数组的最小数字，这题刚看过，于是很快就说出了二分的思路，本来打算写上元素有重复case的代码，时间上不太够了，面试官说太复杂先不考虑了。于是假装没复习过的样子，思考着写完了代码，然后就结束了。

相比于4月份的面试，这次有一些对基础的考察，面试官对java是比较熟悉的，问了一些对Java GC的理解，哪些可以作为GCRoots，描述一些垃圾回收算法的过程，java并发，JUC包之类的问题。之前看面经的时候还是比较熟的，实习了两个月，记得不是很清楚了，有部分问题没怎么答好。

7月二面（7.28）

上来信号不是很好，说话听不太清，就改打电话了。自我介绍完了先开始写题。不做过多描述，内容都在下面了。主要就是一个IP段合并的问题，思路是字符串去掉.号再转long类型，然后直接可以比较区间大小。有一些不太好处理的地方，比如string转long，这里面试官说太麻烦了，就不要实现了。结束了思考了一下，这里有一些问题，首先是需要填充0，否则大小比较有的会出问题。然后是1.1.1.255和1.1.2.0这两个怎么来判断是相邻的。我提了疑问，面试官说当他们是数值+1关系来处理。还有一个是最后转回string的时候，如果有填充0的话，好像判断不了哪些是填充的0，转化存在问题。这些在面试过程中，都被略过了，因为不要求实现。结束了思考之后觉得，只能维护一个转化的对应关系吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
We have a lot of IP segments, but some of the entries can be merged together:
1.1.1.1 - 1.1.1.255
3.1.1.1 - 4.2.3.4
1.1.2.0 - 1.1.2.200
1.1.2.100 - 1.1.2.255

The list above can be merged into:
1.1.1.1 - 1.1.2.255
3.1.1.1 - 4.2.3.4

Write a function to merge this list.

How is time complexity for your code?

class IpPair{
    long left;
    long right;
}

public void ipMerget(String[] list){
    List<String> resultList = new ArrayList<>();
    List<IpPair> ipList = new ArrayList<>();
    for(String ip:list){
        String[] str = ip.split(" - ");
        long left = strToLong(str[0]);
        long right = strToLong(str[1]);
        IpPair pair = new IpPair(left,right);
        ipList.add(pair);
    }
    Collections.sort(new Comparator<>(o1,o2)->(o1.left-o2.left));
    long leftCur = ipList.get(0).getLeft();
    Long rightCur = ipList.get(0).getRight();
    for(int i=1;i<list.size();i++){
       long leftNow = ipList.get(i).getLeft();
       if(rightCur > leftNow){
           long rightNow = ipList.get(i).getRight();
           leftCur = rightNow > rightCur?rightNow:rightCur;
       }else if(rightCur < leftNow){
           if(rightCur+1 == leftNow){
               rightCur = rightNow;
           }else if(rightCur < leftNow){
               String res = longToStr(leftCur)+" - "+longToStr(rightCur);
               resList.add(res);
               leftCur = leftNow;
           }
       }
   }
   return resList;
}
        
        
public long strToLong(String s);

可能我这样做不是最优解，也忘记去问面试官这题他给出的解法。除开这些，代码里很多bug，语法错误。当时面试官说我考虑了一个case，当时没仔细想，同意了他的观点。现在重写了一下代码，发现我考虑了，有点悲伤。下面贴一下优化过的版本吧。照例还是没实现两个类型转化的函数，仅仅示意。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
public class ipMerget {
    public List<String> ipMerget(String[] list){
        List<String> resultList = new ArrayList<>();
        List<IpPair> ipList = new ArrayList<>();
        for(String ip:list){
            String[] str = ip.split(" - ");
            long left = strToLong(str[0]);
            long right = strToLong(str[1]);
            IpPair pair = new IpPair(left,right);
            ipList.add(pair);
        }
        Collections.sort(ipList,(o1,o2)-> (int) (o1.getLeft()-o2.getLeft()));
        long leftCur = ipList.get(0).getLeft();
        Long rightCur = ipList.get(0).getRight();
        for(int i=1;i<ipList.size();i++){
            long leftNow = ipList.get(i).getLeft();
            long rightNow = ipList.get(i).getRight();
            if(rightCur > leftNow){
                rightCur = rightNow > rightCur?rightNow:rightCur;
            }else if(rightCur < leftNow){
                if(rightCur+1 == leftNow){
                    rightCur = rightNow;
                }else{
                    String res = longToStr(leftCur)+" - "+longToStr(rightCur);
                    resultList.add(res);
                    leftCur = leftNow;
                }
            }
        }
        return resultList;
    }

    public long strToLong(String s){
        return Long.parseLong(s);
    }

    public String longToStr(Long s){
        return String.valueOf(s);
    }
}

class IpPair{
    long left;
    long right;

    public IpPair(long left,long right){
        this.left = left;
        this.right = right;
    }

    public long getLeft() {
        return left;
    }

    public void setLeft(long left) {
        this.left = left;
    }

    public long getRight() {
        return right;
    }

    public void setRight(long right) {
        this.right = right;
    }
}

今天还考察了一些其他的问题：

  1. android activity的生命周期（大致说出来了）
  2. android中的内存泄漏问题怎么解决（这个没看面经，也没具体实践过，当时写android app没注意过这个问题）
  3. 给1000个url，怎么判断新给的url在不在已存在url范围内？（答了用hashset来判重，问还有没有别的办法，说了布隆过滤器，不是很满意，然后过了。下来同学说可以用前缀树，想了下还是比较有道理的）
  4. 说昨天查了下我的资料，看到了可能是我的博客，里面有前缀树啥啥的（说了下我是有博客，但没有写过前缀树的文章。细思极恐，这个难道是来提示上一个题的吗，忽略过去了）
  5. 问了一个场景题，如何设计北京地铁查询乘坐路径的系统（大意是答了设计地铁类，站点类，班次类等等。用户输入起始点，目的地和出发时间，根据这几个值做查询，后面讲到了缓存。以及如何查询处在几条不同线路上的起始点和终点，答怎么找站点交点。后面还问了路径长短的问题，建立站点的距离网络来处理。还有考虑线路是环线，正反方向的问题，还有某一方向到点停运，线路节假日停运的问题，以status字段来判断）。考虑得很粗糙，没有考虑设计模式等问题，答得比较杂，想到哪说到哪。

总结

收了感谢信之后，立马找hr问了下评价，被拒理由如下：

average coding skills and average problem solving skills. Algorithm: Below average.

就我自己的感觉而言，4月份的coding其实还可以，除了正则匹配这个不好，没大问题，不知道为什么没后续了。昨天题写得挺好的，就是一开始把自己的思路绕进去了，没转过弯。今天代码思路还行吧，但是结束后的检查离bug free差的太远，被拒也是理所当然。其实实习了一段时间之后，题也没怎么刷了，基础知识也没看了，很生疏。特别是白板编程吧，像Comparator那里，突然忘记怎么写了，事实也是确实写错了。问题还是很大，路还很长。

字节的实习确实给了自己一种虚荣的假象，感觉自己各方面能力能达到大厂的要求了。实际上并不是，可能只是运气好，也可能3-4月份的复习是有成效。可现在的我一无所有，不仅基础和coding退化了，也没有很多的工程能力长进。这次的面试也挺好，给自己提了个醒。仍然需要保持技术的热情，好好看并发、spring、中间件、架构的书籍，然后保持coding的熟练度。

一点彩蛋

今天的面试官在听到我是浙大的之后，问我是在宁波校区还是杭州校区。名义上，他也算是我的学长了。问了我的导师名字，然后笑成他们认识。面试终了，好奇再问了一下，他们是一届的同学。也不知道该不该高兴，好像给导师丢脸了。他们作为相识的同学，也没有给一点偏袒。就这样吧，个人还是非常喜欢微软的面试。重点考察逻辑思维，算法能力，和编程技巧，而弱化技术、语言在面试中的占比。希望之后的某一天有机会可以加入吧。

Author：Qian Yang

原文链接：https://foxliveray.github.io/2020/07/28/%E5%BE%AE%E8%BD%AF%E9%9D%A2%E8%AF%95/

发表日期：July 28th 2020, 1:45:11 pm

更新日期：July 28th 2020, 4:53:42 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 北京微软E+D面试小记
    1. 1.1. 4月一面
      1. 1.1.0.1. 第一题
      2. 1.1.0.2. 第二题
  2. 1.2. 4月二面
  3. 1.3. 7月一面（7.27）
  4. 1.4. 7月二面（7.28）
  5. 1.5. 总结
  6. 1.6. 一点彩蛋
Total : 5
2021
2020
杂记 面经 奇技淫巧