76.复杂链表的复制 题目:有一个复杂链表,其结点除了有一个m_pNext指针指向下一个结点外, 请完成函数ComplexNode* Clone(ComplexNode* pHead),以复制一个复杂链表。 分析:在常见的数据结构上稍加变化,这是一种很新颖的面试题。 要在不到一个小时的时间里解决这种类型的题目,我们需要较快的反应能力, 对数据结构透彻的理解以及扎实的编程功底。 A:一开始想这道题毫无思路,如果蛮来,首先创建好正常的链表,然后考虑sibling这个分量,则需要O(n^2)的时间复杂度,然后一个技巧便可以巧妙的解答此题。看图便知。首先是原始的链表 file:///C:/Users/ADMINI~1/AppData/Local/Temp/enhtmlclip/Image(2).jpg 然后我们还是首先复制每一个结点N为N*,不同的是我们将N*让在对应的N后面,即为 file:///C:/Users/ADMINI~1/AppData/Local/Temp/enhtmlclip/Image(3).jpg 然后我们要确定每一个N*的sibling分量,非常明显,N的sibling分量的next就是N*的sibling分量。 最后,将整个链表拆分成原始链表和拷贝出的链表。 这样,我们就解决了一个看似非常混乱和复杂的问题。
1.给定单链表,检测是否有环。
2.给定两个单链表(head1, head2),检测两个链表是否有交点,如果有返回第一个交点。 如果head1==head2,那么显然相交,直接返回head1。 3.给定单链表(head),如果有环的话请返回从头结点进入环的第一个节点。 运用题一,我们可以检查链表中是否有环。 如果有环,那么p1p2重合点p必然在环中。从p点断开环, 方法为:p1=p, p2=p->next, p->next=NULL。此时,原单链表可以看作两条单链表, 一条从head开始,另一条从p2开始,于是运用题二的方法,我们找到它们的第一个交点即为所求。
5.只给定单链表中某个结点p(非空结点),在p前面插入一个结点。
78.链表和数组的区别在哪里? 分析:主要在基本概念上的理解。
80.阿里巴巴一道笔试题 问题描述: 12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种? http://www.cnblogs.com/yaozhongxiao/archive/2009/11/10/1600516.html 今天阿里淘宝笔试中碰到两道组合数学题,感觉非常亲切,但是笔试中失踪推导不出来 后来查了下,原来是Catalan数。悲剧啊,现在整理一下 Catalan数——卡特兰数】 一.Catalan数的定义令h(1)=1,Catalan数满足递归式:h(n) = h(1)*h(n-1) + h(2)*h(n-2) + ... + h(n-1)h(1),n>=2该递推关系的解为:h(n) = C(2n-2,n-1)/n,n=1,2,3,...(其中C(2n-2,n-1)表示2n-2个中取n-1个的组合数) 问题描述: 12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种? 这个笔试题,很YD,因为把某个递推关系隐藏得很深. 问题分析: 我们先把这12个人从低到高排列,然后,选择6个人排在第一排,那么剩下的6个肯定是在第二排. 用0表示对应的人在第一排,用1表示对应的人在第二排,那么含有6个0,6个1的序列,就对应一种方案. 比如000000111111就对应着 第一排:0 1 2 3 4 5 第二排:6 7 8 9 10 11 010101010101就对应着 第一排:0 2 4 6 8 10 第二排:1 3 5 7 9 11 问题转换为,这样的满足条件的01序列有多少个. 观察1的出现,我们考虑这一个出现能不能放在第二排,显然,在这个1之前出现的那些0,1对应的人 要么是在这个1左边,要么是在这个1前面.而肯定要有一个0的,在这个1前面,统计在这个1之前的0和1的个数. 也就是要求,0的个数大于1的个数. OK,问题已经解决. 如果把0看成入栈操作,1看成出栈操作,就是说给定6个元素,合法的入栈出栈序列有多少个. 这就是catalan数,这里只是用于栈,等价地描述还有,二叉树的枚举,多边形分成三角形的个数,圆括弧插入公式中的 方法数,其通项是c(2n, n)/(n+1). 在<<计算机程序设计艺术>>,第三版,Donald E.Knuth著,苏运霖译,第一卷,508页,给出了证明: 问题大意是用S表示入栈,X表示出栈,那么合法的序列有多少个(S的个数为n) 显然有c(2n, n)个含S,X各n个的序列,剩下的是计算不允许的序列数(它包含正确个数的S和X,但是违背其它条件). 在任何不允许的序列中,定出使得X的个数超过S的个数的第一个X的位置.然后在导致并包括这个X的部分序列中,以 S代替所有的X并以X代表所有的S.结果是一个有(n+1)个S和(n-1)个X的序列.反过来,对一垢一种类型的每个序列,我们都能 逆转这个过程,而且找出导致它的前一种类型的不允许序列.例如XXSXSSSXXSSS必然来自SSXSXXXXXSSS.这个对应说明,不允许 的序列的个数是c(2n, n-1),因此an = c(2n, n) - c(2n, n-1).[Comptes Rendus Acad.Sci.105(Paris, 1887), 436~437] 验证: 其中F表示前排,B表示后排,在枚举出前排的人之后,对应的就是后排的人了,然后再验证是不是满足后面的比前面对应的人高的要求. #include <iostream> using namespace std; int bit_cnt(int n) { int result = 0; for (; n; n &= n-1, ++result); return result; } int main() { int F[6], B[6]; int ans = 0; for (int state = 0; state < (1 << 12); ++state) if (bit_cnt(state) == 6) { int i = 0, j = 0; for (int k = 0; k < 12; ++k) if (state&(1<<k)) F[i++] = k; else B[j++] = k; int ok = 1; for (int k = 0; k < 6; ++k) if (B[k] < F[k]) {ok = 0; break;} ans += ok; } cout << ans << endl; return 0; } 结果:132 而c(12, 6)/7 = 12*11*10*9*8*7/(7*6*5*4*3*2) = 132 注意:c(2n, n)/(n+1) = c(2n, n) - c(2n, n-1) 估计出题的人也读过<<计算机程序艺术>>吧. PS: 另一个很YD的问题: 有编号为1到n(n可以很大,不妨在这里假定可以达到10亿)的若干个格子,从左到右排列. 在某些格子中有一个棋子,不妨设第xi格有棋子(1<=i<=k, 1<=k<=n) 每次一个人可以把一个棋子往左移若干步, 但是不能跨越其它棋子,也要保证每个格子至多只有一个棋子. 两个人轮流移动,移动不了的为输,问先手是不是有必胜策略. 三.Catalan数的典型应用: 1.括号化问题。矩阵链乘: P=A1×A2×A3×……×An,依据乘法结合律,不改变其顺序,只用括号表示成对的乘积,试问有几种括号化的方案? 2.将多边行划分为三角形问题。将一个凸多边形区域分成三角形区域(划分线不交叉)的方法数? 类似:在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数? 3.出栈次序问题。一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列? 类似:有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票,另外n人只有10元钞票,剧院无其它钞票,问有多少中方法使得只要有10元的人买票,售票处就有5元的钞票找零?(将持5元者到达视作将5元入栈,持10元者到达视作使栈中某5元出栈) 类似:一位大城市的律师在他住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果他从不穿越(但可以碰到)从家到办公室的对角线,那么有多少条可能的道路? 分析:对于每一个数来说,必须进栈一次、出栈一次。我们把进栈设为状态‘1’,出栈设为状态‘0’。n个数的所有状态对应n个1和n个0组成的2n位二进制数。由于等待入栈的操作数按照1‥n的顺序排列、入栈的操作数b大于等于出栈的操作数a(a≤b),因此输出序列的总数目=由左而右扫描由n个1和n个0组成的2n位二进制数,1的累计数不小于0的累计数的方案种数。 在2n位二进制数中填入n个1的方案数为c(2n,n),不填1的其余n位自动填0。从中减去不符合要求(由左而右扫描,0的累计数大于1的累计数)的方案数即为所求。 不符合要求的数的特征是由左而右扫描时,必然在某一奇数位2m+1位上首先出现m+1个0的累计数和m个1的累计数,此后的2(n-m)-1位上有n-m个 1和n-m-1个0。如若把后面这2(n-m)-1位上的0和1互换,使之成为n-m个0和n-m-1个1,结果得1个由n+1个0和n-1个1组成的2n位数,即一个不合要求的数对应于一个由n+1个0和n-1个1组成的排列。 反过来,任何一个由n+1个0和n-1个1组成的2n位二进制数,由于0的个数多2个,2n为偶数,故必在某一个奇数位上出现0的累计数超过1的累计数。同样在后面部分0和1互换,使之成为由n个0和n个1组成的2n位数,即n+1个0和n-1个1组成的2n位数必对应一个不符合要求的数。 因而不合要求的2n位数与n+1个0,n-1个1组成的排列一一对应。 显然,不符合要求的方案数为c(2n,n+1)。由此得出 输出序列的总数目=c(2n,n)-c(2n,n+1)=1/(n+1)*c(2n,n)。 (这个公式的下标是从h(0)=1开始的)
先来几组百度的面试题: =================== 81.第1组百度面试题 1.一个int数组,里面数据无任何限制,要求求出所有这样的数a, 其左边的数都小于等于它,右边的数都大于等于它。 能否只用一个额外数组和少量其它空间实现。 解答: 分析:最原始的方法是检查每一个数 array ,看是否左边的数都小于等于它,右边的数都大于等于它。这样做的话,要找出所有这样的数,时间复杂度为O(N^2)。 其实可以有更简单的方法,我们使用额外数组,比如rightMin[],来帮我们记录原始数组array右边(包括自己)的最小值。假如原始数组为: array[] = {7, 10, 2, 6, 19, 22, 32}, 那么rightMin[] = {2, 2, 2, 6, 19, 22, 32}. 也就是说,7右边的最小值为2, 2右边的最小值也是2。有了这样一个额外数组,当我们从头开始遍历原始数组时,我们保存一个当前最大值 max, 如果当前最大值刚好等于rightMin, 那么这个最大值一定满足条件。还是刚才的例子。 第一个值是7,最大值也是7,因为7 不等于 2, 继续, 第二个值是10,最大值变成了10,但是10也不等于2,继续, 第三个值是2,最大值是10,但是10也不等于2,继续, 第四个值是6,最大值是10,但是10不等于6,继续, 第五个值是19,最大值变成了19,而且19也等于当前rightMin[4] = 19, 所以,满足条件。 如此继续下去,后面的几个都满足。 #include <iostream> 2 3 using namespace std; 4 5 #define max(a,b) a>b?a:b 6 #define min(a,b) a<b?a:b 7 8 void findNum(int data[],int len) 9 {10 int* a = new int[len];11 int* b = new int[len];12 a[len-1] = data[len-1];13 for (int i = len-2;i > 0;i--)14 {15 a = min(data,a[i+1]);16 }17 18 if (data[0] <= a[1])19 {20 cout<<"0:"<<data[0]<<endl;21 }22 23 a[0] = data[0];24 if (data[1] >= a[0] && data[1] <= a[2])25 {26 cout<<"1:"<<data[1]<<endl;27 }28 29 for (int i = 1;i < len-2;i++)30 {31 a = max(data,a[i-1]);32 if (data[i+1] >= a && data[i+1] <= a[i+2])33 {34 cout<<i+1<<":"<<data[i+1]<<endl;35 }36 }37 a[len-2] = max(data[len-2],a[len-3]);38 if (data[len-1] >= a[len-2])39 {40 cout<<len-1<<":"<<data[len-1]<<endl;41 }42 }43 44 int main()45 {46 int data[10] = {1,3,2,4,6,7,5,9,11,10};47 findNum(data,10);48 } 2.一个文件,内含一千万行字符串,每个字符串在1K以内, 要求找出所有相反的串对,如abc和cba。 文件的大小上限是10G,不可能在内存操作了。考虑设计一种hash使得如果两个字符串维相反串能得出相同的hash值,然后用该hash将文件中的字符串散列到不同的文件中,再在各文件中进行匹配。比如这样的hash函数对字符串上所有字符的ascii求和,因为长度在1K以内,因此范围在int之内。更进一步,可以在上面那个hash后面再加一个字符串长度,可以得到更好的散列效果。 在各个单独文件中匹配时,如果采用的是第二种hash函数,那么该文件中的所有字符串都有相同的长度。如果hash效果好,那么这个文件应该小到可以在内存中进行操作了。将文件拷贝为两份,分别按照不同规则hash:第一份按前k位哈希,第二份将字符串的头尾进行颠倒后按前k位哈希(只是对于排序算法颠倒,不必实际颠倒)。这里的按前k位哈希只需要前k位相同能得到相同结果就好,比如第i位的ascii乘以2^i。两份拷贝中hash值相同的就很可能是要求的相反串对了,再进行实际匹配,工作量应该就可以接受了。 3.STL的set用什么实现的?为什么不用hash? 是用红黑树实现的,红黑树是一种平衡性很好的二分查找树。要使用hash的话,就需要为不同的存储类型编写哈希函数,这样就照顾不到容器的模板性了,而是用红黑树只需要为不同类型重载operator<就可以了。
82.第2组百度面试题 2.给出一个文件,里面包含两个字段{url、size},
83.第3组百度面试题 2.百度笔试题 原型:extern void *memmove(void *dest, const void *src, unsigned int count); 功能:由src所指内存区域复制count个字节到dest所指内存区域。说明:src和dest所指内存区域可以重叠,但复制后src内容会被更改。函数返回指向dest的指针。 功能类似于memcpy,不同的是memcpy内存区域不可重叠 例子: char *p="hello world!"; char *q=(char*)malloc(sizeof(char)*strlen(p)); memmove(q,p,sizeof(p)+1); 1.memmove 函数原型:void *memmove(void *dest, const void *source, size_t count) 返回值说明:返回指向dest的void *指针 参数说明:dest,source分别为目标串和源串的首地址。count为要移动的字符的个数 函数说明:memmove用于从source拷贝count个字符到dest,如果目标区域和源区域有重叠的话,memmove能够保证源串在被覆盖之前将重叠区域的字节拷贝到目标区域中。 memmove(),如果两函数重叠,赋值仍正确进行。 如果你不能保证是否有重叠,为了确保复制的正确性,你必须用memmove void *memmove(void *dest, const void *source, size_t count) { assert((NULL != dest) && (NULL != source)); char *tmp_source, *tmp_dest; tmp_source = (char *)source; tmp_dest = (char *)dest; if((dest + count<source) || (source + count) <dest)) {// 如果没有重叠区域 while(count--) *tmp_dest++ = *tmp_source++; } else { //如果有重叠 tmp_source += count - 1; tmp_dest += count - 1; while(count--) *--tmp_dest = *--tmp; } return dest; } 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,要求复杂度最低。 首先是1/2的情况,我们一次性生成两个数值,如果是00或者11丢弃,否则留下,01为1,10为0,他们的概率都是p*(1-p)是相等的,所以等概率了。 然后是1/n的情况了,我们以5为例,此时我们取x=2,因为C(2x,x)=C(4,2)=6是比5大的最小的x,此时我们就是一次性生成4位二进制,把1出现个数不是2的都丢弃,这时候剩下六个:0011,0101,0110,1001,1010,1100,取最小的5个,即丢弃1100,那么我们对于前5个分别编号1到5,这时候他们的概率都是p*p*(1-p)*(1-p)相等了。 关键是找那个最小的x,使得C(2x,x)>=n这样能提升查找效率。 因为C(n,i)最大是在i接近n/2的地方取得,此时我有更大比率的序列用于生成,换句话说被抛掉的更少了,这样做是为了避免大量生成了丢弃序列而使得生成速率减慢,实际上我之所以将x取定是为了让我取得的序列生成的概率互相相等,比如C(2x,x)的概率就是[p(1-p)]^x,互等的样例空间内保证了对应的每个值取得的样例等概率。 3.有10个文件,每个文件1G, 每个文件的每一行都存放的是用户的query,每个文件的query都可能重复。 要求按照query的频度排序.
85.又见字符串的问题 86. 怎样编写一个程序,把一个有序整数数组放到二叉树中? 分析:本题考察二叉搜索树的建树方法,简单的递归结构。 关于树的算法设计一定要联想到递归,因为树本身就是递归的定义。 using namespace std;struct TreeNode { int m_nValue; TreeNode *m_pLeft; TreeNode *m_pRight;};//把一个有序整数数组放到二叉树void RecurCreateTree(int *p, int length, TreeNode *&pHead){ if (length > 0) { pHead = new TreeNode; int mid = length/2; pHead->m_nValue = p[mid]; pHead->m_pLeft = NULL; pHead->m_pRight = NULL; RecurCreateTree(p, mid, pHead->m_pLeft); RecurCreateTree(p + mid + 1, length - mid - 1, pHead->m_pRight);; } else { pHead = NULL; }}//中序递归遍历void MidRecurTraversal(TreeNode* pHead){ if (NULL != pHead) { MidRecurTraversal(pHead->m_pLeft); cout<<pHead->m_nValue<<" "; MidRecurTraversal(pHead->m_pRight); }}int _tmain(int argc, _TCHAR* argv[]){ int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ,11, 12}; TreeNode *pHead = NULL; RecurCreateTree(arr, sizeof(arr)/sizeof(arr[0]), pHead); MidRecurTraversal(pHead); cout<<endl; return 0;} 而,学会把递归改称非递归也是一种必要的技术。 毕竟,递归会造成栈溢出,关于系统底层的程序中不到非不得以最好不要用。 但是对某些数学问题,就一定要学会用递归去解决。 87. 1.大整数数相乘的问题。(这是2002年在一考研班上遇到的算法题) 2.求最大连续递增数字串(如“ads3sl456789DF3456ld345AA”中的“456789”) 3.实现strstr功能,即在父串中寻找子串首次出现的位置。 (笔试中常让面试者实现标准库中的一些函数) 88.2005年11月金山笔试题。编码完成下面的处理函数。 函数将字符串中的字符'*'移到串的前部分, 前面的非'*'字符后移,但不能改变非'*'字符的先后顺序,函数返回串中字符'*'的数量。 如原始串为:ab**cd**e*12, 处理后为*****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个木头和它重量一样, 把配对的石头和木头找出来。 92. 1.多人排成一个队列,我们认为从低到高是正确的序列,但是总有部分人不遵守秩序。 如果说,前面的人比后面的人高(两人身高一样认为是合适的), 那么我们就认为这两个人是一对“捣乱分子”,比如说,现在存在一个序列: 176, 178, 180, 170, 171 这些捣乱分子对为 <176, 170>, <176, 171>, <178, 170>, <178, 171>, <180, 170>, <180, 171>, 那么,现在给出一个整型序列,请找出这些捣乱分子对的个数(仅给出捣乱分子对的数目即可,不用具体的对) 要求: 输入: 为一个文件(in),文件的每一行为一个序列。序列全为数字,数字间用”,”分隔。 输出: 为一个文件(out),每行为一个数字,表示捣乱分子的对数。 详细说明自己的解题思路,说明自己实现的一些关键点。 并给出实现的代码 ,并分析时间复杂度。 限制: 输入每行的最大数字个数为100000个,数字最长为6位。程序无内存使用限制。 思路:最简单的就是用两层循环,即考察每个元素,检查该元素后面的元素是否小于它,如果是就找到一个捣乱分子对。复杂度为O(n^2)。这道题的一种改进方案是用分治法,用到了归并排序的思想。我们可以将数组分成两部分,总的捣乱分子对为: 前半部分的捣乱分子对 + 后半部分的捣乱分子对 + X,这里的X为两部分合并中出现的捣乱分子对,什么情况下会出现呢?假设前半部分的元素范围为 A[from] 到A[mid],后半部分的元素范围为A[mid + 1] 到A[to],考虑前半部分的某元素A和后半部分的某元素A[j],如果A[j] < A,由于两部分都是排好序的,因此捣乱分子对增加 mid - i + 1个,也就是说A[j]小于A, A[i+1].. A[mid],这个关系显然成立。 参考代码: int Merge(int *pArray, int from, int mid, int to) { int i = from, j = mid + 1; int k = 0, num = 0; int *pTmp = new int[to-from+1]; while(i<=mid && j<=to) //归并排序的主框架 { if(pArray <= pArray[j]) pTmp[k++] = pArray[i++]; else { num += (mid - i + 1); //增加捣乱分子对 for(int l = i; l <= mid; l++) //输出捣乱分子 cout<<pArray[l]<<' '<<pArray[j]<<endl; pTmp[k++] = pArray[j++]; } } while(i <= mid) pTmp[k++] = pArray[i++]; while(j <= to) pTmp[k++] = pArray[j++]; for(k = from ; k <= to; k++) pArray[k] = pTmp[k - from]; delete [] pTmp; return num; } int MergeSort(int *pArray, int from, int to) { if(from < to) { int mid = (from + to) /2; int num = MergeSort(pArray, from ,mid) + MergeSort(pArray, mid+1, to); //分别算出两部分的捣乱分子对 num += Merge(pArray, from, mid, to); //合并中出现的捣乱分子对 return num; } return 0; } 93.在一个int数组里查找这样的数,它大于等于左侧所有数,小于等于右侧所有数。 直观想法是用两个数组a、b。a、b分别保存从前到i的最大的数和从后到i的最小的数, 一个解答:这需要两次遍历,然后再遍历一次原数组, 将所有data>=a[i-1]&&data<=b的data找出即可。 给出这个解答后,面试官有要求只能用一个辅助数组,且要求少遍历一次。 94.微软笔试题 求随机数构成的数组中找到长度大于=3的最长的等差数列9 d- x' W) w9 ?" o3 b0 R 输出等差数列由小到大: 如果没有符合条件的就输出 格式: 输入[1,3,0,5,-1,6] 输出[-1,1,3,5] 要求时间复杂度,空间复杂度尽量小 动态规划求解。设f[j]为以a,a[j]结尾的等差数列的最长长度。那么 递归方程为:f[j]=max{f[k]+1,a[k]-a==a-a[j]},起始条件f[j]=1;伪代码如下: for(int k =0; k <n; k++) for(int i=k+1;i<n;i++) for(int j=i+1;j<n;j++) if(a[k]-a == a-a[j]) f[j] = (f[j]<f[k]+1?f[k]+1:f[j]); 而,最长长度为即为max{f[j]},即以a,a[j]结尾,通过一次查找即可求出是那些元素组成的解。复杂度O(n^3)。 95.华为面试题 1 判断一字符串是不是对称的,如:abccba 2.用递归的方法判断整数组a[N]是不是升序排列 int is_ascending(int a[],int length){ if(length==1)return 1; if (a[length-1]>a[length]) { return 0; }else { return is_ascending(a,length-1); } } 96.08年中兴校园招聘笔试题 1.编写strcpy 函数 已知strcpy 函数的原型是 char *strcpy(char *strDest, const char *strSrc); 其中strDest 是目的字符串,strSrc 是源字符串。不调用C++/C 的字符串库函数,请 编写函数 strcpy 最后压轴之戏,终结此微软等100题系列V0.1版。 那就, 连续来几组微软公司的面试题,让你一次爽个够: ====================== 97.第1组微软较简单的算法面试题 1.编写反转字符串的程序,要求优化速度、优化空间。 2.在链表里如何发现循环链接? 3.编写反转字符串的程序,要求优化速度、优化空间。 4.给出洗牌的一个算法,并将洗好的牌存储在一个整形数组里。 5.写一个函数,检查字符是否是整数,如果是,返回其整数值。 (或者:怎样只用4行代码编写出一个从字符串到长整形的函数?) 98.第2组微软面试题 1.给出一个函数来输出一个字符串的所有排列。 2.请编写实现malloc()内存分配函数功能一样的代码。 3.给出一个函数来复制两个字符串A和B。字符串A的后几个字节和字符串B的前几个字节重叠。 4.怎样编写一个程序,把一个有序整数数组放到二叉树中? 5.怎样从顶部开始逐层打印二叉树结点数据?请编程。 6.怎样把一个链表掉个顺序(也就是反序,注意链表的边界条件并考虑空链表)?
99.第3组微软面试题 1.烧一根不均匀的绳,从头烧到尾总共需要1个小时。 现在有若干条材质相同的绳子,问如何用烧绳的方法来计时一个小时十五分钟呢? a绳从两头烧,同时b绳从一头烧,当a绳烧尽时,灭掉b绳,同时c绳从两头烧,在c绳烧尽时,b绳从两头烧,结束时即为1小时15分钟。 2.你有一桶果冻,其中有黄色、绿色、红色三种,闭上眼睛抓取同种颜色的两个。 抓取多少个就可以确定你肯定有两个同一颜色的果冻?(5秒-1分钟) 3.如果你有无穷多的水,一个3公升的提捅,一个5公升的提捅,两只提捅形状上下都不均匀, 问你如何才能准确称出4公升的水?(40秒-3分钟) 一个岔路口分别通向诚实国和说谎国。 来了两个人,已知一个是诚实国的,另一个是说谎国的。 诚实国永远说实话,说谎国永远说谎话。现在你要去说谎国, 但不知道应该走哪条路,需要问这两个人。请问应该怎么问?(20秒-2分钟) 100.第4组微软面试题,挑战思维极限 1.12个球一个天平,现知道只有一个和其它的重量不同,问怎样称才能用三次就找到那个球。 13个呢?(注意此题并未说明那个球的重量是轻是重,所以需要仔细考虑)(5分钟-1小时) 2.在9个点上画10条直线,要求每条直线上至少有三个点?(3分钟-20分钟) 3.在一天的24小时之中,时钟的时针、分针和秒针完全重合在一起的时候有几次? 都分别是什么时间?你怎样算出来的?(5分钟-15分钟) 终结附加题: 微软面试题,挑战你的智商 ========== 说明:如果你是第一次看到这种题,并且以前从来没有见过类似的题型, 并且能够在半个小时之内做出答案,说明你的智力超常..) 1.第一题 . 五个海盗抢到了100颗宝石,每一颗都一样大小和价值连城。他们决定这么分: 抽签决定自己的号码(1、2、3、4、5) 首先,由1号提出分配方案,然后大家表决,当且仅当超过半数的人同意时, 按照他的方案进行分配,否则将被扔进大海喂鲨鱼 如果1号死后,再由2号提出分配方案,然后剩下的4人进行表决, 当且仅当超过半数的人同意时,按照他的方案进行分配,否则将被扔入大海喂鲨鱼。 依此类推 条件:每个海盗都是很聪明的人,都能很理智地做出判断,从而做出选择。 问题:第一个海盗提出怎样的分配方案才能使自己的收益最大化? 倒推法解答即可。 2.一道关于飞机加油的问题,已知: 每个飞机只有一个油箱, 飞机之间可以相互加油(注意是相互,没有加油机) 一箱油可供一架飞机绕地球飞半圈, 问题: 为使至少一架飞机绕地球一圈回到起飞时的飞机场,至少需要出动几架飞机? (所有飞机从同一机场起飞,而且必须安全返回机场,不允许中途降落,中间没有飞机场) |
[技术| 编程·课件·Linux] 100道经典算法题(76-100)
sissi
· 发布于 2012-10-21 22:31
· 3419 次阅读
转载文章时务必注明原作者及原始链接,并注明「发表于 软院网 RuanYuan.Net 」,并不得对作品进行修改。