算法面试题总结.doc

算法面试题总结

资料仅供参考
1 算法面试题总结
1.把二元查找树转变成排序的双向链表
 题目：
输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。
要求不能创立任何新的结点，只调整指针的指向。
   10
  / \
  6  14
 / \ / \
4  8 12 16
 转换成双向链表
4=6=8=10=12=14=16。
解：首先我们定义的二元查找树 节点的数据结构如下：
 typedef struct tree
{
  int data; // value of node
  struct tree *left; // left child of node
  struct tree *right; // right child of node
}*ptree;

ptree f(ptree root,int sign)//sign==0返回链头，sign==1返回链尾
{ //main函数中调用f(root,0);
ptree p=root;
if(p->left) //如果左子树非空
{
p->left = f(p->left,1);//第4个参数为，表明f函数返回root左子树中根的链尾
p->left->right = p; //双链表中left记录前驱，right记录后继
}
if(p->right)
{
p->right=f(p->right,0);
p->right->left = p;
}
if(sign==0) while(p->left) p=p->left ;//顺着left找到双链表首元素
else while(p->right)p=p->right;//顺着right找到双链表尾元素
return p;
}

2.设计包含min函数的栈。
定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。
要求函数min、push以及pop的时间复杂度都是O(1)。

3.求子数组的最大和
题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，
因此输出为该子数组的和18。
解：设数组元素为a[1~n]，f(i)表示以a[i]为尾元素的最大子段和，则有
f(1)=a[1], f(i)=max{f(i-1)+a[i], a[i]} (i>1)
动态规划求f(i), b[i]保存f(i)的值。
Int f(int i)
{ int j,max;
max=b[1]=a[1];
for(j=2;j<=I;j++)
{
b[i]=a[i-1]>0? a[i-1]+a[i] : a[i];
if(b[i]>max) max=b[i];
}
return max;//返回b[1]~b[i]中最大值
}

4.在二元树中找出和为某一值的所有路径
题目：输入一个整数和一棵二元树。
从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。
打印出和与输入整数相等的所有路径。
例如 输入整数22和如下二元树
  10  
  / \   
 5  12   
 /   \   
4     7
则打印出两条路径：10, 12和10, 5, 7。
解：首先我们定义的二元查找树 节点的数据结构如下：
 typedef struct tree
{
  int data; // value of node
  struct tree *left; // left child of node
  struct tree *right; // right child of node
}*ptree;

ptree X[MAX];//X记住路径
设树的根为root; 指定和为S，以下为回溯算法
void f(int k, ptree root, int sum)//sum为已访问结点元素之和
{ int j, ss=sum+root->data;
X[k]=root;
if(ss ==S)
{
printf(“\n”);
for(j=1;j<=k;j++) printf(“%d ”,X[j]->data);
}
else
{
if(root->left && ssleft,ss);
if(root->right&&ssright,ss);
}
}

5.查找最小的k个元素
题目：输入n个整数，输出其中最小的k个。
例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。
解：1：能够借用找第k小元素的办法，当找到第k小元素时，这一元素和它左边的元素构成最小的k个元素。
2：能够考虑用小堆排序的办法，每一次小堆调整得到最小的元素，进行k次小堆调整即可得到k个最小元素的有序序列。

第6题
腾讯面试题： 
给你10分钟时间，根据上排给出十个数，在其下排填出对应的十个数 
要求下排每个数都是先前上排那十个数在下排出现的次数。 
上排的十个数如下： 
【0，1，2，3，4，5，6，7，8，9】
举一个例子， 
数值: 0,1,2,3,4,5,6,7,8,9 
分配: 6,2,1,0,0,0,1,0,0,0 
0在下排出现了6次，1在下排出现了2次， 
2在下排出现了1次，3在下排出现了0次.... 
以此类推..
解：设X[0~9]分别为数字0~9出现次数，即回溯算法求解向量，同时用S[0~9]记住X[0~9]中数字0~9出现次数。
【0，1，2，3，4，5，6，7，8，9】，
X[]={ }
void f(int k)
{ int j;
if(k==10) for(j=0;j<10;j++) cout<j]<<” ”;
else for(j=0;j<10;j++)
{ X[k]=j;
S[j]++;
f(k+1);
S[j]--;
}
}
void main( ){ f(0); }
第7题
微软亚院之编程判断俩个链表是否相交
给出俩个单向链表的头指针，比如h1，h2，判断这俩个链表是否相交。
为了简化问题，我们假设俩个链表均不带环。
解：无环且能相交，形状应该只能为
简单的处理，即对两个单链表都访问到尾结点，看最后访问的尾结点是否相同。
问题扩展：
1.如果链表可能有环列?
2.如果需要求出俩个链表相交的第一个节点列?

