经典面试题（二）附答案 算法+数据结构+代码 微软Microsoft、谷歌Google、百度、腾讯

1.正整数序列Q中的每个元素都至少能被正整数a和b中的一个整除，现给定a和b，需要计算出Q中的前几项，

例如，当a=3，b=5，N=6时，序列为3，5，6，9，10，12

(1)、设计一个函数void generate（int a,int b,int N ,int * Q）计算Q的前几项

(2)、设计测试数据来验证函数程序在各种输入下的正确性。

感觉有点类似归并排序的Merge。有两个数组A、B。

数组A存放：3*1、3*2、3*3…

数组B存放：5*1、5*2、5*3…

有两个指针 i, j，分别指向A、B的第一个元素。取Min( A[i], B[j] )，并将较小值的指针前移，然后继续比较。

当然，编程实现的时候，完全没有必要申请两个数组，用两个变量就可以。

1. #include <iostream>
2. using namespace std;
3. void Generate( int a,int b,int N ,int * Q )
4. {
5. int tmpA, tmpB;
6. int i = 1;
7. int j = 1;
8. for( int k=0; k<N; k++ )
9. {
10. tmpA = a * i;
11. tmpB = b * j;
12. if( tmpA <= tmpB )
13. {
14. Q[k] = tmpA;
15. i++;
16. }
17. else
18. {
19. Q[k] = tmpB;
20. j++;
21. }
22. }
23. }
24. int main()
25. {
26. int Q[6];
27. Generate( 3, 5, 6 ,Q );
28. return 0;
29. }

#include <iostream>
using namespace std;

void Generate( int a,int b,int N ,int * Q )
{
	int tmpA, tmpB;
	int i = 1;
	int j = 1;

	for( int k=0; k<N; k++ )
	{
		tmpA = a * i;
		tmpB = b * j;

		if( tmpA <= tmpB )
		{
			Q[k] = tmpA;
			i++;
		}
		else
		{
			Q[k] = tmpB;
			j++;
		}
	}
}

int main()
{
	int Q[6];
	Generate( 3, 5, 6 ,Q );
	return 0;
}

2.有一个由大小写组成的字符串，现在需要对他进行修改，将其中的所有小写字母排在大写字母的前面（大写或小写字母之间不要求保持原来次序），如有可能尽量选择时间和空间效率高的算法c语言函数原型void proc（char *str）

也可以采用你自己熟悉的语言

应该类似快排的partition。快排的partition也有两种常见的实现：从左往右扫描、从两头往中间扫描。这里使用从左往后扫描的方式。

字符串在调整的过程中可以分成两个部分：已排好的小写字母部分、待调整的剩余部分。用两个指针i和j，其中i指向待调整的剩余部分的第一个元素，用j指针遍历待调整的部分。当j指向一个小写字母时，交换i和j所指的元素。向前移动i、j，直到字符串末尾。

1. #include <iostream>
2. using namespace std;
3. void Proc( char *str )
4. {
5. int i = 0;
6. int j = 0;
7. //移动指针i, 使其指向第一个大写字母
8. while( str[i] != '\0' && str[i] >= 'a' && str[i] <= 'z' ) i++;
9. if( str[i] != '\0' )
10. {
11. //指针j遍历未处理的部分，找到第一个小写字母
12. for( j=i; str[j] != '\0'; j++ )
13. {
14. if( str[j] >= 'a' && str[j] <= 'z' )
15. {
16. char tmp = str[i];
17. str[i] = str[j];
18. str[j] = tmp;
19. i++;
20. }
21. }
22. }
23. }
24. int main()
25. {
26. char data[] = "SONGjianGoodBest";
27. Proc( data );
28. return 0;
29. }

#include <iostream>
using namespace std;

void Proc( char *str )
{
	int i = 0;
	int j = 0;

	//移动指针i, 使其指向第一个大写字母
	while( str[i] != '\0' && str[i] >= 'a' && str[i] <= 'z' ) i++;

	if( str[i] != '\0' )
	{
		//指针j遍历未处理的部分，找到第一个小写字母
		for( j=i; str[j] != '\0'; j++ )
		{
			if( str[j] >= 'a' && str[j] <= 'z' )
			{
				char tmp = str[i];
				str[i] = str[j];
				str[j] = tmp;
				i++;
			}
		}
	}
}

