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

简历面

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

一面

1. 说说 const char *ptr 和 char const *ptr的区别 （常量指针和指针常量的区别）
2. 写出一个包含以下元素的结构体的大小

    char a;
    char b;
    double c; 
    int d; 

   （这个的考点是字节对齐）
3. static的作用 （静态变量、内部函数）
4. 宏和inline区别 （直接替换和内联）
5. 说说纯虚函数和虚函数 （C++基础常识，纯虚函数看成是一个接口）
6. new和malloc区别（经典八股了，要知道 new 是调用的 malloc）
7. 说出以下代码每行的作用和运行结果

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

8. 手撸算法：最大子矩阵和，我是用 的做法写出来的（代码在下面）
9. 口述算法：N个数，有一个数出现超过N/2，寻找这个数 （一个栈去维护，和栈顶相同就进栈，不同就出栈）
10. 口述算法：链表倒数第K数（老算法题了）
11. 静态链接库和动态链接库的区别（编译时加载和运行时加载）
12. epoll和select的作用（IO多路复用，虽然我没用过，但是我会背八股啊）
13. 手撸多线程编程题：队列取数和放数交替操作（代码在下面）
14. 聊项目，因为自己的项目是实现了一个小的关系型数据库，正好这是数据库内核组，于是就.........被花式吊打
    这里有一个面试官教我的，假如数据库写日志的时候突然断电，这时候硬盘里的数据是不完整的，你怎么保证你这个日志是能用的 （校 验 码）

    二面

15. 聊大一时候的图像检索的项目
16. 聊数据库这个项目
17. 聊聊数据库的 ACID 是怎么个实现方法，锁可以实现吗？（S2PL + MVCC 实现）
18. 手撸算法题：
    按段（段内的元素不翻转）翻转链表：如链表 1->2->3->4->5->6->7->8->9，如果段大小为3，翻转后为7->8->9->4->5->6->1->2->3。
    注意段大小作为参数传入。要求编写可以运行的测试用例（有main函数和足够的测试集），注意代码规范。

三面

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

四面（交叉面）

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

五面（hr面）

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

个人代码

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

内存分配器

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

// 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;
}