http://www.cnblogs.com/xwdreamer/archive/2011/12/13/2296910.html
44.腾讯面试题：
1.设计一个魔方（六面）的程序。
2.有一千万条短信，有重复，以文本文件的形式保存，一行一条，有重复。
请用5分钟时间，找出重复出现最多的前10条。
3.收藏了1万条url，现在给你一条url，如何找出相似的url。（面试官不解释何为相似）
45.雅虎：
1.对于一个整数矩阵，存在一种运算，对矩阵中任意元素加一时，需要其相邻（上下左右）
某一个元素也加一，现给出一正数矩阵，判断其是否能够由一个全零矩阵经过上述运算得到。
2.一个整数数组，长度为n，将其分为m份，使各份的和相等，求m的最大值
比如{3，2，4，3，6} 可以分成{3，2，4，3，6} m=1;
{3,6}{2,4,3} m=2
{3,3}{2,4}{6} m=3 所以m的最大值为3
46.搜狐：
四对括号可以有多少种匹配排列方式？比如两对括号可以有两种：（）（）和（（））
47.创新工场：
求一个数组的最长递减子序列 比如{9，4，3，2，5，4，3，2}的最长递减子序列为{9，5，4，3，2}
48.微软：
一个数组是由一个递减数列左移若干位形成的，比如{4，3，2，1，6，5}
是由{6，5，4，3，2，1}左移两位形成的，在这种数组中查找某一个数。
49.一道看上去很吓人的算法面试题：
如何对n个数进行排序，要求时间复杂度O(n)，空间复杂度O(1)
50.网易有道笔试：
1.求一个二叉树中任意两个节点间的最大距离，两个节点的距离的定义是 这两个节点间边的个数，
比如某个孩子节点和父节点间的距离是1，和相邻兄弟节点间的距离是2，优化时间空间复杂度。
2.求一个有向连通图的割点，割点的定义是，
如果除去此节点和与其相关的边，有向图不再连通，描述算法。
——————————————————————-
51.和为n连续正数序列。
题目：输入一个正数n，输出所有和为n连续正数序列。
例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以输出3个连续序列1-5、4-6和7-8。
分析：这是网易的一道面试题。
52.二元树的深度。
题目：输入一棵二元树的根结点，求该树的深度。
从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
例如：输入二元树：
10
/
6 14
/ /
4 12 16
输出该树的深度3。
二元树的结点定义如下：
struct SBinaryTreeNode // a node of the binary tree
{
int m_nValue; // value of node
SBinaryTreeNode m_pLeft; // left child of node
SBinaryTreeNode m_pRight; // right child of node
};
分析：这道题本质上还是考查二元树的遍历。
53.字符串的排列。
题目：输入一个字符串，打印出该字符串中字符的所有排列。
例如输入字符串abc，则输出由字符a、b、c所能排列出来的所有字符串
abc、acb、bac、bca、cab和cba。
分析：这是一道很好的考查对递归理解的编程题，
因此在过去一年中频繁出现在各大公司的面试、笔试题中。
54.调整数组顺序使奇数位于偶数前面。
题目：输入一个整数数组，调整数组中数字的顺序，使得所有奇数位于数组的前半部分，
所有偶数位于数组的后半部分。要求时间复杂度为O(n)。
55.
题目：类CMyString的声明如下：
class CMyString
{
public:
CMyString(char pData = NULL);
CMyString(const CMyString& str);
~CMyString(void);
CMyString& operator = (const CMyString& str);
private:
char m_pData;
};
请实现其赋值运算符的重载函数，要求异常安全，即当对一个对象进行赋值时发生异常，对象的状态不能改变。
56.最长公共字串。
题目：如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中，
则字符串一称之为字符串二的子串。
注意，并不要求子串（字符串一）的字符必须连续出现在字符串二中。
请编写一个函数，输入两个字符串，求它们的最长公共子串，并打印出最长公共子串。
例如：输入两个字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它们的最长公共子串，
则输出它们的长度4，并打印任意一个子串。
分析：求最长公共子串（Longest Common Subsequence, LCS）是一道非常经典的动态规划题，
因此一些重视算法的公司像MicroStrategy都把它当作面试题。
57.用俩个栈实现队列。
题目：某队列的声明如下：
template<typename T> class CQueue
{
public:
CQueue() {}
~CQueue() {}
void appendTail(const T& node); // append a element to tail
void deleteHead(); // remove a element from head
private:
T> m_stack1;
T> m_stack2;
};
分析：从上面的类的声明中，我们发现在队列中有两个栈。
因此这道题实质上是要求我们用两个栈来实现一个队列。
相信大家对栈和队列的基本性质都非常了解了：栈是一种后入先出的数据容器，
因此对队列进行的插入和删除操作都是在栈顶上进行；队列是一种先入先出的数据容器，
我们总是把新元素插入到队列的尾部，而从队列的头部删除元素。
58.从尾到头输出链表。
题目：输入一个链表的头结点，从尾到头反过来输出每个结点的值。链表结点定义如下：
struct ListNode
{
int m_nKey;
ListNode m_pNext;
};
分析：这是一道很有意思的面试题。
该题以及它的变体经常出现在各大公司的面试、笔试题中。
59.不能被继承的类。
题目：用C++设计一个不能被继承的类。
分析：这是Adobe公司2007年校园招聘的最新笔试题。
这道题除了考察应聘者的C++基本功底外，还能考察反应能力，是一道很好的题目。
60.在O（1）时间内删除链表结点。
题目：给定链表的头指针和一个结点指针，在O(1)时间删除该结点。链表结点的定义如下：
struct ListNode
{
int m_nKey;
ListNode m_pNext;
};
函数的声明如下：
void DeleteNode(ListNode pListHead, ListNode pToBeDeleted);
分析：这是一道广为流传的Google面试题，能有效考察我们的编程基本功，还能考察我们的反应速度，
更重要的是，还能考察我们对时间复杂度的理解。
————————————————————————-
61.找出数组中两个只出现一次的数字
题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。
请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
分析：这是一道很新颖的关于位运算的面试题。
62.找出链表的第一个公共结点。
题目：两个单向链表，找出它们的第一个公共结点。
链表的结点定义为：
struct ListNode
{
int m_nKey;
ListNode m_pNext;
};
分析：这是一道微软的面试题。微软非常喜欢与链表相关的题目，
因此在微软的面试题中，链表出现的概率相当高。
63.在字符串中删除特定的字符。
题目：输入两个字符串，从第一字符串中删除第二个字符串中所有的字符。
例如，输入”They are students.”和”aeiou”，
则删除之后的第一个字符串变成”Thy r stdnts.”。
分析：这是一道微软面试题。在微软的常见面试题中，与字符串相关的题目占了很大的一部分，
因为写程序操作字符串能很好的反映我们的编程基本功。
64. 寻找丑数。
题目：我们把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，
但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。
求按从小到大的顺序的第1500个丑数。
分析：这是一道在网络上广为流传的面试题，据说google曾经采用过这道题。
65.输出1到最大的N位数
题目：输入数字n，按顺序输出从1最大的n位10进制数。比如输入3，
则输出1、2、3一直到最大的3位数即999。
分析：这是一道很有意思的题目。看起来很简单，其实里面却有不少的玄机。
66.颠倒栈。
题目：用递归颠倒一个栈。例如输入栈{1, 2, 3, 4, 5}，1在栈顶。
颠倒之后的栈为{5, 4, 3, 2, 1}，5处在栈顶。
67.俩个闲玩娱乐。
1.扑克牌的顺子
从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。
2-10为数字本身，A为1，J为11，Q为12，K为13，而大小王可以看成任意数字。
2.n个骰子的点数。
把n个骰子扔在地上，所有骰子朝上一面的点数之和为S。输入n，
打印出S的所有可能的值出现的概率。
68.把数组排成最小的数。
题目：输入一个正整数数组，将它们连接起来排成一个数，输出能排出的所有数字中最小的一个。
例如输入数组{32, 321}，则输出这两个能排成的最小数字32132。
请给出解决问题的算法，并证明该算法。
分析：这是09年6月份百度的一道面试题，
从这道题我们可以看出百度对应聘者在算法方面有很高的要求。
69.旋转数组中的最小元素。
题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个排好序的数组的一个旋转，
输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1。
分析：这道题最直观的解法并不难。从头到尾遍历数组一次，就能找出最小的元素，
时间复杂度显然是O(N)。但这个思路没有利用输入数组的特性，我们应该能找到更好的解法。
70.给出一个函数来输出一个字符串的所有排列。
ANSWER 简单的回溯就可以实现了。当然排列的产生也有很多种算法，去看看组合数学，
还有逆序生成排列和一些不需要递归生成排列的方法。
印象中Knuth的<TAOCP>第一卷里面深入讲了排列的生成。这些算法的理解需要一定的数学功底，
也需要一定的灵感，有兴趣最好看看。
71.数值的整数次方。
题目：实现函数double Power(double base, int exponent)，求base的exponent次方。
不需要考虑溢出。
分析：这是一道看起来很简单的问题。可能有不少的人在看到题目后30秒写出如下的代码：
double Power(double base, int exponent)
{
double result = 1.0;
for(int i = 1; i <= exponent; ++i)
result = base;
return result;
}
72.
题目：设计一个类，我们只能生成该类的一个实例。
分析：只能生成一个实例的类是实现了Singleton模式的类型。
73.对策字符串的最大长度。
题目：输入一个字符串，输出该字符串中对称的子字符串的最大长度。
比如输入字符串“google”，由于该字符串里最长的对称子字符串是“goog”，因此输出4。
分析：可能很多人都写过判断一个字符串是不是对称的函数，这个题目可以看成是该函数的加强版。
74.数组中超过出现次数超过一半的数字
题目：数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。
分析：这是一道广为流传的面试题，包括百度、微软和Google在内的多家公司都
曾经采用过这个题目。要几十分钟的时间里很好地解答这道题，
除了较好的编程能力之外，还需要较快的反应和较强的逻辑思维能力。
75.二叉树两个结点的最低共同父结点
题目：二叉树的结点定义如下：
struct TreeNode
{
int m_nvalue;
TreeNode m_pLeft;
TreeNode m_pRight;
};
输入二叉树中的两个结点，输出这两个结点在数中最低的共同父结点。
分析：求数中两个结点的最低共同结点是面试中经常出现的一个问题。这个问题至少有两个变种。
76.复杂链表的复制
题目：有一个复杂链表，其结点除了有一个m_pNext指针指向下一个结点外，
还有一个m_pSibling指向链表中的任一结点或者NULL。其结点的C++定义如下：
struct ComplexNode
{
int m_nValue;
ComplexNode m_pNext;
ComplexNode m_pSibling;
};
下图是一个含有5个结点的该类型复杂链表。
图中实线箭头表示m_pNext指针，虚线箭头表示m_pSibling指针。为简单起见，
指向NULL的指针没有画出。
请完成函数ComplexNode Clone(ComplexNode pHead)，以复制一个复杂链表。
分析：在常见的数据结构上稍加变化，这是一种很新颖的面试题。
要在不到一个小时的时间里解决这种类型的题目，我们需要较快的反应能力，
对数据结构透彻的理解以及扎实的编程功底。
77.关于链表问题的面试题目如下：
1.给定单链表，检测是否有环。
使用两个指针p1,p2从链表头开始遍历，p1每次前进一步，p2每次前进两步。如果p2到达链表尾部，
说明无环，否则p1、p2必然会在某个时刻相遇(p1==p2)，从而检测到链表中有环。
2.给定两个单链表(head1, head2)，检测两个链表是否有交点，如果有返回第一个交点。
如果head1==head2，那么显然相交，直接返回head1。
否则，分别从head1,head2开始遍历两个链表获得其长度len1与len2，假设len1>=len2，
那么指针p1由head1开始向后移动len1-len2步，指针p2=head2，
下面p1、p2每次向后前进一步并比较p1p2是否相等，如果相等即返回该结点，
否则说明两个链表没有交点。
3.给定单链表(head)，如果有环的话请返回从头结点进入环的第一个节点。
运用题一，我们可以检查链表中是否有环。
如果有环，那么p1p2重合点p必然在环中。从p点断开环，
方法为：p1=p, p2=p->next, p->next=NULL。此时，原单链表可以看作两条单链表，
一条从head开始，另一条从p2开始，于是运用题二的方法，我们找到它们的第一个交点即为所求。
4.只给定单链表中某个结点p(并非最后一个结点，即p->next!=NULL)指针，删除该结点。
办法很简单，首先是放p中数据,然后将p->next的数据copy入p中，接下来删除p->next即可。
5.只给定单链表中某个结点p(非空结点)，在p前面插入一个结点。
办法与前者类似，首先分配一个结点q，将q插入在p后，接下来将p中的数据copy入q中，
然后再将要插入的数据记录在p中。
78.链表和数组的区别在哪里？
分析：主要在基本概念上的理解。
但是最好能考虑的全面一点，现在公司招人的竞争可能就在细节上产生，
谁比较仔细，谁获胜的机会就大。
79.
1.编写实现链表排序的一种算法。说明为什么你会选择用这样的方法？
2.编写实现数组排序的一种算法。说明为什么你会选择用这样的方法？
3.请编写能直接实现strstr()函数功能的代码。
80.阿里巴巴一道笔试题
问题描述:
12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?
这个笔试题,很YD,因为把某个递归关系隐藏得很深。
先来几组百度的面试题：
===================
81.第1组百度面试题
1.一个int数组，里面数据无任何限制，要求求出所有这样的数a[i]，
其左边的数都小于等于它，右边的数都大于等于它。
能否只用一个额外数组和少量其它空间实现。
2.一个文件，内含一千万行字符串，每个字符串在1K以内，
要求找出所有相反的串对，如abc和cba。
3.STL的set用什么实现的？为什么不用hash？
82.第2组百度面试题
1.给出两个集合A和B，其中集合A={name}，
集合B={age、sex、scholarship、address、…}，
要求：
问题1、根据集合A中的name查询出集合B中对应的属性信息；
问题2、根据集合B中的属性信息（单个属性，如age<20等），查询出集合A中对应的name。
2.给出一个文件，里面包含两个字段{url、size}，
即url为网址，size为对应网址访问的次数，
要求：
问题1、利用Linux Shell命令或自己设计算法，
查询出url字符串中包含“baidu”子字符串对应的size字段值；
问题2、根据问题1的查询结果，对其按照size由大到小的排列。
（说明：url数据量很大，100亿级以上）
83.第3组百度面试题
1.今年百度的一道题目
百度笔试：给定一个存放整数的数组，重新排列数组使得数组左边为奇数，右边为偶数。
要求：空间复杂度O(1)，时间复杂度为O（n）。
2.百度笔试题
用C语言实现函数void memmove(void dest, const void src, size_t n)。
memmove函数的功能是拷贝src所指的内存内容前n个字节到dest所指的地址上。
分析：
由于可以把任何类型的指针赋给void类型的指针
这个函数主要是实现各种数据类型的拷贝。
84.第4组百度面试题
2010年3道百度面试题[相信，你懂其中的含金量]
1.a~z包括大小写与0~9组成的N个数
用最快的方式把其中重复的元素挑出来。
2.已知一随机发生器，产生0的概率是p，产生1的概率是1-p，现在要你构造一个发生器，
使得它构造0和1的概率均为1/2；构造一个发生器，使得它构造1、2、3的概率均为1/3；…，
构造一个发生器，使得它构造1、2、3、…n的概率均为1/n，要求复杂度最低。
3.有10个文件，每个文件1G，
每个文件的每一行都存放的是用户的query，每个文件的query都可能重复。
要求按照query的频度排序.
85.又见字符串的问题
1.给出一个函数来复制两个字符串A和B。
字符串A的后几个字节和字符串B的前几个字节重叠。
分析：记住，这种题目往往就是考你对边界的考虑情况。
2.已知一个字符串，比如asderwsde,寻找其中的一个子字符串比如sde的个数，
如果没有返回0，有的话返回子字符串的个数。
86.
怎样编写一个程序，把一个有序整数数组放到二叉树中？
分析:本题考察二叉搜索树的建树方法，简单的递归结构。
关于树的算法设计一定要联想到递归，因为树本身就是递归的定义。
而，学会把递归改称非递归也是一种必要的技术。
毕竟，递归会造成栈溢出，关于系统底层的程序中不到非不得以最好不要用。
但是对某些数学问题，就一定要学会用递归去解决。
87.
1.大整数数相乘的问题。（这是2002年在一考研班上遇到的算法题）
2.求最大连续递增数字串（如“ads3sl456789DF3456ld345AA”中的“456789”）
3.实现strstr功能，即在父串中寻找子串首次出现的位置。
（笔试中常让面试者实现标准库中的一些函数）
88.2005年11月金山笔试题。编码完成下面的处理函数。
函数将字符串中的字符''移到串的前部分，
前面的非''字符后移，但不能改变非''字符的先后顺序，函数返回串中字符''的数量。
如原始串为：abcde12，
处理后为*abcde12，函数并返回值为5。（要求使用尽量少的时间和辅助空间）
89.神州数码、华为、东软笔试题
1.2005年11月15日华为软件研发笔试题。实现一单链表的逆转。
2.编码实现字符串转整型的函数（实现函数atoi的功能），据说是神州数码笔试题。如将字符
串 ”+123”123, ”-0123”-123, “123CS45”123, “123.45CS”123, “CS123.45”0
3.快速排序（东软喜欢考类似的算法填空题，又如堆排序的算法等）
4.删除字符串中的数字并压缩字符串。
如字符串”abc123de4fg56”处理后变为”abcdefg”。注意空间和效率。
（下面的算法只需要一次遍历，不需要开辟新空间，时间复杂度为O(N)）
5.求两个串中的第一个最长子串（神州数码以前试题）。
如"abractyeyt","dgdsaeactyey"的最大子串为"actyet"。
90.
1.不开辟用于交换数据的临时空间，如何完成字符串的逆序
(在技术一轮面试中，有些面试官会这样问)。
2.删除串中指定的字符
（做此题时，千万不要开辟新空间，否则面试官可能认为你不适合做嵌入式开发）
3.判断单链表中是否存在环。
91.
1.一道著名的毒酒问题
有1000桶酒，其中1桶有毒。而一旦吃了，毒性会在1周后发作。
现在我们用小老鼠做实验，要在1周内找出那桶毒酒，问最少需要多少老鼠。
2.有趣的石头问题
有一堆1万个石头和1万个木头，对于每个石头都有1个木头和它重量一样，
把配对的石头和木头找出来。