一面2020/12/1/14：00（一个小时）

闲聊

1. 自我介绍：只说了学校
2. 实习时间
3. 上一段实习时间（两个月？）

实习经历

1. 实习经历
   • ++++++
   • 用的数据库，mysql

mysql

1. 你一般用的什么存储引擎：默认那个innodb

2. 事务的四种隔离性：

   • 未提交读
   • 提交读
   • 可重复读
   • 序列化

3. 序列化解决了什么问题：幻读

4. 什么是幻读

5. 用什么实现了可重复读：mvcc

6. 具体讲一讲mvcc

   • 版本链
   • 阅读视图

7. 有没有听过**锁：没有

8. 说一下B树和B+树：

   说了相同空间下，B+树的高度比B树矮的优点

9. 只看数据结构呢，从查询的角度：

   B+树更好地进行范围检索

10. B树在什么情况下比B+树要好：。。。不太清楚

11. 知道monngodb吗，它用的B树：只知道名字，没去看过

网络编程

1. 做过网络编程吗：只是看过，但是没有自己实现过
2. 实习中有搭过http服务器吗：没有，实习时间比较短，没有接触过这方面的代码

c++基础

1. 说一说模板和类的区别：说的不太好
2. 指针和引用的区别
   • 指针指向地址，引用自身就是地址
   • 指针是固定8字节大小
   • （提示）指针可以为空，引用声明的时候需要初始化

git

1. 用过git，说一下git的命令：一些简单的，add，commit，push，status这些
2. 知道rebase命令吗：好像是撤回？
3. 不，也是一种merge

linux

1. 用过grep吗：用过，就是过滤
2. grep的过程是怎样的：。。。字符串匹配。。。（不知道咋说了）
3. （提示）：一个递归
4. （继续提示）比如说cat file | grep A | grep B：就是先把全文扫出来，再从结果里面找包含A的，再从结果里面找包含B的。
5. 这是不是像一个漏斗呀，就是管道，知道管道吗：你说的这种管道的概念，我之前没有遇到过

手撕

1. 现在开始写几个题吧，先来一个难一点的（然后面试官小哥很认真的帮我把题目念了一遍，问我题目懂了没）：懂了

2. 我是直接敲代码还是先说思路：先说一说吧

   滑动窗口，一个大小为m的窗口，用哈希统计窗口里面各个字符的数量，然后比较字符数量和m的字符进行比较。如果相同，就是满足条件了

3. 代码（十分钟不到解决了。。。）

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

bool equal(unordered_map<char, int> a, unordered_map<char, int> b) {
    for (auto i: a) {
        if (i.second != b[i.first]) return false;
    }
    return true;
}
int main() {
    string m = "abcd";
    string n = "tbcacbdata";
    unordered_map<char, int> um1, um2;
    int left = 0;
    int right = 0;
    while (right < m.length()) {
        um1[m[right]] ++;
        um2[n[right]] ++;
        ++ right;
    }
    for (; right < n.length(); ++ right, ++ left) {
        if (equal(um1, um2)) {
            cout << left << endl;
            return left;
        }
        um2[n[left]] --;
        um2[n[right]] ++;
    }
    if (equal(um1, um2)) {
        cout << left;
        return left;
    } 
    cout << -1 ;
    return -1;
}

4. 好，我再选一个难一点的题（选了一会），时间复杂度要小于O(n+m)

5. 可以等于O(n+m)吗：不行

6. 用二分吧，先找A数组中的中位数，再到另外一个数组里面去查找这个中位数，然后就可以知道这个数在两个数组里面的位置了。就相当于两个数组合并之后的总的位置，就可以找到了。（面试官反问我的思路）对对，然后再这个下标，就可以知道需要求的中位数是在它左边还是右边了。如果知道它在中位数的左边还是右边，那么就可以进一步的二分。就比如说，它在左边的话，那么可以又从A中中位数的左边，再取中位数，然后再进行相同的操作，最后可以得到总体的它的中位数的位置。

7. 但是最后这个中位数在B数组里面呢：这个是可以逼近的吧，我也会在B里面二分。最后是可以得到一个。。。比如最后只缩进到A里面了，比如说最后A里面只有一个a，一个b，它们是相邻的，但是这两个数都不是中位数。但是这两个数在B里面的位置也是知道的对吧。然后，它肯定就在B里面的这个范围内，是吧。就比如说，你A里面的这个A和B，它们是相邻的。那么我们就可以找到B里面它们的相当于插入的位置是吧。然后插入进行的这个位置里面，这个范围，它那个中位数肯定就在这里面吧。对吧，是吧。

