天天看点

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

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没说全,剩下的都不会(只是觉得貌似见过而已)。。。。

继续阅读