2013腾讯实习生一面流水账

suika — Wed, 24 Apr 2013 01:46:53 +0000

笔试过后第三天出结果，同一个教室的下午3点就接到面试通知了，我这边一直寂静……
后来接到了腾讯的电话，说我资料填的不详细，让我补充
要补的就是诸如面试岗位、城市、擅长的语言等。我觉得很奇怪，我明明都填了，并且从电话那边的口气来听，他也看得到我之前填的资料
或许只是来确认下，或是要我再考虑吧。我想想确实也有点问题，本科做的项目都用java，但是擅长的选的c/c++；岗位填的后台，简历里却又说平时爱好做游戏

到了晚上6点，都准备明天去霸面了，终于还是收到通知了。

通知是下午2点，实际上1点半就被叫进去了。
在宾馆的标准间里面的，面试官看着非常年轻，感觉和我差不多年纪吧，一点都不摆架子，很和善。
进门递了简历以后，还没等面试官就位我开始自我介绍，为的是抢占先机。
先是提到自己本科的毕设，引起了对面的兴趣，然后balabala
说完毕设，说本科的几个java网站项目，面试官终于来精神了，首先是问了使用的架构，分工，负载情况
然后问我，看你最擅长的是c/c++，那你java怎么样？
呃，两年没用java了，只能如实托出
然后面试官就java问了几个基础问题，比如说：
GC的工作原则和垃圾回收机制是什么？我只答了最基础的引用计数OTL…… 回来的路上想到，GC的任务是保证内存可用，回收内存只是一方面，另一方面还有内存碎片等问题，所以多机制是必然的
java里会不会内存泄露？我一开始回答说不会，因为java走的全都是引用，逃不掉引用计数。后来又补了下，GC认为一个变量要呆的时间比程序员认为的要长，那就算内存泄露，这种情况是可能出现的
JVM内部调用类库的方式是什么？我也完全空白，只好说不会。但是我说我可以做个推测，于是就把c/c++里面静态链接、动态链接大概说了一下
还问我有没有做过多线程？我就中兴比赛的那个程序说了一下，不过很快意识到应该是问java下的，就凭印象回答了runnable接口和thread类

回答之后，我询问了一下，面试官是不是主要就是做java的，对面回答说是wapqq门户网站模块的后台
感觉java的问题都答得很糟糕，但是面试官还是很和善的样子，说我们轻松一下，来聊聊怎么做个俄罗斯方块小游戏吧
然后我就把我常用的游戏结构给写上去了，主循环，渲染模块，逻辑模块，帧控制，在纸上做了大体表示
不过感觉回答的太快了，所以思路显得很乱。因为前面的结构早就有数了，我一上来就开始说怎么设计里面对象的类和属性了，不太好
并且忽略了对面擅长java的事情，应该把模块关系、类的构造和继承关系都清晰地写出来才对。

对面还特地问了一下，为什么要帧控制

问完游戏，他开始继续低头看我简历，我就抓紧机会，问了一下他们公司这边的情况。这次来重庆面试后台的有三个组，除去他们这个java组之外，另外两个组是c/c++为主，但都是类似服务器半开发半维护的样子。他们java组都是用的自己的框架，很少用开源的东西。面试官还问我，对他们做的后台方向有没有兴趣，我说，我以前也做过类似的工作，我觉得能来做这个的话是非常宝贵的机会，我想去
（其实心里也在想，本科以后就放弃做java网站后台了，还真没想过要重新做这个……不过我也没得挑，能过一面就算成功了）

至此面试就结束了，大概30分钟的样子，其他同学貌似都有被问40分钟。临走的时候对面说觉得还行，大概2,3天后会有结果。不过我回来想想，java的几个问题真是回答的乱七八糟，进二面估计很玄了。只能算是自己运气好，没有碰上爱给压力的面试官

2013重庆腾讯实习生笔试的两道题

suika — Sat, 20 Apr 2013 04:37:25 +0000

（今天连bluehost好慢
刚刚被虐回来，稍微总结一下
题的范围很广，从TCPIP协议、数据库、算法与数据结构、计算机系统到语言细节，都有涉及

另外今年的笔试题里有10道选择题、5道填空和加分题的第一题都与去年的题目一模一样 OTL……
没看去年的题亏死了

挑两道印象比较深的题记录下：
（都是去年的题，网上都有公开，应该不算是私自公布试卷了吧）

两人猜数字，范围为[1,100]， 甲写一个数字，让乙猜。
如果乙猜的偏小，甲会说偏小，但是如果某一次甲猜的偏大，乙之后都只会说对或不对。
问： 乙最少可以在多少次内保证猜对？在这种策略下，第一个猜的数字是什么？

看到这道题，首先可以推导出这两问的答案一定是同一数字。若第一次猜X且偏大，则之后需猜X-1次方能保证猜中，即最少需猜X次。
于是递推一下，设最少猜X次才能保证猜对，则第一次必定猜X
第二次要猜多少呢？第二次猜的时候，要保证在猜偏大的情况下，后面再猜X-2次就能保证猜中，所以第二次要猜X+X-1
同理，第三次若猜偏大，后面要再猜X-3次，所以第三次猜的数为X+X-1+X-2……直至猜了N次之后，猜的数>=100
这就是一个初项为X，公差为-1，项数为N的等差数列求和，即约束方程 $X*N-\frac{N*(N-1)}{2}=100$ 下求X的最小值
$X=\frac{100}{N} + \frac{N}{2} - \frac12$ ， $N=\sqrt{200}$ 时有极值，X约为14
答案就是14 14

两个数组a[N]，b[N]，其中A[N]的各个元素值已知
现给b[i]赋值，b[i] = a[0]*a[1]*a[2]...*a[N-1]/a[i]；
要求：
1.不准用除法运算
2.除了循环计数值，a[N],b[N]外，不准再用其他任何变量（包括局部变量，全局变量等）
3.满足时间复杂度O（n），空间复杂度O（1）

在编程之美上出现过类似的
这个题不准用其他变量，那只能在a和b上下手了
我的思路是，对于b[i]来说，可以拆成a[0]*a[1]*...*a[i-1]和a[i+1]*a[i+2]*...*a[N-1]两部分，这两部分用O(n)分别求出来，最后再乘起来就行了
代码见下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include

void foo(int a[], int b[], int N){
b[0] = 1;
//乘完左边，存在b[i]里。此时b[i]表示从a[0] * ... *a[i-1]的积
for (int i = 1; i < N; ++i){
b[i] = b[i-1] * a[i-1];
}

//乘完右边，存在a[i]里。a[i]表示从a[i] *...*a[N-1]的积
for (int i = N-2; i > 0; --i){
a[i] *= a[i + 1];
}

//两边乘起来
for (int i = 0; i < N - 1; ++i){
b[i] *= a[i + 1];
}
}

int main(){
int a[10] = {1,2,3,4,5,6,7,8,9,10};
int b[10];
foo(a,b,10);
for (int i = 0; i < 10; ++i){
printf("%d\n", b[i]);
}
}

我这种写法的缺点是改变了输入数组a，这个不太好。把好写法贴一份：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

void problem(int* a, long long* b, int N)
{
b[0] = 1;
for(int i = 1; i < N; ++i)
{
b[i] = b[i-1] * a[i-1]; // 分水岭的前半段乘积
}

b[0] = a[N - 1];
for(int i = N - 2; i >= 1; --i)
{
b[i] *= b[0];
b[0] *= a[i]; // 分水岭的后半段乘积，是从数组尾部向前循环的
}
}

西瓜田 » 实习

2013腾讯实习生一面流水账

2013重庆腾讯实习生笔试的两道题