int main()
{
	char data[] = "SONGjianGoodBest";
	Proc( data );
	return 0;
}

 3.如何随机选取1000个关键字。

给定一个数据流，其中包含无穷尽的搜索关键字（比如，人们在谷歌搜索时不断输入的关键字）。如何才能从这个无穷尽的流中随机的选取1000个关键字？

说实话我不会做，是看网上的答案。感觉是对的，但又说不上为什么。

思路是这样的：

1.申请一个1000个元素的数组，用于保存最后选中的关键字

2.将数据流中前1000个直接放入数组中

3.对于第n个元素（n>1000）, 以1000/n的概率随机替换数组中的一个元素

这个就能保证每个元素都以1000/n的概率被选中。哎，为什么？先放这吧，以后再说。

4.判断一个自然数是否是某个数的平方。说明：当然不能使用开方运算。

也就是判断一个自然数是否是完全平方数。

方法一：从1开始逐个尝试，即判断1*1，2*2，3*3…,算法复杂度O( N^0.5 )

方法二：相当于在1…N之间找一个数x，使x*x = N。这样看就是一个查找问题，所以用折半查找。算法复杂度O( logN )。

方法三：使用完全平方数的性质：每个完全平方数都可以表示成一系列奇数的和。

不妨这样简单理解一下：

设x是一个完全平方数，即 x = a^2，所以

a^2 = ( a – 1 +1 )^2 = (a-1)^2 + 2( a – 1 ) + 1

=( (a-2) + 1 )^2 + 2( a – 1 ) + 1

=(a-2)^2 + ( 2( a – 2 ) + 1 ) + (2( a – 1 ) + 1 )

即 x = 1 + 3 + 5 + … + (2( a – 1 ) + 1 )

故x可以表示为一系列奇数的和.

因此判断完全平方数的算法：x – 1 – 3 – 5…即从x中连续不断的减去一个奇数，如果结果可以为0，则x是完全平方数。否则，不是。算法复杂度O(N )，当然由于这里做的全部是减法，可能也回比较快。

5.给定能随机生成整数1到5的函数，写出能随机生成整数1到7的函数。

关键是要保证每个数字产生的概率相等。

把能随机生成整数1到5的函数记为R15。

我的想法是：把R15调用6次，然后统计这6次中，某个数字出现的次数。比如，统计1出现的次数。1的次数[0, 6],然后给次数加一，就可以随机生成1到7之间的整数。

网上的解法：首先，调用7次R15。然后，取最大值对应的下标，由这些值构成了一个新数组。然后继续调用R15，直到最后只剩下一个数字。

{ 1，2，3，4，5，6，7 }

5，3，1，5，2，4，5

{ 1， ， ，4， ， ，7 }

4， ， ，1， ， ，3

{ 1 }

6.1024! 末尾有多少个？

求末尾0个数，也就是对1024！进行因子分解，求因子中10的个数。在进一步，因子中10的个数，就相当与质因子中2*5的个数。因为质因子5的个数比2少，所以也就是求1024！中质因子5的个数。

1，2，3，…，1024中哪些数都含有质因子5？主要有以下几类：

第一类：5的倍数，1024/5 = 204个

第二类：25的倍数，1024/25 = 40个

第三类：125的倍数，1024/125 = 8个

第四类：625的倍数，1024/625 = 1个

则，总的因子5的个数：204 + 40 + 8 + 1 = 253

当然，为什么加起来就是最后的答案？这个不难，自己想想吧。

7. 有个海盗，按照等级从5到1排列，最大的海盗有权提议他们如何分享枚金币。

但其他人要对此表决，如果多数反对，那他就会被杀死。

他应该提出怎样的方案，既让自己拿到尽可能多的金币又不会被杀死？

（提示：有一个海盗能拿到98%的金币）

很有意思的一个题。嘿嘿，不会做，也还是看网上答案的。

当有5个人时，等级为5的海盗，等级最高，他来分配。分配时要考虑两个问题：利益最大、不被杀死。至于他的分配方案会不会招来杀身之祸，完全取决于其他4个人的反应。所以考虑，4个人的情况。

