这里用来记录我积累的面试题
基本
1.c++虚函数
解答：
这个直接百度吧：http://baike.baidu.com/view/161302.htm
2.C语言，下面两个表达式是否相等
if(strlen(x)>=strlen(y))...
if(strlen(x)-strlen(y)>=0)...
解答：
不一定相等。第二条语句结果永远为真。strlen的返回值是无符号整数。两个无符号整数的结果也是无符号整数，结果永远为真。
3.请列举面向对象设计的三个基本要素及五种主要设计原则。
http://blog.163.com/lee_020/blog/static/1247556020129237189609/
4.简述windows内存管理的几种方式及其优缺点。
5.简述数据库以及线程产生的原理及其必要条件。
http://www.cnblogs.com/cxd4321/archive/2012/05/28/2521542.html
6.C++的内存分配几种方式及其注意事项。
内存的三种分配方式：
1． 从静态存储区分配：此时的内存在程序编译的时候已经分配好，并且在程序的整个运行期间都存在。全局变量，static变量等在此存储。
2． 在栈区分配：相关代码执行时创建，执行结束时被自动释放。局部变量在此存储。栈内存分配运算内置于处理器的指令集中，效率高，但容量有限。
3． 在堆区分配：动态分配内存。用new/malloc时开辟，delete/free时释放。生存期由用户指定，灵活。但有内存泄露等问题。
有一篇blog讲c++内存管理的，很不错。
http://www.cnblogs.com/lancidie/archive/2011/08/05/2128318.html
7.稳定的排序算法有哪几种？
快速排序、希尔排序、堆排序、直接选择排序不是稳定的排序算法，而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法
http://baike.baidu.com/view/547325.htm?fromTaglist
8.面向对象中，const 函数的处理，出现继承是又怎么处理？
9.类似printf能够接受变长字符串 call？
10c#/java的多维数组。
http://www.cnblogs.com/tianhao960/articles/273425.html
11.shared_ptr,auto_ptr
12单例模式
http://blog.csdn.net/boyhailong/article/details/6645681
13 const的基本概念。
http://baike.baidu.com/view/1065598.htm
14.TCP/IP协议分了几层？每一层有哪些功能？为什么要有网络层？
http://baike.soso.com/v6873774.htm
15. TCP协议的三次握手分析？
http://www.cnblogs.com/rootq/articles/1377355.html
16.调用惯例
http://blog.csdn.net/zhu_liangwei/article/details/9703383
17.重载函数
出现在相同作用域中的两个函数，如果具有相同的名字而形参不同，则成为重载函数。
函数不能仅仅基于不同的返回值类型而实现重载。
任何程序都经由一个main函数实例。main函数不能重载。
函数重载确定（即函数配匹）是将函数调用与重载函数集合中的一个函数相关联的过程。通过自动提取函数调用中实际使用的实际参数与重载集合中各个函数提供的形参做比较，编译器实现该调用与函数匹配。匹配结果有三种可能：
（1）编译器找到与实惨最佳匹配的函数，并生成调用该函数的代码。
（2）找不到形参与函数调用的实参匹配的函数，这种情况下，编译器将给出编译错误信息。
（3）存在多个与实参匹配的函数，但没有一二是明确的最佳选择。这种情况也是错误的，该调用具有二义性。
void f(); void f(int); void f(int, int); void f(double,double = 3.14);
函数调用：f(42,2.56)
重载确定的三个步骤：
1.候选函数：确定该调用所考虑的重载函数集合。
2.选择可行函数：从候选函数中选择一个或多个函数，它们能够用该调用中指定的实参来调用。f(int ,int),f(double,double).
3.寻找最佳匹配（如果有）：原则是实参类型与形参类型越接近则匹配越佳。
4.含有多个形参的重载确定
编译器通过依次检查每一个实例来决定哪个或那些函数匹配最佳。如果有且仅有一个函数满足下列条件，则匹配成功：
（1）其每个实参的匹配都不劣于其他可行函数需要的匹配。
（2）至少有一个实参的匹配由于其他可行函数提供的匹配。
检查了所有实参后，仍找不到唯一最佳匹配函数，则该调用错误。这个例子具有二义性。错误。
操作系统
1.进程间通信方式。
2.进程和线程的基本概念。
设计模式
1.MVC
网络
1..tcp协议的特点
算法
1.非递归中序（后序，先序）遍历二叉树
2.只用位运算求a+b
#include<stdio.h>
int add(int a,int b)
{
int s,w,tmp;
s=a^b;
w=a&b;
while(w){
tmp=s;
s=s^(w<<1);
w=tmp&(w<<1);
}
return s;
}
int main()
{
int a,b;
scanf("%d%d",&a,&b);
printf("a+b=%d\n",add(a,b));
return 0;
}
简单版本函数
int add2(int a,int b)
{
if(b)
return add2(a^b,(a&b)<<1);
else
return a;
}
3.用只能产生1-5之间随机数的函数，产生1-7的随机数。
4.一个大小为n的数组，里面的数都属于范围[0, n-1]，有不确定的重复元素，找到至少一个重复元素，要求O(1)空间和O(n)时间。
http://blog.csdn.net/morewindows/article/details/8204460
http://blog.csdn.net/morewindows/article/details/8212446
仿照这篇文章粗略写了一个：
#include<stdio.h>
int FindRepeat(int *a,int n)
{
int i;
for(i=0;i<n;i++){
int tmp=a[i]>=n?a[i]-n:a[i];
if(a[tmp]>=n)
return tmp;
else
a[tmp]+=n;
}
return -1;
}
void printarray(const int *a,int n)
{
int i;
for(i=0;i<n;i++)
printf("%4d",a[i]);
printf("\n");
}
int main()
{
#define N 10
int a[N]={0,3,2,4,5,4,7,6,9,0};
printarray(a,N);
printf("%d\n",FindRepeat(a,N));
return 0;
}
5.公司组织一次羽毛球比赛，采用淘汰制，假设公司有1001个人，如果要评出“羽毛球第一”至少要进行多少场的比赛？请简述过程，并编写代码模拟比赛过程？（百度）
想法：1001一个人选出第一，一定要淘汰1000个人，一场比赛只可淘汰一个人，所有至少1000场比赛。
6一百个灯泡排成一排，第一轮将所有灯泡打开；第二轮每隔一个灯泡关掉一个。即排在偶数的灯泡被关掉，第三轮每隔两个灯泡，将开着的灯泡关掉，关掉的灯泡打开。依次类推，第100轮结束的时候，还有几盏灯泡亮着？（百度）
http://www.51projob.com/a/baidu/20121009/1188.html
7.二分法查找，可以设定当出现重复数时，可选其中的最前一个（或最后一个）？
8.最短路径的求法。
9.在N个整数查找序列中的最大数和最小数 及 所需要的比较次数？
http://blog.csdn.net/zoushidexing/article/details/8798469
10.shell 中标准输出和错误输出的区别？（搜狐）
11.如何随机选取1000个关键字 。给定一个数据流，其中包含无穷尽的搜索关键字（比如，人们在谷歌搜索时不断输入的关键字）。如何才能从这个无穷尽的流中随机的选取1000个关键字？ （Google，百度）
定义长度为1000的数组。
对于数据流中的前1000个关键字，显然都要放到数组中。
对于数据流中的的第n（n>1000）个关键字，我们知道这个关键字被随机选中的概率为 1000/n。所以我们以 1000/n 的概率用这个关键字去替换数组中的随机一个。这样就可以保证所有关键字都以 1000/n的概率被选中。
对于后面的关键字都进行这样的处理，这样我们就可以保证数组中总是保存着1000个随机关键字。
类似这一题：
给定一个未知长度的整数流，如何随机选取一个数
方法1.
将整个整数流保存到一个数组中，然后再随机选取。
如果整数流很长，无法保存下来，则此方法不能使用。
方法2.
如果整数流在第一个数后结束，则我们必定会选第一个数作为随机数。
如果整数流在第二个数后结束，我们选第二个数的概率为1/2。我们以1/2的概率用第2个数替换前面选的随机数，得到满足条件的新随机数。
....
如果整数流在第n个数后结束，我们选第n个数的概率为1/n。我们以1/n的概率用第n个数替换前面选的随机数，得到满足条件的新随机数。
....
利用这种方法，我们只需保存一个随机数，和迄今整数流的长度即可。所以可以处理任意长的整数流。
蓄水池抽象算法：http://blog.jobbole.com/42550/
12.给定一个固定长度的数组，将递增整数序列写入这个数组。当写到数组尾部时，返回数组开始重新写，并覆盖先前写过的数。请在这个特殊数组中找出给定的整数？（Google）
13.给定两个已排序序列，找出共同的元素。 （Google）
14.找到链表的倒数第m个节点。（Google）
想法：使用两个指针，并使它们指向的节点相距m-1个。然后同时向前移动两个指针，当一个指针指最后一个节点时，第二个指针指向倒数第m个节点。
15. 给定一个排序数组，如何构造一个二叉排序树（二叉查找树，Binary Sort Tree)？（Google）
16.将无向无环连通图转换成深度最小的树 （Goolge）
想法：题目可以等价于找到了两个叶节点，使得两个叶节点之间的距离最远。根节点就是这两个叶节点路径的中间点（或者中间两个点的任意一个）。我们可以每次都将连接度为1的节点删掉，直到最后只剩下1个或2个节点，则这一个节点，或者两个节点中的任意一个，就是我们要找的根节点。
17.有一个特殊的链表，其中每个节点不但有指向下一个节点的指针pNext，还有一个指向链表中任意节点的指针pRand，如何拷贝这个特殊链表？ （Google，百度）
18.将字符串中的小写字母排在大写字母的前面 有一个由大小写组成的字符串，现在需要对它进行修改，将其中的所有小写字母排在大写字母的前面（大写或小写字母之间不要求保持原来次序）。
19.有n个红蓝绿3种不同颜色的球，随机排成一列。现在需要使同种颜色的球排在一起并且按红蓝绿的顺序。
荷兰国旗问题：http://blog.csdn.net/zhu_liangwei/article/details/10097657
挑战你的逻辑
1.5个人分蛋糕
2.死囚犯猜帽子颜色
3.老鼠测试毒药。
有1000瓶药，其中有且只有一瓶是毒药。现在有10只小白鼠可用于测试毒药。小白鼠在服用毒药之后一个星期之后死亡。问，1.给你一个星期，如何测试出毒药？2.给你两个星期，你需要多少只老鼠？
4.等车概率问题
5.下棋输赢问题
6.电梯选楼层问题
7.海盗分金币问题
8.假定一个国家，生男孩的和生女孩的概率相等（0.5）。这个国家的父母特别喜欢男孩子，所有有孩子的家庭都要是在生一个男孩之后才停止生育。求问，若干年后，该国家的男女比例是多少？
9.现有140g沙子， 给你一台天平，天平只有7g和2g砝码各一个，让你称出90克的沙子出来？
10.给定一个数N，找出所有小于N的质数？
11.随机生成和为S的N个正整数？
这个解法很好：http://blog.csdn.net/morewindows/article/details/8439393
12.N个球中有且只有一个重量少于其他的球，外形相同。采用三次天平称重，N最多是多少？
13.如果在高速公路上30分钟内看到一辆车开过的几率是0.95，那么在10分钟内看到一辆车开过的几率是多少？(假设为常概率条件下)
参考资料：
编程之美
Pointers on C
C++ Primer
C Traps and Pitfalls
谷歌笔试题：
http://tieba.baidu.com/p/1567915420