8. 那你这个时间复杂度是多少呢：这个，在A里面二分的复杂度是O(logn)，在B里面二分的复杂度是O(logm)，最后那个。。。就可以忽略不计了吧。最后就是一个logn*logm。

9. 还是挺高的：还是挺高的？

10. 你简单写一下代码吧：（然后和面试官一边讲，一边写，差不多10分钟）

#include <iostream>
using namespace std;

vector<int> a, b;
int binarySearch(vector<int> a, int b, int left, int right) {

}
int find() {

}
int main() {
    int aL = 0;
    int aR = a.size()-1;

    int bL = 0;
    int bR = b.size()-1;
    while (aL < aR) {
        // aN 是中位数的下标
        // c 是中位数
        int aN = find(a, aL, aR);
        int bN = binarySearch(b, c, bL, bR);
        if (aN + bN == (a.size() + b.size()/2))
        if (aN + bN < (a.size() + b.size())/2) {
            aL = aN;
            bL = bN;
        } else {
            aR = aN;
            bR = bN;
        }
    }
    if (aN + bN == (a.size() + b.size()/2)) {

    }
}

反问

• 你们是哪个组呢：游戏中台，业务很杂
• 那主要进行的工作呢：各种后台的工作都有

二面2020/12/3/14: 00/一小时

自我介绍

1. 自我介绍

C++新特性

1. 介绍一下c++11新特性：lambda表达式、智能指针、类型转换、右值引用
2. 什么类型转换：static_cast, const_cast这些
3. 这些和强（制）转（换）有什么区别：封装了错误处理吧，具体的我也不太清楚了
4. 还有其他特性吗（提示：关键字）：哦哦，还有类型推导那个。
5. 可以拼出来吗：de(**)type，中间两个字符不太记得了。。。
6. 那新的遍历方式知道吗：哦哦，auto，它可以直接推断出右边的类型
7. 它有哪些作用呢：它可以在声明、初始化的时候直接推断出类型，不用像以前写迭代器一样写一大串了。遍历也可以像python一样了。
8. 它还能做什么吗：它貌似还能做函数的传递参数？
9. 是吗？：操作好像很复杂，我也不太确定。。。。
10. 常用的智能指针有哪些：unique, share, weak
11. 具体说说它们：unique只能指向一个对象（意识到说错）
12. 对指针还是对象进行约束？：对指针进行约束
13. 开始指正，你的意思是unique只能指向一个对象，指针不能修改；还是说这个对象只能由一个unique指针指向，不能有其他unique指针：不能有其他unique指针
14. 继续说：weak主要是解决share指针的问题，当它们互相指向的时候，。。。我想一想。。。。比如。。。一个。。。额。。厮。。。这个解决的问题主要是它们释放的时候不能完全的把它们的内存释放掉。它具体的那个，我现在可能一下说不出来。
15. 你是不是这个用的比较少：嗯，是的。。

STL

1. 简历上说看过stl源码，问两个问题，string存在栈还是堆中：emmm
2. string s = "abc", “abc”存在哪："abc"应该存在栈上，哦不对，是堆上面
3. 你是怎么想的呢：因为之前在学计算机系统基础的时候，栈主要还是在函数调用的时候搭建的临时的。所以我觉得它应该不在栈上面，应该就是在堆上面
4. 另一道关于string的题（不记得了）：不知道
5. 那你stl源码是看了哪些：vector，list，map，set，优先队列这些。。。。
6. 那你说一说vector<t> v吧：它首先会有一个构造器，会给它分配空间</t>
7. 它的默认空间是多少：这个我不太记得，但是它之后扩展是2倍扩展，然后它会分配它的迭代器嘛，首先它的begin和end，它在声明的时候就是这些吧。
8. 迭代器是怎么动态分配：动态分配？它是会在一开始的时候，比如它一开始的时候是0嘛，就是什么元素都没有的时候，然后后面会根据它的push，然后增加嘛。
9. 它内部元素可以重复嘛：可以重复
10. 它内部实现是什么：数组
11. 它扩容的过程是怎样的：它之前做法应该是把它重新开辟一个空间，空间是原先的两倍，然后把原先的数组移过去，现在的话，应该是用那个右值引用吧。
12. 这里右值引用怎么实现呢：我的理解就是它原先的那块地方不变，变成它现在的。。。。我是这样想的，把它看成一个指针，它原先是指向这的，然后去指向原先的那个空间，就是会被free掉的那个，把它要free那个东西保存下来，就是延长它的声明周期。
13. 那它之前的空间只有它现在的一半，这怎么办呢：这个我就不知道了

