阿里云后台开发面经（已OC）

@[toc]
写在前面，供大家参考。
阿里巴巴的提前批会有很多组出来提前捞人，所以建议大家先多投几个组（因为都是私下里面试，不会进阿里的招聘系统，相当于白嫖面试）。而且组与组之间信息是独立的，你在这个组挂了不会影响其他组的面试结果。
我就是面了很多组，也通过了不少组，然后和心仪的组谈要求（再面一轮再进系统）- -最后选了个组进系统。

简历面

编译器是怎么优化的（O1，O2 优化分别干了什么，常量折叠、内联处理等等）
C++程序有哪几个段（和操作系统差不多，无非是堆区、栈区、text段等等）
可以只有堆没有栈吗（函数的调用是通过栈去实现的，在硬件级的支持下用栈可以增加效率）
vector内存是咋分配的（这个记一下是按照2的指数级分配的，如果不够了就分配到下一个2的指数级数字上去）
知道线程池吗（balabala 自己的项目里面实现过一个线程池，这个在百度上搜一下就能搜到不错的答案）
手撸内存分配器
通过一个数组来管理资源，需要使用时从数组中分配一个成员，使用完毕后从数组中释放该成员，释放后的成员可以被再次分配使用；请实现一个结构用来快速的对资源进行分配和释放。
（这个题目的难度在于 free 以后的要能被再次利用，这个其实操作系统里面已经给了很多不错的方法，我是用一个空闲链表实现的）

一面

说说 const char *ptr 和 char const *ptr的区别（常量指针和指针常量的区别）
写出一个包含以下元素的结构体的大小
```
 char a;
 char b;
 double c; 
 int d; 
```
（这个的考点是字节对齐）
static的作用（静态变量、内部函数）
宏和inline区别（直接替换和内联）
说说纯虚函数和虚函数（C++基础常识，纯虚函数看成是一个接口）
new和malloc区别（经典八股了，要知道 new 是调用的 malloc）

说出以下代码每行的作用和运行结果

char *p = (char *) malloc(10); 
sizeof(p)= 4
free(p+1)

手撸算法：最大子矩阵和，我是用 $O(n^3)$ 的做法写出来的（代码在下面）
口述算法：N个数，有一个数出现超过N/2，寻找这个数（一个栈去维护，和栈顶相同就进栈，不同就出栈）
口述算法：链表倒数第K数（老算法题了）
静态链接库和动态链接库的区别（编译时加载和运行时加载）
epoll和select的作用（IO多路复用，虽然我没用过，但是我会背八股啊）
手撸多线程编程题：队列取数和放数交替操作（代码在下面）
聊项目，因为自己的项目是实现了一个小的关系型数据库，正好这是数据库内核组，于是就.........被花式吊打
这里有一个面试官教我的，假如数据库写日志的时候突然断电，这时候硬盘里的数据是不完整的，你怎么保证你这个日志是能用的（校验码）
二面
聊大一时候的图像检索的项目
聊数据库这个项目
聊聊数据库的 ACID 是怎么个实现方法，锁可以实现吗？（S2PL + MVCC 实现）
手撸算法题：
按段（段内的元素不翻转）翻转链表：如链表 1->2->3->4->5->6->7->8->9，如果段大小为3，翻转后为7->8->9->4->5->6->1->2->3。
注意段大小作为参数传入。要求编写可以运行的测试用例（有main函数和足够的测试集），注意代码规范。

三面

Linux系统怎么看cache的相关信息（在一个系统文件里，自己研究哈）
什么情况下内容会存进cache，怎么看cache的内容（计算机里为什么需要cache的存在呢，解决内存和cpu速度不匹配的情况）
聊项目。。。日常数据库
算法题1：找二叉树最深的节点
算法题2：遍历二叉树最底层的节点
算法题3：在一个无向图中，如何判断两点是否联通
算法题4：在一个有向图中，如何判断两点是否联通
上述四个题都是 DFS/BFS 解的，效率基本都差不多。
这一面还是比较简单的，几个算法题就是dfs、bfs来回考，判联通可以用并查集操作一下。

四面（交叉面）

聊项目（面试官似乎不是数据库的，打哈哈）
进程和线程区别（必背八股！）
进程间的通信方式（管道、信号量、锁、消息队列等等）
如何调试C++多线程程序（GDB，切 thread）
聊人生

五面（hr面）

自我介绍
自己擅长什么不擅长什么
聊聊ACM经历（自己带了两年的 acm 队，总会有些感悟的）
说说自己的学校怎么样（知乎没名份水平）
自己成绩怎么样（勉强凑活）
人生最大的挫折是什么（高考崩了）

个人代码

因为阿里伯乐写代码是有存档的，所以就贴一下方便大家指教。

内存分配器

//通过一个数组来管理资源，
//需要使用时从数组中分配一个成员；
//使用完毕后从数组中释放该成员，释放后的成员可以被再次分配使用；请实现一个结构用来快速的对资源进行分配和释放。

// 10000这种数字是跟面试官沟通以后随便写的
class memory_manage {
public:
    obj* m_malloc() {
        obj* p = nullptr;
        if(l.size()) {
            p = l.front();
            l.erase(l.begin());
        } else if(cur<10000) {
            p = &arr[cur++];
        }
        return p;

    }

    void m_free(obj* p) {
        l.push_back(p);
    }

private:
    obj arr[10000];
    int cur = 0;
    list<obj*> l;
};

最大子矩阵和

N * N

-10 1 2 3
2 3 4 -100
1 2 3 5
0 0 0 0

K*M
和最大的子矩阵

O(N^2)
第一步：矩阵前缀和O(n^2)
第二步：遍历子矩阵O(n^4)

int a[N+2][N+2];
int sum[N+2][N+2];

void FindMax(int n) {
    int cur = 0,ans = 0;
    memset(sum,0,sizeof(sum));
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            sum[i][j] = sum[i-1][j] + a[i][j];
        }
    }
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            cur = 0;
            for(int k=1; k<=n; k++) {
                cur = cur + (sum[j][k]-sum[i-1][k]);
                if(cur<0) cur = 0;
                else ans = cur;
            }
        }
    }
    return ans;
}

多线程题

mutex g_mutex;
condition_variable cv;
queue<int> q;
bool flag = 0; // 0放，1取

int get() {
    lock_guard<mutex> mtx(g_mutex);
    cv.wait(mtx,[] {return flag==1;});
    int val = q.front();
    q.pop();
    flag = 0;
    cv.notify_one();
    return val;
}

void put(int val) {
    lock_guard<mutex> mtx(g_mutex);
    cv.wait(mtx,[] {return flag==0;});
    q.push(val);
    flag = 1;
    cv.notify_one();
    return;
}

#面经##阿里云##C++工程师#