微软面试一百道题目精选

第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]a[i]&&i=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&(1i))&&X+=(Yi)intfoo(intn){intr=n;T(r,n,0);T(r,n,1);T(r,n,2);…T(r,n,31);returnr1;}第13题：题目：输入一个单向链表，输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。链表结点定义如下：structListNode{intm_nKey;ListNode*m_pNext;};Answer:Twoways.1:recordthelengthofthelinkedlist,thengon-ksteps.2:usetwocursors.Timecomplexitiesareexactlythesame.Node*lastK(Node*head,intk){if(k0)error(“k0”);Node*p=head,*pk=head;for(;k0;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&&fe){if(sumdest)sum=*(++f);elsesum=*(--e);}if(sum==dest)printf(“%d,%d\n”,*f,*e);}第15题：题目：输入一颗二元查找树，将该树转换为它的镜像，即在转换后的二元查找树中，左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。例如输入：8/\610/\/\57911输出：8/\106/\/\11975定义二元查找树的结点为：structBSTreeNode//anodeinthebinarysearchtree(BST){intm_nValue;//valueofnodeBSTreeNode*m_pLeft;//leftchildofnodeBSTreeNode*m_pRight;//rightchildofnode};ANSWER:Thisisthebasicapplicationofrecursion.PS:Idon’tlikethem_xxnamingconvension.voidswap(Node**l,Node**r){Node*p=*l;*l=*r;*r=p;}voidmirror(Node*root){if(root==NULL)return;swap(&(root-left),&(root-right));mirror(root-left);mirror(root-right);}voidmirrorIteratively(Node*root){if(root==NULL)return;stackNode*buf;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题：题目（微软）：输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。例如输入8/\610/\/\57911输出861057911。ANSWER:Thenodesinthelevelsareprintedinthesimilarmannertheirparentswereprinted.SoitshouldbeanFIFOqueuetoholdthelevel.Ireallydon’trememberthefunctionnameofthestlqueue,soIwillwriteitinJava...voidprintByLevel(Noderoot){Nodesentinel=newNode();LinkedListNodeq=newLinkedListNode();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!=’\0’){a[*p]++;p++;}p=str;while(*p!=’\0’){if(a[*p]==1)return*p;}return‘\0’;//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,so