操作系统

1. 一个c程序在内存中的地址结构是怎么样的：上面是栈下面是堆，堆里面有代码区、数据区、存静态数据的。
2. 它是在一次性全部分配完的嘛：不是的，它是一个虚拟空间吧。所以它在物理里面的分布就是乱七八糟的吧。然后它是通过一个虚地址转物理地址实现的。所以它在刚开始的时候，就不是一次把所有空间全分配给他，就是说它用到的时候，才分配。
3. 知道缺页中断嘛：比如说它要访问某个数据，这个数据它会去查快表，快表里没有，就去查页面，这个页面就是说电脑在操作系统里面，会把用到的数据一页一页的放到内存里，比如你第一次访问数据，它不在内存里，它就会去磁盘读。
4. 你说了快表，快表的位置在哪：在内存和CPU中间。
5. 快表是在高速缓存吗：是的吧
6. 你确定吗：不确定，撤了一会计算机各个结构
7. 说一下总线吧：IO有一条总线吧，就是外部设备，CPU里面各个寄存器之间也有一条，（这里说了一两分钟吧，没说好）

实习经历

1. 说一下实习经历***
2. **的冲突怎么解决：人为解决

项目经历

1. ++++++++

算法

1. 算法：

   已知城市的东西视图、南北视图，求城市的最大体积和最小体积

   （题目和代码刷新就没了，就不写了）

   • 刚开始的思路是想确定某些可以确定的位置和值
   • 但是想了几分钟，改了思路，不去管他的位置，直接去算他的体积
   • 最大体积：由东西视图，得出一个城市A，行全部变成东西视图的值；由南北视图得出一个城市B，列全部变成南北视图的值。然后遍历两个城市，每个点取最小值，得到最大体积
   • 最小体积：把两个视图的值存到一个集合中。由集合的值a，遍历两个视图，求出两个视图中a出现的次数nums1, nums2。然后ans += max(nums1, nums2)*a

游戏中台三面2020/12/3/15: 05（45分钟）

1. 问基本情况

2. 自我介绍

3. 实习经历

   • 做了什么东西
   • 遇到了什么困难
   • 学到了什么东西

4. 项目经历：

   • 描述项目
   • 有想过怎么改进吗

5. redis

   • 数据结构
   • 说一下跳表
   • 跳表的效率
   • 集群相关（不知道）

6. 写个sql，在某段时间内0109-0111之间，每天的销售额最高的商品（group不熟，其他的写出来了，没写完）

7. 从n大小的数据中等概率取出m个数

   • 讲出了步骤，但是没记住证明过程（面试前看了这道题，但是偷懒没记证明）
   • 面试官：你看过这道题，但是没说出来，这不是很尴尬。。。

8. 重新换道题吧，难一点的

   一个项链三种颜色红白蓝的珠子，从一个地方剪短，从剪断的左边一直取相同颜色的珠子，从右边也取，求最多能取多少个珠子。（白色可以变两种颜色）

   • 我一开始的想法：由于是一个环，所以要预处理一下，再遍历数组，然后求出每一段连续的相同的颜色的珠子数，得到一个数组，然后求数组中，相邻两个数之和的最大值。
   • 给了我15分钟来写：但是我写了一半8/9分钟后感觉这种方法太复杂了，就看了看题，说了一下另一种方法
   • 直接数有多少个，连续的数第一段有多少个，每次数完之后记录前一段有多少个，然后判断前一段加上当前段有没有大于之前的结果，如果大于的话就赋值过去。中间也需要判断白色，中间相邻的一段如果是白色连接的，两段的总和是没有影响的，但是到了下一段是会有影响的。
   • 你时间复杂度和空间复杂度不还是一样吗：空间变了呀，O(1)了呀。
   • 不可能：我只需要记前一个就行了呀
   • 你编好之后发我微信，你已经没时间了

9. 反问

   • 我最需要提升的是哪一块呢：多深入一点
   • 部门：游戏中台

最后附上写好的代码

#include <iostream>
#include <map>
#include <algorithm>
#include <queue>
#include <cstring>
#include <string>
#include <vector>
#include <unordered_map>

using namespace std;