当有4个人时，等级为4的海盗，等级最高，他来分配。至于他的分配方案会不会招来杀身之祸，完全取决于其他3个人的反应。所以考虑，3个人的情况。

…

当有2个人时，等级为2的海盗，等级最高，他来分配。这时他就可以肆无忌惮的分配了。分配方案：100，0。即给自己100枚金币，给等级为1的海盗0枚金币。虽然对等级为1的海盗来说很不公平，但是他反对也没用，因为只有两个人，他占不了大多数。

再来考虑三个人的问题。当有3个人时，等级为3的海盗，等级最高，他来分配。他只要在前两个人中争取一个人就行。分配方案：99，0，1。这样等级为1的海盗肯定不会反对，因为比2个人的时候分的多。只有等级为2的海盗反对，但是没有用

考虑四个人的情况。分配方案：99，0，1，0。等级为4、2的海盗满意。

五个人的情况。分配方案：98，0，1，0，1。

8.给定一个集合A=[0,1,3,8](该集合中的元素都是在，之间的数字，但未必全部包含)，指定任意一个正整数K，请用A中的元素组成一个大于K的最小正整数。

比如，A=[1,0] K=21 那么输出结构应该为100。

首先，计算正整数K的位数。假设k有m位。把用A中的元素组成一个大于K的最小正整数记为x。那么x就有m位或者m+1位。

根据K的最高位，在A中选数字。分两种情况：A中的数字都比k的最高位小、A中至少有一个数字等于大于k的最高位。

1.A中的数字都比k的最高位小，则x有m+1位。这时，只要用A中的数字组成一个m+1位的最小正整数即可。

2.A中至少有一个数字等于大于k的最高位。这时x的最高位就是不小于K最高位的最小数字。然后，用同样的方法继续比较下一位。

编程实现：很烦，写的都想吐血了。

1. #include <iostream>
2. #include <algorithm>
3. using namespace std;
4. //target为int值，最多是10位数
5. const int MAX_INT_CNT = 20;
6. int NearestInt( int target, int *data, int size )
7. {
8. int ans = 0;
9. //计算target的位数
10. int cnt = 0;
11. int tmp = target;
12. while( tmp > 0 )
13. {
14. cnt++;
15. tmp /= 10;
16. }
17. //将target转换为字符串
18. char des[MAX_INT_CNT];
19. itoa( target, des , 10 );
20. string strTarget( des );
21. //对数组排序
22. sort( data, data+size );
23. int flag = 0;
24. int i, j;
25. for( i=0; i<cnt; i++ )
26. {
27. ans *= 10;
28. //遍历数组，找到一个合适的元素
29. for( j=0; j<size && flag==0; j++ )
30. {
31. if( strTarget[i] == data[j] )
32. {
33. ans += data[j];
34. break;
35. }
36. if( strTarget[i] < data[j] )
37. {
38. ans += data[j];
39. flag = 1;
40. break;
41. }
42. }
43. if( j >= size ) flag = 2;
44. //flag == 2表示前面的数字都相等，只要后面的多一位就行
45. if( flag == 2 )
46. {
47. if( i == 0 )
48. {
49. //找到一个非0元素
50. for( j=0; j<size; j++ )
51. {
52. if( data[j] > 0 )break;
53. }
54. ans += data[j];
55. }
56. else
57. ans += data[0];
58. }
59. //flag == 1表示前面的数字比较大，后面的取最小的数字即可
60. if( flag == 1 ) ans += data[0];
61. }
62. //如果前面的数字都相等
63. if( flag == 2 )
64. {
65. ans *= 10;
66. ans += data[0];
67. }
68. return ans;
69. }
70. int main()
71. {
72. int data[] = { 0, 1, 3, 8 };
73. cout << NearestInt( 21, data, 4 ) << endl;
74. return 0;
75. }

#include <iostream>
#include <algorithm>
using namespace std;

//target为int值，最多是10位数
const int MAX_INT_CNT = 20;

