2022春天的实习面试经历

本文最后更新于:2022年5月24日 下午

目前已经接到微软的实习offer,所以将之前的面试内容都贴在这里了

2022.02.28 微软实习正式批一面

  • 面试时长:约45分钟
  • 面试经过:
    1. 面试官自我介绍
    2. 我的自我介绍
    3. 根据简历上面问了一下项目和本科毕业之后的经历
    4. 写了一道算法题:数组中的逆序对数目(归并排序,平衡树,树状数组或线段树)
      参考:数组中的逆序对
      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
      #include <bits/stdc++.h>

      using namespace std;

      int handle(vector<int>& vec){
      int ret = 0;
      int sz = vec.size();
      if(sz <= 1) return 0;
      int mid = sz / 2;
      vector<int> vec1, vec2;
      vec1.insert(vec1.end(), vec.begin(), vec.begin() + mid);
      vec2.insert(vec2.end(), vec.begin() + mid, vec.end());
      ret += handle(vec1);
      ret += handle(vec2);
      vec.clear();
      int pos1 = 0, pos2 = 0;
      while(pos1 < vec1.size() or pos2 < vec2.size()){
      if(pos1 < vec1.size() and pos2 < vec2.size()){
      if(vec1[pos1] > vec2[pos2]){
      ret += vec1.size() - pos1;
      vec.push_back(vec2[pos2++]);
      }else{
      vec.push_back(vec1[pos1++]);
      }
      }else if(pos1 < vec1.size()){
      vec.push_back(vec1[pos1++]);
      }else if(pos2 < vec2.size()){
      ret += vec1.size() - pos1;
      vec.push_back(vec2[pos2++]);
      }
      }
      return ret;
      }

      int main(){
      vector<int> arr{7,6,8,3,5};
      int ans = handle(arr);
      cout << ans << endl;
      vector<int> brr{9,8,7,6,5,4,3,2,1};
      vector<int> crr{1,2,3,4,5,6,7,8,9};
      vector<int> drr{1, 1};
      cout << handle(brr) << endl;
      cout << handle(crr) << endl;
      cout << handle(drr) << endl;
      return 0;
      }
    5. 场景题:考虑在一个短链接生成系统中,如何设计短链接生成。
    6. 反问:简历有没有什么问题

2022.03.01 字节跳动飞书实习一面

  • 面试时长:约28分钟

  • 面试经过:

    1. 自我介绍
    2. 问了一下之前在百度实习的项目的内容
    3. C++的面向对象的特点
    4. 多态的实现形式
    5. 讲一讲Python语言和C++语言的区别
    6. 三次握手的过程
    7. 保证TCP传输的可靠性的实现
    8. 浏览器输入网址之后的过程
    9. C++虚函数,纯虚函数,虚析构函数
    10. C++的vector的底层实现
    11. 智能指针(用过,但是不太熟。直接说没怎么用)
    12. 线程和进程
    13. 虚拟内存
    14. 进程调度的状态
    15. 写个代码:给定一个query字符串,和pattern字符串,问能不能在pattern字符串中插入若干个小写字母,使得query串和pattern串一致。
    query pattern 结果
    FoolBar FB true
    FoolBarTest FB false
    FoolBar FBa true
    FoolBar FaB false
    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
    #include <bits/stdc++.h>

    using namespace std;

    bool match(string query, string pattern){
    int n = query.size(), m = pattern.size();
    int i = 0, j = 0;
    while(i < n or j < m){
    if(i < n and j < m){
    if(query[i] == pattern[j]){
    i++;
    j++;
    }else if(islower(query[i])){
    ++i;
    }else{
    return false;
    }
    }else if(j < m){
    return false;
    }else if(i < n){
    if(isupper(query[i]))
    return false;
    ++i;
    }
    }
    return true;
    }
    int main(){
    cout << match("FoolBar", "FB") << endl;
    cout << match("FoolBarTest", "FB") << endl;
    cout << match("FoolBar", "FBa") << endl;
    cout << match("FoolBar", "FaB") << endl;
    return 0;
    }
    1. 反问:没什么问题

