记腾讯创新班面试

昨天参加了腾讯创新班3+1的面试，觉得收获匪浅，腾讯果然很多大牛啊。废话少说下，记一下面试时候几个有趣的问题，第一个是:

 

 

//代码一
for(int i = 0 ; i<N ; i++){
 
     A;
     B;
     C;
}

//代码二
for(int i = 0 ; i<N ; i++){
     A;    
}

for(int i = 0 ; i<N ; i++){
     B;
}

for(int i = 0 ; i<N ; i++){  
     C;
}

 

 问题是，在什么情景下会出现代码一比代码二快执行完，在什么情况下代码二比代码一快执行完？

答案一：线程阻塞可以达到代码一比代码二更快执行完的效果。具体一点说就是A语句是启动的一个线程ThreadA，然后ThreadA在运行的过程中受到阻塞。由于只是线程ThreadA受到阻塞，对主线程没什么影响，主线程会继续执行下去。所以代码什么时候执行完取决于最后一个启动的ThreadA的结束时间。由于二中的最后一个的启动时间比一中的早，顾可以出现二比一块执行完得情况。

答案二是：A，B，C分别都是读取文件的操作，在这种情况下代码二的效率会比代码一的效率高很多

答案三是：A是i--；B是i++；在代码二中形成了死循环，所以一会比二快

 

 

问题二:

一个长字符窜和一个短字符串，判断短字符串中的所有字符是否在长的字符窜中。

答案是：

一：直接遍历，效果比较差

二：把所有的长字符窜的字母存进一个hashmap中，再用段字符窜的所有字母去hashmap中的去找。由于字符串很长，所以中间必然很多重复字母，用hashmap存储去除重复字母，并且查找效率很高，所以这个算法效率较高。

三：把长字符窜的所有字母存进一个set中，记录set中元素个数a，再继续把短字符串的字母也放进set中，在记录元素个数b，比较a，b就可以得到结果。

四：用一个01的窜记录每个26个字母在长窜中字母是否出现的情况，然后遍历短窜，可以通过短窜中的字母，找到对应的01位置，判断短窜的字母是否在长窜中。这种的查找效率和比hashmap高，而且节省空间。

 

问题三：

有一百个阶梯，一个人每次可以走一步或者两步，一共有多少种走法？

答案一：用动态规划的方法，声明一个int result[101]的数组，用result[n]来存储当有n级阶梯时，一共有多少种走法。可以result【0】=0，result【1】=1，然后result【n】=result【n-1】+result【n-2】

答案二：用排列组合的方法。很容易可以得出走一步的次数x和走两步的次数y，然后可以用排列组合的方法计算出来

 

以上的答案如有不对，请各位大牛们批评指出。或者如果大家如果有什么好的想法也可以分享一下

 

总结：感觉腾讯的面试由浅到深，逐渐深入，要你不断优化你的代码，很考发散性思维。虽然顺利通过了三面，但是自己还有很多不足之处，很多地方还要提高。在等通知中，希望可以通过吧。God bless me 。

 

 

评论

6 楼 liujiahaogood 2011-07-25  

……搞错了，你是对的

基德KID.1412 写道

不错，，但是我有个问题

问题三：
result【2】=2，而你那里result【2】=result【1】+result【0】=1 ？？

你好细心啊， 我当时只是把方法想出来，都没怎么注意细节，应该是我错了。n是表示阶梯的数目，所以当有两级阶梯时应该有两种走法，故result【2】=2才对，所以result【0】应该等于1.
不过用你的“从第一级开始”这种理解也行。

5 楼 gzhu_101majia 2011-07-19  

基德KID.1412 写道

哎……搞错了，你是对的

从第1级开始，result【0】 = 0， result【1】 = 1， result【2】 = 1

kid小孩好！！！

4 楼 基德KID.1412 2011-07-18  

哎……搞错了，你是对的

从第1级开始，result【0】 = 0， result【1】 = 1， result【2】 = 1

3 楼 基德KID.1412 2011-07-18  

从0级开始……result【1】 = 1， result【2】= 2；
从1级开始……result【1】 = 0， result【2】 = 1；

2 楼 基德KID.1412 2011-07-18  

不错，，但是我有个问题

问题三：
result【2】=2，而你那里result【2】=result【1】+result【0】=1 ？？

1 楼 chriszeng87 2011-06-26  

不错啊，现场还能想到几种解法，楼主基本功真扎实