面试--微软面试100题全部答案.docx 126页

'本文转载自CSDN大牛的一篇博客：http://blog.csdn.net/v_july_v/article/details/6870251作者：July、阿财时间：二零一一年十月十三日。我能够看到此文，还要多谢陈同学！让我得以及时分享给大家微软面试100题全部答案个人整理的前60题的答案可参见以下三篇文章：1.微软100题第1题-20题答案http://blog.csdn.net/v_JULY_v/archive/2011/01/10/6126406.aspx[博文I]2.微软100题第21-40题答案http://blog.csdn.net/v_JULY_v/archive/2011/01/10/6126444.aspx[博文II]3.微软100题第41-60题答案http://blog.csdn.net/v_JULY_v/archive/2011/02/01/6171539.aspx[博文III]最新整理的全部100题的答案参见如下（重复的，以及一些无关紧要的题目跳过）：1.把二元查找树转变成排序的双向链表题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。10/614//481216转换成双向链表4=6=8=10=12=14=16。首先我们定义的二元查找树节点的数据结构如下：structBSTreeNode{intm_nValue;//valueofnodeBSTreeNode*m_pLeft;//leftchildofnodeBSTreeNode*m_pRight;//rightchildofnode};ANSWER:Thisisatraditionalproblemthatcanbesolvedusingrecursion.Foreachnode,connectthedoublelinkedlistscreatedfromleftandrightchildnodetoformafulllist./***@paramrootTherootnodeofthetree*@returnTheheadnodeoftheconvertedlist. */BSTreeNode*treeToLinkedList(BSTreeNode*root){BSTreeNode*head,*tail;helper(head,tail,root);returnhead;}voidhelper(BSTreeNode*&head,BSTreeNode*&tail,BSTreeNode*root){BSTreeNode*lt,*rh;if(root==NULL){head=NULL,tail=NULL;return;}helper(head,lt,root->m_pLeft);helper(rh,tail,root->m_pRight);if(lt!=NULL){lt->m_pRight=root;root->m_pLeft=lt;}else{head=root;}if(rh!=NULL){root->m_pRight=rh;rh->m_pLeft=root;}else{tail=root;}}2.设计包含min函数的栈。定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。ANSWER:StackisaLIFOdatastructure.Whensomeelementispoppedfromthestack,thestatuswillrecovertotheoriginalstatusasbeforethatelementwaspushed.Sowecanrecovertheminimumelement,too.structMinStackElement{intdata;intmin;};structMinStack{MinStackElement*data;intsize; inttop;}MinStackMinStackInit(intmaxSize){MinStackstack;stack.size=maxSize;stack.data=(MinStackElement*)malloc(sizeof(MinStackElement)*maxSize);stack.top=0;returnstack;}voidMinStackFree(MinStackstack){free(stack.data);}voidMinStackPush(MinStackstack,intd){if(stack.top==stack.size)error(“outofstackspace.”);MinStackElement*p=stack.data[stack.top];p->data=d;p->min=(stack.top==0?d:stack.data[top-1]);if(p->min>d)p->min=d;top++;}intMinStackPop(MinStackstack){if(stack.top==0)error(“stackisempty!”);returnstack.data[--stack.top].data;}intMinStackMin(MinStackstack){if(stack.top==0)error(“stackisempty!”);returnstack.data[stack.top-1].min;}3.求子数组的最大和题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。例如输入的数组为1,-2,3,10,-4,7,2,-5，和最大的子数组为3,10,-4,7,2，因此输出为该子数组的和18。ANSWER:Atraditionalgreedyapproach.Keepcurrentsum,slidefromlefttoright,whensum<0,resetsumto0.intmaxSubarray(inta[],intsize){if(size<=0)error(“errorarraysize”);intsum=0;intmax=-(1<<31);intcur=0; while(curmax){max=sum;}elseif(sum<0){sum=0;}}returnmax;}4.在二元树中找出和为某一值的所有路径题目：输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。例如输入整数22和如下二元树10/512/47则打印出两条路径：10,12和10,5,7。二元树节点的数据结构定义为：structBinaryTreeNode//anodeinthebinarytree{intm_nValue;//valueofnodeBinaryTreeNode*m_pLeft;//leftchildofnodeBinaryTreeNode*m_pRight;//rightchildofnode};ANSWER:Usebacktrackingandrecurison.Weneedastacktohelpbacktrackingthepath.structTreeNode{intdata;TreeNode*left;TreeNode*right;};voidprintPaths(TreeNode*root,intsum){intpath[MAX_HEIGHT];helper(root,sum,path,0);}voidhelper(TreeNode*root,intsum,intpath[],inttop){path[top++]=root.data;sum-=root.data; if(root->left==NULL&&root->right==NULL){if(sum==0)printPath(path,top);}else{if(root->left!=NULL)helper(root->left,sum,path,top);if(root->right!=NULL)helper(root->right,sum,path,top);}top--;sum-=root.data;}5.查找最小的k个元素题目：输入n个整数，输出其中最小的k个。例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。ANSWER:Thisisaverytraditionalquestion...O(nlogn):catI_FILE|sort-n|head-nKO(kn):doinsertionsortuntilkelementsareretrieved.O(n+klogn):TakeO(n)timetobottom-upbuildamin-heap.Thensift-downk-1times.SotraditionalthatIdon’twanttowritethecodes...Onlygivesthesiftupandsiftdownfunction./***@paramitheindexoftheelementinheapa[0...n-1]tobesiftedupvoidsiftup(inta[],inti,intn){while(i>0){intj=(i&1==0?i-1:i+1);intp=(i-1)>>1;if(jnext!=NULL){h1=h1->next;}while(h2->next!=NULL){h2=h2->next;}returnh1==h2;}//iftherecouldexistcycleintisJoined(Node*h1,Node*h2){Node*cylic1=testCylic(h1);Node*cylic2=testCylic(h2);if(cylic1+cylic2==0)returnisJoinedSimple(h1,h2);if(cylic1==0&&cylic2!=0||cylic1!=0&&cylic2==0)return0;Node*p=cylic1;while(1){if(p==cylic2||p->next==cylic2)return1;p=p->next->next; cylic1=cylic1->next;if(p==cylic1)return0;}}Node*testCylic(Node*h1){Node*p1=h1,*p2=h1;while(p2!=NULL&&p2->next!=NULL){p1=p1->next;p2=p2->next->next;if(p1==p2){returnp1;}}returnNULL;}第8题此贴选一些比较怪的题，，由于其中题目本身与算法关系不大，仅考考思维。特此并作一题。1.有两个房间，一间房里有三盏灯，另一间房有控制着三盏灯的三个开关，这两个房间是分割开的，从一间里不能看到另一间的情况。现在要求受训者分别进这两房间一次，然后判断出这三盏灯分别是由哪个开关控制的。有什么办法呢？ANSWER:Skip.2.你让一些人为你工作了七天，你要用一根金条作为报酬。金条被分成七小块，每天给出一块。如果你只能将金条切割两次，你怎样分给这些工人?ANSWER:1+2+4;3.★用一种算法来颠倒一个链接表的顺序。现在在不用递归式的情况下做一遍。ANSWER:Node*reverse(Node*head){if(head==NULL)returnhead;if(head->next==NULL)returnhead;Node*ph=reverse(head->next);head->next->next=head;head->next=NULL;returnph;}Node*reverseNonrecurisve(Node*head){if(head==NULL)returnhead;Node*p=head; Node*previous=NULL;while(p->next!=NULL){p->next=previous;previous=p;p=p->next;}p->next=previous;returnp;}★用一种算法在一个循环的链接表里插入一个节点，但不得穿越链接表。ANSWER:Idon’tunderstandwhatis“Chuanyue”.★用一种算法整理一个数组。你为什么选择这种方法?ANSWER:Whatis“Zhengli?”★用一种算法使通用字符串相匹配。ANSWER:Whatis“Tongyongzifuchuan”...astringwith“*”and“?”?Ifso,hereisthecode.intmatch(char*str,char*ptn){if(*ptn==‘’)return1;if(*ptn==‘*’){do{if(match(str++,ptn+1))return1;}while(*str!=‘’);return0;}if(*str==‘’)return0;if(*str==*ptn||*ptn==‘?’){returnmatch(str+1,ptn+1);}return0;}★颠倒一个字符串。优化速度。优化空间。voidreverse(char*str){reverseFixlen(str,strlen(str));}voidreverseFixlen(char*str,intn){char*p=str+n-1;while(str=0&&str[j--]==sub[k--]);if(k<0)returnj+1;if(i+1=len&&strncmp(sub,p-len+1,len)==0)returni-len;p++;}return-1;}★比较两个字符串，用O(n)时间和恒量空间。ANSWER:Whatis“comparingtwostrings”?Justnormalstringcomparison?ThenaturalwayuseO(n)timeandO(1)space.intstrcmp(char*p1,char*p2){while(*p1!=‘’&&*p2!=‘’&&*p1==*p2){p1++,p2++;}if(*p1==‘’&&*p2==‘’)return0;if(*p1==‘’)return-1;if(*p2==‘’)return1;return(*p1-*p2);//itcanbenegotiatedwhethertheabove3if’sarenecessary,Idon’tliketoomitthem.}★假设你有一个用1001个整数组成的数组，这些整数是任意排列的，但是你知道所有的整数都在1到1000(包括1000)之间。此外，除一个数字出现两次外，其他所有数字只出现一次。假设你只能对这个数组做一次处理，用一种算法找出重复的那个数字。如果你在运算中使用了辅助的存储方式，那么你能找到不用这种方式的算法吗?ANSWER:Sumupallthenumbers,thensubtractthesumfrom1001*1002/2.Anotherway,useAXORAXORB=B:intfindX(inta[]){intk=a[0];for(inti=1;i<=1000;i++) k~=a[i]~i;}returnk;}★不用乘法或加法增加8倍。现在用同样的方法增加7倍。ANSWER:n<<3;(n<<3)-n;第9题判断整数序列是不是二元查找树的后序遍历结果题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true，否则返回false。例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果：8/610//57911因此返回true。如果输入7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回false。ANSWER:Thisisaninterestingone.Thereisatraditionalquestionthatrequiresthebinarytreetobere-constructedfrommid/post/preorderresults.Thisseemssimilar.Fortheproblemsrelatedto(binary)trees,recursionisthefirstchoice.Inthisproblem,weknowinpost-orderresults,thelastnumbershouldbetheroot.SowehaveknowntherootoftheBSTis8intheexample.Sowecansplitthearraybytheroot.intisPostorderResult(inta[],intn){returnhelper(a,0,n-1);}inthelper(inta[],ints,inte){if(e==s)return1;inti=e-1;while(a[e]>a[i]&&i>=s)i--;if(!helper(a,i+1,e-1))return0;intk=l;while(a[e]=s)i--;returnhelper(a,s,l);}第10题翻转句子中单词的顺序。题目：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。 句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。例如输入“Iamastudent.”，则输出“student.aamI”。Answer:Alreadydonethis.Skipped.第11题求二叉树中节点的最大距离...如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，我们姑且定义"距离"为两节点之间边的个数。写一个程序，求一棵二叉树中相距最远的两个节点之间的距离。ANSWER:Thisisinteresting...Alsorecursively,thelongestdistancebetweentwonodesmustbeeitherfromroottooneleaf,orbetweentwoleafs.Fortheformercase,it’sthetreeheight.Forthelattercase,itshouldbethesumoftheheightsofleftandrightsubtreesofthetwoleaves’mostleastancestor.Thefirstcaseisalsothesumtheheightsofsubtrees,justtheheight+0.intmaxDistance(Node*root){intdepth;returnhelper(root,depth);}inthelper(Node*root,int&depth){if(root==NULL){depth=0;return0;}intld,rd;intmaxleft=helper(root->left,ld);intmaxright=helper(root->right,rd);depth=max(ld,rd)+1;returnmax(maxleft,max(maxright,ld+rd));}第12题题目：求1+2+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字以及条件判断语句（A?B:C）。ANSWER:1+..+n=n*(n+1)/2=(n^2+n)/2itiseasytogetx/2,sotheproblemistogetn^2thoughnoif/elseisallowed,wecaneasillygoaroundusingshort-pass.usingmacrotomakeitfancier:#defineT(X,Y,i)(Y&(1<>1;}第13题：题目：输入一个单向链表，输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。链表结点定义如下：structListNode{intm_nKey;ListNode*m_pNext;};Answer:Twoways.1:recordthelengthofthelinkedlist,thengon-ksteps.2:usetwocursors.Timecomplexitiesareexactlythesame.Node*lastK(Node*head,intk){if(k<0)error(“k<0”);Node*p=head,*pk=head;for(;k>0;k--){if(pk->next!=NULL)pk=pk->next;elsereturnNULL;}while(pk->next!=NULL){p=p->next,pk=pk->next;}returnp;}第14题：题目：输入一个已经按升序排序过的数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。ANSWER:Usetwocursors.Oneatfrontandtheotherattheend.Keeptrackofthesumbymovingthecursors.voidfind2Number(inta[],intn,intdest){int*f=a,*e=a+n-1;intsum=*f+*e;while(sum!=dest&&fleft),&(root->right));mirror(root->left);mirror(root->right);}voidmirrorIteratively(Node*root){if(root==NULL)return;stackbuf; buf.push(root);while(!stack.empty()){Node*n=stack.pop();swap(&(root->left),&(root->right));if(root->left!=NULL)buf.push(root->left);if(root->right!=NULL)buf.push(root->right);}}第16题：题目（微软）：输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。例如输入78/610//57911输出861057911。ANSWER:Thenodesinthelevelsareprintedinthesimilarmannertheirparentswereprinted.SoitshouldbeanFIFOqueuetoholdthelevel.Ireallydon’trememberthefunctionnameofthestlqueue,soIwillwriteitinJava...voidprintByLevel(Noderoot){Nodesentinel=newNode();LinkedListq=newLinkedList();q.addFirst(root);q.addFirst(sentinel);while(!q.isEmpty()){Noden=q.removeLast();if(n==sentinel){System.out.println(“n”);q.addFirst(sentinel);}else{System.out.println(n);if(n.left()!=null)q.addFirst(n.left());if(n.right()!=null)q.addFirst(n.right());}}}第17题：题目：在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff，则输出b。分析：这道题是2006年google的一道笔试题。ANSWER: Again,thisdependsonwhatis“char”.Let’sassumeitasASCII.charfirstSingle(char*str){inta[255];memset(a,0,255*sizeof(int));char*p=str;while(*p!=’’){a[*p]++;p++;}p=str;while(*p!=’’){if(a[*p]==1)return*p;}return‘’;//thismusttheonethatoccursexact1time.}第18题：题目：n个数字（0,1,…,n-1）形成一个圆圈，从数字0开始，每次从这个圆圈中删除第m个数字（第一个为当前数字本身，第二个为当前数字的下一个数字）。当一个数字删除后，从被删除数字的下一个继续删除第m个数字。求出在这个圆圈中剩下的最后一个数字。July：我想，这个题目，不少人已经见识过了。ANSWER:Actually,althoughthisisasotraditionalproblem,Iwasalwaystolazytothinkaboutthisoreventosearchfortheanswer.(Whatashame...).Finally,bygoogleIfoundtheelegantsolutionforit.Thekeysare:1)ifweshifttheidsbyk,namely,startfromkinsteadof0,weshouldaddtheresultbyk%n2)afterthefirstround,westartfromk+1(possibly%n)withn-1elements,thatisequaltoan(n-1)problemwhilestartfrom(k+1)thelementinsteadof0,sotheansweris(f(n-1,m)+k+1)%n3)k=m-1,sof(n,m)=(f(n-1,m)+m)%n.finally,f(1,m)=0;NowthisisaO(n)solution.intjoseph(intn,intm){intfn=0;for(inti=2;i<=n;i++){fn=(fn+m)%i;}returnfn;}hu...长出一口气。。。第19题：题目：定义Fibonacci数列如下：/0n=0f(n)=1n=1 f(n-1)+f(n-2)n=2输入n，用最快的方法求该数列的第n项。分析：在很多C语言教科书中讲到递归函数的时候，都会用Fibonacci作为例子。因此很多程序员对这道题的递归解法非常熟悉，但....呵呵，你知道的。。ANSWER:Thisisthetraditionalproblemofapplicationofmathematics...letA={11}{10}f(n)=A^(n-1)[0,0]thisgivesaO(logn)solution.intf(intn){intA[4]={1,1,1,0};intresult[4];power(A,n,result);returnresult[0];}voidmultiply(int[]A,int[]B,int_r){_r[0]=A[0]*B[0]+A[1]*B[2];_r[1]=A[0]*B[1]+A[1]*B[3];_r[2]=A[2]*B[0]+A[3]*B[2];_r[3]=A[2]*B[1]+A[3]*B[3];}voidpower(int[]A,intn,int_r){if(n==1){memcpy(A,_r,4*sizeof(int));return;}inttmp[4];power(A,n>>1,_r);multiply(_r,_r,tmp);if(n&1==1){multiply(tmp,A,_r);}else{memcpy(_r,tmp,4*sizeof(int));}}第20题：题目：输入一个表示整数的字符串，把该字符串转换成整数并输出。例如输入字符串"345"，则输出整数345。ANSWER:ThisquestioncheckshowtheintervieweeisfamiliarwithC/C++?I’msobadatC/C++...intatoi(char*str){intneg=0; char*p=str;if(*p==‘-’){p++;neg=1;}elseif(*p==‘+’){p++;}intnum=0;while(*p!=‘’){if(*p>=0&&*p<=9){num=num*10+(*p-’0’);}else{error(“illegalnumber”);}p++;}returnnum;}PS:Ididn’tfigureouthowtotellaoverflowproblemeasily.第21题2010年中兴面试题编程求解：输入两个整数n和m，从数列1，2，3.......n中随意取几个数,使其和等于m,要求将其中所有的可能组合列出来.ANSWERThisisacombinationgenerationproblem.voidfindCombination(intn,intm){if(n>m)findCombination(m,m);intaux[n];memset(aux,0,n*sizeof(int));helper(m,0,aux);}voidhelper(intdest,intidx,intaux[],intn){if(dest==0)dump(aux,n);if(dest<=0||idx==n)return;helper(dest,idx+1,aux,n);aux[idx]=1;helper(dest-idx-1,idx+1,aux,n);aux[idx]=0;}voiddump(intaux[],intn){for(inti=0;idata>h2->data){head=h2;h2=h2->next;}else{head=h1;h1=h1->next;}Node*current=head;while(h1!=NULL&&h2!=NULL){if(h1==NULL||(h2!=NULL&&h1->data>h2->data)){current->next=h2;h2=h2->next;current=current->next;}else{current->next=h1;h1=h1->next;current=current->next;}}current->next=NULL;returnhead;}第25题：写一个函数,它的原形是intcontinumax(char*outputstr,char*intputstr)功能：在字符串中找出连续最长的数字串，并把这个串的长度返回，并把这个最长数字串付给其中一个函数参数outputstr所指内存。例如："abcd12345ed125ss123456789"的首地址传给intputstr后，函数将返回9，outputstr所指的值为123456789ANSWER:intcontinumax(char*outputstr,char*inputstr){intlen=0;char*pstart=NULL;intmax=0;while(1){if(*inputstr>=‘0’&&*inputstr<=’9’){len++;}else{if(len>max)pstart=inputstr-len;len=0;} if(*inputstr++==’’)break;}for(inti=0;i>=8;}returnc;}29.栈的push、pop序列题目：输入两个整数序列。其中一个序列表示栈的push顺序，判断另一个序列有没有可能是对应的pop顺序。为了简单起见，我们假设push序列的任意两个整数都是不相等的。比如输入的push序列是1、2、3、4、5，那么4、5、3、2、1就有可能是一个pop系列。因为可以有如下的push和pop序列：push1，push2，push3，push4，pop，push5，pop，pop，pop，pop，这样得到的pop序列就是4、5、3、2、1。但序列4、3、5、1、2就不可能是push序列1、2、3、4、5的pop序列。ANSWERThisseemsinteresting.However,aquitestraightforwardandpromisingwayistoactuallybuildthestackandcheckwhetherthepopactioncanbeachieved.intisPopSeries(intpush[],intpop[],intn){stackhelper;inti1=0,i2=0;while(i2>,asimilarproblemsplitsanarraytohalvesasevenaspossible.Itispossibletotakebinarysearch,whenSUMofthearrayisnottoohigh.Elsethisisaquitetimeconsumingbruteforceproblem.Icannotfigureoutareasonablesolution.33.实现一个挺高级的字符匹配算法：给一串很长字符串，要求找到符合要求的字符串，例如目的串：1231******3***2,12*****3这些都要找出来其实就是类似一些和谐系统。。。。。ANSWERNotaclearproblem.Seemsabitsetcando.34.实现一个队列。队列的应用场景为：一个生产者线程将int类型的数入列，一个消费者线程将int类型的数出列ANSWERIdon’tknowmultithreadprogrammingatall....35.求一个矩阵中最大的二维矩阵(元素和最大).如:120342345111530中最大的是:4553要求:(1)写出算法;(2)分析时间复杂度;(3)用C写出关键代码ANSWERThisisthetraditionalprobleminProgrammingPearls.However,thebestresultistoocomplicatedtoachieve.Soletsdothesuboptimalone.O(n^3)solution.1)Wehaveknowthatthesimilarproblemfor1dimarraycanbedoneinO(n)time.However,thiscannotbedoneinbothdirectionsinthesametime.Wecanonlycalculatetheaccumulationsforallthesublistfromitoj,(0<=i<=jacc(i,j)voidaccumulate(inta[],intn,intacc[]){inti=0;acc[i]=a[i];for(i=1;i1){inti,j;for(i=0,j=0;im,generatearandomnumberR=rand(N)in[0,N),replacea[R]withnewnumberifRfallsin[0,m).3.大量的URL字符串，如何从中去除重复的，优化时间空间复杂度ANSWER1.Usehashmapifthereisenoughmemory.2.Ifthereisnoenoughmemory,usehashtoputurlstobins,anddoituntilwecanfitthebinintomemory.39.网易有道笔试：(1).求一个二叉树中任意两个节点间的最大距离，两个节点的距离的定义是这两个节点间边的个数，比如某个孩子节点和父节点间的距离是1，和相邻兄弟节点间的距离是2，优化时间空间复杂度。ANSWERHavedonethis.(2). 求一个有向连通图的割点，割点的定义是，如果除去此节点和与其相关的边，有向图不再连通，描述算法。ANSWERDodfs,recordlow[i]asthelowestvertexthatcanbereachedfromiandi’ssuccessornodes.Foreachedgei,iflow[i]=iandiisnotaleafindfstree,theniisacutpoint.Theothercaseistherootofdfs,ifroothastwoormorechildren,itisacutpoint./***gisdefinedas:g[i][]istheoutedges,g[i][0]istheedgecount,g[i][1...g[i][0]]aretheotherendpoints.*/intcnt=0;intvisited[MAX_NUM];intlowest[MAX_NUM];voidgetCutPoints(int*g[],intcuts[],intn){memset(cuts,0,sizeof(int)*n);memset(visited,0,sizeof(int)*n);memset(lowest,0,sizeof(int)*n);for(inti=0;ivisit[g[s][i]]){low=visit[g[s][i]];}}}lowest[s]=low;if(s==root&&out>1){cuts[s]=1;} returnlow;}40.百度研发笔试题引用自：zp1553348771)设计一个栈结构，满足一下条件：min，push，pop操作的时间复杂度为O(1)。ANSWERHavedonethis.2)一串首尾相连的珠子(m个)，有N种颜色(N<=10)，设计一个算法，取出其中一段，要求包含所有N中颜色，并使长度最短。并分析时间复杂度与空间复杂度。ANSWERUseaslidingwindowandacountingarray,plusacounterwhichmonitorsthenumofzeroslotsincountingarray.Whenthereisstillzeroslot(s),advancethewindowhead,untilthereisnozeroslot.Thenshrinkthewindowuntilaslotcomeszero.Thenonecandidatesegmentof(window_size+1)isachieved.Repeatthis.ItisO(n)algorithmsinceeachitemisswallowedandleftbehindonlyonce,andeitheroperationisinconstanttime.intshortestFullcolor(inta[],intn,intm){intc[m],ctr=m;inth=0,t=0;intmin=n;while(1){while(ctr>0&&h=n)returnmin;while(1){c[a[t]]--;if(c[a[t]]==0)break;t++;}if(min>h-t)min=h-t;t++;ctr++;}}3)设计一个系统处理词语搭配问题，比如说中国和人民可以搭配，则中国人民人民中国都有效。要求：*系统每秒的查询数量可能上千次；*词语的数量级为10W；*每个词至多可以与1W个词搭配 当用户输入中国人民的时候，要求返回与这个搭配词组相关的信息。ANSWERThisproblemcanbesolvedinthreesteps:1.identifythewords2.recognizethephrase3.retrievetheinformationSolutionof1:ThemosttrivialwaytoefficientlyidentifythewordsishashtableorBST.AbalancedBSTwith100wordsisabout17levelshigh.Consideringthat100kisnotabignumber,hashingisenough.Solutionof2:Sincethephraseinthisproblemconsistsofonly2words,itiseasytosplitthewords.Therewon’tbealotofcandidates.Tofindalegalcombination,weneedthe“matching”information.Soforeachword,weneedsomedatastructuretotellwhetherawordcanco-occurwithit.100kisabadnumber--cannotfitintoa16bitdigit.However,10k*100kisnottoobig,sowecansimplyusearrayofsortedarraytodothis.1Gintegers,or4Gbytesisnotabignumber,WecanalsousesomethinglikeVInttosavealotofspace.Tofindanindexina10ksortedarray,14comparisonsareenough.Aboveoperationcanbedoneinanyreasonablework-station"smemoryveryfast,whichshouldbetheresultofexecutionofaboutafewthousandsofsimplestatements.Solutionof3:Theinformationcouldbetobigtofitinthememory.SoaB-treemaybeadoptedtoindexthecontents.Cachingtechniquesisalsohelpful.Consideringthereareatmost10^9entries,a3or4levelofB-treeisokay,soitwillbeatmost5diskaccess.However,therearethousandsofrequestsandwecanonlydohundredsofdiskseekingpersecond.Itcouldbenecessarytodispatchtheinformationtoseveralworkstations.41.求固晶机的晶元查找程序晶元盘由数目不详的大小一样的晶元组成，晶元并不一定全布满晶元盘，照相机每次这能匹配一个晶元，如匹配过，则拾取该晶元，若匹配不过，照相机则按测好的晶元间距移到下一个位置。求遍历晶元盘的算法求思路。ANSWERDontunderstand.42.请修改append函数，利用这个函数实现：两个非降序链表的并集，1->2->3和2->3->5并为1->2->3->5另外只能输出结果，不能修改两个链表的数据。ANSWERIdon’tquiteunderstandwhatitmeansby“notmodifyinglinkedlist’sdata”.Ifsomenodeswillbegivenup,itisweirdforthisrequirement.Node*head(Node*h1,Node*h2){if(h1==NULL)returnh2;if(h2==NULL)returnh1;Node*head;if(h1->datadata){head=h1;h1=h1->next;}else{head=h2;h2=h2->next; }Node*p=head;while(h1!=NULL||h2!=NULL){Node*candi;if(h1!=NULL&&h2!=NULL&&h1->datadata||h2==NULL){candi=h1;h1=h1->next;}else{candi=h2;h2=h2->next;}}if(candi->data==p->data)delete(candi);else{p->next=candi;p=candi;}}returnhead;}43.递归和非递归俩种方法实现二叉树的前序遍历。ANSWERvoidpreorderRecursive(TreeNode*node){if(node==NULL)return;visit(node);preorderRecursive(node->left);preorderRecursive(node->right);}Fornon-recursivetraversals,astackmustbeadoptedtoreplacetheimplicitprogramstackinrecursiveprograms.voidpreorderNonrecursive(TreeNode*node){stacks;s.push(node);while(!s.empty()){TreeNode*n=s.pop();visit(n);if(n->right!=NULL)s.push(n->right);if(n->left!=NULL)s.push(n->left);}}voidinorderNonrecursive(TreeNode*node){stacks;TreeNode*current=node;while(!s.empty()||current!=NULL){ if(current!=NULL){s.push(current);current=current->left;}else{current=s.pop();visit(current);current=current->right;}}}Postordernonrecursivetraversalisthehardestone.However,asimpleobservationhelpsthatthenodefirsttraversedisthenodelastvisited.Thisrecallsthefeatureofstack.Sowecoulduseastacktostoreallthenodesthenpopthemoutaltogether.Thisisaveryelegantsolution,whiletakesO(n)space.Otherverysmartmethodsalsowork,butthisistheoneIlikethemost.voidpostorderNonrecursive(TreeNode*node){//visitingoccursonlywhencurrenthasnorightchildorlastvisitedishisrightchildstacksTraverse,sVisit;sTraverse.push(node);while(!sTraverse.empty()){TreeNode*p=sTraverse.pop();sVisit.push(p);if(p->left!=NULL)sTraverse.push(p->left);if(p->right!=NULL)sTraverse.push(p->right);}while(!sVisit.empty()){visit(sVisit.pop);}}44.腾讯面试题：1.设计一个魔方（六面）的程序。ANSWERThisisaproblemtotestOOP.TheobjectMagicCubemusthavefollowingfeatures1)holdscurrentstatus2)easilydoingtransform3)judgewhetherthefinalstatusisachieved4)totest,itcanbeinitialized5)outputcurrentstatuspublicclassMagicCube{//6faces,9chipseachface privatebytechips[54];staticfinalintX=0;staticfinalintY=1;staticfinalintZ=1;voidtransform(intdirection,intlevel){switchdirection:{X:{transformX(level);break;}Y:{transformY(level);break;}Z:{transformZ(level);break;}default:thrownewRuntimeException(“whatdirection?”);}voidtransformX(intlevel){…}}}//reallytiredofmakingthis...}2.有一千万条短信，有重复，以文本文件的形式保存，一行一条，有重复。请用5分钟时间，找出重复出现最多的前10条。ANSWER10Mmsgs,eachatmost140chars,that’s1.4G,whichcanfittomemory.Sousehashmaptoaccumulateoccurrencecounts.Thenuseaheaptopickmaximum10.3.收藏了1万条url，现在给你一条url，如何找出相似的url。（面试官不解释何为相似）ANSWERWhataSBinterviewer...ThecompanynameshouldbeclaimedandifImetsuchainterviewer,IwillcontesttoHR.Thepurposeofinterviewistoseetheabilityofcommunication.Thisiskindofsinglesideshutdownofinformationexchange.Myfirstanswerwillbedoingeditdistancetotheurlandeverycandidate.Thenitdependsonwhatinterviewerwillreact.Otheroptionsincludes:fingerprints,tries...45.雅虎：1.对于一个整数矩阵，存在一种运算，对矩阵中任意元素加一时，需要其相邻（上下左右）某一个元素也加一，现给出一正数矩阵，判断其是否能够由一个全零矩阵经过上述运算得到。ANSWERAassignmentproblem.Twowaystosolve.1:duplicateeachcelltoasmanyasitsvalue,doHungarianalgorithm.DenotethesumofthematrixasM,theedgenumberis2M,sothecomplexityis2*M*M;2:standardmaximumflow.IfthesizeofmatrixisNxN,thenthealgorithmusingFordFulkersonalgorithmisM*N*N.toocomplex...IwilldothiswhenIhavetime...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的最大值为3ANSWERTworestrictionsonm,1)1<=m<=n;2)Sum(array)modm=0NOTE:nohintthata[i]>0,somcouldbelargerthansum/max;Sofirstlypreparethecandidates,thendoabruteforcesearchonpossiblem’s.Inthesearch,aDPisavailable,sinceiff(array,m)=OR_i(f(array-subset(i),m)),whereSum(subset(i))=m.intmaxShares(inta[],intn){intsum=0;inti,m;for(i=0;i=2;m--){if(summodm!=0)continue;intaux[n];for(i=0;idsl){dsl=s;lastdsl=i;}}//nowtraceback.for(inti=lastdsl-1,j=dsl-1;i>=0&&j>=0;i--){if(a[i]==ds[j]){j--;}elseif(a[i]t)return-1;intm=s+(t-s)/2;if(a[m]==k)returnm;elseif(a[s]>=k&&k>a[m])returnhelper(a,k,s,m-1);elsereturnhelper(a,k,m+1,e);}49.一道看上去很吓人的算法面试题：如何对n个数进行排序，要求时间复杂度O(n)，空间复杂度O(1)ANSWER:Soacomparisonsortisnotallowed.Countingsort’sspacecomplexityisO(n).Moreideasmustbeexchangedtofindmoreconditions,elsethisisacrap.50.网易有道笔试：1.求一个二叉树中任意两个节点间的最大距离，两个节点的距离的定义是这两个节点间边的个数，比如某个孩子节点和父节点间的距离是1，和相邻兄弟节点间的距离是2，优化时间空间复杂度。ANSWER:Havedonethisbefore.2.求一个有向连通图的割点，割点的定义是，如果除去此节点和与其相关的边，有向图不再连通，描述算法。ANSWER:Havedonethisbefore.-------------------------------------------------------------------51.和为n连续正数序列。题目：输入一个正数n，输出所有和为n连续正数序列。例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以输出3个连续序列1-5、4-6和7-8。分析：这是网易的一道面试题。ANSWER:Itseemsthatthiscanbesolvedbyfactorization.However,factorizationoflargenisimpractical!Supposen=i+(i+1)+...+(j-1)+j,thenn=(i+j)(j-i+1)/2=(j*j-i*i+i+j)/2=>j^2+j+(i-i^2-2n)=0=>j=sqrt(i^2-i+1/4+2n)-1/2Weknow1<=i20){error(“areyoucrazy?”);}byted[n];intpos[n],dpos[n];//pos[i],thepositionofi’thnumber,dpos[i]thenumberins[i]isthedpos[i]’thsmallestqsort(s);//IcannotremembertheformofqsortinC...memset(d,-1,sizeof(byte)*n);for(inti=0;idpos[r];i--)d[i]=-d[i];}}intfindFirstAvailable(chars[],byted[],intpos[],intn){for(inti=n-1;i>1;i--){if(s[pos[i]]>s[pos[i]+d[pos[i]]])returnpos[i];}return-1;}#defineaswap(ARR,X,Y){intt=ARR[X];ARR[X]=ARR[y];ARR[Y]=t;}voidswap(chars[],intpos[],intdpos[],byted[],intr,ints){aswap(s,r,s);aswap(d,r,s);aswap(pos,dpos[r],dpos[s]);aswap(dpos,r,s);}Maybefullofbugs.Pleaserefertoalgorithmmanualforexplansion.Pros:AmotizedO(1)timeforeachmove.Onlytwocharacterschangepositionforeachmove.Cons:asyoucansee,verycomplicated.Extraspaceneeded.54.调整数组顺序使奇数位于偶数前面。题目：输入一个整数数组，调整数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。要求时间复杂度为O(n)。 ANSWER:Thisproblemmakesmerecalltheprocessofpartitioninquicksort.voidpartition(inta[],intn){inti=j=0;while(i1+a[(i-1)*l2+j-1])?max:1+a[(i-1)*l2+j-1];}}}returna[l1*l2-1];}57.用俩个栈实现队列。题目：某队列的声明如下：templateclassCQueue{public:CQueue(){}~CQueue(){}voidappendTail(constT&node);//appendaelementtotailvoiddeleteHead();//removeaelementfromheadprivate:Stackm_stack1;Stackm_stack2;};分析：从上面的类的声明中，我们发现在队列中有两个栈。因此这道题实质上是要求我们用两个栈来实现一个队列。相信大家对栈和队列的基本性质都非常了解了：栈是一种后入先出的数据容器，因此对队列进行的插入和删除操作都是在栈顶上进行；队列是一种先入先出的数据容器，我们总是把新元素插入到队列的尾部，而从队列的头部删除元素。ANSWERTraditionalprobleminCLRS.voidappendTail(constT&node){m_stack1.push(node);}TgetHead(){if(!m_stack2.isEmpty()){returnm_stack2.pop();}if(m_stack1.isEmpty())error(“deletefromemptyqueue”); while(!m_stack1.isEmpty()){m_stack2.push(m_stack1.pop());}returnm_stack2.pop();}58.从尾到头输出链表。题目：输入一个链表的头结点，从尾到头反过来输出每个结点的值。链表结点定义如下：structListNode{intm_nKey;ListNode*m_pNext;};分析：这是一道很有意思的面试题。该题以及它的变体经常出现在各大公司的面试、笔试题中。ANSWERHaveansweredthis...59.不能被继承的类。题目：用C++设计一个不能被继承的类。分析：这是Adobe公司2007年校园招聘的最新笔试题。这道题除了考察应聘者的C++基本功底外，还能考察反应能力，是一道很好的题目。ANSWER:Idon’tknowc++.Maybeitcanbedonebyimplementanemptyprivatedefaultconstructor.60.在O（1）时间内删除链表结点。题目：给定链表的头指针和一个结点指针，在O(1)时间删除该结点。链表结点的定义如下：structListNode{intm_nKey;ListNode*m_pNext;};函数的声明如下：voidDeleteNode(ListNode*pListHead,ListNode*pToBeDeleted);分析：这是一道广为流传的Google面试题，能有效考察我们的编程基本功，还能考察我们的反应速度，更重要的是，还能考察我们对时间复杂度的理解。ANSWER:Copythedatafromtobedeleted’snexttotobedeleted.thendeletetobedeleted.Thespecialcaseistobedeleteisthetail,thenwemustiteratetofinditspredecessor.TheamortizedtimecomplexityisO(1). -------------------------------------------------------------------------61.找出数组中两个只出现一次的数字题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。分析：这是一道很新颖的关于位运算的面试题。ANSWER:XOR.62.找出链表的第一个公共结点。题目：两个单向链表，找出它们的第一个公共结点。链表的结点定义为：structListNode{intm_nKey;ListNode*m_pNext;};分析：这是一道微软的面试题。微软非常喜欢与链表相关的题目，因此在微软的面试题中，链表出现的概率相当高。ANSWER:Havedonethis.63.在字符串中删除特定的字符。题目：输入两个字符串，从第一字符串中删除第二个字符串中所有的字符。例如，输入”Theyarestudents.”和”aeiou”，则删除之后的第一个字符串变成”Thyrstdnts.”。分析：这是一道微软面试题。在微软的常见面试题中，与字符串相关的题目占了很大的一部分，因为写程序操作字符串能很好的反映我们的编程基本功。ANSWER:Havedonethis?Useabytearray/characterhashtorecordsecondstring.thenusetwopointerstoshrinkthe1ststring.64.寻找丑数。题目：我们把只包含因子2、3和5的数称作丑数（UglyNumber）。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第1500个丑数。分析：这是一道在网络上广为流传的面试题，据说google曾经采用过这道题。ANSWER:TRADITIONAL.Useheap/priorityqueue.intno1500(){intheap[4500];heap[0]=2;heap[1]=3;heap[2]=5;intsize=3;for(inti=1;i<1500;i++){ints=heap[0]; heap[0]=s*2;siftDown(heap,0,size);heap[size]=s*3;siftUp(heap,size,size+1);heap[size+1]=s*5;siftUp(heap,size+1,size+2);size+=2;}}voidsiftDown(intheap[],intfrom,intsize){intc=from*2+1;while(c0){intp=(from-1)/2;if(heap[p]>heap[from])swap(heap,p,from);from=p;}}65.输出1到最大的N位数题目：输入数字n，按顺序输出从1最大的n位10进制数。比如输入3，则输出1、2、3一直到最大的3位数即999。分析：这是一道很有意思的题目。看起来很简单，其实里面却有不少的玄机。ANSWER:Somaybencouldexceedi32?Icannottellwhereisthetrick...Whowilloutput2*10^9numbers...66.颠倒栈。题目：用递归颠倒一个栈。例如输入栈{1,2,3,4,5}，1在栈顶。颠倒之后的栈为{5,4,3,2,1}，5处在栈顶。ANSWER:Interesting...voidreverse(Stackstack){if(stack.size()==1)return;Objecto=stack.pop();reverse(stack);putToBottom(stack,o);} voidputToBottom(Stackstack,Objecto){if(stack.isEmpty()){stack.push(o);return;}Objecto2=stack.pop();putToBottom(stack,o);stack.push(o2);}67.俩个闲玩娱乐。1.扑克牌的顺子从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2-10为数字本身，A为1，J为11，Q为12，K为13，而大小王可以看成任意数字。ANSWER://makeking=0booleanisStraight(inta[]){Arrays.sort(a);if(a[0]>0)returncheckGaps(a,0,4,0);if(a[0]==0&&a[1]!=0)returncheckGaps(a,1,4,1);returncheckGaps(a,2,4,2);}booleancheckGaps(int[]a,ints,inte,intallowGaps){inti=s;while(i6,f(m,n)=0wherem(){intcompareTo(Integeri1,Integeri2){return(“”+i1+i2).compare(“”+i2+i1);}});StringBuffersb=newStringBuffer();for(inti=0;ia[m])returnhelper(a,s,m);elsereturnhelper(a,m+1,t);}70.给出一个函数来输出一个字符串的所有排列。ANSWER简单的回溯就可以实现了。当然排列的产生也有很多种算法，去看看组合数学，还有逆序生成排列和一些不需要递归生成排列的方法。印象中Knuth的第一卷里面深入讲了排列的生成。这些算法的理解需要一定的数学功底，也需要一定的灵感，有兴趣最好看看。ANSWER:Havedonethis.71.数值的整数次方。题目：实现函数doublePower(doublebase,intexponent)，求base的exponent次方。不需要考虑溢出。分析：这是一道看起来很简单的问题。可能有不少的人在看到题目后30秒写出如下的代码：doublePower(doublebase,intexponent){doubleresult=1.0;for(inti=1;i<=exponent;++i)result*=base;returnresult; }ANSWER…doublepower(doublebase,intexp){if(exp==1)returnbase;doublehalf=power(base,exp>>1);return(((exp&1)==1)?base:1.0)*half*half;}72.题目：设计一个类，我们只能生成该类的一个实例。分析：只能生成一个实例的类是实现了Singleton模式的类型。ANSWERI’mnotgoodatmultithreadprogramming...Butifwesetalazyinitialization,the“if”conditioncouldbeinterruptedthusmultipleconstructorcouldbecalled,sowemustaddsynchronizedtotheifjudgements,whichisalossofefficiency.Puttingittothestaticinitializationwillguaranteethattheconstructoronlybeexecutedoncebythejavaclassloader.publicclassSingleton{privatestaticSingletoninstance=newSingleton();privatesynchronizedSingleton(){}publicSingletongetInstance(){returninstance();}}Thismaynotbecorrect.I’mquitebadatthis...73.对策字符串的最大长度。题目：输入一个字符串，输出该字符串中对称的子字符串的最大长度。比如输入字符串“google”，由于该字符串里最长的对称子字符串是“goog”，因此输出4。分析：可能很多人都写过判断一个字符串是不是对称的函数，这个题目可以看成是该函数的加强版。ANSWERBuildasuffixtreeofxandinverse(x),thelongestanagramisnaturallyfound.SuffixtreecanbebuiltinO(n)timesothisisalineartimesolution.74.数组中超过出现次数超过一半的数字题目：数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。分析：这是一道广为流传的面试题，包括百度、微软和Google在内的多家公司都曾经采用过这个题目。要几十分钟的时间里很好地解答这道题，除了较好的编程能力之外，还需要较快的反应和较强的逻辑思维能力。ANSWERDeleteeverytwodifferentdigits.Thelastonethatleftistheone.intgetMajor(inta[],intn){ intx,cnt=0;for(inti=0;im_pLeft,X,Y);TreeNode*right=getLCA(root->m_pRight,X,Y);if(left==NULL)returnright;elseif(right==NULL)returnleft;elsereturnroot;}76.复杂链表的复制题目：有一个复杂链表，其结点除了有一个m_pNext指针指向下一个结点外，还有一个m_pSibling指向链表中的任一结点或者NULL。其结点的C++定义如下：structComplexNode{intm_nValue;ComplexNode*m_pNext;ComplexNode*m_pSibling; };下图是一个含有5个结点的该类型复杂链表。图中实线箭头表示m_pNext指针，虚线箭头表示m_pSibling指针。为简单起见，指向NULL的指针没有画出。请完成函数ComplexNode*Clone(ComplexNode*pHead)，以复制一个复杂链表。分析：在常见的数据结构上稍加变化，这是一种很新颖的面试题。要在不到一个小时的时间里解决这种类型的题目，我们需要较快的反应能力，对数据结构透彻的理解以及扎实的编程功底。ANSWERHaveheardthisbefore,neverseriouslythoughtit.Thetrickislikethis:takeuseoftheoldpSibling,makeitpointstothenewcreatedclonednode,whilemakethenewclonednode’spNextbackuptheoldpSibling.ComplexNode*Clone(ComplexNode*pHead){if(pHead==NULL)returnNULL;preClone(pHead);inClone(pHead);returnpostClone(pHead);}voidpreClone(ComplexNode*pHead){ComplexNode*p=newComplexNode();p->m_pNext=pHead->m_pSibling;pHead->m_pSibling=p;if(pHead->m_pNext!=NULL)preClone(pHead->m_pNext);}voidinClone(ComplexNode*pHead){ComplexNode*pSib=pNew->m_pNext;if(pSib==NULL){pNew->m_pSibling=NULL;}else{pNew->m_pSibling=pSib->m_pSibling;}if(pHead->m_pNext!=NULL)inClone(pHead->m_pNext);}ComplexNode*postClone(ComplexNode*pHead){ComplexNode*pNew=pHead->m_pSibling;ComplexNode*pSib=pNew->m_pNext;if(pHead->m_pNext!=NULL){pNew->m_pNext=pHead->m_pNext->m_pSibling;pHead->m_pSibling=pSib;postClone(pHead->m_pNext);}else{pNew->pNext=NULL;pHead->m_pSibling=NULL;} returnpNew;}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.链表和数组的区别在哪里？分析：主要在基本概念上的理解。但是最好能考虑的全面一点，现在公司招人的竞争可能就在细节上产生，谁比较仔细，谁获胜的机会就大。ANSWER1.Besidesthecommonstaff,linkedlistismoreabstractandarrayisusuallyabasicrealworldobject.Whenmentioning“linkedlist”,itdoesn’tmatterhowitisimplemented,thatis,aslongasitsupports“getdata”and“getnext”,itisalinkedlist.Butalmostallprogramminglanguagesprovidesarrayasabasicdatastructure.2.Soarrayismorebasic.Youcanimplementalinkedlistinanarray,butcannotintheotherdirection.79.1.编写实现链表排序的一种算法。说明为什么你会选择用这样的方法？ANSWERForlinkedlistsorting,usuallymergesortisthebestchoice.Pros:O(1)auxilaryspace,comparedtoarraymergesort.Nonodecreation,justpointeroperations.Node*linkedListMergeSort(Node*pHead){intlen=getLen(pHead);returnmergeSort(pHead,len);} Node*mergeSort(Node*p,intlen){if(len==1){p->next=NULL;returnp;}Node*pmid=p;for(inti=0;inext;}Node*p1=mergeSort(p,len/2);Node*p2=mergeSort(pmid,len-len/2);returnmerge(p1,p2);}Node*merge(Node*p1,Node*p2){Node*p=NULL,*ph=NULL;while(p1!=NULL&&p2!=NULL){if(p1->datadata){if(ph==NULL){ph=p=p1;}else{p->next=p1;p1=p1->next;p=p->next;}}else{if(ph==NULL){ph=p=p2;}else{p->next=p2;p2=p2->next;p=p->next;}}}p->next=(p1==NULL)?p2:p1;returnph;}2.编写实现数组排序的一种算法。说明为什么你会选择用这样的方法？ANSWERActually,itdependsonthedata.Ifarbitrarydataisgiveninthearray,Iwouldchoosequicksort.Itisasytoimplement,fast.3.请编写能直接实现strstr()函数功能的代码。ANSWERSubstringtest?Havedonethis.80.阿里巴巴一道笔试题问题描述:12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?这个笔试题,很YD,因为把某个递归关系隐藏得很深。ANSWERMustbe1ab……cde……ccouldbe2thto7th(hastobesmallerthand,e...those5numbers),sof(12)=6f(10)=6*5f(8)=30*4f(6)=120*3f(4)=360*2f(2)=720 81.第1组百度面试题1.一个int数组，里面数据无任何限制，要求求出所有这样的数a[i]，其左边的数都小于等于它，右边的数都大于等于它。能否只用一个额外数组和少量其它空间实现。ANSWERSortthearraytoanotherarray,compareitwiththeoriginalarray,alla[i]=b[i]areanswers.2.一个文件，内含一千万行字符串，每个字符串在1K以内，要求找出所有相反的串对，如abc和cba。ANSWERSowehave~10Gdata.Itisunlikelytoputthemallintomainmemory.Anyway,calculatethehashofeachlineinthefirstround,atthesecondroundcalculatethehashofthereverseofthelineandremembersonlythelinenumberpairsthatthehashesofthetwodirectionscollides.Thelastroundonlytestthoselines.3.STL的set用什么实现的？为什么不用hash？ANSWERIdon’tquiteknow.Onlyheardofthatmapinstlisimplementedwithred-blacktree.Onegoodthingoverhashisthatyoudon’tneedtore-hashwhendatasizegrows.82.第2组百度面试题1.给出两个集合A和B，其中集合A={name}，集合B={age、sex、scholarship、address、...}，要求：问题1、根据集合A中的name查询出集合B中对应的属性信息；问题2、根据集合B中的属性信息（单个属性，如age<20等），查询出集合A中对应的name。ANSWERSQL?Notagooddefinedquestion.2.给出一个文件，里面包含两个字段{url、size}，即url为网址，size为对应网址访问的次数要求：问题1、利用LinuxShell命令或自己设计算法，查询出url字符串中包含“baidu”子字符串对应的size字段值；问题2、根据问题1的查询结果，对其按照size由大到小的排列。（说明：url数据量很大，100亿级以上）ANSWER1.shell:gawk‘/baidu/{print$2}’FILE2.shell:gawk‘/baidu/{print$2}’FILE|sort-n-r83.第3组百度面试题1.今年百度的一道题目百度笔试：给定一个存放整数的数组，重新排列数组使得数组左边为奇数，右边为偶数。要求：空间复杂度O(1)，时间复杂度为O（n）。ANSWERHavedonethis.2.百度笔试题用C语言实现函数void*memmove(void*dest,constvoid*src,size_tn)。memmove 函数的功能是拷贝src所指的内存内容前n个字节到dest所指的地址上。分析：由于可以把任何类型的指针赋给void类型的指针,这个函数主要是实现各种数据类型的拷贝。ANSWER//Tomymemory,usuallymemcpydoesn’tcheckoverlap,memmovedovoid*memmove(void*dest,constvoid*src,size_tn){if(dest==NULL||src==NULL)error(“NULLpointers”);byte*psrc=(byte*)src;byte*pdest=(byte*)dest;intstep=1;if(dest=nandC(M-1,2)end)returnNULL;intm=start+(end-start)/2;Node*root=newNode(array[m]);root->left=helper(array,start,m-1);root->right=helper(array,m+1,end);returnroot;} 87.1.大整数数相乘的问题。（这是2002年在一考研班上遇到的算法题）ANSWERDooverflowmanually.finalstaticlongmask=(1<<31)-1;ArrayListmultiply(ArrayLista,ArrayListb){ArrayListresult=newArrayList(a.size()*b.size()+1);for(inti=0;ix,inta,intbase,ArrayListresult){if(a==0)return;longoverflow=0;inti;for(i=0;i>31);}while(overflow!=0){longtmp=result.get(base+i)+overflow;result.set(base+i,(int)(mask&tmp));overflow=(tmp>>31);}}2.求最大连续递增数字串（如“ads3sl456789DF3456ld345AA”中的“456789”）ANSWERHavedonethis.3.实现strstr功能，即在父串中寻找子串首次出现的位置。（笔试中常让面试者实现标准库中的一些函数）ANSWERHavedonethis.88.2005年11月金山笔试题。编码完成下面的处理函数。函数将字符串中的字符"*"移到串的前部分，前面的非"*"字符后移，但不能改变非"*"字符的先后顺序，函数返回串中字符"*"的数量。如原始串为：ab**cd**e*12，处理后为*****abcde12，函数并返回值为5。（要求使用尽量少的时间和辅助空间）ANSWERIt’slikepartitioninquicksort.Justkeepthenon-*partstable. intpartitionStar(chara[]){intcount=0;inti=a.length-1,j=a.length-1;//iforthecursor,jforthefirstnon-*charwhile(i>=0){if(a[i]!=‘*’){swap(a,i--,j--);}else{i--;count++;}}returncount;}89.神州数码、华为、东软笔试题1.2005年11月15日华为软件研发笔试题。实现一单链表的逆转。ANSWERHavedonethis.2.编码实现字符串转整型的函数（实现函数atoi的功能），据说是神州数码笔试题。如将字符串”+123”123,”-0123”-123,“123CS45”123,“123.45CS”123,“CS123.45”0ANSWERintatoi(constchar*a){if(*a==’+’)returnatoi(a+1);elseif(*a==’-’)return-atoi(a+1);char*p=a;intc=0;while(*p>=‘0’&&*p<=‘9’){c=c*10+(*p-‘0’);}returnc;}3.快速排序（东软喜欢考类似的算法填空题，又如堆排序的算法等）ANSWERStandardsolution.Skip.4.删除字符串中的数字并压缩字符串。如字符串”abc123de4fg56”处理后变为”abcdefg”。注意空间和效率。（下面的算法只需要一次遍历，不需要开辟新空间，时间复杂度为O(N)）ANSWERAlsopartition,keepnon-digitstable.char*partition(constchar*str){char*i=str;//iforcursor,jforthefirstdigitchar;char*j=str;while(*i!=‘’){ if(*i>‘9’||*i<‘0’){*j++=*i++;}else{*i++;}}*j=‘’;returnstr;}5.求两个串中的第一个最长子串（神州数码以前试题）。如"abractyeyt","dgdsaeactyey"的最大子串为"actyet"。ANSWERUsesuffixtree.Thelongestcommonsubstringisthelongestprefixofthesuffixes.O(n)tobuildsuffixtree.O(n)tofindthelcs.90.1.不开辟用于交换数据的临时空间，如何完成字符串的逆序(在技术一轮面试中，有些面试官会这样问)。ANSWERTwocursors.2.删除串中指定的字符（做此题时，千万不要开辟新空间，否则面试官可能认为你不适合做嵌入式开发）ANSWERHavedonethis.3.判断单链表中是否存在环。ANSWERHavedonethis.911.一道著名的毒酒问题有1000桶酒，其中1桶有毒。而一旦吃了，毒性会在1周后发作。现在我们用小老鼠做实验，要在1周内找出那桶毒酒，问最少需要多少老鼠。ANSWERHavedonethis.10mices.2.有趣的石头问题有一堆1万个石头和1万个木头，对于每个石头都有1个木头和它重量一样，把配对的石头和木头找出来。ANSWERQuicksort. 92.1.多人排成一个队列,我们认为从低到高是正确的序列,但是总有部分人不遵守秩序。如果说,前面的人比后面的人高(两人身高一样认为是合适的),那么我们就认为这两个人是一对“捣乱分子”,比如说,现在存在一个序列:176,178,180,170,171这些捣乱分子对为<176,170>,<176,171>,<178,170>,<178,171>,<180,170>,<180,171>,那么,现在给出一个整型序列,请找出这些捣乱分子对的个数(仅给出捣乱分子对的数目即可,不用具体的对)要求：输入:为一个文件(in)，文件的每一行为一个序列。序列全为数字，数字间用”,”分隔。输出：为一个文件(out)，每行为一个数字，表示捣乱分子的对数。详细说明自己的解题思路，说明自己实现的一些关键点。并给出实现的代码，并分析时间复杂度。限制：输入每行的最大数字个数为100000个，数字最长为6位。程序无内存使用限制。ANSWERTheansweristheswapnumberofinsertionsort.Thestraightforwardmethodistodoinsertionsortandaccumulatetheswapnumbers,whichisslow:O(n^2)Asub-quadraticsolutioncanbedonebyDP.f(n)=f(n-1)+Index(n)Index(n),whichistodeterminehowmanynumbersissmallerthana[n]ina[0..n-1],canbedoneinlog(n)timeusingBSTwithsubtreesize.93.在一个int数组里查找这样的数，它大于等于左侧所有数，小于等于右侧所有数。直观想法是用两个数组a、b。a[i]、b[i]分别保存从前到i的最大的数和从后到i的最小的数，一个解答：这需要两次遍历，然后再遍历一次原数组，将所有data[i]>=a[i-1]&&data[i]<=b[i]的data[i]找出即可。给出这个解答后，面试官有要求只能用一个辅助数组，且要求少遍历一次。ANSWERItisnaturaltoimprovethehint...justduringthesecondtraversal,dotherangeminimumandpickingtogether.Thereisnoneedtostoretherangeminimums.94.微软笔试题求随机数构成的数组中找到长度大于=3的最长的等差数列,输出等差数列由小到大:如果没有符合条件的就输出格式：输入[1,3,0,5,-1,6]输出[-1,1,3,5]要求时间复杂度，空间复杂度尽量小ANSWER Firstlysortthearray.ThendoDP:foreacha[i],updatethelengthofthearithmeticsequences.That’saO(n^3)solution.Eacharithmeticsequencecanbedeterminedbythelastitemandthestepsize.95.华为面试题1判断一字符串是不是对称的，如：abccbaANSWERTwocursors.2.用递归的方法判断整数组a[N]是不是升序排列ANSWERbooleanisAscending(inta[]){returnisAscending(a,0);}booleanisAscending(inta[],intstart){returnstart==a.length-1||isAscending(a,start+1);}96.08年中兴校园招聘笔试题1．编写strcpy函数已知strcpy函数的原型是char*strcpy(char*strDest,constchar*strSrc);其中strDest是目的字符串，strSrc是源字符串。不调用C++/C的字符串库函数，请编写函数strcpyANSWERchar*strcpy(char*strDest,constchar*strSrc){if(strSrc==NULL)returnNULL;char*i=strSrc,*j=strDest;while(*i!=‘’){*j++=*i++;}*j=‘’;returnstrDest;}Maybeyouneedtocheckifsrcanddestoverlaps,thendecidewhethertocopyfromtailtohead.最后压轴之戏，终结此微软等100题系列V0.1版。那就，连续来几组微软公司的面试题，让你一次爽个够：======================97.第1组微软较简单的算法面试题1.编写反转字符串的程序，要求优化速度、优化空间。ANSWERHavedonethis. 2.在链表里如何发现循环链接？ANSWERHavedonethis.3.编写反转字符串的程序，要求优化速度、优化空间。ANSWERHavedonethis.4.给出洗牌的一个算法，并将洗好的牌存储在一个整形数组里。ANSWERHavedonethis.5.写一个函数，检查字符是否是整数，如果是，返回其整数值。（或者：怎样只用4行代码编写出一个从字符串到长整形的函数？）ANSWERCharorstring?havedoneatoi;98.第2组微软面试题1.给出一个函数来输出一个字符串的所有排列。ANSWERHavedonethis...2.请编写实现malloc()内存分配函数功能一样的代码。ANSWERWaytoohardasaninterviewquestion...Pleasecheckwikipediaforsolutions...3.给出一个函数来复制两个字符串A和B。字符串A的后几个字节和字符串B的前几个字节重叠。ANSWERCopyfromtailtohead.4.怎样编写一个程序，把一个有序整数数组放到二叉树中？ANSWERHavedonethis.5.怎样从顶部开始逐层打印二叉树结点数据？请编程。ANSWERHavedonethis...6.怎样把一个链表掉个顺序（也就是反序，注意链表的边界条件并考虑空链表）？ANSWERHavedonethis... 99.第3组微软面试题1.烧一根不均匀的绳，从头烧到尾总共需要1个小时。现在有若干条材质相同的绳子，问如何用烧绳的方法来计时一个小时十五分钟呢？ANSWERMayhavedonethis...burnfrombothsidegives½hour.2.你有一桶果冻，其中有黄色、绿色、红色三种，闭上眼睛抓取同种颜色的两个。抓取多少个就可以确定你肯定有两个同一颜色的果冻？（5秒-1分钟）ANSWER4.3.如果你有无穷多的水，一个3公升的提捅，一个5公升的提捅，两只提捅形状上下都不均匀，问你如何才能准确称出4公升的水？（40秒-3分钟）ANSWER5to3=>22to3,remaining15toremaining1=>4一个岔路口分别通向诚实国和说谎国。来了两个人，已知一个是诚实国的，另一个是说谎国的。诚实国永远说实话，说谎国永远说谎话。现在你要去说谎国，但不知道应该走哪条路，需要问这两个人。请问应该怎么问？（20秒-2分钟）ANSWERSeemstherearetoomanyanswers.Iwillpickanyonetoask:howtogettoyourcountry?Thenpicktheotherway.100.第4组微软面试题，挑战思维极限1.12个球一个天平，现知道只有一个和其它的重量不同，问怎样称才能用三次就找到那个球。13个呢？（注意此题并未说明那个球的重量是轻是重，所以需要仔细考虑）（5分钟-1小时）ANSWERToocomplicated.Gofindbrainteaseranswersbyyourself.2.在9个点上画10条直线，要求每条直线上至少有三个点？（3分钟-20分钟）3.在一天的24小时之中，时钟的时针、分针和秒针完全重合在一起的时候有几次？都分别是什么时间？你怎样算出来的？（5分钟-15分钟）30终结附加题：微软面试题，挑战你的智商==========说明：如果你是第一次看到这种题，并且以前从来没有见过类似的题型，并且能够在半个小时之内做出答案，说明你的智力超常..） 1.第一题.五个海盗抢到了100颗宝石，每一颗都一样大小和价值连城。他们决定这么分：抽签决定自己的号码（1、2、3、4、5）首先，由1号提出分配方案，然后大家表决，当且仅当超过半数的人同意时，按照他的方案进行分配，否则将被扔进大海喂鲨鱼如果1号死后，再由2号提出分配方案，然后剩下的4人进行表决，当且仅当超过半数的人同意时，按照他的方案进行分配，否则将被扔入大海喂鲨鱼。依此类推条件：每个海盗都是很聪明的人，都能很理智地做出判断，从而做出选择。问题：第一个海盗提出怎样的分配方案才能使自己的收益最大化？Answer:Atraditionalbrainteaser.Consider#5,whatever#4proposes,hewon’tagree,so#4mustagreewhatever#3proposes.Soifthereareonly#3-5,#3shouldpropose(100,0,0).Sotheexpectedincomeof#3is100,and#4and#5is0for3guyproblem.Sowhatever#2proposes,#3won’tagree,butif#2give#4and#5$1,theycangetmorethan3-guysubproblem.So#2willpropose(98,0,1,1).Sofor#1,ifgive#2lessthan$98,#2won’tagree.Buthecangive#3$1and#4or#5$2,sothisisa(97,0,1,2,0)solution.2.一道关于飞机加油的问题，已知：每个飞机只有一个油箱，飞机之间可以相互加油（注意是相互，没有加油机）一箱油可供一架飞机绕地球飞半圈，问题：为使至少一架飞机绕地球一圈回到起飞时的飞机场，至少需要出动几架飞机？（所有飞机从同一机场起飞，而且必须安全返回机场，不允许中途降落，中间没有飞机场）-------------------------------------------------------------------------------------------------------------------------------更多面试题，请参见：微软、谷歌、百度等公司经典面试100题[第1-60题]（微软100题第二版前60题）微软、Google等公司非常好的面试题及解答[第61-70题]（微软100题第二版第61-70题）十道海量数据处理面试题与十个方法大总结（十道海量数据处理面试题）海量数据处理面试题集锦与Bit-map详解（十七道海量数据处理面试题）九月腾讯，创新工场，淘宝等公司最新面试十三题（2011年度9月最新面试30题）十月百度，阿里巴巴，迅雷搜狗最新面试十一题（2011年度十月最新面试题集锦）一切的详情，可看此文：横空出世，席卷Csdn--评微软等数据结构+算法面试100题（在此文中，你能找到与微软100题所有一切相关的东西）所有的资源下载（题目+答案）地址：http://v_july_v.download.csdn.net/本微软等100题系列V0.1版，永久维护地址：http://topic.csdn.net/u/20101126/10/b4f12a00-6280-492f-b785-cb6835a63dc9.html作者声明:“本人July对以上所有任何内容和资料享有版权，转载请注明作者本人July及出处。向你的厚道致敬。谢谢。二零一一年十月十三日、以诸君为傲。 欢迎，任何人，就以上任何内容，题目与答案思路，或其它任何问题、与我联系：本人邮箱：zhoulei0907@yahoo.cn”最新整理的全部100题的答案参见如下（重复的，以及一些无关紧要的题目跳过）：1.把二元查找树转变成排序的双向链表题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。10/614//481216转换成双向链表4=6=8=10=12=14=16。首先我们定义的二元查找树节点的数据结构如下：structBSTreeNode{intm_nValue;//valueofnodeBSTreeNode*m_pLeft;//leftchildofnodeBSTreeNode*m_pRight;//rightchildofnode};ANSWER:Thisisatraditionalproblemthatcanbesolvedusingrecursion.Foreachnode,connectthedoublelinkedlistscreatedfromleftandrightchildnodetoformafulllist./***@paramrootTherootnodeofthetree*@returnTheheadnodeoftheconvertedlist.*/BSTreeNode*treeToLinkedList(BSTreeNode*root){BSTreeNode*head,*tail;helper(head,tail,root);returnhead;}voidhelper(BSTreeNode*&head,BSTreeNode*&tail,BSTreeNode*root){BSTreeNode*lt,*rh;if(root==NULL){head=NULL,tail=NULL;return;}helper(head,lt,root->m_pLeft);helper(rh,tail,root->m_pRight); if(lt!=NULL){lt->m_pRight=root;root->m_pLeft=lt;}else{head=root;}if(rh!=NULL){root->m_pRight=rh;rh->m_pLeft=root;}else{tail=root;}}2.设计包含min函数的栈。定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。ANSWER:StackisaLIFOdatastructure.Whensomeelementispoppedfromthestack,thestatuswillrecovertotheoriginalstatusasbeforethatelementwaspushed.Sowecanrecovertheminimumelement,too.structMinStackElement{intdata;intmin;};structMinStack{MinStackElement*data;intsize;inttop;}MinStackMinStackInit(intmaxSize){MinStackstack;stack.size=maxSize;stack.data=(MinStackElement*)malloc(sizeof(MinStackElement)*maxSize);stack.top=0;returnstack;}voidMinStackFree(MinStackstack){free(stack.data);}voidMinStackPush(MinStackstack,intd){if(stack.top==stack.size)error(“outofstackspace.”);MinStackElement*p=stack.data[stack.top]; p->data=d;p->min=(stack.top==0?d:stack.data[top-1]);if(p->min>d)p->min=d;top++;}intMinStackPop(MinStackstack){if(stack.top==0)error(“stackisempty!”);returnstack.data[--stack.top].data;}intMinStackMin(MinStackstack){if(stack.top==0)error(“stackisempty!”);returnstack.data[stack.top-1].min;}3.求子数组的最大和题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。例如输入的数组为1,-2,3,10,-4,7,2,-5，和最大的子数组为3,10,-4,7,2，因此输出为该子数组的和18。ANSWER:Atraditionalgreedyapproach.Keepcurrentsum,slidefromlefttoright,whensum<0,resetsumto0.intmaxSubarray(inta[],intsize){if(size<=0)error(“errorarraysize”);intsum=0;intmax=-(1<<31);intcur=0;while(curmax){max=sum;}elseif(sum<0){sum=0;}}returnmax;}4.在二元树中找出和为某一值的所有路径题目：输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。例如输入整数22和如下二元树 10/512/47则打印出两条路径：10,12和10,5,7。二元树节点的数据结构定义为：structBinaryTreeNode//anodeinthebinarytree{intm_nValue;//valueofnodeBinaryTreeNode*m_pLeft;//leftchildofnodeBinaryTreeNode*m_pRight;//rightchildofnode};ANSWER:Usebacktrackingandrecurison.Weneedastacktohelpbacktrackingthepath.structTreeNode{intdata;TreeNode*left;TreeNode*right;};voidprintPaths(TreeNode*root,intsum){intpath[MAX_HEIGHT];helper(root,sum,path,0);}voidhelper(TreeNode*root,intsum,intpath[],inttop){path[top++]=root.data;sum-=root.data;if(root->left==NULL&&root->right==NULL){if(sum==0)printPath(path,top);}else{if(root->left!=NULL)helper(root->left,sum,path,top);if(root->right!=NULL)helper(root->right,sum,path,top);}top--;sum-=root.data;}5.查找最小的k个元素题目：输入n个整数，输出其中最小的k个。例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。ANSWER:Thisisaverytraditionalquestion... O(nlogn):catI_FILE|sort-n|head-nKO(kn):doinsertionsortuntilkelementsareretrieved.O(n+klogn):TakeO(n)timetobottom-upbuildamin-heap.Thensift-downk-1times.SotraditionalthatIdon’twanttowritethecodes...Onlygivesthesiftupandsiftdownfunction./***@paramitheindexoftheelementinheapa[0...n-1]tobesiftedupvoidsiftup(inta[],inti,intn){while(i>0){intj=(i&1==0?i-1:i+1);intp=(i-1)>>1;if(jnext!=NULL){h1=h1->next;}while(h2->next!=NULL){h2=h2->next;}returnh1==h2;}//iftherecouldexistcycleintisJoined(Node*h1,Node*h2){Node*cylic1=testCylic(h1);Node*cylic2=testCylic(h2);if(cylic1+cylic2==0)returnisJoinedSimple(h1,h2);if(cylic1==0&&cylic2!=0||cylic1!=0&&cylic2==0)return0;Node*p=cylic1;while(1){if(p==cylic2||p->next==cylic2)return1;p=p->next->next;cylic1=cylic1->next;if(p==cylic1)return0;}}Node*testCylic(Node*h1){Node*p1=h1,*p2=h1;while(p2!=NULL&&p2->next!=NULL){p1=p1->next;p2=p2->next->next;if(p1==p2){returnp1;}}returnNULL;} 第8题此贴选一些比较怪的题，，由于其中题目本身与算法关系不大，仅考考思维。特此并作一题。1.有两个房间，一间房里有三盏灯，另一间房有控制着三盏灯的三个开关，这两个房间是分割开的，从一间里不能看到另一间的情况。现在要求受训者分别进这两房间一次，然后判断出这三盏灯分别是由哪个开关控制的。有什么办法呢？ANSWER:Skip.2.你让一些人为你工作了七天，你要用一根金条作为报酬。金条被分成七小块，每天给出一块。如果你只能将金条切割两次，你怎样分给这些工人?ANSWER:1+2+4;3.★用一种算法来颠倒一个链接表的顺序。现在在不用递归式的情况下做一遍。ANSWER:Node*reverse(Node*head){if(head==NULL)returnhead;if(head->next==NULL)returnhead;Node*ph=reverse(head->next);head->next->next=head;head->next=NULL;returnph;}Node*reverseNonrecurisve(Node*head){if(head==NULL)returnhead;Node*p=head;Node*previous=NULL;while(p->next!=NULL){p->next=previous;previous=p;p=p->next;}p->next=previous;returnp;}★用一种算法在一个循环的链接表里插入一个节点，但不得穿越链接表。ANSWER:Idon’tunderstandwhatis“Chuanyue”.★用一种算法整理一个数组。你为什么选择这种方法?ANSWER:Whatis“Zhengli?”★用一种算法使通用字符串相匹配。ANSWER: Whatis“Tongyongzifuchuan”...astringwith“*”and“?”?Ifso,hereisthecode.intmatch(char*str,char*ptn){if(*ptn==‘’)return1;if(*ptn==‘*’){do{if(match(str++,ptn+1))return1;}while(*str!=‘’);return0;}if(*str==‘’)return0;if(*str==*ptn||*ptn==‘?’){returnmatch(str+1,ptn+1);}return0;}★颠倒一个字符串。优化速度。优化空间。voidreverse(char*str){reverseFixlen(str,strlen(str));}voidreverseFixlen(char*str,intn){char*p=str+n-1;while(str=0&&str[j--]==sub[k--]);if(k<0)returnj+1;if(i+1=len&&strncmp(sub,p-len+1,len)==0)returni-len;p++; }return-1;}★比较两个字符串，用O(n)时间和恒量空间。ANSWER:Whatis“comparingtwostrings”?Justnormalstringcomparison?ThenaturalwayuseO(n)timeandO(1)space.intstrcmp(char*p1,char*p2){while(*p1!=‘’&&*p2!=‘’&&*p1==*p2){p1++,p2++;}if(*p1==‘’&&*p2==‘’)return0;if(*p1==‘’)return-1;if(*p2==‘’)return1;return(*p1-*p2);//itcanbenegotiatedwhethertheabove3if’sarenecessary,Idon’tliketoomitthem.}★假设你有一个用1001个整数组成的数组，这些整数是任意排列的，但是你知道所有的整数都在1到1000(包括1000)之间。此外，除一个数字出现两次外，其他所有数字只出现一次。假设你只能对这个数组做一次处理，用一种算法找出重复的那个数字。如果你在运算中使用了辅助的存储方式，那么你能找到不用这种方式的算法吗?ANSWER:Sumupallthenumbers,thensubtractthesumfrom1001*1002/2.Anotherway,useAXORAXORB=B:intfindX(inta[]){intk=a[0];for(inti=1;i<=1000;i++)k~=a[i]~i;}returnk;}★不用乘法或加法增加8倍。现在用同样的方法增加7倍。ANSWER:n<<3;(n<<3)-n;第9题判断整数序列是不是二元查找树的后序遍历结果题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true，否则返回false。例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果：8/610 //57911因此返回true。如果输入7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回false。ANSWER:Thisisaninterestingone.Thereisatraditionalquestionthatrequiresthebinarytreetobere-constructedfrommid/post/preorderresults.Thisseemssimilar.Fortheproblemsrelatedto(binary)trees,recursionisthefirstchoice.Inthisproblem,weknowinpost-orderresults,thelastnumbershouldbetheroot.SowehaveknowntherootoftheBSTis8intheexample.Sowecansplitthearraybytheroot.intisPostorderResult(inta[],intn){returnhelper(a,0,n-1);}inthelper(inta[],ints,inte){if(e==s)return1;inti=e-1;while(a[e]>a[i]&&i>=s)i--;if(!helper(a,i+1,e-1))return0;intk=l;while(a[e]=s)i--;returnhelper(a,s,l);}第10题翻转句子中单词的顺序。题目：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。例如输入“Iamastudent.”，则输出“student.aamI”。Answer:Alreadydonethis.Skipped.第11题求二叉树中节点的最大距离...如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，我们姑且定义"距离"为两节点之间边的个数。写一个程序，求一棵二叉树中相距最远的两个节点之间的距离。ANSWER:Thisisinteresting...Alsorecursively,thelongestdistancebetweentwonodesmustbeeitherfromroottooneleaf,orbetweentwoleafs.Fortheformercase,it’sthetreeheight.Forthelattercase,itshouldbethesumoftheheightsofleftandrightsubtreesofthetwoleaves’mostleastancestor.Thefirstcaseisalsothesumtheheightsofsubtrees,justtheheight+0. intmaxDistance(Node*root){intdepth;returnhelper(root,depth);}inthelper(Node*root,int&depth){if(root==NULL){depth=0;return0;}intld,rd;intmaxleft=helper(root->left,ld);intmaxright=helper(root->right,rd);depth=max(ld,rd)+1;returnmax(maxleft,max(maxright,ld+rd));}第12题题目：求1+2+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字以及条件判断语句（A?B:C）。ANSWER:1+..+n=n*(n+1)/2=(n^2+n)/2itiseasytogetx/2,sotheproblemistogetn^2thoughnoif/elseisallowed,wecaneasillygoaroundusingshort-pass.usingmacrotomakeitfancier:#defineT(X,Y,i)(Y&(1<>1;}第13题：题目：输入一个单向链表，输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。链表结点定义如下：structListNode{intm_nKey;ListNode*m_pNext;};Answer:Twoways.1:recordthelengthofthelinkedlist,thengon-ksteps.2:usetwocursors.Timecomplexitiesareexactlythesame.Node*lastK(Node*head,intk){ if(k<0)error(“k<0”);Node*p=head,*pk=head;for(;k>0;k--){if(pk->next!=NULL)pk=pk->next;elsereturnNULL;}while(pk->next!=NULL){p=p->next,pk=pk->next;}returnp;}第14题：题目：输入一个已经按升序排序过的数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。ANSWER:Usetwocursors.Oneatfrontandtheotherattheend.Keeptrackofthesumbymovingthecursors.voidfind2Number(inta[],intn,intdest){int*f=a,*e=a+n-1;intsum=*f+*e;while(sum!=dest&&fleft),&(root->right));mirror(root->left);mirror(root->right);}voidmirrorIteratively(Node*root){if(root==NULL)return;stackbuf;buf.push(root);while(!stack.empty()){Node*n=stack.pop();swap(&(root->left),&(root->right));if(root->left!=NULL)buf.push(root->left);if(root->right!=NULL)buf.push(root->right);}}第16题：题目（微软）：输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。例如输入78/610// 57911输出861057911。ANSWER:Thenodesinthelevelsareprintedinthesimilarmannertheirparentswereprinted.SoitshouldbeanFIFOqueuetoholdthelevel.Ireallydon’trememberthefunctionnameofthestlqueue,soIwillwriteitinJava...voidprintByLevel(Noderoot){Nodesentinel=newNode();LinkedListq=newLinkedList();q.addFirst(root);q.addFirst(sentinel);while(!q.isEmpty()){Noden=q.removeLast();if(n==sentinel){System.out.println(“n”);q.addFirst(sentinel);}else{System.out.println(n);if(n.left()!=null)q.addFirst(n.left());if(n.right()!=null)q.addFirst(n.right());}}}第17题：题目：在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff，则输出b。分析：这道题是2006年google的一道笔试题。ANSWER:Again,thisdependsonwhatis“char”.Let’sassumeitasASCII.charfirstSingle(char*str){inta[255];memset(a,0,255*sizeof(int));char*p=str;while(*p!=’’){a[*p]++;p++;}p=str;while(*p!=’’){if(a[*p]==1)return*p;}return‘’;//thismusttheonethatoccursexact1time.}第18题：题目：n个数字（0,1,…,n-1）形成一个圆圈，从数字0开始， 每次从这个圆圈中删除第m个数字（第一个为当前数字本身，第二个为当前数字的下一个数字）。当一个数字删除后，从被删除数字的下一个继续删除第m个数字。求出在这个圆圈中剩下的最后一个数字。July：我想，这个题目，不少人已经见识过了。ANSWER:Actually,althoughthisisasotraditionalproblem,Iwasalwaystolazytothinkaboutthisoreventosearchfortheanswer.(Whatashame...).Finally,bygoogleIfoundtheelegantsolutionforit.Thekeysare:1)ifweshifttheidsbyk,namely,startfromkinsteadof0,weshouldaddtheresultbyk%n2)afterthefirstround,westartfromk+1(possibly%n)withn-1elements,thatisequaltoan(n-1)problemwhilestartfrom(k+1)thelementinsteadof0,sotheansweris(f(n-1,m)+k+1)%n3)k=m-1,sof(n,m)=(f(n-1,m)+m)%n.finally,f(1,m)=0;NowthisisaO(n)solution.intjoseph(intn,intm){intfn=0;for(inti=2;i<=n;i++){fn=(fn+m)%i;}returnfn;}hu...长出一口气。。。第19题：题目：定义Fibonacci数列如下：/0n=0f(n)=1n=1f(n-1)+f(n-2)n=2输入n，用最快的方法求该数列的第n项。分析：在很多C语言教科书中讲到递归函数的时候，都会用Fibonacci作为例子。因此很多程序员对这道题的递归解法非常熟悉，但....呵呵，你知道的。。ANSWER:Thisisthetraditionalproblemofapplicationofmathematics...letA={11}{10}f(n)=A^(n-1)[0,0]thisgivesaO(logn)solution.intf(intn){intA[4]={1,1,1,0};intresult[4];power(A,n,result);returnresult[0];} voidmultiply(int[]A,int[]B,int_r){_r[0]=A[0]*B[0]+A[1]*B[2];_r[1]=A[0]*B[1]+A[1]*B[3];_r[2]=A[2]*B[0]+A[3]*B[2];_r[3]=A[2]*B[1]+A[3]*B[3];}voidpower(int[]A,intn,int_r){if(n==1){memcpy(A,_r,4*sizeof(int));return;}inttmp[4];power(A,n>>1,_r);multiply(_r,_r,tmp);if(n&1==1){multiply(tmp,A,_r);}else{memcpy(_r,tmp,4*sizeof(int));}}第20题：题目：输入一个表示整数的字符串，把该字符串转换成整数并输出。例如输入字符串"345"，则输出整数345。ANSWER:ThisquestioncheckshowtheintervieweeisfamiliarwithC/C++?I’msobadatC/C++...intatoi(char*str){intneg=0;char*p=str;if(*p==‘-’){p++;neg=1;}elseif(*p==‘+’){p++;}intnum=0;while(*p!=‘’){if(*p>=0&&*p<=9){num=num*10+(*p-’0’);}else{error(“illegalnumber”);}p++;}returnnum;}PS:Ididn’tfigureouthowtotellaoverflowproblemeasily. 第21题2010年中兴面试题编程求解：输入两个整数n和m，从数列1，2，3.......n中随意取几个数,使其和等于m,要求将其中所有的可能组合列出来.ANSWERThisisacombinationgenerationproblem.voidfindCombination(intn,intm){if(n>m)findCombination(m,m);intaux[n];memset(aux,0,n*sizeof(int));helper(m,0,aux);}voidhelper(intdest,intidx,intaux[],intn){if(dest==0)dump(aux,n);if(dest<=0||idx==n)return;helper(dest,idx+1,aux,n);aux[idx]=1;helper(dest-idx-1,idx+1,aux,n);aux[idx]=0;}voiddump(intaux[],intn){for(inti=0;idata>h2->data){head=h2;h2=h2->next;}else{head=h1;h1=h1->next;}Node*current=head;while(h1!=NULL&&h2!=NULL){if(h1==NULL||(h2!=NULL&&h1->data>h2->data)){current->next=h2;h2=h2->next;current=current->next;}else{current->next=h1;h1=h1->next;current=current->next;}}current->next=NULL; returnhead;}第25题：写一个函数,它的原形是intcontinumax(char*outputstr,char*intputstr)功能：在字符串中找出连续最长的数字串，并把这个串的长度返回，并把这个最长数字串付给其中一个函数参数outputstr所指内存。例如："abcd12345ed125ss123456789"的首地址传给intputstr后，函数将返回9，outputstr所指的值为123456789ANSWER:intcontinumax(char*outputstr,char*inputstr){intlen=0;char*pstart=NULL;intmax=0;while(1){if(*inputstr>=‘0’&&*inputstr<=’9’){len++;}else{if(len>max)pstart=inputstr-len;len=0;}if(*inputstr++==’’)break;}for(inti=0;i>=8;}returnc;}29.栈的push、pop序列题目：输入两个整数序列。其中一个序列表示栈的push顺序，判断另一个序列有没有可能是对应的pop顺序。为了简单起见，我们假设push序列的任意两个整数都是不相等的。比如输入的push序列是1、2、3、4、5，那么4、5、3、2、1就有可能是一个pop系列。因为可以有如下的push和pop序列：push1，push2，push3，push4，pop，push5，pop，pop，pop，pop，这样得到的pop序列就是4、5、3、2、1。但序列4、3、5、1、2就不可能是push序列1、2、3、4、5的pop序列。ANSWERThisseemsinteresting.However,aquitestraightforwardandpromisingwayistoactuallybuildthestackandcheckwhetherthepopactioncanbeachieved.intisPopSeries(intpush[],intpop[],intn){stackhelper; inti1=0,i2=0;while(i2>,asimilarproblemsplitsanarraytohalvesasevenaspossible.Itispossibletotakebinarysearch,whenSUMofthearrayisnottoohigh.Elsethisisaquitetimeconsumingbruteforceproblem.Icannotfigureoutareasonablesolution.33.实现一个挺高级的字符匹配算法：给一串很长字符串，要求找到符合要求的字符串，例如目的串：1231******3***2,12*****3这些都要找出来其实就是类似一些和谐系统。。。。。ANSWERNotaclearproblem.Seemsabitsetcando.34.实现一个队列。队列的应用场景为：一个生产者线程将int类型的数入列，一个消费者线程将int类型的数出列ANSWERIdon’tknowmultithreadprogrammingatall....35.求一个矩阵中最大的二维矩阵(元素和最大).如:1203423451 11530中最大的是:4553要求:(1)写出算法;(2)分析时间复杂度;(3)用C写出关键代码ANSWERThisisthetraditionalprobleminProgrammingPearls.However,thebestresultistoocomplicatedtoachieve.Soletsdothesuboptimalone.O(n^3)solution.1)Wehaveknowthatthesimilarproblemfor1dimarraycanbedoneinO(n)time.However,thiscannotbedoneinbothdirectionsinthesametime.Wecanonlycalculatetheaccumulationsforallthesublistfromitoj,(0<=i<=jacc(i,j)voidaccumulate(inta[],intn,intacc[]){inti=0;acc[i]=a[i];for(i=1;i1){inti,j;for(i=0,j=0;im,generatearandomnumberR=rand(N)in[0,N),replacea[R]withnewnumberifRfallsin[0,m).3.大量的URL字符串，如何从中去除重复的，优化时间空间复杂度ANSWER1.Usehashmapifthereisenoughmemory.2.Ifthereisnoenoughmemory,usehashtoputurlstobins,anddoituntilwecanfitthebinintomemory.39.网易有道笔试：(1).求一个二叉树中任意两个节点间的最大距离，两个节点的距离的定义是这两个节点间边的个数，比如某个孩子节点和父节点间的距离是1，和相邻兄弟节点间的距离是2，优化时间空间复杂度。ANSWERHavedonethis.(2).求一个有向连通图的割点，割点的定义是，如果除去此节点和与其相关的边，有向图不再连通，描述算法。ANSWERDodfs,recordlow[i]asthelowestvertexthatcanbereachedfromiandi’ssuccessornodes.Foreachedgei,iflow[i]=iandiisnotaleafindfstree,theniisacutpoint.Theothercaseistherootofdfs,ifroothastwoormorechildren,itisacutpoint./***gisdefinedas:g[i][]istheoutedges,g[i][0]istheedgecount,g[i][1...g[i][0]]aretheotherendpoints.*/intcnt=0;intvisited[MAX_NUM];intlowest[MAX_NUM];voidgetCutPoints(int*g[],intcuts[],intn){memset(cuts,0,sizeof(int)*n);memset(visited,0,sizeof(int)*n);memset(lowest,0,sizeof(int)*n);for(inti=0;ivisit[g[s][i]]){low=visit[g[s][i]];}}}lowest[s]=low;if(s==root&&out>1){cuts[s]=1;}returnlow;}40.百度研发笔试题引用自：zp1553348771)设计一个栈结构，满足一下条件：min，push，pop操作的时间复杂度为O(1)。ANSWERHavedonethis.2)一串首尾相连的珠子(m个)，有N种颜色(N<=10)，设计一个算法，取出其中一段，要求包含所有N中颜色，并使长度最短。并分析时间复杂度与空间复杂度。ANSWERUseaslidingwindowandacountingarray,plusacounterwhichmonitorsthenumofzeroslotsincountingarray.Whenthereisstillzeroslot(s),advancethewindowhead,untilthereisnozeroslot.Thenshrinkthewindowuntilaslotcomeszero.Thenonecandidatesegmentof(window_size+1)isachieved.Repeatthis.ItisO(n)algorithmsinceeachitemisswallowedandleftbehindonlyonce,andeitheroperationisinconstanttime.intshortestFullcolor(inta[],intn,intm){intc[m],ctr=m;inth=0,t=0;intmin=n; while(1){while(ctr>0&&h=n)returnmin;while(1){c[a[t]]--;if(c[a[t]]==0)break;t++;}if(min>h-t)min=h-t;t++;ctr++;}}3)设计一个系统处理词语搭配问题，比如说中国和人民可以搭配，则中国人民人民中国都有效。要求：*系统每秒的查询数量可能上千次；*词语的数量级为10W；*每个词至多可以与1W个词搭配当用户输入中国人民的时候，要求返回与这个搭配词组相关的信息。ANSWERThisproblemcanbesolvedinthreesteps:1.identifythewords2.recognizethephrase3.retrievetheinformationSolutionof1:ThemosttrivialwaytoefficientlyidentifythewordsishashtableorBST.AbalancedBSTwith100wordsisabout17levelshigh.Consideringthat100kisnotabignumber,hashingisenough.Solutionof2:Sincethephraseinthisproblemconsistsofonly2words,itiseasytosplitthewords.Therewon’tbealotofcandidates.Tofindalegalcombination,weneedthe“matching”information.Soforeachword,weneedsomedatastructuretotellwhetherawordcanco-occurwithit.100kisabadnumber--cannotfitintoa16bitdigit.However,10k*100kisnottoobig,sowecansimplyusearrayofsortedarraytodothis.1Gintegers,or4Gbytesisnotabignumber,WecanalsousesomethinglikeVInttosavealotofspace.Tofindanindexina10ksortedarray,14comparisonsareenough.Aboveoperationcanbedoneinanyreasonablework-station"smemoryveryfast,whichshouldbetheresultofexecutionofaboutafewthousandsofsimplestatements.Solutionof3:Theinformationcouldbetobigtofitinthememory.SoaB-treemaybeadoptedtoindexthecontents.Cachingtechniquesisalsohelpful.Consideringthereareatmost10^9entries,a3or4levelofB-treeisokay,soitwillbeatmost5diskaccess.However,therearethousandsofrequestsandwecanonlydohundredsofdiskseekingpersecond.Itcouldbenecessarytodispatchtheinformationtoseveralworkstations. 41.求固晶机的晶元查找程序晶元盘由数目不详的大小一样的晶元组成，晶元并不一定全布满晶元盘，照相机每次这能匹配一个晶元，如匹配过，则拾取该晶元，若匹配不过，照相机则按测好的晶元间距移到下一个位置。求遍历晶元盘的算法求思路。ANSWERDontunderstand.42.请修改append函数，利用这个函数实现：两个非降序链表的并集，1->2->3和2->3->5并为1->2->3->5另外只能输出结果，不能修改两个链表的数据。ANSWERIdon’tquiteunderstandwhatitmeansby“notmodifyinglinkedlist’sdata”.Ifsomenodeswillbegivenup,itisweirdforthisrequirement.Node*head(Node*h1,Node*h2){if(h1==NULL)returnh2;if(h2==NULL)returnh1;Node*head;if(h1->datadata){head=h1;h1=h1->next;}else{head=h2;h2=h2->next;}Node*p=head;while(h1!=NULL||h2!=NULL){Node*candi;if(h1!=NULL&&h2!=NULL&&h1->datadata||h2==NULL){candi=h1;h1=h1->next;}else{candi=h2;h2=h2->next;}}if(candi->data==p->data)delete(candi);else{p->next=candi;p=candi;}}returnhead;}43.递归和非递归俩种方法实现二叉树的前序遍历。ANSWERvoidpreorderRecursive(TreeNode*node){if(node==NULL)return; visit(node);preorderRecursive(node->left);preorderRecursive(node->right);}Fornon-recursivetraversals,astackmustbeadoptedtoreplacetheimplicitprogramstackinrecursiveprograms.voidpreorderNonrecursive(TreeNode*node){stacks;s.push(node);while(!s.empty()){TreeNode*n=s.pop();visit(n);if(n->right!=NULL)s.push(n->right);if(n->left!=NULL)s.push(n->left);}}voidinorderNonrecursive(TreeNode*node){stacks;TreeNode*current=node;while(!s.empty()||current!=NULL){if(current!=NULL){s.push(current);current=current->left;}else{current=s.pop();visit(current);current=current->right;}}}Postordernonrecursivetraversalisthehardestone.However,asimpleobservationhelpsthatthenodefirsttraversedisthenodelastvisited.Thisrecallsthefeatureofstack.Sowecoulduseastacktostoreallthenodesthenpopthemoutaltogether.Thisisaveryelegantsolution,whiletakesO(n)space.Otherverysmartmethodsalsowork,butthisistheoneIlikethemost.voidpostorderNonrecursive(TreeNode*node){//visitingoccursonlywhencurrenthasnorightchildorlastvisitedishisrightchildstacksTraverse,sVisit;sTraverse.push(node);while(!sTraverse.empty()){ TreeNode*p=sTraverse.pop();sVisit.push(p);if(p->left!=NULL)sTraverse.push(p->left);if(p->right!=NULL)sTraverse.push(p->right);}while(!sVisit.empty()){visit(sVisit.pop);}}44.腾讯面试题：1.设计一个魔方（六面）的程序。ANSWERThisisaproblemtotestOOP.TheobjectMagicCubemusthavefollowingfeatures1)holdscurrentstatus2)easilydoingtransform3)judgewhetherthefinalstatusisachieved4)totest,itcanbeinitialized5)outputcurrentstatuspublicclassMagicCube{//6faces,9chipseachfaceprivatebytechips[54];staticfinalintX=0;staticfinalintY=1;staticfinalintZ=1;voidtransform(intdirection,intlevel){switchdirection:{X:{transformX(level);break;}Y:{transformY(level);break;}Z:{transformZ(level);break;}default:thrownewRuntimeException(“whatdirection?”);}voidtransformX(intlevel){…}}}//reallytiredofmakingthis...}2.有一千万条短信，有重复，以文本文件的形式保存，一行一条，有重复。请用5分钟时间，找出重复出现最多的前10条。ANSWER10Mmsgs,eachatmost140chars,that’s1.4G,whichcanfittomemory. Sousehashmaptoaccumulateoccurrencecounts.Thenuseaheaptopickmaximum10.3.收藏了1万条url，现在给你一条url，如何找出相似的url。（面试官不解释何为相似）ANSWERWhataSBinterviewer...ThecompanynameshouldbeclaimedandifImetsuchainterviewer,IwillcontesttoHR.Thepurposeofinterviewistoseetheabilityofcommunication.Thisiskindofsinglesideshutdownofinformationexchange.Myfirstanswerwillbedoingeditdistancetotheurlandeverycandidate.Thenitdependsonwhatinterviewerwillreact.Otheroptionsincludes:fingerprints,tries...45.雅虎：1.对于一个整数矩阵，存在一种运算，对矩阵中任意元素加一时，需要其相邻（上下左右）某一个元素也加一，现给出一正数矩阵，判断其是否能够由一个全零矩阵经过上述运算得到。ANSWERAassignmentproblem.Twowaystosolve.1:duplicateeachcelltoasmanyasitsvalue,doHungarianalgorithm.DenotethesumofthematrixasM,theedgenumberis2M,sothecomplexityis2*M*M;2:standardmaximumflow.IfthesizeofmatrixisNxN,thenthealgorithmusingFordFulkersonalgorithmisM*N*N.toocomplex...IwilldothiswhenIhavetime...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的最大值为3ANSWERTworestrictionsonm,1)1<=m<=n;2)Sum(array)modm=0NOTE:nohintthata[i]>0,somcouldbelargerthansum/max;Sofirstlypreparethecandidates,thendoabruteforcesearchonpossiblem’s.Inthesearch,aDPisavailable,sinceiff(array,m)=OR_i(f(array-subset(i),m)),whereSum(subset(i))=m.intmaxShares(inta[],intn){intsum=0;inti,m;for(i=0;i=2;m--){if(summodm!=0)continue;intaux[n];for(i=0;idsl){dsl=s;lastdsl=i;}}//nowtraceback.for(inti=lastdsl-1,j=dsl-1;i>=0&&j>=0;i--){if(a[i]==ds[j]){j--;}elseif(a[i]t)return-1;intm=s+(t-s)/2;if(a[m]==k)returnm;elseif(a[s]>=k&&k>a[m])returnhelper(a,k,s,m-1);elsereturnhelper(a,k,m+1,e);}49.一道看上去很吓人的算法面试题：如何对n个数进行排序，要求时间复杂度O(n)，空间复杂度O(1)ANSWER:Soacomparisonsortisnotallowed.Countingsort’sspacecomplexityisO(n).Moreideasmustbeexchangedtofindmoreconditions,elsethisisacrap. 50.网易有道笔试：1.求一个二叉树中任意两个节点间的最大距离，两个节点的距离的定义是这两个节点间边的个数，比如某个孩子节点和父节点间的距离是1，和相邻兄弟节点间的距离是2，优化时间空间复杂度。ANSWER:Havedonethisbefore.2.求一个有向连通图的割点，割点的定义是，如果除去此节点和与其相关的边，有向图不再连通，描述算法。ANSWER:Havedonethisbefore.-------------------------------------------------------------------51.和为n连续正数序列。题目：输入一个正数n，输出所有和为n连续正数序列。例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以输出3个连续序列1-5、4-6和7-8。分析：这是网易的一道面试题。ANSWER:Itseemsthatthiscanbesolvedbyfactorization.However,factorizationoflargenisimpractical!Supposen=i+(i+1)+...+(j-1)+j,thenn=(i+j)(j-i+1)/2=(j*j-i*i+i+j)/2=>j^2+j+(i-i^2-2n)=0=>j=sqrt(i^2-i+1/4+2n)-1/2Weknow1<=i20){error(“areyoucrazy?”);}byted[n];intpos[n],dpos[n];//pos[i],thepositionofi’thnumber,dpos[i]thenumberins[i]isthedpos[i]’thsmallestqsort(s);//IcannotremembertheformofqsortinC...memset(d,-1,sizeof(byte)*n);for(inti=0;idpos[r];i--)d[i]=-d[i]; }}intfindFirstAvailable(chars[],byted[],intpos[],intn){for(inti=n-1;i>1;i--){if(s[pos[i]]>s[pos[i]+d[pos[i]]])returnpos[i];}return-1;}#defineaswap(ARR,X,Y){intt=ARR[X];ARR[X]=ARR[y];ARR[Y]=t;}voidswap(chars[],intpos[],intdpos[],byted[],intr,ints){aswap(s,r,s);aswap(d,r,s);aswap(pos,dpos[r],dpos[s]);aswap(dpos,r,s);}Maybefullofbugs.Pleaserefertoalgorithmmanualforexplansion.Pros:AmotizedO(1)timeforeachmove.Onlytwocharacterschangepositionforeachmove.Cons:asyoucansee,verycomplicated.Extraspaceneeded.54.调整数组顺序使奇数位于偶数前面。题目：输入一个整数数组，调整数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。要求时间复杂度为O(n)。ANSWER:Thisproblemmakesmerecalltheprocessofpartitioninquicksort.voidpartition(inta[],intn){inti=j=0;while(i1+a[(i-1)*l2+j-1])?max:1+a[(i-1)*l2+j-1];}}}returna[l1*l2-1];}57.用俩个栈实现队列。题目：某队列的声明如下：templateclassCQueue{ public:CQueue(){}~CQueue(){}voidappendTail(constT&node);//appendaelementtotailvoiddeleteHead();//removeaelementfromheadprivate:Stackm_stack1;Stackm_stack2;};分析：从上面的类的声明中，我们发现在队列中有两个栈。因此这道题实质上是要求我们用两个栈来实现一个队列。相信大家对栈和队列的基本性质都非常了解了：栈是一种后入先出的数据容器，因此对队列进行的插入和删除操作都是在栈顶上进行；队列是一种先入先出的数据容器，我们总是把新元素插入到队列的尾部，而从队列的头部删除元素。ANSWERTraditionalprobleminCLRS.voidappendTail(constT&node){m_stack1.push(node);}TgetHead(){if(!m_stack2.isEmpty()){returnm_stack2.pop();}if(m_stack1.isEmpty())error(“deletefromemptyqueue”);while(!m_stack1.isEmpty()){m_stack2.push(m_stack1.pop());}returnm_stack2.pop();}58.从尾到头输出链表。题目：输入一个链表的头结点，从尾到头反过来输出每个结点的值。链表结点定义如下：structListNode{intm_nKey;ListNode*m_pNext;};分析：这是一道很有意思的面试题。该题以及它的变体经常出现在各大公司的面试、笔试题中。ANSWERHaveansweredthis...59.不能被继承的类。 题目：用C++设计一个不能被继承的类。分析：这是Adobe公司2007年校园招聘的最新笔试题。这道题除了考察应聘者的C++基本功底外，还能考察反应能力，是一道很好的题目。ANSWER:Idon’tknowc++.Maybeitcanbedonebyimplementanemptyprivatedefaultconstructor.60.在O（1）时间内删除链表结点。题目：给定链表的头指针和一个结点指针，在O(1)时间删除该结点。链表结点的定义如下：structListNode{intm_nKey;ListNode*m_pNext;};函数的声明如下：voidDeleteNode(ListNode*pListHead,ListNode*pToBeDeleted);分析：这是一道广为流传的Google面试题，能有效考察我们的编程基本功，还能考察我们的反应速度，更重要的是，还能考察我们对时间复杂度的理解。ANSWER:Copythedatafromtobedeleted’snexttotobedeleted.thendeletetobedeleted.Thespecialcaseistobedeleteisthetail,thenwemustiteratetofinditspredecessor.TheamortizedtimecomplexityisO(1).-------------------------------------------------------------------------61.找出数组中两个只出现一次的数字题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。分析：这是一道很新颖的关于位运算的面试题。ANSWER:XOR.62.找出链表的第一个公共结点。题目：两个单向链表，找出它们的第一个公共结点。链表的结点定义为：structListNode{intm_nKey;ListNode*m_pNext;};分析：这是一道微软的面试题。微软非常喜欢与链表相关的题目，因此在微软的面试题中，链表出现的概率相当高。ANSWER:Havedonethis. 63.在字符串中删除特定的字符。题目：输入两个字符串，从第一字符串中删除第二个字符串中所有的字符。例如，输入”Theyarestudents.”和”aeiou”，则删除之后的第一个字符串变成”Thyrstdnts.”。分析：这是一道微软面试题。在微软的常见面试题中，与字符串相关的题目占了很大的一部分，因为写程序操作字符串能很好的反映我们的编程基本功。ANSWER:Havedonethis?Useabytearray/characterhashtorecordsecondstring.thenusetwopointerstoshrinkthe1ststring.64.寻找丑数。题目：我们把只包含因子2、3和5的数称作丑数（UglyNumber）。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第1500个丑数。分析：这是一道在网络上广为流传的面试题，据说google曾经采用过这道题。ANSWER:TRADITIONAL.Useheap/priorityqueue.intno1500(){intheap[4500];heap[0]=2;heap[1]=3;heap[2]=5;intsize=3;for(inti=1;i<1500;i++){ints=heap[0];heap[0]=s*2;siftDown(heap,0,size);heap[size]=s*3;siftUp(heap,size,size+1);heap[size+1]=s*5;siftUp(heap,size+1,size+2);size+=2;}}voidsiftDown(intheap[],intfrom,intsize){intc=from*2+1;while(c0){intp=(from-1)/2;if(heap[p]>heap[from])swap(heap,p,from);from=p; }}65.输出1到最大的N位数题目：输入数字n，按顺序输出从1最大的n位10进制数。比如输入3，则输出1、2、3一直到最大的3位数即999。分析：这是一道很有意思的题目。看起来很简单，其实里面却有不少的玄机。ANSWER:Somaybencouldexceedi32?Icannottellwhereisthetrick...Whowilloutput2*10^9numbers...66.颠倒栈。题目：用递归颠倒一个栈。例如输入栈{1,2,3,4,5}，1在栈顶。颠倒之后的栈为{5,4,3,2,1}，5处在栈顶。ANSWER:Interesting...voidreverse(Stackstack){if(stack.size()==1)return;Objecto=stack.pop();reverse(stack);putToBottom(stack,o);}voidputToBottom(Stackstack,Objecto){if(stack.isEmpty()){stack.push(o);return;}Objecto2=stack.pop();putToBottom(stack,o);stack.push(o2);}67.俩个闲玩娱乐。1.扑克牌的顺子从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2-10为数字本身，A为1，J为11，Q为12，K为13，而大小王可以看成任意数字。ANSWER://makeking=0booleanisStraight(inta[]){Arrays.sort(a);if(a[0]>0)returncheckGaps(a,0,4,0);if(a[0]==0&&a[1]!=0)returncheckGaps(a,1,4,1); returncheckGaps(a,2,4,2);}booleancheckGaps(int[]a,ints,inte,intallowGaps){inti=s;while(i6,f(m,n)=0wherem(){intcompareTo(Integeri1,Integeri2){return(“”+i1+i2).compare(“”+i2+i1);}});StringBuffersb=newStringBuffer();for(inti=0;ia[m])returnhelper(a,s,m);elsereturnhelper(a,m+1,t);}70.给出一个函数来输出一个字符串的所有排列。ANSWER简单的回溯就可以实现了。当然排列的产生也有很多种算法，去看看组合数学，还有逆序生成排列和一些不需要递归生成排列的方法。印象中Knuth的第一卷里面深入讲了排列的生成。这些算法的理解需要一定的数学功底，也需要一定的灵感，有兴趣最好看看。ANSWER:Havedonethis.71.数值的整数次方。题目：实现函数doublePower(doublebase,intexponent)，求base的exponent次方。不需要考虑溢出。分析：这是一道看起来很简单的问题。可能有不少的人在看到题目后30秒写出如下的代码：doublePower(doublebase,intexponent){doubleresult=1.0;for(inti=1;i<=exponent;++i)result*=base;returnresult;}ANSWER…doublepower(doublebase,intexp){if(exp==1)returnbase;doublehalf=power(base,exp>>1);return(((exp&1)==1)?base:1.0)*half*half;}72.题目：设计一个类，我们只能生成该类的一个实例。分析：只能生成一个实例的类是实现了Singleton模式的类型。ANSWERI’mnotgoodatmultithreadprogramming...Butifwesetalazyinitialization,the“if”conditioncouldbeinterruptedthusmultipleconstructorcouldbecalled,sowemustaddsynchronizedtotheifjudgements,whichisalossofefficiency.Puttingittothestaticinitializationwillguaranteethattheconstructoronlybeexecutedoncebythejavaclassloader.publicclassSingleton{privatestaticSingletoninstance=newSingleton();privatesynchronizedSingleton(){} publicSingletongetInstance(){returninstance();}}Thismaynotbecorrect.I’mquitebadatthis...73.对策字符串的最大长度。题目：输入一个字符串，输出该字符串中对称的子字符串的最大长度。比如输入字符串“google”，由于该字符串里最长的对称子字符串是“goog”，因此输出4。分析：可能很多人都写过判断一个字符串是不是对称的函数，这个题目可以看成是该函数的加强版。ANSWERBuildasuffixtreeofxandinverse(x),thelongestanagramisnaturallyfound.SuffixtreecanbebuiltinO(n)timesothisisalineartimesolution.74.数组中超过出现次数超过一半的数字题目：数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。分析：这是一道广为流传的面试题，包括百度、微软和Google在内的多家公司都曾经采用过这个题目。要几十分钟的时间里很好地解答这道题，除了较好的编程能力之外，还需要较快的反应和较强的逻辑思维能力。ANSWERDeleteeverytwodifferentdigits.Thelastonethatleftistheone.intgetMajor(inta[],intn){intx,cnt=0;for(inti=0;im_pLeft,X,Y);TreeNode*right=getLCA(root->m_pRight,X,Y);if(left==NULL)returnright;elseif(right==NULL)returnleft;elsereturnroot;}76.复杂链表的复制题目：有一个复杂链表，其结点除了有一个m_pNext指针指向下一个结点外，还有一个m_pSibling指向链表中的任一结点或者NULL。其结点的C++定义如下：structComplexNode{intm_nValue;ComplexNode*m_pNext;ComplexNode*m_pSibling;};下图是一个含有5个结点的该类型复杂链表。图中实线箭头表示m_pNext指针，虚线箭头表示m_pSibling指针。为简单起见，指向NULL的指针没有画出。请完成函数ComplexNode*Clone(ComplexNode*pHead)，以复制一个复杂链表。分析：在常见的数据结构上稍加变化，这是一种很新颖的面试题。要在不到一个小时的时间里解决这种类型的题目，我们需要较快的反应能力，对数据结构透彻的理解以及扎实的编程功底。ANSWERHaveheardthisbefore,neverseriouslythoughtit.Thetrickislikethis:takeuseoftheoldpSibling,makeitpointstothenewcreatedclonednode,whilemakethenewclonednode’spNextbackuptheoldpSibling.ComplexNode*Clone(ComplexNode*pHead){if(pHead==NULL)returnNULL;preClone(pHead);inClone(pHead);returnpostClone(pHead);}voidpreClone(ComplexNode*pHead){ComplexNode*p=newComplexNode(); p->m_pNext=pHead->m_pSibling;pHead->m_pSibling=p;if(pHead->m_pNext!=NULL)preClone(pHead->m_pNext);}voidinClone(ComplexNode*pHead){ComplexNode*pSib=pNew->m_pNext;if(pSib==NULL){pNew->m_pSibling=NULL;}else{pNew->m_pSibling=pSib->m_pSibling;}if(pHead->m_pNext!=NULL)inClone(pHead->m_pNext);}ComplexNode*postClone(ComplexNode*pHead){ComplexNode*pNew=pHead->m_pSibling;ComplexNode*pSib=pNew->m_pNext;if(pHead->m_pNext!=NULL){pNew->m_pNext=pHead->m_pNext->m_pSibling;pHead->m_pSibling=pSib;postClone(pHead->m_pNext);}else{pNew->pNext=NULL;pHead->m_pSibling=NULL;}returnpNew;}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.链表和数组的区别在哪里？分析：主要在基本概念上的理解。但是最好能考虑的全面一点，现在公司招人的竞争可能就在细节上产生，谁比较仔细，谁获胜的机会就大。ANSWER1.Besidesthecommonstaff,linkedlistismoreabstractandarrayisusuallyabasicrealworldobject.Whenmentioning“linkedlist”,itdoesn’tmatterhowitisimplemented,thatis,aslongasitsupports“getdata”and“getnext”,itisalinkedlist.Butalmostallprogramminglanguagesprovidesarrayasabasicdatastructure.2.Soarrayismorebasic.Youcanimplementalinkedlistinanarray,butcannotintheotherdirection.79.1.编写实现链表排序的一种算法。说明为什么你会选择用这样的方法？ANSWERForlinkedlistsorting,usuallymergesortisthebestchoice.Pros:O(1)auxilaryspace,comparedtoarraymergesort.Nonodecreation,justpointeroperations.Node*linkedListMergeSort(Node*pHead){intlen=getLen(pHead);returnmergeSort(pHead,len);}Node*mergeSort(Node*p,intlen){if(len==1){p->next=NULL;returnp;}Node*pmid=p;for(inti=0;inext;}Node*p1=mergeSort(p,len/2);Node*p2=mergeSort(pmid,len-len/2);returnmerge(p1,p2);}Node*merge(Node*p1,Node*p2){Node*p=NULL,*ph=NULL;while(p1!=NULL&&p2!=NULL){if(p1->datadata){if(ph==NULL){ph=p=p1;}else{p->next=p1;p1=p1->next;p=p->next;}}else{if(ph==NULL){ph=p=p2;}else{p->next=p2;p2=p2->next;p=p->next;}}}p->next=(p1==NULL)?p2:p1; returnph;}2.编写实现数组排序的一种算法。说明为什么你会选择用这样的方法？ANSWERActually,itdependsonthedata.Ifarbitrarydataisgiveninthearray,Iwouldchoosequicksort.Itisasytoimplement,fast.3.请编写能直接实现strstr()函数功能的代码。ANSWERSubstringtest?Havedonethis.80.阿里巴巴一道笔试题问题描述:12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?这个笔试题,很YD,因为把某个递归关系隐藏得很深。ANSWERMustbe1ab……cde……ccouldbe2thto7th(hastobesmallerthand,e...those5numbers),sof(12)=6f(10)=6*5f(8)=30*4f(6)=120*3f(4)=360*2f(2)=72081.第1组百度面试题1.一个int数组，里面数据无任何限制，要求求出所有这样的数a[i]，其左边的数都小于等于它，右边的数都大于等于它。能否只用一个额外数组和少量其它空间实现。ANSWERSortthearraytoanotherarray,compareitwiththeoriginalarray,alla[i]=b[i]areanswers.2.一个文件，内含一千万行字符串，每个字符串在1K以内，要求找出所有相反的串对，如abc和cba。ANSWERSowehave~10Gdata.Itisunlikelytoputthemallintomainmemory.Anyway,calculatethehashofeachlineinthefirstround,atthesecondroundcalculatethehashofthereverseofthelineandremembersonlythelinenumberpairsthatthehashesofthetwodirectionscollides.Thelastroundonlytestthoselines.3.STL的set用什么实现的？为什么不用hash？ANSWERIdon’tquiteknow.Onlyheardofthatmapinstlisimplementedwithred-blacktree.Onegoodthingoverhashisthatyoudon’tneedtore-hashwhendatasizegrows.82.第2组百度面试题1.给出两个集合A和B，其中集合A={name}，集合B={age、sex、scholarship、address、...}， 要求：问题1、根据集合A中的name查询出集合B中对应的属性信息；问题2、根据集合B中的属性信息（单个属性，如age<20等），查询出集合A中对应的name。ANSWERSQL?Notagooddefinedquestion.2.给出一个文件，里面包含两个字段{url、size}，即url为网址，size为对应网址访问的次数要求：问题1、利用LinuxShell命令或自己设计算法，查询出url字符串中包含“baidu”子字符串对应的size字段值；问题2、根据问题1的查询结果，对其按照size由大到小的排列。（说明：url数据量很大，100亿级以上）ANSWER1.shell:gawk‘/baidu/{print$2}’FILE2.shell:gawk‘/baidu/{print$2}’FILE|sort-n-r83.第3组百度面试题1.今年百度的一道题目百度笔试：给定一个存放整数的数组，重新排列数组使得数组左边为奇数，右边为偶数。要求：空间复杂度O(1)，时间复杂度为O（n）。ANSWERHavedonethis.2.百度笔试题用C语言实现函数void*memmove(void*dest,constvoid*src,size_tn)。memmove函数的功能是拷贝src所指的内存内容前n个字节到dest所指的地址上。分析：由于可以把任何类型的指针赋给void类型的指针,这个函数主要是实现各种数据类型的拷贝。ANSWER//Tomymemory,usuallymemcpydoesn’tcheckoverlap,memmovedovoid*memmove(void*dest,constvoid*src,size_tn){if(dest==NULL||src==NULL)error(“NULLpointers”);byte*psrc=(byte*)src;byte*pdest=(byte*)dest;intstep=1;if(dest=nandC(M-1,2)end)returnNULL;intm=start+(end-start)/2;Node*root=newNode(array[m]);root->left=helper(array,start,m-1);root->right=helper(array,m+1,end);returnroot;}87.1.大整数数相乘的问题。（这是2002年在一考研班上遇到的算法题）ANSWERDooverflowmanually.finalstaticlongmask=(1<<31)-1;ArrayListmultiply(ArrayLista,ArrayListb){ArrayListresult=newArrayList(a.size()*b.size()+1);for(inti=0;ix,inta,intbase,ArrayListresult){if(a==0)return;longoverflow=0;inti;for(i=0;i>31);}while(overflow!=0){ longtmp=result.get(base+i)+overflow;result.set(base+i,(int)(mask&tmp));overflow=(tmp>>31);}}2.求最大连续递增数字串（如“ads3sl456789DF3456ld345AA”中的“456789”）ANSWERHavedonethis.3.实现strstr功能，即在父串中寻找子串首次出现的位置。（笔试中常让面试者实现标准库中的一些函数）ANSWERHavedonethis.88.2005年11月金山笔试题。编码完成下面的处理函数。函数将字符串中的字符"*"移到串的前部分，前面的非"*"字符后移，但不能改变非"*"字符的先后顺序，函数返回串中字符"*"的数量。如原始串为：ab**cd**e*12，处理后为*****abcde12，函数并返回值为5。（要求使用尽量少的时间和辅助空间）ANSWERIt’slikepartitioninquicksort.Justkeepthenon-*partstable.intpartitionStar(chara[]){intcount=0;inti=a.length-1,j=a.length-1;//iforthecursor,jforthefirstnon-*charwhile(i>=0){if(a[i]!=‘*’){swap(a,i--,j--);}else{i--;count++;}}returncount;}89.神州数码、华为、东软笔试题1.2005年11月15日华为软件研发笔试题。实现一单链表的逆转。ANSWERHavedonethis.2.编码实现字符串转整型的函数（实现函数atoi的功能），据说是神州数码笔试题。如将字符串”+123”123,”-0123”-123,“123CS45”123,“123.45CS”123,“CS123.45”0ANSWER intatoi(constchar*a){if(*a==’+’)returnatoi(a+1);elseif(*a==’-’)return-atoi(a+1);char*p=a;intc=0;while(*p>=‘0’&&*p<=‘9’){c=c*10+(*p-‘0’);}returnc;}3.快速排序（东软喜欢考类似的算法填空题，又如堆排序的算法等）ANSWERStandardsolution.Skip.4.删除字符串中的数字并压缩字符串。如字符串”abc123de4fg56”处理后变为”abcdefg”。注意空间和效率。（下面的算法只需要一次遍历，不需要开辟新空间，时间复杂度为O(N)）ANSWERAlsopartition,keepnon-digitstable.char*partition(constchar*str){char*i=str;//iforcursor,jforthefirstdigitchar;char*j=str;while(*i!=‘’){if(*i>‘9’||*i<‘0’){*j++=*i++;}else{*i++;}}*j=‘’;returnstr;}5.求两个串中的第一个最长子串（神州数码以前试题）。如"abractyeyt","dgdsaeactyey"的最大子串为"actyet"。ANSWERUsesuffixtree.Thelongestcommonsubstringisthelongestprefixofthesuffixes.O(n)tobuildsuffixtree.O(n)tofindthelcs.90.1.不开辟用于交换数据的临时空间，如何完成字符串的逆序(在技术一轮面试中，有些面试官会这样问)。ANSWERTwocursors. 2.删除串中指定的字符（做此题时，千万不要开辟新空间，否则面试官可能认为你不适合做嵌入式开发）ANSWERHavedonethis.3.判断单链表中是否存在环。ANSWERHavedonethis.911.一道著名的毒酒问题有1000桶酒，其中1桶有毒。而一旦吃了，毒性会在1周后发作。现在我们用小老鼠做实验，要在1周内找出那桶毒酒，问最少需要多少老鼠。ANSWERHavedonethis.10mices.2.有趣的石头问题有一堆1万个石头和1万个木头，对于每个石头都有1个木头和它重量一样，把配对的石头和木头找出来。ANSWERQuicksort.92.1.多人排成一个队列,我们认为从低到高是正确的序列,但是总有部分人不遵守秩序。如果说,前面的人比后面的人高(两人身高一样认为是合适的),那么我们就认为这两个人是一对“捣乱分子”,比如说,现在存在一个序列:176,178,180,170,171这些捣乱分子对为<176,170>,<176,171>,<178,170>,<178,171>,<180,170>,<180,171>,那么,现在给出一个整型序列,请找出这些捣乱分子对的个数(仅给出捣乱分子对的数目即可,不用具体的对)要求：输入:为一个文件(in)，文件的每一行为一个序列。序列全为数字，数字间用”,”分隔。输出：为一个文件(out)，每行为一个数字，表示捣乱分子的对数。详细说明自己的解题思路，说明自己实现的一些关键点。并给出实现的代码，并分析时间复杂度。限制：输入每行的最大数字个数为100000个，数字最长为6位。程序无内存使用限制。ANSWERTheansweristheswapnumberofinsertionsort.Thestraightforwardmethodistodoinsertionsortandaccumulatetheswapnumbers,whichisslow:O(n^2)Asub-quadraticsolutioncanbedonebyDP. f(n)=f(n-1)+Index(n)Index(n),whichistodeterminehowmanynumbersissmallerthana[n]ina[0..n-1],canbedoneinlog(n)timeusingBSTwithsubtreesize.93.在一个int数组里查找这样的数，它大于等于左侧所有数，小于等于右侧所有数。直观想法是用两个数组a、b。a[i]、b[i]分别保存从前到i的最大的数和从后到i的最小的数，一个解答：这需要两次遍历，然后再遍历一次原数组，将所有data[i]>=a[i-1]&&data[i]<=b[i]的data[i]找出即可。给出这个解答后，面试官有要求只能用一个辅助数组，且要求少遍历一次。ANSWERItisnaturaltoimprovethehint...justduringthesecondtraversal,dotherangeminimumandpickingtogether.Thereisnoneedtostoretherangeminimums.94.微软笔试题求随机数构成的数组中找到长度大于=3的最长的等差数列,输出等差数列由小到大:如果没有符合条件的就输出格式：输入[1,3,0,5,-1,6]输出[-1,1,3,5]要求时间复杂度，空间复杂度尽量小ANSWERFirstlysortthearray.ThendoDP:foreacha[i],updatethelengthofthearithmeticsequences.That’saO(n^3)solution.Eacharithmeticsequencecanbedeterminedbythelastitemandthestepsize.95.华为面试题1判断一字符串是不是对称的，如：abccbaANSWERTwocursors.2.用递归的方法判断整数组a[N]是不是升序排列ANSWERbooleanisAscending(inta[]){returnisAscending(a,0);}booleanisAscending(inta[],intstart){returnstart==a.length-1||isAscending(a,start+1);}96.08年中兴校园招聘笔试题1．编写strcpy函数已知strcpy函数的原型是char*strcpy(char*strDest,constchar*strSrc);其中strDest是目的字符串，strSrc是源字符串。不调用C++/C的字符串库函数，请编写函数strcpy ANSWERchar*strcpy(char*strDest,constchar*strSrc){if(strSrc==NULL)returnNULL;char*i=strSrc,*j=strDest;while(*i!=‘’){*j++=*i++;}*j=‘’;returnstrDest;}Maybeyouneedtocheckifsrcanddestoverlaps,thendecidewhethertocopyfromtailtohead.最后压轴之戏，终结此微软等100题系列V0.1版。那就，连续来几组微软公司的面试题，让你一次爽个够：======================97.第1组微软较简单的算法面试题1.编写反转字符串的程序，要求优化速度、优化空间。ANSWERHavedonethis.2.在链表里如何发现循环链接？ANSWERHavedonethis.3.编写反转字符串的程序，要求优化速度、优化空间。ANSWERHavedonethis.4.给出洗牌的一个算法，并将洗好的牌存储在一个整形数组里。ANSWERHavedonethis.5.写一个函数，检查字符是否是整数，如果是，返回其整数值。（或者：怎样只用4行代码编写出一个从字符串到长整形的函数？）ANSWERCharorstring?havedoneatoi;98.第2组微软面试题1.给出一个函数来输出一个字符串的所有排列。ANSWERHavedonethis... 2.请编写实现malloc()内存分配函数功能一样的代码。ANSWERWaytoohardasaninterviewquestion...Pleasecheckwikipediaforsolutions...3.给出一个函数来复制两个字符串A和B。字符串A的后几个字节和字符串B的前几个字节重叠。ANSWERCopyfromtailtohead.4.怎样编写一个程序，把一个有序整数数组放到二叉树中？ANSWERHavedonethis.5.怎样从顶部开始逐层打印二叉树结点数据？请编程。ANSWERHavedonethis...6.怎样把一个链表掉个顺序（也就是反序，注意链表的边界条件并考虑空链表）？ANSWERHavedonethis...99.第3组微软面试题1.烧一根不均匀的绳，从头烧到尾总共需要1个小时。现在有若干条材质相同的绳子，问如何用烧绳的方法来计时一个小时十五分钟呢？ANSWERMayhavedonethis...burnfrombothsidegives½hour.2.你有一桶果冻，其中有黄色、绿色、红色三种，闭上眼睛抓取同种颜色的两个。抓取多少个就可以确定你肯定有两个同一颜色的果冻？（5秒-1分钟）ANSWER4.3.如果你有无穷多的水，一个3公升的提捅，一个5公升的提捅，两只提捅形状上下都不均匀，问你如何才能准确称出4公升的水？（40秒-3分钟）ANSWER5to3=>22to3,remaining15toremaining1=>4一个岔路口分别通向诚实国和说谎国。来了两个人，已知一个是诚实国的，另一个是说谎国的。诚实国永远说实话，说谎国永远说谎话。现在你要去说谎国，但不知道应该走哪条路，需要问这两个人。请问应该怎么问？（20秒-2分钟）ANSWER Seemstherearetoomanyanswers.Iwillpickanyonetoask:howtogettoyourcountry?Thenpicktheotherway.100.第4组微软面试题，挑战思维极限1.12个球一个天平，现知道只有一个和其它的重量不同，问怎样称才能用三次就找到那个球。13个呢？（注意此题并未说明那个球的重量是轻是重，所以需要仔细考虑）（5分钟-1小时）ANSWERToocomplicated.Gofindbrainteaseranswersbyyourself.2.在9个点上画10条直线，要求每条直线上至少有三个点？（3分钟-20分钟）3.在一天的24小时之中，时钟的时针、分针和秒针完全重合在一起的时候有几次？都分别是什么时间？你怎样算出来的？（5分钟-15分钟）30终结附加题：微软面试题，挑战你的智商==========说明：如果你是第一次看到这种题，并且以前从来没有见过类似的题型，并且能够在半个小时之内做出答案，说明你的智力超常..）1.第一题.五个海盗抢到了100颗宝石，每一颗都一样大小和价值连城。他们决定这么分：抽签决定自己的号码（1、2、3、4、5）首先，由1号提出分配方案，然后大家表决，当且仅当超过半数的人同意时，按照他的方案进行分配，否则将被扔进大海喂鲨鱼如果1号死后，再由2号提出分配方案，然后剩下的4人进行表决，当且仅当超过半数的人同意时，按照他的方案进行分配，否则将被扔入大海喂鲨鱼。依此类推条件：每个海盗都是很聪明的人，都能很理智地做出判断，从而做出选择。问题：第一个海盗提出怎样的分配方案才能使自己的收益最大化？Answer:Atraditionalbrainteaser.Consider#5,whatever#4proposes,hewon’tagree,so#4mustagreewhatever#3proposes.Soifthereareonly#3-5,#3shouldpropose(100,0,0).Sotheexpectedincomeof#3is100,and#4and#5is0for3guyproblem.Sowhatever#2proposes,#3won’tagree,butif#2give#4and#5$1,theycangetmorethan3-guysubproblem.So#2willpropose(98,0,1,1).Sofor#1,ifgive#2lessthan$98,#2won’tagree.Buthecangive#3$1and#4or#5$2,sothisisa(97,0,1,2,0)solution.2.一道关于飞机加油的问题，已知：每个飞机只有一个油箱，飞机之间可以相互加油（注意是相互，没有加油机）一箱油可供一架飞机绕地球飞半圈，问题： 为使至少一架飞机绕地球一圈回到起飞时的飞机场，至少需要出动几架飞机？（所有飞机从同一机场起飞，而且必须安全返回机场，不允许中途降落，中间没有飞机场）-------------------------------------------------------------------------------------------------------------------------------更多面试题，请参见：微软、谷歌、百度等公司经典面试100题[第1-60题]（微软100题第二版前60题）微软、Google等公司非常好的面试题及解答[第61-70题]（微软100题第二版第61-70题）十道海量数据处理面试题与十个方法大总结（十道海量数据处理面试题）海量数据处理面试题集锦与Bit-map详解（十七道海量数据处理面试题）九月腾讯，创新工场，淘宝等公司最新面试十三题（2011年度9月最新面试30题）十月百度，阿里巴巴，迅雷搜狗最新面试十一题（2011年度十月最新面试题集锦）一切的详情，可看此文：横空出世，席卷Csdn--评微软等数据结构+算法面试100题（在此文中，你能找到与微软100题所有一切相关的东西）所有的资源下载（题目+答案）地址：http://v_july_v.download.csdn.net/本微软等100题系列V0.1版，永久维护地址：http://topic.csdn.net/u/20101126/10/b4f12a00-6280-492f-b785-cb6835a63dc9.html作者声明:“本人July对以上所有任何内容和资料享有版权，转载请注明作者本人July及出处。向你的厚道致敬。谢谢。二零一一年十月十三日、以诸君为傲。欢迎，任何人，就以上任何内容，题目与答案思路，或其它任何问题、与我联系：本人邮箱：zhoulei0907@yahoo.cn”'