int main(){
    // string s = "wbrrwwrrwwwwwwwwwwbbbwbbwbrrrwwb";
    string s = "rwwwwwwwwwwbwwwwwwwwrwwwwrwwwwwwwwwwbwwwwwwrwwww";
    int n = s.length();

    int first = 0;  // 第一个连续相同颜色数
    int pri = 0;    // 前一个连续相同颜色数
    int cur = 0;    // 当前连续相同颜色数
    int isFirst = 1;
    int ans = 0;

    int head = 0;
    // 找到第一个不是 'w' 的位置head
    while (s[head] == 'w') {
       head = (head + 1)%n;
       if (head == 0) break;
    }
    // 找到head前一个不同颜色的位置
    int cnt = (head-1 < 0)?head+n-1:head-1;
    while (s[cnt] == 'w'||s[cnt] == s[head]) {
        cnt = (cnt-1 < 0)?cnt+n-1:cnt-1;
    }
    // 得到连续相同颜色的第一个非w的位置
    head = (cnt + 1)%n;
    while (s[head] == 'w') {
        head = (head + 1)%n;
        // 计算前面的w数
        cur ++;
    }

    for (int i = head; i != head||isFirst; ) {
        cout << i << ' ';
        int cnt = i;
        int wNums = 0;
        while (s[i] == s[cnt]||s[cnt] == 'w') {
            // 计算末尾连续 w 数
            if (s[cnt] == 'w')
                wNums ++;
            else wNums = 0;
            cur ++;
            cnt = (cnt+1)%n;
        }
        ans = max(ans, pri + cur);
        pri = cur;
        cur = 0;
        if (wNums) {
            pri -= wNums;
            cur += wNums;
        }
        if (isFirst) {
            first = cur;
            isFirst = 0;
        }
        i = cnt;
    }
    ans = max(ans, pri + first);
    cout << endl << ans ;
    return 0;
}

以上都是面试过程中的回答，没有加其他东西，也没有修改错误，有错误的地方欢迎大家纠正！最后许愿offer！
对了，大部分的冒号，左边是面试官，右边是我的回答。个别是反过来，看官自己判断，见谅了。

2020.12.4 更新

二面算法题：lc 807. 保持城市天际线

三面算法题：1752: 项链（注意：这个oj里面这个题的测试样例expected应该是错的，bbwbrrrwbrbrrrrb的expected是5。完全过不了）

再补一个修改过的代码，加了几个特殊情况

#include<bits/stdc++.h>
using namespace std;
int main(){
    // string s = "wbrrwwrrwwwwwwwwwwbbbwbbwbrrrwwb";
    string s = "rwwwwwwwwwwbwwwwwwwwrwwwwrwwwwwwwwwwbwwwwwwrwwww";
    while (cin >> s) {
        // cout << s << endl;
        int n = s.length();

        int first = 0;  // 第一个连续相同颜色数
        int pri = 0;    // 前一个连续相同颜色数
        int cur = 0;    // 当前连续相同颜色数
        int isFirst = 1;
        int ans = 0;

        int head = 0;
        // 找到第一个不是 'w' 的位置head
        while (s[head] == 'w') {
           head = (head + 1)%n;
           if (head == 0) break;
        }
        // 全 w 的情况
        if (head == 0&&s[0] == 'w') {
            cout << n << endl;
            continue;
        }
        // 找到head前一个不同颜色的位置
        int cnt = (head-1 < 0)?head+n-1:head-1;
        while (s[cnt] == 'w'||s[cnt] == s[head]) {
            cnt = (cnt-1 < 0)?cnt+n-1:cnt-1;
            if (cnt == head) break;
        }
        // 只有 w 和另外一种颜色的情况
        if (cnt == head) {
            cout << n << endl;
            continue;
        }
        // 得到连续相同颜色的第一个非w的位置
        head = (cnt + 1)%n;
        while (s[head] == 'w') {
            head = (head + 1)%n;
            // 计算前面的w数
            cur ++;
        }

        int nums = 0;  // 记录有几个连续相同颜色段
        for (int i = head; i != head||isFirst; ) {

            int cnt = i;
            int wNums = 0;
            while (s[i] == s[cnt]||s[cnt] == 'w') {
                // 计算末尾连续 w 数
                if (s[cnt] == 'w')
                    wNums ++;
                else wNums = 0;
                cur ++;
                cnt = (cnt+1)%n;
            }
            ans = max(ans, pri + cur);
            pri = cur;
            cur = 0;
            if (wNums) {
                pri -= wNums;
                cur += wNums;
            }
            if (isFirst) {
                first = cur;
                isFirst = 0;
            }
            i = cnt;
            nums ++;
        }
        ans = max(ans, pri + first);
        // 只有两个连续段，中间还有 w 的情况
        if (nums == 2) {
            for (int i = head-1; s[i] == 'w'; i = (i-1 < 0)?i+n-1:i-1)
                ans --;
        }
        cout << ans << endl;
    }
    return 0;
}