阿里 ICBU C/C++ (暑期实习生) 一面+二面经验
个人经历
大一参加微信小程序获西北赛区二等奖（队长身份）
ACM-ICPC 两银一铜 ACM-CCPC:两铜 CF-rating: 1900+，18年暑假开始搞ACM
C++项目经历：无，只有课设（黑窗口）
略懂前端，自己搭过博客，做过一两个小的项目（微信小程序）
对于答案比较固定的问题就不列出回答了，只写一下开放性问题的回答
一面
Time: 2020.4.4 (22:03-22:57)
大一参加微信小程序的项目相关:
答: 当时刚学了前端，离提交作品仅剩20天，后端(PHP和Node)都还没学，只做了个类似 to do list 的小程序，数据存放在缓存中，不过在大二的时候做数据库的课设时用TP5搭建了一个商场类小程序（跟着imooc的七月老师学习的）
C++11 有了解过吗？
答: 有了解过，比赛中也用的很多，例如auto，unordered_map，>>优化等等，但是其他特性例如智能指针，右值引用几乎没有用过
map的时间复杂度，底层，unordered_map的时间复杂度(unordered_map的时间复杂度答错了，在这之前一直不知道他的底层是哈希表，只知道它比map快)
红黑树是否了解，为什么有了AVL还要有红黑树？（说了一下红黑树的概念和性质，第二问不知道，答案应该是红黑树的复杂度更稳定，因为它的条件不如AVL严苛）
hash表相关（没答全）
智能指针（当时不会）
socket编程（完全没接触过）
多线程（没接触过，刚开始学操作系统，学校开课晚）
ACM里面你主要负责那一块？（数据结构和图论）
讲一下最近做的你认为比较难的图论题目，比如网络流什么的（顺着面试官的思路讲了前几天刚训练的网络流题（其实应该可以换个简单一些的）2017西安ICPC-E,但其实当时并没有讲的很清楚...因为这个建模还算比较复杂的，而且电话面试只能靠口述)
接下来开始手搓代码
给一个满二叉树序列，构建二叉树（指针版本）
- 很容易想到了下标规律（根和左右子节点序号的二倍关系），但是用指针是真的难受，一不小心就掉进了陷阱
二叉树镜像反转
- 递归就可以了
#include<iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void dfs(TreeNode *&rt, int id, int tot){
if(rt == nullptr){
rt = new TreeNode(a[id]);
}
int lson = id * 2;
int rson = id * 2 + 1;
if(lson tot && a[lson] != 0){
dfs(rt->left, lson, tot);
}
if(rson tot && a[rson] != 0){
dfs(rt->right, rson, tot);
}
}
void reverse(TreeNode *rt){
if(rt->left != nullptr){
reverse(rt->left);
}
if(rt->right != nullptr){
reverse(rt->right);
}
swap(rt->left, rt->right);
}
int main(){
int a[1000], n;
scanf("%d", &n);
n = (1<<n) - 1;
for(int i=1;i<n;i++){
scanf("%d", &a[i]);
}
TreeNode * root = new TreeNode;
dfs(&root, 1, n);
return 0;
}
因为面试官也搞过竞赛，最后又聊了聊竞赛和开发的区别（变量命名，全局开数组之类的），结束之前提醒我这几天学一下socket,进程线程相关,说二面会更加严格（天，有那么一丝丝激动）。
在一面过后二面之前的这四天里:
入门了Socket编程并总结到博客中
学习AVL和红黑树等细节操作（大概看懂了，并没有记住），了解红黑树的优势
学习智能指针
学习右值引用
学习进程和线程相关（看了看课本，从面经里面挖了一些可以看得懂的考点去准备了一下）
复习Linux命令，鼓起勇气重拾vim(因为比赛的缘故一直想学，学过，也放弃过)
复习TCP+UDP相关
二面
Time:2020.4.8 (20:01-20:54)
自我介绍
微信小程序项目相关（看来是有项目就一定会被问，不过这也是我写在简历里面唯一的项目）
ACM学习过程与计算机基础知识学习过程的体会和经验
答：ACM需要大量的练习，在后期做题重在思考，如果没有思路就会消耗掉大量的时间，知识多而且难需要总结+经常性复习。计算机基础知识虽然有分为学科，但是他们或多或少有些关联，日常学习要多将思考他们的联系和区别，应对考试复习要对课本知识有系统的总结和针对性的做题复习，但是针对实际应用，也和ACM刷题类似，要多练习和总结。遇到问题要寻求多种途径去解决。
C++11，C++14，C++17（只对C++11有些了解...几乎和一面答得一样）
vector和map等等，他们的底层是什么样的，各种操作复杂度？
hash相关（没答全，我真是个憨憨）
智能指针（嘿嘿）
右值引用（还好刚看过）
多态如何实现（虚函数那一堆）
虚析构函数的必要性
inline和宏的区别（答了一些，感觉没答全）
extern有什么用
如何定位一个函数或者一个变量（依稀记得在VS里面按F12可以跳过去，但是面试官补问如果是Linux呢？一脸茫然）
你平时Linux用的多吗？（刷题用一用，基本命令知道一些）
接下来是手搓代码
单链表，存放整数，删除一个整数，要求近似复杂度
此题有坑，经过面试官提示，逐渐意识到以下两点
删除的是一个整数，而不是一个节点(直接改变值就好了，并不需要改变前面那个节点的next)
近似复杂度
，也就是不要求针对所有情况复杂度都是
扫描）
struct Node{
int val;
Node* next;
};
Node* head;
void del(Node* head, Node* p){
// 空链表的情况
if(head == nullptr || p == nullptr) return;
// 针对后面还有节点的情况
if(p->next != nullptr){
p->val = p->next->val;
Node* tmp = p->next;
p->next = tmp->next;
delete tmp;
} else if(head == p){//针对只有一个节点的情况
delete head;
head = nullptr;
p = nullptr;
} else {
// 针对后面没有节点情况，需要改变前面的指向，要O(n)扫描
while(head->next != p){
head = head->next;
}
delete head->next;
head->next = nullptr;
}
}
- 基础
// 输出值
// why?: up cast
int main(int argc, char** argv){
std::cout 25u - 50;
std::cout 25u - 50l;
return 0;
}
第一个输出-25，溢出处理（计算机组成原理基础知识）
第二个Linux环境输出-25
但是面试结束之后在Windows测试了一下，结果如下：
有大佬知道这个是因为什么嘛？
- 不用加减乘除实现加法（位运算）
这个题应该挺常见（网上一搜一大片），但是面试时第一次遇到，冷静下来跟面试官口嗨了一下数电里面进位加法器的原理，他说是对的，但是循环过程中i++也用到了加法
然后想了想，写了下面这个代码：
//不用加减乘除，实现整型求和
int sum(int a, int b) {
if( (a & b) == 0){
return a | b;
}
else
return sum((a|b)-(a&b), (a&b)<<1);
}
(a|b) - (a&b) 可不就是 a^b嘛，但是我当时愣是没反应过来
最后面试官问将来有什么打算，我说想多尝试尝试，如果能继续深造还是要继续深造。紧接着他又问如果把我调到测试岗位，能不能接受
当然...能接受啊（我现在感觉自己就是一个无情的刷题机器，感觉其他什么都不会，不管研发还是测试，能有机会还是想都尝试尝试）
最后问了一下面试官，如果面试能成功，我这段时间还要学些什么？
Linux
网络编程
搜索相关
...
好啦，面经告一段落了，不知道还会不会有第三面，但是经过这两次面试，发现了自己基础还有很大的不足，心中对ACM金牌还有向往，但现在觉得巩固巩固基础是非常重要的，虽然时间上确实有很大冲突，但是我不会再拿“我在搞ACM”这种理由来欺骗自己了。
希望这篇面经能够给各位带来一些帮助，也欢迎大家和我交流。这次面的是暑假实习生，知识还比较基础没有涉及到项目。而对于这些知识，很多面经里面都是重复的，对自己而言，最重要的还是沉下心来把这些知识重新整理一遍，方便之后复习。
理解为王，总结是为了之后更快的复习，不要害怕忘记，忘记=忘+记，忘是很正常的。（复习的时候，经常感觉自己学的不是工科而是文科，这大概就是实践太少的缘故吧）
最后祝各位offer++！！！~
update（4.15）: 后来接到了测试部门的电话，经过几天的考虑之后还是打算不去了。
#阿里巴巴2021暑期实习##实习##面经##C++工程师##校招##阿里巴巴#记录2023年-2024年的笔试、面试问题~
