2014年腾讯面试试题8道

1. 根据以下代码?

int ack(int m,int n)

{

if(m == 0)

return n + 1;

else if(n == 0)

return ack(m-1,1);

else

return ack(m – 1 , ack(m , n-1));

}

如果ack(3,3),。结果为多少

2. A，B两个整数集合，设计一个算法求他们的交集，尽可能的高效。

我的回答的：如果对于数据较小(10W以下)我会采取哈希的方法去求数集较小的那个集合的hash值存在hash表中，然后对另一个表中每一个数进行hash，如果在hash表中找到则这个数是交集的数，输出。这个算法时间效率是O(n+m)，空间效率O(3n+m);(因为hash几乎浪费掉一半空间)

对于大数据，我则先把数据hash%100的样子分到许多个小文件中，然后对这些hash值的次数建立一颗二叉查找树，遍历另一个集合的数来找，找到一个就输出一个，最后得到集合数。算法效率是O(n/100*m*log(n/100))，空间效率O(n+m)

3. 请设计一个排队系统，能够让每个进入队伍的用户都能看到自己在队列中所处的位置和变化，队伍可能随时有人加入和退出;当有人退出影响到用户的位置排名时需要及时反馈到用户。

4.怎么在linux下查找一个文件中有多少个给定的字符串

答：这题本来想考察我的shell编程的能力吧，不过我说这个不会，然后他问我如果写程序实现呢

我答我会用trie树去记录字符串出现的次数

然后有被问道更深入一点的，如果文件过大呢?

我答，那就把文件内容hash取模分成多个足够小的文件，然后每个小文件trie记录结果，输出一个小文件，最后把所有结果文件合并就可以得到最终结果

5. 写二叉查找树的查找算法，答案就不写了，简单。

写完之后，面试官又问我由这里到一个什么地方的，要求最短时间，怎么求

这个就是问最短路算法，我就答了这个，然后他又问我怎么知道去的路径通不通，我答用传递闭包去计算，

他问我如何传递闭包，然后我就画图演示了一下这个过程

6. 进程与线程的区别

这题我答得非常不好，我只答了进程有资源，线程没资源，进程个数有限，而线程的个数几乎不限，进程的调度慢，线程的调度快这些基础点

但是被问到为什么进程调度比线程慢时，我答不出，我答是因为用户态和内核态的转换造成的，但是百度一下，答案应该是因为线程调度是在进程中进行，在同一存储区内操作，而进程则在不同存储区操作，所以进程调度数度比线程慢

7. 问我TCP/IP有多少层

我答OSI标准有7层，但是目前工业大多使用5层的标准，然后回答了一下这些标准，我只会答5层标准的那一个。。。

接着又问我IP层(网络层)的作用，

我答了很多，又说了什么TCP、UDP的，然后在面试官的知道下，我才答出，网络层的作用是映射作用，主要是IP和MAC地址、端口的映射(我不知道对不对。。)

接着又问我TCP和UDP的区别

我就答，TCP是有连接的，UDP是无连接的，TCP通过三次握手保证数据的可靠性，UDP则没有

最后还问我滑动窗口的东西，我就答了滑动窗口是为了保证数据被客户端正确接收了，他又问我为什么能保证，然后我就画图演示滑动窗口的发送、接收、移动过程

8：写一个函数，计算给定的一个整数中有多少个0