int NearestInt( int target, int *data, int size )
{
	int ans = 0;

	//计算target的位数
	int cnt = 0;
	int tmp = target;
	while( tmp > 0 )
	{
		cnt++;
		tmp /= 10;
	}

	//将target转换为字符串
	char des[MAX_INT_CNT];
	itoa( target, des , 10 );
	string strTarget( des );

	//对数组排序
	sort( data, data+size );

	int flag = 0;
	int i, j;
	for( i=0; i<cnt; i++ )
	{
		ans *= 10;
		//遍历数组，找到一个合适的元素
		for( j=0; j<size && flag==0; j++ )
		{
			if( strTarget[i] == data[j] )
			{
				ans += data[j];
				break;
			}
			if( strTarget[i] < data[j] )
			{
				ans += data[j];
				flag = 1;
				break;
			}
		}
		if( j >= size ) flag = 2;
		//flag == 2表示前面的数字都相等，只要后面的多一位就行
		if( flag == 2 )
		{
			if( i == 0 )
			{
				//找到一个非0元素
				for( j=0; j<size; j++ )
				{
					if( data[j] > 0 )break;
				}
				ans += data[j];
			}
			else
				ans += data[0];
		}
		//flag == 1表示前面的数字比较大，后面的取最小的数字即可
		if( flag == 1 ) ans += data[0];
	}
	//如果前面的数字都相等
	if( flag == 2 )
	{
		ans *= 10;
		ans += data[0];
	}
	return ans;
}

int main()
{
	int data[] = { 0, 1, 3, 8 };

	cout << NearestInt( 21, data, 4 ) << endl;
	return 0;
}

9. 用C语言实现一个revert函数，它的功能是将输入的字符串在原串上倒序后返回。

基本的字符串操作。应该没有什么问题，比起链表的反转简单多了。

1. char* Revert( char *str )
2. {
3. if( str != NULL )
4. {
5. char *begin = str;
6. char *end = str;
7. while( *end != '\0' ) end++;
8. end--;
9. while( begin != end )
10. {
11. char tmp = *begin;
12. *begin = *end;
13. *end = tmp;
14. begin++;
15. end--;
16. }
17. }
18. return str;
19. }

char* Revert( char *str )
{
	if( str != NULL )
	{
		char *begin = str;
		char *end = str;
		while( *end != '\0' ) end++;
		end--;

		while( begin != end )
		{
			char tmp = *begin;
			*begin = *end;
			*end = tmp;

			begin++;
			end--;
		}
	}
	return str;
}

10.用C语言实现函数void * memmove(void*dest, const void *src, size_t n)。memmove函数的功能是拷贝src所指的内存内容前n个字节到dest所指的地址上。

其实就是自己写一个memcpy函数。注意下面三种情况：

指针为空

两个指针间距过小( 如dest = 10010, src =10020, n = 20 )

void*的转换

1. void* Memmove( void *dest, const void *src, size_t n )
2. {
3. char *cDest = (char*) dest;
4. char *cSrc = (char*) src;
5. assert( cDest != NULL && cSrc != NULL );
6. assert( cDest >= cSrc + n || cSrc >= cDest + n );
7. while( n-- )    *cDest++ = *cSrc++;
8. return dest;
9. }

void* Memmove( void *dest, const void *src, size_t n )
{
	char *cDest = (char*) dest;
	char *cSrc = (char*) src;

	assert( cDest != NULL && cSrc != NULL );
	assert( cDest >= cSrc + n || cSrc >= cDest + n );

	while( n-- )	*cDest++ = *cSrc++;
	return dest;
}

11.有一根厘米的细木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。木杆很细，同时只能通过一只蚂蚁。开始时，蚂蚁的头朝左还是朝右是任意的，它们只会朝前走或调头，但不会后退。当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。

编写程序，求所有蚂蚁都离开木杆的最小时间和最大时间。

不知这题是想考什么。

题目的难点在于：初始状态，蚂蚁的方向任意。因为只有5个蚂蚁，每只蚂蚁的方向只有左、右两种选择，因此5只蚂蚁的初始方向有2^5 = 32种情况。

没有想到什么好的算法，只能枚举所有情况。对每种情况，模拟蚂蚁的爬杆过程：沿初始方向前进、每秒更新一次蚂蚁的位置、更新完成后进行碰撞检测。当所有蚂蚁都爬出细杆后，就可以得到所需时间。最后，在所有的初始情况下，求最小时间和最大时间。索性数据量很小，时间可以接受。

