腾讯互娱
简历是去年在腾讯招聘官网投的，都快忘记这事了，前一周突然来了面试邀请。一共面了两轮，都是电面，现在在等结果。这算是我人生第一次面试工作，还是蛮有意义的，趁着还有印象+录了一部分音，赶紧过来记录一下。
初面
- 【～1:50】开始是惯例的自我介绍，说了一下专业、成绩、个人特点，（面试官表示GPA有点东西，却不知我就这点东西… my vegetable explodes）
- 【～7:40】面试官提出让我选一个有代表性的项目介绍一下。针对选的项目，展开问了挺多——遇到了什么问题，怎么处理的，配置方面，分工方面等等。因为做过的项目都是些中规中矩的项目，没有什么很炫酷的技术，所以也没什么波澜
- 【～9:00】针对简历上提到做过的游戏，进行了一些简单的提问，使用的开发引擎，使用的开发语言，有没有用过Lua等脚本语言，对Python的了解程度如何。我除了C++比较系统的学习过，其他的都说只是有一定的了解，能用的程度……（流下了没技术的泪水.jpg）
- 【～16:00】面试官听我对C++还比较自信，比较细致的考察了一下各方面基础内容，下面用问答形式给出大致过程。
- C++11新特性有过了解吗，说一下都有哪些吧
- 一个是比较好用的关键字auto，¥@#&*%……
- 经常跟它一起出现的关键字是什么？
- 应该是decltype吧？
- 对，那智能指针了解吗？
- 就是shared_ptr吗？
- 对，为什么要用到智能指针呢？
- 避免在忘记delete和发生异常时造成资源释放的问题，比普通指针安全性高一些……&¥#@%……
- new/delete和malloc/free有什么区别
- 前面这一对是C++提供的关键字，malloc和free是C提供的库函数，前面这个在用来创建类对象的时候会自动调用构造函数，后面的要自己手动计算需要分配的空间大小！@#¥%&*……
- （小声地）嗯…不完全正确……那其他的一些新特性呢
- 还有lambda表达式比较常用
- 你一般在什么时候用lambda表达式呢
- 主要是在写比较函数的时候，一些比较简单的比较函数如果只用一次，就不太适合专门写一个具名函数，容易污染命名空间，而且可读性也不会更高
- 那lambda表达式有什么优缺点呢
- 优点比较明显，写起来方便，不会污染命名空间等等，缺点就是如果函数比较复杂的时候可读性会比较低（用的比较少，一时也想不出很典型的优缺点…）
- 用过强枚举类型吗
- （我也是之后查了才知道这方面的内容，当时完全不知道这个，瞎猜可能是变体数据类型，菜哭）是variant吗？
- （些许的尴尬…）那应该我们说的不是一个东西
- const关键字你一般在什么情况下会用
- 修饰函数参数或者函数本身，保证传入对象或者调用对象本身不会被修改，很多时候也用来代替某些宏定义，因为宏不提供编译检查，不够安全……
- 对C++编译连接过程了解吗？（这里我重复了一下问题内容，可能语气显得有点不确定）对，就是gcc连接器这一类的，比较概念性的东西。我就是简单问一下看看你了解的程度。（我估计这应该就是看看个人对一项技术研究的深度吧）
- （我简单答了一下CSAPP讲的那一套流程，没有太深入，不复述了，面试官的意思是了解到这个程度就差不多了，然而我心里明白要是说的很深入肯定能加分就是了…）
- 构造函数可以是虚函数吗
- 不可以，（虚函数表原理那一套）。不过如果一个类有虚函数，析构函数最好是虚函数
- 初始化列表有哪些应用情景
- （简单说了一下，初始化列表和构造函数体里的不同，其实不是很确定）
- 那什么时候必须用初始化列表
- 调用父类构造函数和const的成员变量的时候吧…（不确定…）
- 【～40:00】下一步转战代码，加了面试官QQ，发来一个腾讯文档。（如果有不了解这个的，其实就是云同步的word文档，没有任何提示功能，你的每个按键操作对面都能同步看到）写代码过程中，面试官没有在听电话，只是在看你写代码（这种方式真特容易紧张导致大脑空白…）
- 【～42:00】写完代码又回过头来询问关于数据结构方面的内容
- 【～45:00】算法数据结构等等基础的内容就到这里，之后聊了一下关于游戏引擎等等岗位相关的内容
- 【～48:00】最后给了提问环节，我问了一个关于腾讯在市场导向方面的问题，其实也是因为国内和国外游戏市场的价值观差距太大了，一直也挺想了解的
- P.S. 面完感觉已经凉了…除了C++好像没有答得上来的，显得学习领域很没有广度，但是面完过了一会一查居然状态是复试了……就当是人品了
二面
- 二面除了开始简单的交流一下基本情况和意向之外，就是硬核的两道算法题，不贴代码了
- 第一个：给一个长len的数组，让你删除里面最大的N个数，重复的数字算一个。len很大，N不大
- 我的实现思路就是用一个最大堆，遍历一遍数组，都扔到堆里。然后从堆顶拿数，每拿出一个，都把后面跟着的重复的删掉，直到拿出N个数，然后遍历一遍数组把符合的删掉，把后面的往前挪
- 面完之后自己反思了一下思路，又跟大佬交流了一下，有这么几个问题，最基本的至少应该倒着扫描，这样不会重复挪很多次后面的部分，其次堆应该大小够用就行，毕竟len很长，等于多了一份拷贝，空间效率不够高
- 第二个：n个桶n个球，序号都是1～n，每个桶只能放一个球，放的球的序号跟桶的序号不能一样，一共有多少种放的方式
- 第一个：给一个长len的数组，让你删除里面最大的N个数，重复的数字算一个。len很大，N不大
- 二面完之后还给我留了一道题，可能是觉得我这两道题做的还可以，想进一步考察一下。
- 题目是考官自己出的概念，叫格式化树，反正我之后查是没有查到相关概念了。具体的定义我也记不太清了，大概有这么几点：格式化树是用来输出显示的，是对普通的树进行一系列规整得到的，同一节点的子节点之间的距离要相同，父节点要在所有子节点的中间，相同深度的节点所在的高度要相同，要求整个树所占面积尽量小。
- 题目的需求不是特别明确，要求也很open，面试官的意思是尽量写，当天晚上之前把代码发过去，什么程度不做要求。
- 我根据自己的理解限制了一下需求，尽可能简单，但还是只能做到局部最优解，而且还采用了暴力枚举等等效率比较低的做法……只能说这类题目上下限确实很高，跟OJ那些有明确解和思路的算法题不一样，还是需要以后重点关注一下的
- 贴一下代码吧，大概写了4个小时（可见水平很菜了……），可能参考意义不大，我甚至都没有测试过……
typedef struct {
int id;
//other data...
vector<Node*> children; //the order of the sub nodes is exactly the shown order in picture
} Node;
class Tree {
private:
Node* root;
void format();
//other functions...
};
/*
* this implementation can only find local optimal solutions, assuming each step has no aftereffect (actually not)
* format the tree from the lowest level
* for each node, mapping to a deque, which stores a pair of displacements relative to the node for the most left and right sub nodes for each sub level
* after formating all sub nodes of a node, use brutal force to compute the possible Minimal gap with the deques of the sub nodes
* during the process, maintain the optimal permutation, after enumerate all the cases, compute the deque of the current node
* suppose :
* 1. nodes with the same depth must have the same y
* 2. the sub nodes of different nodes cannot be interlaced
* 3. the distance of every two sub nodes of a single node must be the same
*/
void Tree::format()
{
if (root == nullptr)
return;
//post order traversal of the tree
stack< pair<Node*, int> > stackOfNodes; //int element is used to record the times of encountering the node
unordered_map<Node*, deque<pair<int, int>>> subLevelDis; //the pair of two ints records the left and the right displacement * 2 of the level relative to its parent
stackOfNodes.push(make_pair(root, 1));
while (!stackOfNodes.empty())
{
Node* curNode = stackOfNodes.top().first;
int cnt = stackOfNodes.top().second;
switch (cnt)
{
case 1:
//the sub nodes of the current node havent been formatted yet
stackOfNodes.top().second = 2;
//push the sub nodes to stack in the reverse node such that the first child is on the top
for (auto it = curNode->children.rbegin(); it != curNode->children.rend(); ++it)
{
stackOfNodes.push(make_pair(*it, 1));
}
break; //end case1
case 2:
//the sub nodes of the current node have been formatted
stackOfNodes.pop();
//format the order of sub nodes of the current node
vector<Node*>& childrens = curNode->children;
if (!childrens.empty())
{
int cntOfChildren = childrens.size();
vector<int> permutation(cntOfChildren); //the permutation of the index of the sub nodes
for (int i = 0; i < cntOfChildren; ++i)
permutation[i] = i;
int minMaxGap = INT_MAX;
vector<int> minMaxPermutation(cntOfChildren);
//use brutal force to check each permutation
//for each permutation, find the max gap
do
{
int maxGap = 0;
//compute the gap between each two adjacent node
for (int i = 0; i < cntOfChildren - 1; ++i)
{
int tempMaxGap = 0;
auto& deque1 = subLevelDis[childrens[permutation[i]]];
auto& deque2 = subLevelDis[childrens[permutation[i+1]]];
int minLen = min(deque1.size(), deque2.size());
auto it1 = deque1.begin(), it2 = deque2.begin();
for (int i = 0; i < minLen; ++i, ++it1, ++it2)
{
tempMaxGap = it1->second - it2->first;
maxGap = max(maxGap, tempMaxGap);
}
}
if (maxGap < minMaxGap)
{
minMaxGap = maxGap;
minMaxPermutation.assign(permutation.begin(), permutation.end());
}
} while (next_permutation(permutation.begin(), permutation.end()));
//reorder the subnodes according to the indice in minMaxPermutation
vector<Node*> tempChildrens(childrens.begin(), childrens.end());
for (int i = 0; i < cntOfChildren; ++i)
{
childrens[i] = tempChildrens[minMaxPermutation[i]];
}
//compute the level displacements of the current node and bind to the node
vector<int> maxLens(cntOfChildren);
int maxLen = 0;
for (int i = 0; i < cntOfChildren; ++i)
{
maxLens[i] = subLevelDis[childrens[i]].size();
maxLen = max(maxLen, maxLens[i]);
}
//for each level, find the index of the most left and right node, then compute the displacement
deque<pair<int, int>> dis;
//if all the sub nodes of current node
if (dis.empty())
dis.push_back(make_pair(-cntOfChildren * minMaxGap, cntOfChildren * minMaxGap));
//otherwise
for (int i = 0; i < maxLen; ++i)
{
int left = 0, right = cntOfChildren;
while (maxLens[left] < i)
++left;
while (maxLens[right] < i)
--right;
int leftDis = subLevelDis[childrens[left]][i].first * 2 + (left * 2 - cntOfChildren) * minMaxGap;
int rightDis = subLevelDis[childrens[right]][i].second * 2 + (right * 2 - cntOfChildren) * minMaxGap;
dis.push_back(make_pair(leftDis, rightDis));
}
subLevelDis[curNode] = dis;
//free the memory space for level displacements of the sub nodes
for (int i = 0; i < cntOfChildren; ++i)
subLevelDis.erase(childrens[i]);
}
break; //end case2
} //end switch
}
}
后记
- 尽管到现在还没有出结果，但是面试过程中暴露的问题已经足够有意义了。下一步，大方向上还是按照自己原本规划的推进，具体执行过程就需要根据这些问题加以侧重了。
- 这学期到现在为止都没有投过简历了，大四之前可能也不再投了，先看看这次面试的结果吧。
- 愿大家都能拿到喜欢的学校或公司的Offer！
2019.3.28
Reeker
相关阅读
在Win10系统中，我们可通过显卡的控制面板进行一些显卡更为高级设置，此时就需要打开显卡控制面板，win10控制面板在哪?其实显卡控制面
岗位方向商业分析师 Job Descriptionhttps://campus.meituan.com/jobs?jobFamily=4&jobId=2177&jobType=1&pageNo=1 批次2019.8.2
分享一下我老师大神的人工智能教程！零基础，通俗易懂！http://blog.csdn.net/jiangjunshow也欢迎大家转载本篇文章。分享知识，造福人民，
哈喽，你我相约七点半，你来了么^_^产品经理日报继续为您带来今日最新的资讯：美团正式入局共享充电宝，行业竞争加剧；Snapchat新功能，用人
华为的招聘流程一直非常复杂，本人最近参加了华为的社招，对全部流程有一个总体了解，包括流程，面试题目类型，分享给大家，希望大家能有所帮