2022.03.04 微软实习正式批三面

备注:一面和二面是平行的,一面通过之后就没有二面了。

  • 面试时长:约36分钟
  • 面试经过:
    1. 我的自我介绍
    2. 问了下在百度实习的情况
    3. 写一道算法题
      类似的题目:单字符重复子串的最大长度
      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
      /*

      Given an array with around 100K elements, each element is within [0,100K ], how to get maxsubsequencelength with same value if you have a opportunity to swap two elements?

      2 2 3 1 4 5 1 1 0 1 7 => 4

      */
      #include <bits/stdc++.h>
      using namespace std;
      typedef pair<int, int> PII;
      int solve(vector<int> arr){
      if(arr.size() == 0) return 0;
      map<int, vector<PII>> mp;
      int n = arr.size();
      int cur = 0;
      for(int i = 0; i < n; ++i){
      if(arr[i] != arr[cur]){
      // cur, i - 1
      if(mp.count(arr[cur])) mp[arr[cur]].push_back({cur, i - 1});
      else mp[arr[cur]] = {PII{cur, i - 1}};
      cur = i;
      }
      }
      if(cur < n){
      mp[arr[cur]].push_back({cur, n - 1});
      }
      int ans = 1;
      for(auto& [_, vec]: mp){
      if(vec.size() == 1){
      auto& it = vec.front();
      ans = max(ans, it.second - it.first + 1);
      }else if(vec.size() == 2){
      auto& it1 = vec[0];
      auto& it2 = vec[1];
      if(it1.second + 2 == it2.first){
      ans = max(ans, it2.second - it2.first + 1 + it1.second - it1.first + 1);
      }else{
      ans = max(ans, it1.second - it1.first + 2);
      ans = max(ans, it2.second - it2.first + 2);
      }
      }else{
      int m = vec.size();
      ans = max(ans, vec[0].second - vec[0].first + 2);
      for(int i = 1; i < m; ++i){
      ans = max(ans, vec[i].second - vec[i].first + 2);
      if(vec[i - 1].second + 2 == vec[i].first){
      ans = max(ans, vec[i].second - vec[i].first + 1 + vec[i - 1].second - vec[i - 1].first + 1 + 1);
      }
      }
      }
      }
      return ans;
      }

      int main(){
      cout << solve({2, 2, 3, 1, 4, 5, 1, 1, 0, 1, 7}) << endl;
      cout << solve({2, 2, 2, 1, 2, 2, 2}) << endl;
      cout << solve({2, 2, 1, 2, 2, 2}) << endl;
      cout << solve({2, 1, 2, 2, 1, 2, 2, 2}) << endl;
      cout << solve({2}) << endl;
      cout << solve({}) << endl;
      return 0;
      }
    4. 有三枚硬币,指定一种得到1/7概率的情况。
    5. 反问:部门情况