1. const int LEFT = 0;
2. const int RIGHT = 1;
3. //记录每个蚂蚁的初始方向
4. int dir[5];
5. //记录每个蚂蚁的初始位置
6. int pos[5];
7. //记录每个蚂蚁是否爬出了细杆
8. bool isFinish[5];
9. void Init( int  i )
10. {
11. //初始化蚂蚁的方向
12. int tmp = i;
13. int mask = 0x0001;
14. for( int j=0; j<5; j++ )
15. {
16. dir[j] = ( tmp & mask ) ? RIGHT : LEFT;
17. tmp >>= 1;
18. }
19. //初始化蚂蚁的位置
20. pos[0] = 3;
21. pos[1] = 7;
22. pos[2] = 11;
23. pos[3] = 17;
24. pos[4] = 23;
25. //初始化蚂蚁的状态标志
26. memset( isFinish, false, sizeof(isFinish) );
27. }
28. void AntTime( int &maxTime, int &minTime )
29. {
30. int max = 0;
31. int min = 10000000;
32. //依次处理32种情况
33. for( int i=0; i<32; i++ )
34. {
35. Init( i );
36. //记录已经爬出细杆的蚂蚁个数
37. int cnt = 0;
38. //每秒检测一次
39. int time;
40. for( time=1; ; time++ )
41. {
42. //更新蚂蚁位置
43. for( int j=0; j<5; j++ )
44. {
45. if( !isFinish[j] )
46. {
47. if( dir[j] == LEFT )
48. pos[j]--;
49. else
50. pos[j]++;
51. }
52. }
53. //检测蚂蚁是否已爬出细杆
54. for( int m=0; m<5; m++ )
55. {
56. if( !isFinish[m] && ( pos[m] < 0 || pos[m] > 23 ) )
57. {
58. isFinish[m] = true;
59. cnt++;
60. }
61. }
62. //如果所有的蚂蚁都已经爬出细杆，则跳出
63. if( cnt >= 5 ) break;
64. //如果相撞，则掉头
65. for( int k=0; k<5; k++ )
66. {
67. if( !isFinish[k] )
68. {
69. if( ( k == 0 && pos[k] == pos[k+1] ) || ( k == 5 && pos[k] == pos[k-1] ) ||
70. ( ( k > 0 && k < 5 ) && ( pos[k] == pos[k+1] || pos[k] == pos[k-1] ) )
71. )
72. {
73. dir[k] = ( dir == LEFT ) ? RIGHT : LEFT;
74. }
75. }
76. }
77. }
78. if( time > max ) max = time;
79. if( time < min ) min = time;
80. }
81. maxTime = max;
82. minTime = min;
83. }

const int LEFT = 0;
const int RIGHT = 1;

//记录每个蚂蚁的初始方向
int dir[5];
//记录每个蚂蚁的初始位置
int pos[5];
//记录每个蚂蚁是否爬出了细杆
bool isFinish[5];

void Init( int  i )
{
	//初始化蚂蚁的方向
	int tmp = i;
	int mask = 0x0001;
	for( int j=0; j<5; j++ )
	{
		dir[j] = ( tmp & mask ) ? RIGHT : LEFT;
		tmp >>= 1;
	}

	//初始化蚂蚁的位置
	pos[0] = 3;
	pos[1] = 7;
	pos[2] = 11;
	pos[3] = 17;
	pos[4] = 23;

	//初始化蚂蚁的状态标志
	memset( isFinish, false, sizeof(isFinish) );
}

