腾讯QQ客户端实习一面
腾讯QQ客户端实习一面
腾讯春招实习生面试，之前面试WXG后台开发凉了，被QQ安卓客户端部门捞了。 面试官一样也是和蔼可亲，面试平台是坑爹的牛X网，全程听着自己的回音超级难受。后续是简历又回到了WXG一面，这是什么情况啊……一、基础知识
面试开始前，我先问了面试官是哪个方向的客户端（移动or桌面，因为我只知道被客户端捞了不知道具体是哪个方向）。当我得知是移动客户端时我方了——Java和安卓开发已经荒废了N久，不过我的简历语言只写了C++，应该不会为难我。
然后开始个人介绍，我强调了以前对Java很感兴趣但后面已经转了C艹，同时安卓开发也仅限于最基础的（暗示面试官之后不要问这方面的内容）。然后面试官问我的个人项目（不是软件类的纯课余生活），问我中间遇到了什么困难。接下来是问基础知识：
加粗为我个人不懂的，日后强化。
1，我如何理解虚拟内存，做什么的，有啥作用。
2，系统调用的详细过程。这里我一开始不懂什么是系统调用，我以为是个动词。后来面试官耐心详细的告诉我系统调用指用户态到内核态的过程。然后问我用户态和内核态的区别，用户态如何进入内核态。
3，你学过Java（内心：我没有，别瞎说啊 ）也学过C艹，这两种语言内存管理的异同？我以前读过半本《深入理解Java虚拟机》，因此可以阿巴阿巴一下他们的异同。说到不同点，我提了一嘴C艹可能产生内存泄露，JVM可以自动回收内存空间，给自己挖了个大坑。。。
4，你提到C艹可能内存泄漏，那Java呢，Java会不会内存泄漏？我想了好一会，告诉面试官：“这个问题的正确答案肯定是也会产生，但是按照我所学知识应该是不会产生。。。因为JVM的那么多种GC机制都实在是太强了。”然后面试官继续暗示我有没有特殊情况。。。我的天我的JVM虚拟机一年多之前看的，我看的时候好像还真不会泄露啊，于是我拿这本书挡枪，还是坚持了不会泄露：“那些回收算法都太智能了……”于是又挖了下一个坑。。。
5，那他有哪些算法（垃圾回收）？我的天这我真忘了，那些垃圾回收器以前确实看的津津有味，但是名字都不记得了（第二天才想起来一些），只能拿这本书看了太久挡枪。于是面试官改问：“那大概的原理呢”。这个时候我真的要吐血了。。。但好歹还记得一点点，回答了一种引用计数器的，还有一种新生代老年代的，于是新的坑又被挖下了。。。
6，划分新生代和老年代的目的是什么？（面试官大哥，我求你了我简历都不提Java和JVM虚拟机了能换个话题吗 ）好在这个问题还是挺简单的，阿巴阿巴过了。
7，平时编程有没有出现过栈溢出，我举了指针越界、递归极深和死循环调度的例子。然后问我一般的栈有多大？此时我已经心肺停止 正确答案应该是：linux系统下默认栈大小是10m,windows系统下默认栈大小是1m。每个线程1m，因此一个进程（默认2g）可以创建2048个线程。
8，你有听说过某些语言支持的尾递归吗？我还以为是伪递归，写面经的时候才发现是我太天真 相关知识补充到下面了。可以大大节省栈空间，只保留最后一个递归的栈帧。
9，操作系统怎么进行进程调度，即进程调度算法。
10，压轴问题：现在我们要做个文件的下载，有什么方法提升文件下载速度？我回答了：“这一方面不太清楚，但应该可以用多线程实现。”然后追问线程数应该是多少个，取决于什么。。。我回答取决于文件大小、网络带宽、服务端客户端内存大小之类的。又被追问下的更快和哪方面有关系？晕了。。。有没有大牛能回答这个问题。
二、实际应用题
如何产生一个长度为100的数组，里面填满数字1-100不重复，而且数组内数字排序必须纯随机。
这题总共用了一个小时，一开始提出用一个数组记录某个数字是否被使用过，然后不断调用随机函数往目标数组塞数字，重复了就继续抽。但这样显然时间效率不高。于是又提出引进类似哈希冲突时的线性探测，避免在剩下最后一些数字未使用的情况下要不断的抽，通过线性探测直接把某些未使用的数字提出来用。时间复杂度约为O(nlogn)，空间复杂度O(n)。
后面又提出一种方法，用一个数组储存1~100的全排列，空间消耗O(n!)，但其实也可以接受毕竟只是1-100，之后每次用随机函数产生一个下标，访问数组取出即可，这样时间复杂度只是O(1)。但是面试官说如果数字为1-1000，那就不行了。
于是面试官提出新要求，不要使用辅助空间，提示我能否在原有1-100顺序排列的数组上将其打乱。我很快就想到了从a[0]开始，每次抽一个随机数比如抽到10，那就交换a[0]和a[10]，第二次抽到99，那就交换a[2] 和a[99]。时间复杂度仅为O(n)，空间复杂度O(1)。事后才得知这道题是大名鼎鼎的洗牌算法。当然我的算法还是和他们的有一点点区别，不过实际效果都差不多。
于是面试官让我去实现这个算法，中间遇到了一个超级大坑：随机函数每次产生的数字都一样，详情看这篇文章：C++ srand()只能调用一次，否则rand()每次返回相同值，最后侥幸解决了问题。
#include <iostream>
#include <ctime>
using namespace std;
void getRand(int *arr)
{
int i, j, temp;
srand((unsigned)time(NULL));
for (i = 0; i < 100; ++i)
{
j = rand() % 100;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
return;
}
int main()
{
int a[100], i;
for (i = 0; i < 100; ++i)
a[i] = i + 1;
getRand(a);
for (i = 0; i < 100; ++i)
cout << a[i] << ' ';
} 三、总结
第二天写这篇面经的时候，心情是沉重的……因为此时已经收到消息第三天又要进行WXG后台开发一面，回到了最初的起点，只能继续加油了，多刷点算法题，随便记得少给自己挖坑。