第8题
此贴选一些 比较怪的题，，由于其中题目本身与算法关系不大，仅考考思维。特此并作一题。
1.有两个房间，一间房里有三盏灯，另一间房有控制着三盏灯的三个开关，
这两个房间是 分割开的，从一间里不能看到另一间的情况。
现在要求受训者分别进这两房间一次，然后判断出这三盏灯分别是由哪个开关控制的。
有什么办法呢？
解：灯的亮灭只有2种状态，开关也只有2种状态，可是需要区分3盏灯，增加一个新状态量：加热一定时间的灯泡会发热。这样的话，能够区分的灯能够增加到4盏，
进开关所在屋，闭合开关1,2，约5分钟后，关闭1，闭合开关3，进入灯所在屋，发光又发热被2控制，发光不发热的被3控制，不发光而发热的被1控制，不发光不发热的被4控制。

2.你让一些人为你工作了七天，你要用一根金条作为报酬。金条被分成七小块，每天给出一块。
如果你只能将金条切割两次，你怎样分给这些工人?
解：7=1+2+4

3.
★用一种算法来颠倒一个链接表的顺序。现在在不用递归式的情况下做一遍。
解：用单链表的头插法，把从头到尾的结点依次重新插入依次。
★用一种算法在一个循环的链接表里插入一个节点，但不得穿越链接表。

★用一种算法整理一个数组。你为什么选择这种方法?

★用一种算法使通用字符串相匹配。

★颠倒一个字符串。优化速度。优化空间。

★颠倒一个句子中的词的顺序，比如将“我叫克丽丝”转换为“克丽丝叫我”，实现速度最快，移动最少。
词？ 是“克丽丝叫我”还是“丝丽克叫我”？
★找到一个子字符串。优化速度。优化空间。

★比较两个字符串，用O(n)时间和恒量空间。
解：int strcmp(char *s1, char *s2)
{
while(*s1 && *s2 && *(s1++) == *(s2++)) ;
return *s1-*s2;
}
★假设你有一个用1001个整数组成的数组，这些整数是任意排列的，可是你知道所有的整数都在1到1000(包括1000)之间。另外，除一个数字出现两次外，其它所有数字只出现一次。假设你只能对这个数组做一次处理，用一种算法找出重复的那个数字。如果你在运算中使用了辅助的存储方式，那么你能找到不用这种方式的算法吗?
解：累加求和 -（1+2+…+1000）

★不用乘法或加法增加8倍。现在用同样的方法增加7倍。

第9题
判断整数序列是不是二元查找树的后序遍历结果
题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。
如果是返回true，否则返回false。
例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果：
         8
      /  \
     6    10
    / \  / \
5  7 9  11
因此返回true。
如果输入7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回false。
解：设数组a[from~to]，函数f(from, to)判断其是否能够为某二叉树后序结果，
int f(int from, int to)
{ int i=from,j, s1,s2;
while(iom~j]为左子树部分，a[j+1~to-1]为右子树部分
while(i=j) s1=1;
else s1= f(from,j);//对左子树判断
if(j+1>=to-1) s2=1;
else s2= f(j+1,to-1); //对右子树判断
return s1&&s2; //返回左右子树判断 与结果
}