2022.03.08 字节跳动飞书实习二面

  • 面试时长:约60分钟
  • 面试经过:
    1. 自我介绍

    2. 介绍下在百度实习的项目

    3. 介绍下去年做的项目

    4. 讲讲几种设计模式

    5. 写个单例

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      class Config{
      private:
      Config(): ptr(nullptr){}
      void update(string s){
      delete ptr;
      ptr = new string(s);
      }
      string query(){
      if(ptr == nullptr) ptr = new string("123");
      return *ptr;
      }
      };

      static int val = 0;
      int query(){
      return val;
      }
      void update(int x){
      val = x;
      }
    6. 说一下数据库的隔离模式

    7. 开放性问题:讲一下如何考虑操作系统拷贝一个文件

    8. 开放性问题:word文档如何单词纠错

    9. 算法题:一维接雨水

      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
      class Solution {
      public:
      int trap(vector<int>& height) {
      vector<int> st1, st2;
      vector<int> pref(height.size());
      int n = height.size();
      pref[0] = height[0];
      for(int i = 1; i < n; ++i){
      pref[i] = pref[i - 1] + height[i];
      }
      for(int i = 0; i < n; ++i){
      while(!st2.empty() and height[i] >= height[st2.back()]) st2.pop_back();
      st2.push_back(i);
      }
      for(int i = n - 1; i >= 0; --i){
      while(!st1.empty() and height[i] >= height[st1.back()]) st1.pop_back();
      st1.push_back(i);
      }
      reverse(st1.begin(), st1.end());
      reverse(st2.begin(), st2.end());
      int ans = 0;
      for(int i = 1; i < st1.size(); ++i){
      int curp = st1[i], prep = st1[i - 1];
      int ts = height[prep] * (curp - prep - 1) - (pref[curp - 1] - pref[prep]);
      ans += ts;
      }
      for(int i = 1; i < st2.size(); ++i){
      int curp = st2[i], prep = st2[i - 1];
      int ts = height[prep] * (prep - curp - 1) - (pref[prep - 1] - pref[curp]);
      ans += ts;
      }
      int tl = st1.back(), tr = st2.back();
      ans += (tr - tl) * height[tl] - (pref[tr] - pref[tl]);
      return ans;
      }
      };
    10. 反问:部门情况和面试流程

2022.03.10 蚂蚁集团大安全技术部实习一面

备注:电话面试,感觉闲聊为主

  • 面试时长:约25分钟
  • 面试过程:
    1. 面试官自我介绍
    2. 我的自我介绍
    3. 询问百度实习经过
    4. 一顿闲聊
    5. 重载函数的规则和底层实现
    6. const关键字
    7. malloc、free和new、delete
    8. delete和delete []
    9. 函数的调用约定(参数的入栈顺序)
    10. vector扩容
    11. 什么情况下vector的迭代器会失效(扩容和删除元素)
    12. 动态库和静态库(没写过)
    13. 跨平台开发
    14. 本科和研究生之间的gap
    15. 有空去做下笔试(补充,3月14日完成笔试)
    16. 反问:没啥问题
    17. 面试官再介绍了一下蚂蚁和阿里

2022.03.14 字节跳动飞书实习三面

  • 面试时长:22分钟
  • 面试经过:
    hr面,主要了解下个人情况和职业规划等。
    本来是视频面,因为通讯不好,改成电话面试。

2022.03.16 美团实习一面

备注:主动终止流程

2022.03.29 Hulu实习一面

  • 面试时长:60分钟
  • 面试经过:
    1. C++虚函数是怎么实现的
    2. struct和class区别
    3. C和C++区别
    4. 除了面向过程和面向对象,你还知道其他编程思想吗
    5. 说一下inline
    6. 选个项目讲一下
    7. 写个题吧
      给定一个正整数nn,计算出满足一下条件的整数nn的个数:1<k<n1 < k < n,并且kkk+1k + 1具有相同个数的的正因数。
      比如1414的正因数有(1,2,7,14)(1, 2, 7, 14)1515的正因数有(1,3,5,15)(1, 3, 5, 15)k=14k=14满足条件。(3n107)(3 \leq n \leq 10^7)
      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
      // 面试的时候只想到基于调和级数的O(n*log(n))的算法,这里补充一下O(n)的算法
      // 基于线性筛,http://oi-wiki.com/math/number-theory/sieve/#_10
      #include <vector>
      #include <iostream>
      using namespace std;
      vector<int> SieveOfEuler(int n){
      vector<int> ret(n + 1, 0); //约数个数
      vector<int> vis(n + 1, 0); //是否访问标记
      vector<int> prime; // 质数表
      vector<int> num(n + 1, 0); // 最小质数因子出现次数
      ret[1] = 1;
      for(int i = 2; i <= n; ++i){
      if(!vis[i]){
      vis[i] = 1;
      prime.push_back(i);
      ret[i] = 2;
      num[i] = 1;
      }
      for(auto& it: prime){
      if(n / it < i) break;
      vis[it * i] = 1;
      if(i % it == 0){
      num[i * it] = num[i] + 1;
      ret[i * it] = ret[i] / num[i * it] * (num[i * it] + 1);
      break;
      }else{
      num[i * it] = 1;
      ret[i * it] = ret[i] * 2;
      }
      }
      }
      return ret;
      }
      int main(){
      int n = 1e7;
      auto&& res = SieveOfEuler(n);
      int ans = 0;
      for(int i = 1; i <= n; ++i){
      if(res[i] == res[i - 1]){
      ++ans;
      }
      }
      cout << ans << endl;
      return 0;
      }
    8. 面试官介绍了一下部门情况