void AntTime( int &maxTime, int &minTime )
{
	int max = 0;
	int min = 10000000;

	//依次处理32种情况
	for( int i=0; i<32; i++ )
	{
		Init( i );	

		//记录已经爬出细杆的蚂蚁个数
		int cnt = 0;

		//每秒检测一次
		int time;
		for( time=1; ; time++ )
		{
			//更新蚂蚁位置
			for( int j=0; j<5; j++ )
			{
				if( !isFinish[j] )
				{
					if( dir[j] == LEFT )
						pos[j]--;
					else
						pos[j]++;
				}
			}

			//检测蚂蚁是否已爬出细杆
			for( int m=0; m<5; m++ )
			{
				if( !isFinish[m] && ( pos[m] < 0 || pos[m] > 23 ) )
				{
					isFinish[m] = true;
					cnt++;
				}
			}

			//如果所有的蚂蚁都已经爬出细杆，则跳出
			if( cnt >= 5 ) break;			

			//如果相撞，则掉头
			for( int k=0; k<5; k++ )
			{
				if( !isFinish[k] )
				{
					if( ( k == 0 && pos[k] == pos[k+1] ) ||	( k == 5 && pos[k] == pos[k-1] ) ||
					    ( ( k > 0 && k < 5 ) && ( pos[k] == pos[k+1] || pos[k] == pos[k-1] ) )
				      )
					{
						dir[k] = ( dir == LEFT ) ? RIGHT : LEFT;
					}
				}
			}
		}

		if( time > max ) max = time;
		if( time < min ) min = time;
	}
	maxTime = max;
	minTime = min;
}

12.请定义一个宏，比较两个数a、b的大小，不能使用大于、小于、if语句

这里有两种做法：正数的绝对值等于本身、两数相减判断符号位

1. #define MAX( a, b ) ( fabs( a, b ) == ( (a) - (b) ) ? (a) : (b) )
2. #define MMAX( a, b ) ( ( ( (a) - (b) ) & ( 1 << 31 ) ) ? (a) : (b) )

#define MAX( a, b ) ( fabs( a, b ) == ( (a) - (b) ) ? (a) : (b) )
#define MMAX( a, b ) ( ( ( (a) - (b) ) & ( 1 << 31 ) ) ? (a) : (b) )

13.两个数相乘，小数点后位数没有限制，请写一个高精度算法

14.有A、B、C、D四个人，要在夜里过一座桥。他们通过这座桥分别需要耗时1、2、5、10分钟，只有一支手电，并且同时最多只能两个人一起过桥。请问，如何安排，能够在17分钟内这四个人都过桥？

这题想想不难，就不知道具体编程应该怎么实现，能想到的就是DFS。这里的17分钟应该就是最短时间了。先不管编程实现了，说说具体的思路吧

首先，要到对岸，每次不能只过一个人。因为这个人拿了手电，其他人都过不了。这样，每次过桥，必须两个人。两个人过去，其中一个人再拿了手电回来。那选哪两个人过去，哪个人再回来？当然是时间最小的啦。所以，5分钟的人和10分钟的人结伴过河，这样可以把5分钟的时间淹没在10分钟内，共需10钟就可以完成。在让时间最小的人拿了手电回去，那自然选1分钟的人了。也就是说，1分钟的人必须在5、10之前到达对岸。

这样，整个过程就是：1、2先到对岸（2Min），2拿了手电返回（2Min），5、10再结伴过桥（10Min），1拿手电返回（1Min），最后1、2结伴过桥（2Min），总共刚好17分钟。

15.有12个小球,外形相同,其中一个小球的质量与其他11个不同，给一个天平,问如何用3次把这个小球找出来，并且求出这个小球是比其他的轻还是重

很久以前的题了，估计大多数人都见过。类似折半查找的方法，把问题的规模以O( lgn )的速度减小。12---6---3---1。当剩3个时，问题最精妙，这时有三种状态可利用：天平左半、天平右边、不在天平两端。这提示我们，其实27个小桥也可以用这个方法。27---9----3----1，即称3次就可以完成。

其实，这里可以总结一个规律：( 3^(n-1), 3^n ]内的数都只需n次就可以完成。即，10、11、12、….、27个球都只用3次就可以。

16.在一个文件中有10G 个整数，乱序排列，要求找出中位数。内存限制为2G。只写出思路即可。

海量数据处理的问题。10G个数，中位数就是第5G、第5G+1个数。回想一下，一般情况下求中位数的做法：类似于快排的partition，找到一个数，使比它小的数的个数占到总数的一半就行。所以，可以把数值空间分段，然后统计每一段中数据的个数，这样就可以很容易的确定中位数在那一段。找个该段后，数据量已经急剧减小了，剩下的问题就好处理了。这种方法可以说是桶排序的思想，也可以说是hash的思想。下面具体分析一下：

