微软苏州 7.9 onsite面经

刚刚面完微软苏州，在动车上写的这篇面经。
今天下午一共面试了4轮，明天早上还有一轮online 面试。

Round 1:
写一个函数来判断，过去任意一秒内来自同一ip的请求是否超过100次，如果超过，则返回该ip地址。
    这是一道我原来在地里见过的题目，当然可以用unordered_map 来完成，key是ip，value是存着来自该ip地址的所有请求的timestamp。来了一个ip之后，就去判断1秒内的请求数量是否超过100，如果超过100，就存在一个unordered_set里面（因为只要过去任意1秒内，同一ip地址的请求超过100次，之后请求，都认为该ip是bad ip）;
    第二种方法是用循环数组来判断，我一提到用循环数组，面试官就叫我马上实现循环数组这个类。这个我没有完成的很好，所以第一轮感觉一般；

Round 2:
给你一个长方体和一个点p(x,y,z),求这个长方体表面以及体内，离点p最近的那个点，并且返回坐标。
     反正第一眼看到这个题目，我是一点头绪都没有的。但是幸好面试官给了一些提示，然后一步一步的引导我，最后才实现一个方法。首先面试官让我实现一个类，来表示这个长方体，确定这个长方体的坐下点坐标在（0，0，0），然后类的构造函数给了长，宽，高分别为a,b,c，我就用a,b,c来表示了其他七个顶点。
     后面面试官提示降维操作。相当于先处理x，假设（minX，maxX）是长方体的x的范围。如果x < minX,则说明最短距离点在左侧面，如果x>maxX,则说明最短距离点在右侧面，如果 x>=minX && x <= maxX,则说明最短距离点在相对应x的横切面，然后就相当于求一个面到一个点的距离最短的点；

Round 3:
给一个二叉树，然后求二叉树中有祖先和子代关系的节点之间的差值的绝对值最大的是多少。要求时间复杂度O(n);
    dfs的一道题目。用minVal,和maxVal来保存之前祖先节点的最小和最大值，遍历到当前节点，res = max(res,abs(node->val-minVal)), res = max(res,abs(node->val-maxVal)), 然后更新minVal和maxVal;


Round 4:
给两个正int数，a和b，然后求a%b,不能用乘法和除法。
     首先用的方法是
     while(a>b){
         a = a - b;
     }
     return a;
   就是一直减b直到a<b,但是面试觉得每次只减一个b有点慢，在面试官的提示下，每次减完之后，如果a还大于，就把b<<1 ,左移一位，相当于乘以2，如果a == 0，就返回0，如果 a<0了，就把a在加上此时的b，然后b>>1，再重新进入循环。直接贴代码：
  int getMod(int a,int b){
     if(b == 1)
        return 0;
     int ob = b;
     while(a > ob){
          int t = a - b;
          if(t>0){
              a = t;
. ----              b = b<<1;
             }
         else if(t == 0){
              return 0;}
        else {
            a = t + b;
            b = b>> 1;}
}
     return a;
  }


当然后面面试叫我写几个测试案例，觉得b = b << 1有可能要超过INT_MAX,所以写了一个函数，如果b<<1超过INT_MAX就维持b不变，如果没有超过，就返回b<<1;


因为这轮面试的是team leader,所以在这道题之后，还询问了一些其他问题。比如说你如何实现百度地图，如果存储数据；你遇到了哪些眼前一亮的产品体验等等。

总结来说，第一轮面试，我觉得发挥的有点糟糕，因为这是一道看过的题目，不应该出现问题。（可能就是因为看过，所以就想着去回忆做法，而不去想如果解决）。其他的问题在面试的提示下，都算能实现解法。

明天早上还有一轮面试，因为把面经发出来，能给我带来好运。

如果觉得有帮助，也可以赞助点大米。






. 1point3acres







补充内容 (2019-7-10 09:41):
今天的第五轮面试被取消了，不知道地里的人有没有遇到过类似的情况。大概率感觉是挂了

补充内容 (2019-7-11 09:18):
因为前面几轮面试不佳，所以第五轮boss面就被取消了。反思过后，觉得一轮面试中，基本上要pass两道题，才可能得到positive

循环数组 arraydeque  应该就是 循环数组实现的index =  (head+1)%(n-1)  , n = len(arr), 但是 没有明白  循环数组实 和 判断 同一个ip请求超过有什么关系?

楼主循环数组还是维护一个ip到长度为100的数组的map嘛？新ip访问过来，指针循环可以指向数组中最久的访问。不知道理解的对不对

预祝楼主拿到offer

crystal0309 发表于 2019-7-11 08:07
. check 1point3acres for more.楼主，第五轮是aa面吗？除了算法，还问ood之类的吗？

第五轮应该不是AA面，看网上说有很多面了6轮

楼主你好，祝你明天面试成功，请问这是校招吗？

楼主，谢谢分享。求一个面到一个点的距离最短的点，怎么做？

有结果了记得更新哈

楼主，第五轮是aa面吗？除了算法，还问ood之类的吗？

请问楼主现在还可以投简历吗？

同+1，被取消第五轮面试，不过我是直接问了hr，面完就知道结果了

是否有一轮英文面试呢请问？

楼主面的是什么组呢？