2022.04.11 Hulu实习二面

  • 面试时间:60分钟
  • 面试经过:
    1. 自我介绍一下
    2. 讲一下之前的百度实习项目
    3. 先写个题吧
      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
      // 有两个没有刻度的水桶和一个蓄水量无限的水池,一个容量为x升,
      // 另一个容量为y升,每次取水/倒水视为一次操作,现需要量出z升水
      // Q1:能否实现
      // Q2:最少需要多少次操作
      #include <iostream>
      #include <vector>
      #include <queue>
      #include <map>
      #include <algorithm>
      #include <numeric>

      using namespace std;
      typedef tuple<int, int, int> TII;

      int solve(int x, int y, int z) {
      if (z % gcd(x, y) != 0) return -1; // 不可实现
      queue<tuple<int, int, int>> Q;
      map<tuple<int, int, int>, int> mp;
      tuple<int, int, int> ini{0, 0, 0};
      mp[ini] = 0;
      Q.push(ini);
      while (!Q.empty()) {
      TII it = Q.front();
      Q.pop();
      if (get<2>(it) == z) {
      return mp[it];
      }
      auto[tx, ty, tz] = it;
      TII nex1{x, ty, tz}; // 将水从池子中灌入到x容器中
      TII nex2{tx, y, tz}; // 将水从池子中灌入到y容器中
      TII nex3{min(tx + ty, x), max(0, tx + ty - x), tz}; // 将水从y容器灌入到x容器中
      TII nex4{max(tx + ty - y, 0), min(tx + ty, y), tz}; // 将水从x容器灌入到y容器中
      TII nex5{tx, 0, tz}; // 清空y容器
      TII nex6{0, ty, tz}; // 清空x容器
      TII nex7{0, ty, tz + tx}; // 将水从x容器中灌入到z
      TII nex8{tx, 0, tz + ty}; // 将水从y容器中灌入到z
      vector<TII> nexs{nex1, nex2, nex3, nex4, nex5, nex6, nex7, nex8};
      for (auto &nx: nexs) {
      if (!mp.count(nx) and get<2>(nx) <= z) {
      mp[nx] = mp[it] + 1;
      Q.push(nx);
      }
      }
      }
      return -1;
      }

      int main() {
      cout << solve(1, 2, 3) << endl;
      cout << solve(2, 2, 1) << endl;
      cout << solve(2, 2, 2) << endl;
      cout << solve(2, 2, 0) << endl;
      cout << solve(3, 1, 2) << endl;
      return 0;
      }
    4. 那就再写个题吧
      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
      67
      68
      69
      70
      71
      72
      73
      74
      75
      76
      77
      78
      79
      80
      81
      82
      // 在电影院中有一排座位,0代表空,1代表已经有人在座位上了,现在又来了2个人,因为疫情需要,把它安排某个没人的座位上,使任意两人直接距离最大,返回其中最短的距离。(座位足够的情况下)

      // 以下是面试的时候和面试官讨论的情况:
      // 所有区间两边都有人 - 要么做一个区间,要么两个不同区间
      // 有1-2个一边没有人的区间
      // 只有一个空区间
      #include <string>
      #include <iostream>
      using namespace std;
      // 求左右端点都是1的最小的区间和最大三个区间的长度
      tuple<int, int, int, int> subSolve(const string& str){
      assert(str.front() == '1' and str.back() == '1');
      int cur = 0;
      int max1 = 0, max2 = 0, max3 = 0;
      int ans = INT_MAX;
      auto&& update = [&](int val){
      if(val > max1){
      max3 = max2;
      max2 = max1;
      max1 = val;
      }else if(val > max2){
      max3 = max2;
      max2 = max1;
      }else if(val > max3){
      max3 = val;
      }
      };
      for(int i = 1; i < (int)str.size(); ++i){
      if(str[i] == '1'){
      if(i - cur > 1){
      update(i - cur);
      }
      ans = min(ans, i - cur);
      cur = i;
      }
      }
      return {ans, max1, max2, max3};
      }
      int solve(string str){
      if(str.front() == '1' and str.back() == '1'){ // 左右端点都是1的情况
      auto [minv, mx1, mx2, mx3] = subSolve(str);
      return min(minv, max(mx1 / 3, mx2 / 2));
      }else if(str.front() == '1'){ // 左端点是1的情况
      auto rPos = str.find_last_of('1');
      if(rPos == 0){
      return (int)(str.size() - 3 - rPos) / 2 + 1;
      }else{
      auto [minv, mx1, mx2, mx3] = subSolve(str.substr(0, rPos + 1));
      int len = str.size() - 1 - rPos;
      int tmpv = solve(str.substr(0, rPos + 1));
      int ttv = min(len - 1, min(minv, mx1 / 2));
      return min(minv, max((int)(str.size() - 3 - rPos) / 2 + 1, max(tmpv, ttv)));
      }
      }else if(str.back() == '1'){ // 右端点是1的情况,翻转一下字符串,就得到了上面的一种情况
      reverse(str.begin(), str.end());
      return solve(str);
      }else{ // 左右端点都是0的情况
      auto lPos = str.find_first_of('1');
      if(lPos == string::npos){ // 没有1的情况
      return str.size() - 1;
      }else{ // 有1的情况
      int rPos = str.find_last_of('1');
      int candinate = min(str.size() - rPos - 1, lPos);
      auto tmp = max(solve(str.substr(0, rPos + 1)), solve(str.substr(lPos)));
      if(lPos != rPos){
      auto [minv, x1, x2, x3] = subSolve(str.substr(lPos, rPos - lPos + 1));
      candinate = min(candinate, minv);
      }
      return max(candinate, tmp);
      }
      }
      }

      int main(){
      cout << solve("1000100001") << endl;
      cout << solve("10000000000000100101") << endl;
      cout << solve("1000001001") << endl;
      cout << solve("0000010001") << endl;
      cout << solve("000000000010001") << endl;
      cout << solve("000100000000000000000") << endl;
      return 0;
      }