第10题
翻转句子中单词的顺序。
题目：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。
句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。
例如输入“I am a student.”，则输出“student. a am I”。
解：假设句子存放在char s[MAX]中，
void f( )
{ char tmp;
Int len=strlen(s),I,j,k;
for(i=0,j=len-1;i
while(s[j+1]!=‘ ’) j++;定位单词的尾
k=j+2;
while(i // value of node
int lh,rh,h;//lh,rh为左、右子树高度，h=max(lh,rh)+1
  struct tree *left; // left child of node
  struct tree *right; // right child of node
}*ptree ;
假设树的根为root
求各非叶子节点的左右子树高度
int h(ptree root)//返回h
{ if(!root) return 0;
root->lh=h(root->left);
root->rh=h(root->right);
return root->h=(root->lh > root->rh? root->lh+1 : root->rh+1);
}
//求最大距离，最大距离有3种可能，两节点均在左子树、右子树，或一个在左，一个在右
Int f(ptree root)
{ int len1,len2,len3;
If(!root) return 0;
Else
{ len1=f(root->left);//左子树中最大距离值
len2= f(root->right);//右子树中最大距离值
len3=1; //一个顶点在左子树，一个顶点在右子树，最大距离值
if(root->left) len3+=root->left->h;
if(root->right) len3+=root->right->h;
if(len1n-1);
return s;
}

第13题：
题目：输入一个单向链表，输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。
链表结点定义如下：  
struct ListNode
{
  int m_nKey;
  ListNode* m_pNext;
};

第14题：
题目：输入一个已经按升序排序过的数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。
要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。
例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。
解：假设数组为a[1~n]，输入和的数字为S，算法思路
for(i=1,j=n;i S) j--;

第15题：
题目：输入一颗二元查找树，将该树转换为它的镜像，即在转换后的二元查找树中，左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。
例如输入：
  8
/ \
6 10
/ \ / \
5 7 9 11
输出：
8
/ \
10 6
/ \ / \
11 9 7 5
解：写递归函数，左右子树交换。
首先我们定义的二元查找树 节点的数据结构如下：
 typedef struct tree
{
  int data; // value of node
  struct tree *left; // left child of node
  struct tree *right; // right child of node
}*ptree;
void f(ptree root)
{ if(!root) return ;
f(root->left);//对左右子树进行镜像处理
f(root->right);
if(root->left || root->right)
{ ptree tmp=root->left;
root->left = root->right;
root->right=tmp;
}
}

第16题：
题目（微软）：
输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。  
例如输入
   8
  / \
 6 10
/ \ / \
5 7 9 11
输出8 6 10 5 7 9 11。
解：用队列实现。

第17题：
题目：在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff，则输出b。  
分析：这道题是 google的一道笔试题。
解：用数组a[26]存放个字符出现次数{初始化为0}，用b[26]存放依次出现字符顺序，对整个字符串扫描一次，设当前扫描字符为c，则执行a[c-‘a’]++;如果a[c-‘a’]==1，则b[k++]=c;其中k初始值为0；扫描结束后依次检查b[0]~b[k-1]，如果a[b[t]-‘a’]==1则输出b[t]。

第18题：
题目：n个数字（0,1,…,n-1）形成一个圆圈，从数字0开始，
每次从这个圆圈中删除第k个数字（第一个为当前数字本身，第二个为当前数字的下一个数字）。
当一个数字删除后，从被删除数字的下一个继续删除第k个数字。
求出在这个圆圈中剩下的最后一个数字。
解：
（1）简单算法，
按循环链表删除结点方式，没删除一个结点需付出O(m)的代价，一共删除n-1个节点，因此复杂度为O(nk)，如果n，m都达到10^8，则整个算法运算量将达到10^16。
（2）高效算法
经典的约瑟夫环问题设n个人围成一圈，标号为0..n-1，从第一个人开始依次从1到k循环报数，当报到k的时候此人出圈。设J(n, k, i)表示第i个出圈的人的标号。
定理一:J(n, k, 1) = (k-1) MOD n, (n>=1, k>=1) ………… (1)
证明：由定义直接得证。
定理二：J(n+1, k, i+1) = (k + J(n, k, i)) MOD (n+1), (n>=1, k>=1, 1<=i<=n) ………… (2)
证明：设g = J(n, k, i)，因此如果有n个人，从0开始报号，第i个出圈的标号为g。现在考虑J(n+1, k, i+1)，因为J(n+1, k, 1) = (k-1) MOD (n+1)，即第一步的时候删除数字(k-1) MOD (n+1)，第二步的时候从数字k开始数起。因而问题变为了找到剩下的n个数字中从k开始数起被删除的第i个数字(注意这时(k-1) MOD (n+1)已经被删除了)，而这恰好就是(g+k) MOD (n+1)，(2)成立。根据(2)，很容易求得n个数里面第i个出圈的数。就根据这个定理递推计算。即求J(n,k,n)即可。
根据递推关系式，n呈单步递减变化，每一步变化仅常量个运算，因此算法复杂度为O(n)。

第19题：
题目：定义Fibonacci数列如下：  
  / 0 n=0
f(n)= 1 n=1
  \ f(n-1)+f(n-2) n=2
输入n，用最快的方法求该数列的第n项。
分析：在很多C语言教科书中讲到递归函数的时候，都会用Fibonacci作为例子。
因此很多程序员对这道题的递归解法非常熟悉，但....呵呵，你知道的。。
解：根据递推关系式，采用动态规划算法。

第20题：
题目：输入一个表示整数的字符串，把该字符串转换成整数并输出。
例如输入字符串"345"，则输出整数345。
解：略。

第21题
中兴面试题
编程求解：
输入两个整数 n 和 m，从数列1，2，3.......n 中随意取几个数，使其和等于 m，要求将其中所有的可能组合列出来.
解：回溯算法(子集和数问题)。
Int X[MAX];
void f(int k, int sum)//sum=X[1]+X[2]+…+X[k-1]
{ int i;

if(sum==m)
{
printf(“\n”);
for(i=1;iA、B、C三人都能够看见其余两人额头上的牌，看完后让她们猜自己额头上是什么颜色的牌，
A说不知道，B说不知道，C说不知道，然后A说知道了。
请教如何推理，A是怎么知道的。
如果用程序，又怎么实现呢？

第23题：
用最简单，最快速的方法计算出下面这个圆形是否和正方形相交。"  
3D坐标系 原点(0.0,0.0,0.0)
圆形:
半径r = 3.0
圆心o = (*.*, 0.0, *.*)
正方形:
4个角坐标;  
1:(*.*, 0.0, *.*)
2:(*.*, 0.0, *.*)
3:(*.*, 0.0, *.*)
4:(*.*, 0.0, *.*)
解：首先计算出正方形四条边的直线方程，并依据点到直线距离公式，计算出圆心到四条边的距离（设为d1,d2,d3,d4），且只要d1~d4有一个小于r，则相交，否则不相交。

第24题：
链表操作，
（1）.单链表就地逆置，
（2）合并链表

第25题：
写一个函数,它的原形是int continumax(char *outputstr,char *intputstr)
功能：
在字符串中找出连续最长的数字串，并把这个串的长度返回，
并把这个最长数字串付给其中一个函数参数outputstr所指内存。
例如："abcd12345ed125ss"的首地址传给intputstr后，函数将返回9，
outputstr所指的值为

26.左旋转字符串
题目：
定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部。
如把字符串abcdef左旋转2位得到字符串cdefab。请实现字符串左旋转的函数。
要求时间对长度为n的字符串操作的复杂度为O(n)，辅助内存为O(1)。

27.跳台阶问题
题目：一个台阶总共有n级，如果一次能够跳1级，也能够跳2级。
求总共有多少总跳法，并分析算法的时间复杂度。
这道题最近经常出现，包括MicroStrategy等比较重视算法的公司
都曾先后选用过个这道题作为面试题或者笔试题。
解：f(n)表一共有多少种跳法
f(1)=1; f(2)=2; f(n)=f(n-1)+f(n-2),n>2，然后如斐波那契数列一样，动态规划算法。

28.整数的二进制表示中1的个数
题目：输入一个整数，求该整数的二进制表示中有多少个1。
例如输入10，由于其二进制表示为1010，有两个1，因此输出2。
分析：
这是一道很基本的考查位运算的面试题。
包括微软在内的很多公司都曾采用过这道题。

29.栈的push、pop序列
题目：输入两个整数序列。其中一个序列表示栈的push顺序，
判断另一个序列有没有可能是对应的pop顺序。
为了简单起见，我们假设push序列的任意两个整数都是不相等的。 
比如输入的push序列是1、2、3、4、5，那么4、5、3、2、1就有可能是一个pop系列。
因为能够有如下的push和pop序列：
push 1，push 2，push 3，push 4，pop，push 5，pop，pop，pop，pop，
这样得到的pop序列就是4、5、3、2、1。
但序列4、3、5、1、2就不可能是push序列1、2、3、4、5的pop序列。
解：为简单起见，设push序列为递增的，要判断a[1~n]系列是否为可能的pop序列，对于任意a[i]只需检查a[i]右侧比a[i]小的数字是否构成递减序列。例如上面4、3、5、1、2，其中4右侧比它小的数分别为3、1、2，不是递减序列，因此它为不可能的pop序列。
int f( )
{
Int i,j,X[MAX],k;
for(i=1;i<=n;i++)
{
k=0; j=i+1;
X[0]=a[i];
while(j<=n) if(a[j]X[k]) return 0;//不构成递减序列
X[++k]=a[j];
}
}
return 1;//上面没有碰到非递减情况，则是可能的pop序列，时间复杂度O(n2)
}

30.在从1到n的正数中1出现的次数
题目：输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。
例如输入12，从1到12这些整数中包含1 的数字有1，10，11和12，1一共出现了5次。
分析：这是一道广为流传的google面试题。
解：先对N各个数位进行运算分析，设N=an*10n+an-1*10n-1+…+a1*101+a0，即其个位数为a0,十位数为a1,…，用f(N)表示1到N的所有整数中1出现次数，则有：
f(N)= 0 N=0

an*n*10n-1+(an>1? 10n : (N-10n+1))+f(N%10n) N>0
例如当N介于1~9时f(N)=1，可由上面递推式验证。另外验证下面两个：
f(14)=1*1*1+(14-10+1)+f(14%10)=6+f(4)=7
f(114)=1*2*10+(114-100+1)+f(114%100)=35+f(14)=42
（分析另外展开）

31.华为面试题：
一类似于蜂窝的结构的图，进行搜索最短路径（要求5分钟）

32.
有两个序列a,b，大小都为n,序列元素的值任意整数，无序；
要求：经过交换a,b中的元素，使[序列a元素的和]与[序列b元素的和]之间的差最小。
例如:  
var a=[100,99,98,1,2, 3];
var b=[1, 2, 3, 4,5,40];
解：回溯算法，与礼物分配算法接近。

33.
实现一个挺高级的字符匹配算法：
给一串很长字符串，要求找到符合要求的字符串，例如目的串：123
1******3***2 ,12*****3这些都要找出来
其实就是类似一些和谐系统。。。。。

34.
实现一个队列。
队列的应用场景为：
一个生产者线程将int类型的数入列，一个消费者线程将int类型的数出列

35.
求一个矩阵中最大的二维矩阵(元素和最大)如:
1 2 0 3 4
2 3 4 5 1
1 1 5 3 0
中最大的是:
4 5
5 3
要求:(1)写出算法;(2)分析时间复杂度;(3)用C写出关键代码
解：假设矩阵为a[m][n]，用f(I,j)表示以a[i][j]为矩形右下角元素的最大子矩阵和，则求出所有f(I,j)后确定其中最大者即可。f(I,j)的计算方式为
Int f(int I,int j)
{
Int i1,j1,tmp[MAX]={0},max=-pow(2,31);
for(i1=I;i1>=0;i1--)
{ sum=0;
for(j1=j;j1>=0;j1--) tmp[j1]+=a[i1][j1];//第一次执行时，仅将矩阵i行值赋值到tmp[ ]
for(j1=j;j1>=0;j1--)
{ sum+=tmp[j1];
If(sum>max) max=sum;
}
}
Return max;//max即为以a[i][j]为矩形右下角元素的最大值
}

第36题-40题（有些题目搜集于CSDN上的网友，已标明）：
36.引用自网友：longzuo
谷歌笔试：
n支队伍比赛，分别编号为0，1，2。。。。n-1，已知它们之间的实力对比关系，
存储在一个二维数组w[n][n]中，w[i][j] 的值代表编号为i，j的队伍中更强的一支。
因此w[i][j]=i 或者j，现在给出它们的出场顺序，并存储在数组order[n]中，
比如order[n] = {4,3,5,8,1......}，那么第一轮比赛就是 4对3， 5对8。.......
胜者晋级，败者淘汰，同一轮淘汰的所有队伍排名不再细分，即能够随便排，
下一轮由上一轮的胜者按照顺序，再依次两两比，比如可能是4对5,直至出现第一名
编程实现，给出二维数组w，一维数组order 和 用于输出比赛名次的数组result[n]，
求出result。
解：按题意应该满足n=2k初始化result[ ]为0，result[i]对应编号为order[i]的队伍最终获得名次。则算法能够如下运行（每一轮比赛两两进行，输者名次为t），
t=n;player1=1;player2=2;
for(i=n/2; i>0;i=i/2)
{ j=0;
player1=1;
while(j if(w[order[player1]][order[player2]] == order[player1]) result[player2]=t--;
else result[player1]=t--;
player1=player2+1;
j++;
}
}
比如order[n] = {4,3,5,8,1......}，最后计算的result[n]={3,6,2,1,8,…}，则说明编号4的队伍最终名次为第3名，编号为3的队伍名次为第6名，…

37
有n个长为m+1的字符串，
如果某个字符串的最后m个字符与某个字符串的前m个字符匹配，则两个字符串能够联接，
问这n个字符串最多能够连成一个多长的字符串，如果出现循环，则返回错误。

38.
百度面试：
1.用天平（只能比较，不能称重）从一堆小球中找出其中唯一一个较轻的，使用x次天平，
最多能够从y个小球中找出较轻的那个，求y与x的关系式。
2.有一个很大很大的输入流，大到没有存储器能够将其存储下来，
而且只输入一次，如何从这个输入流中随机取得m个记录。
3.大量的URL字符串，如何从中去除重复的，优化时间空间复杂度

39.
网易有道笔试：
(1).
求一个二叉树中任意两个节点间的最大距离，
两个节点的距离的定义是 这两个节点间边的个数，
比如某个孩子节点和父节点间的距离是1，和相邻兄弟节点间的距离是2，优化时间空间复杂度。
(2).
求一个有向连通图的割点，割点的定义是，如果除去此节点和与其相关的边，
有向图不再连通，描述算法。

40.百度研发笔试题
引用自：zp
1)设计一个栈结构，满足一下条件：min，push，pop操作的时间复杂度为O(1)。
2)一串首尾相连的珠子(m个)，有N种颜色(N<=10)，
设计一个算法，取出其中一段，要求包含所有N中颜色，并使长度最短。
并分析时间复杂度与空间复杂度。
3)设计一个系统处理词语搭配问题，比如说 中国 和人民能够搭配，
则中国人民 人民中国都有效。要求：
  *系统每秒的查询数量可能上千次；
  *词语的数量级为10W；
  *每个词至多能够与1W个词搭配
当用户输入中国人民的时候，要求返回与这个搭配词组相关的信息。

41.求固晶机的晶元查找程序
晶元盘由数目不详的大小一样的晶元组成，晶元并不一定全布满晶元盘，
照相机每次这能匹配一个晶元，如匹配过，则拾取该晶元，
若匹配不过，照相机则按测好的晶元间距移到下一个位置。
求遍历晶元盘的算法 求思路。

42.请修改append函数，利用这个函数实现：
两个非降序链表的并集，1->2->3 和 2->3->5 并为 1->2->3->5
另外只能输出结果，不能修改两个链表的数据。

43.递归和非递归俩种方法实现二叉树的前序遍历。

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
解：设数组为a[0~n-1]
思路：（1）先求和sum=，对sum约数分解，假设递减排列为k1,k2,…kt，
（2）对集合a[]内元素分为ki（1≤i≤t）个子集，如果能使得所有子集元素之和相等，则ki即为所求。
【将集合分为ki个子集，所有可能的分解方法