因为要统计每一段中数据的个数，所以可以用一个unsigned int型。unsigned int一般占4个字节，可以计数到2^32-1，大约是4G。题目中有10G个数，如果有很多数落在同一个段中，unsigned int肯定不够用。所以，这里的计数用要8字节的long long。即，相当于有一个数组，数组是long long性，数组的每一个元素，代表了一个数据段内的数据个数。这个数组有多大？为了充分利用2G内存，数组大小2G/8 = 256M。即，有数组long long cnt[256M].

假设题目中的10G个数都是4字节的int。如何把这10G个整数，映射到cnt[256M]的数组中。可以使用计算机中的虚拟地址到物理地址的转换。取int的高28位作为数组下标的索引值，这样就可以完成映射。

整个算法的流程：

扫描10G个整数，对每个整数，取高28位，映射到数组的某个元素上

给数组的这个元素加1，表示找到一个属于该数据段的元素

扫描完10G个整数后，数组cnt中就记录了每段中元素的个数

从第一段开始，将元素个数累计，直到值刚好小于5G，则中位数就在该段

这时对10G个整数再扫描一遍，记录该段中每个元素的个数。直至累计到5G即可。

17..一个文件中有40亿个整数，每个整数为四个字节，内存为1GB，写出一个算法：求出这个文件里的整数里不包含的一个整数

方法一：

使用位图。4字节的int，有4G个不同的值。每个值，对应1bit，则共需4G/8 = 512M

内存。初始状态，对512M的位图清零。然后，对这40亿个整数进行统计。如果某个值出现了，那么就把这个值对应的bit置位。最后，扫描位图，找到一个没有被置位的bit即可。

方法二：

分段统计。Long long cnt[512M/8=64M]对应数值空间的64M个数据段。每个数据段包含64个不同值，用一个long long作为这个数据段内的位图，位图占64M*8=512M。

这样扫描一遍40亿个整数后，从数组中找到一个计数小于64的元素，然后查看它的位图，找出未出现的元素。

方法二平均性能应该比方法一快，但它占的内存很恐怖。其实，这两种方法都不是很实际，总共1G的内存，算法就消耗512M甚至1G，那剩下的系统程序怎么办？OS都跑不起来了吧。

18.腾讯服务器每秒有2w个QQ号同时上线，找出5min内重新登入的qq号并打印出来。

这应该是道面试题，面试官随口问了一下。主要是看思路吧。

最简单的想法：直接用STL的set。从某一时刻开始计时，每登陆一个QQ，把它放入set，如果已存则直接打印。直到5min后，就可以over了。下面来简单分析一下算法的负复杂度：

空间复制度：用str存储每个QQ号，假设QQ号有20位，理想情况下每个QQ占20Byte。则5min内的QQ：2w * 60 * 5 = 600w个，需要的存储空间600w * 20byte = 12000w byte = 120M，这样的存储应该可以忍受吧。

时间复杂度：STL的set是用二叉树（更确切的说是：红黑树）实现的，查找效率是O( lgn )，应该还是挺快的吧。

呃，有人说不让用STL。那就自己设计一个数据结构呗。该用什么数据结构呢？想了想，还是继续用树，这里用一个trie tree吧。节点内容包括QQ号、指向子节点的指针（这里有10个，认为QQ由0---9的数字组成）。登陆时间要不要？考虑这样一个问题：是否需要把所有的QQ都保存在内存中？随着时间的增加，登陆的QQ会越来越多，比较好的方法是把长时间不登陆的QQ释放掉。所以需要记录登陆时间，以便于释放长期不登陆的QQ。

1. struct TrieNode
2. {
3. string qq;
4. int lastLoginTime;
5. TrieNode *next[10];
6. };

struct TrieNode
{
	string qq;
	int lastLoginTime;
	TrieNode *next[10];
};

我们的trie上的操作主要有两个：查找并插入、删除。也就是说，这颗树是不断动态变化的，我们需要维护它。

来自：经典面试题（二）附答案 算法+数据结构+代码 微软Microsoft、谷歌Google、百度、腾讯 - sj13051180的专栏 - 博客频道 - CSDN.NET
http://blog.csdn.net/sj13051180/article/details/6733655