2022.05.06 Hulu实习三面(寄)

  • 面试时间: 90分钟
  • 面试经过:
    1. 自我介绍
    2. 聊一下百度实习的Contributions
    3. 问了一下简历上第二个项目的情况
    4. 了解Redis吗
    5. 问了一下消息队列的熟悉情况
    6. 最后还有很多时间,写个算法题:八数码
      这个题通常有三种解法:1,朴素BFS;2.双向BFS;3.A*算法。其中可以用康托展开来保存访问状态。(再也不敢说康托展开是useless了)
      然后面试的时候,凭着对康托展开微弱的印象,现场手搓,果然搓不出来(寄)。
      然后A*又忘记怎么求八数码的估价。
      然后一紧张,忘记能双向BFS优化一下。
      最后面试官说时间不多了,10分钟写完bfs草草下机(寄)。

2022.05.18 Hulu实习四面(寄)

2022.05.18 Hulu实习五面(寄)

最后补充一下笔试情况

  • 微软:3道编程题,全部完成。代码细节可以优化,时间复杂度无法优化。
  • 字节跳动:内推免笔试
  • 美团:5道编程题,第二题只过了55%,其余都做出来了
  • 阿里巴巴:3道编程题,全部做出来了
  • 亚马逊:3道编程题,全部做出来了
  • Hulu:3道编程题,全部做出来了

2022春天的实习面试经历
https://dianhsu.top/2022/05/11/intern-interviews/
作者
Dian Hsu
发布于
2022年5月11日
许可协议