各大计算机公司 笔试及面试 题目 - 人人网（面试）

1、typename 的几个用处？（就相当于与class的区别)

答案：

当某个类姓名依赖于一个模板参数时，就需要使用 typename 关键字，如下示例：

template<typename T> void fun (vector<T> & v)
{
vector<T>::iterator i= v.begin(); //error
typename  vector<T>::iterator i= v.begin();//ok
//....
}
           

附注： 为了区分模板成员和其它成员，可能需要使用 template作为限定词（出现这种概率的情况很少），对象.template 成员函数 （如：m.template get_new<int>()）；

2、Map的底层实现机制。

3、一致性HASH。

4、在一个文本中，将一些由特殊字符组成的字符串替换成相应图片的高效算法。（比如：短信中的表情）。

5、如何计算两个1000位数的乘法。

6、在一个很长的数字串中（比如1W个以上），找出连续的10个数字，使得其和是最大的。

7、在一个数字是连续（但不是已经排好序的）的字串中，其中有一个缺失了，找出那个缺失的数字。（如：13298674，则缺失的那个是5）。

答案：http://www.cnblogs.com/youwang/archive/2011/03/30/find_missing_number.html

[算法] 找出丢失的数字

有一组数字，从1到n中减少了一个数，顺序也被打乱了，放在一个n-1的数组里，请找出丢失的数字。

1. 用1+2+...+n（即n(n+1)/2）减去当前输入数据的总和。时间复杂度为O(n)，空间复杂度O(1)，缺点是容易溢出。缓解溢出的方法，求1+2+...+n的时候，边加边减。假如数组为a，那么这可以这么计算1-a[0]+2-a[1]+...+(n-1)-a[n-2]+n。
2. 用1*2*...*n除以当前输入的数据的积。时间复杂度O(n)，空间复杂度O(1)。缺点也是容易溢出，缓解的办法：1/a[0]*2/a[1]...(n-1)/a[n-2]*n（得用浮点除法）。
3. 用1^2^...^n逐个异或当前输入数据。时间复杂度为O(n)，空间复杂度O(1)。这是比较完美的解决办法，不存在溢出的问题。
4. 对输入数据排序，然后从头到尾遍历一次。时间复杂度O(nlgn)，空间复杂度O(1)（还取决于排序算法）。缺点很明显，时间复杂度过高。
5. 对输入数据进行Hash，然后从头到位遍历一次。时间复杂度O(n)，空间复杂度O(n)。

问题扩展1：如果是少了两个数，那又该怎么办呢？

假设丢失的两个数为x和y。

1. 用1+2+...+n减去当前输入数据的总和，可以得到x+y；用

   

   减去当前输入数据的平方和可以得到

   

   。联立两个方程可以得到x和y。时间复杂度O(n)，空间复杂度O(1)。问题是容易溢出。
2. 用1+2+...+n减去当前输入数据的总和，可以得到x+y；用1*2*...*n除以输入数据的积可以得到xy。联立可以得到x和y。时间复杂度O(n)，空间复杂度O(1)。缺点是容易溢出。
3. 对输入数据排序，然后从头到尾遍历一次。时间复杂度O(nlgn)，空间复杂度O(1)。
4. 对输入数据进行Hash，然后从头到尾遍历一次。时间复杂度O(n)，空间复杂度O(n)。
5. 用1^2^...^n的结果逐个异或当前输入数据，得到x^y。由于x与y不相等，所以x^y的结果中至少有一位是1。我们根据这一位的不同（0或1）将输入数据以及1,2,...,n分成两堆。然后，分别对两堆进行异或即可得到x和y。

问题扩展2：1-1000放到含有1001个元素的数组中，只有唯一的一个元素重复，其他均只出现一次。每个数组元素只能访问一次，设计一个算法，将它找出来。要求不用辅助存储空间。

这个问题的解法类似，用1^2^...^1000的结果逐个异或输入的1001个元素，得到的结果即为所求。

相似问题：

1. 给你n个数，其中有且仅有一个数出现了奇数次，其余的数都出现了偶数次。用线性时间常数空间找出出现了奇数次的那一个数。
2. 给你n个数，其中有且仅有两个数出现了奇数次，其余的数都出现了偶数次。用线性时间常数空间找出出现了奇数次的那两个数。

第1，3没说全，剩下的都不会（只是觉得貌似见过而已）。。。。