微软面试一百道题目精选6082.docx

《微软面试一百道题目精选6082.docx》由会员分享，可在线阅读，更多相关《微软面试一百道题目精选6082.docx（75页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第9 题题判断整整数序列列是不是是二元查查找树的的后序遍遍历结果果题目：输入一一个整数数数组，判判断该数数组是不不是某二二元查找找树的后后序遍历历的结果果。如果果是返回回truue，否否则返回回fallse。例如输输入5、7、6、9、11、10、8，由于于这一整整数序列列是如下下树的后后序遍历历结果：8/ 6 110/ / 55 7 9 111因此此返回ttruee。如果输输入7、4、6、5，没有有哪棵树树的后序序遍历的的结果是是这个序序列，因因此返回回fallse。ANSSWERR:Thiis iis aan iinteeresstinng oone. Thheree iss a traad

2、ittionnal queestiion thaat rrequuirees tthe binnaryy trree to be re-connstrructted froom mmid/posst/ppre ordder ressultts. Thiis sseemms ssimiilarr. FFor thee prrobllemss reelatted to (biinarry) treees, reecurrsioon iis tthe firrst chooicee.In thiis pprobblemm, wwe kknoww inn poost-ordder ressultts,

3、 thee laast nummberr shhoulld bbe tthe rooot. So we havve kknowwn tthe rooot oof tthe BSTT iss 8 in thee exxampple. Soo wee caan sspliit tthe arrray by thee rooot.intt issPosstorrderrRessultt(innt aa, innt nn) rretuurn hellperr(a, 0, n-1);intt heelpeer(iint a, iint s, intt e) iff (ee=ss) rretuurn 1;

4、 innt ii=e-1; whhilee (aaeai & i=s) i-; if (!hhelpper(a, i+11, ee-1) rretuurn 0; innt kk = l; whhilee (aae=s) i-; retturnn heelpeer(aa, ss, ll);第10 题翻转句句子中单单词的顺顺序。题题目：输输入一个个英文句句子，翻翻转句子子中单词词的顺序序，但单单词内字字符的顺顺序不变变。句子子中单词词以空格格符隔开开。为简简单起见见，标点点符号和和普通字字母一样样处理。例如输入“I am a student.”，则输出“student. a am I”。Answe

5、r:Already done this. Skipped.第11 题求二叉叉树中节节点的最最大距离离.如果我我们把二二叉树看看成一个个图，父父子节点点之间的的连线看看成是双双向的，我们姑且定义距离为两节点之间边的个数。写一个程序，求一棵二叉树中相距最远的两个节点之间的距离。ANSWER:This is interesting. Also recursively, the longest distance between two nodes must be either from root to one leaf, or between two leafs. For the former cas

6、e, its the tree height. For the latter case, it should be the sum of the heights of left and right subtrees of the two leaves most least ancestor.The first case is also the sum the heights of subtrees, just the height + 0.int maxxDisstannce(Nodde * rooot) innt ddeptth; reeturrn hhelpper(rooot, deppt

7、h);intt heelpeer(NNodee * rooot, intt &ddeptth) if (rooot = NULLL) ddeptth = 0; reeturrn 00; intt ldd, rrd; innt mmaxlleftt = hellperr(rooot-leeft, ldd); innt mmaxrrighht = heelpeer(rroott-rrighht, rd); deppth = mmax(ld, rdd)+11; retturnn maax(mmaxlleftt, mmax(maxxrigght, ldd+rdd);第12 题题目：求1+2+n，要求不

8、不能使用用乘除法法、foor、whiile、if、elsse、swiitchh、casse 等等关键字字以及条条件判断断语句（A?BB:C）。ANNSWEER:1+.+nn=n*(n+1)/2=(n22+n)/2iit iis eeasyy too geet xx/2, soo thhe pprobblemm iss too geet nn2tthouugh no if/elsse iis aalloowedd, wwe ccan eassillly ggo aarouund usiing shoort-passs.uusinng mmacrro tto mmakee itt faanciie

9、r:#deffinee TT(X, Y, i) (YY & (1i) & XX+=(Y 11;第13 题：题目目：输入入一个单单向链表表，输出出该链表表中倒数数第k 个结点。链链表的倒倒数第00 个结点为为链表的的尾指针针。链表表结点定定义如下下：sttrucct LListtNoddeintt m_nKeey;LListtNodde* m_ppNexxt;Annsweer:Twoo waays. 1: reecorrd tthe lenngthh off thhe llinkked lisst, theen ggo nn-k steeps. 2: usse ttwo currsorrs.TT

10、imee coompllexiitiees aare exaactlly tthe samme.Nodde * laastKK(Noode * hheadd, iint k) if (k0) errror(“k 00;k-) iif (pk-neext!=NUULL) pkk = pk-neext; ellse retturnn NUULL; wwhille (pk-neext!=NUULL) p=pp-nnextt, ppk=ppk-nexxt; reeturrn pp;第14 题：题目目：输入入一个已已经按升升序排序序过的数数组和一一个数字字，在数数组中查查找两个个数，使使得它们们的和正正

11、好是输输入的那那个数字字。要求求时间复复杂度是是O(nn)。如如果有多多对数字字的和等等于输入入的数字字，输出出任意一一对即可可。例如如输入数数组1、2、4、7、11、15 和数字字15。由由于4+11=15，因因此输出出4 和11。ANSSWERR:Usee twwo ccurssorss. OOne at froont andd thhe ootheer aat tthe endd. KKeepp trrackk off thhe ssum by movvingg thhe ccurssorss.vooid finnd2NNumbber(intt a, intt n, innt ddest

12、t) iint *f = aa, *e=aa+n-1; innt ssum = *f + *ee; whiile (suum != ddestt & f ee) iff (ssum leeft), &(rooot-riightt); mmirrror(rooot-lefft); mmirrror(rooot-rigght);voidd miirroorItteraativvelyy(Noode * rroott) iif (rooot = NNULLL) rretuurn; sstacck buff; buff.puush(rooot); wwhille (!sttackk.emmptyy()

13、 Nodde * n = sstacck.ppop(); swaap(&(rooot-leeft), &(rooot-riightt); iff (rroott-lleftt != NUULL) buuf.ppushh(rooot-leeft); iif (rooot-rigght != NULLL) buff.puush(rooot-rigght); 第16 题：题目目（微软软）：输输入一颗颗二元树树，从上上往下按按层打印印树的每每个结点点，同一一层中按按照从左左往右的的顺序打打印。例例如输入入8/ 6 110/ / 55 7 9 111输出出8 66 100 5 7 99 111。ANSS

14、WERR:Thee noodess inn thhe lleveels aree prrintted in thee siimillar mannnerr thheirr paarennts werre pprinntedd. SSo iit sshouuld be an FIFFO qqueuue tto hholdd thhe lleveel. I rreallly donnt remmembber thee fuuncttionn naame of thee sttl qqueuue, so I wwilll wrritee itt inn Jaava.vvoidd prrinttByL

15、Leveel(NNodee rooot) Noode senntinnel = nnew Nodde(); LinnkeddLisst qq=neew LLinkkedLListt(); qq.adddFiirstt(rooot); qq.adddFiirstt(seentiinell); whhilee (!q.iisEmmptyy() Nodde nn = q.rremooveLLastt(); iff (nn=ssenttineel) Syysteem.oout.priintlln(“n”); q.adddFirrst(senntinnel); ellse Syysteem.oout.p

16、riintlln(nn); iif (n.lleftt() != nulll) q.aaddFFirsst(nn.leeft(); if (n.rigght()!=nulll) q.aaddFFirsst(nn.riightt(); 第17 题：题目目：在一一个字符符串中找找到第一一个只出出现一次次的字符符。如输输入abbacccdefff，则则输出bb。分析：这道题题是20006 年goooglee 的一一道笔试试题。AANSWWER:Agaain, thhis deppendds oon wwhatt iss “ccharr”. Letts asssumee itt ass ASSCIII

17、.chhar firrstSSinggle(chaar * sttr) intt a2555; meemseet(aa, 00, 2255*sizzeoff(innt); chaar *p=sstr; wwhille (*p!=0) a*p +; p+; p = sstr; wwhille (*p!=0) if (a*p = 1) reeturrn *p; reeturrn 0; / tthiss muust thee onne tthatt occcurrs eexacct 11 tiime.第18 题：题目目：n个数字字（0,1,n-1）形形成一个个圆圈，从从数字00 开始始，每次次从这个

18、个圆圈中中删除第第m 个数数字（第第一个为为当前数数字本身身，第二二个为当当前数字字的下一一个数字字）。当当一个数数字删除除后，从从被删除除数字的的下一个个继续删删除第mm 个数字。求求出在这这个圆圈圈中剩下下的最后后一个数数字。JJulyy：我想想，这个个题目，不不少人已已经见识识过了。ANSWER:Actually, although this is a so traditional problem, I was always to lazy to think about this or even to search for the answer.(What a shame.). Fina

19、lly, by google I found the elegant solution for it.The keys are:1) if we shift the ids by k, namely, start from k instead of 0, we should add the result by k%n2) after the first round, we start from k+1 ( possibly % n) with n-1 elements, that is equal to an (n-1) problem while start from (k+1)th ele

20、ment instead of 0, so the answer is (f(n-1, m)+k+1)%n3) k = m-1, so f(n,m)=(f(n-1,m)+m)%n.finally, f(1, m) = 0;Now this is a O(n) solution.int joseph(int n, int m) int fn=0; for (int i=2; i1, _rr); muultiiplyy(_rr, _r, tmpp); iff (nn & 1 = 11) muultiiplyy(tmmp, A, _r); eelsee memmcpyy(_rr, ttmp, 4*s

21、izzeoff(innt); 第20 题：题目目：输入入一个表表示整数数的字符符串，把把该字符符串转换换成整数数并输出出。例如如输入字字符串3455，则则输出整整数3445。ANSSWERR:Thiis qquesstioon ccheccks howw thhe iinteerviieweee iis ffamiiliaar wwithh C/C+? IIm so badd att C/C+.int atooi(ccharr * strr) iint negg = 0; chhar * pp = strr; if (*pp = -) pp+; neeg = 1; ellse if (*pp

22、= +) pp+; iint numm = 0; whhilee (*p != 0) iff (*p=0 & *pp mm) ffinddCommbinnatiion(m, m); iint auxxn; memmsett(auux, 0, n*ssizeeof(intt); hhelpper(m, 0, auxx);voiid hhelpper(intt deest, innt iidx, innt aaux, intt n) iff (ddestt = 0) duump(auxx, nn); iff (ddestt = 0 | idxx=nn) rretuurn; hhelpper(des

23、st, idxx+1, auux, n); aauxidxx = 1; hhelpper(desst-iidx-1, idxx+1, auux, n); aauxidxx = 0;voiid ddumpp(innt aaux, intt n) foor (intt i=0; idaatah2-daata) heaad = h22; hh2=hh2-nexxt; elsse heead = hh1; h1=h1-neext; NNodee * currrennt = heead; wwhille (h1 != NULLL & hh2 != NNULLL) iff (hh1 = NNULLL |

24、(hh2!=NULLL & hh1-dattahh2-datta) ccurrrentt-nnextt = h2; h22=h22-nnextt; ccurrrentt = currrennt-nexxt; eelsee ccurrrentt-nnextt = h1; h11=h11-nnextt; ccurrrentt = currrennt-nexxt; ccurrrentt-nnextt = NULLL; reeturrn hheadd;第25 题：写一一个函数数,它的原原形是iint conntinnumaax(ccharr *ooutpputsstr,chaar *inttputts

25、trr)功能能：在字字符串中中找出连连续最长长的数字字串，并并把这个个串的长长度返回回，并把把这个最最长数字字串付给给其中一一个函数数参数ooutpputsstr 所指内内存。例例如：abccd1223455ed1125sss122345567889的的首地址址传给iintpputsstr 后，函函数将返返回9，outtputtstrr 所指指的值为为123345667899ANSSWERR:int conntinnumaax(ccharr *ooutpputsstr, chhar *innputtstrr) iint lenn = 0; chhar * ppstaart = NNULLL;

26、intt maax = 0; wwhille (1) iif (*innputtstrr = 00 & *inpputsstr maax) psttartt = inpputsstr-lenn; leen = 0; if (*iinpuutsttr+=0) bbreaak; foor (intt i=0; illen; i+) *ouutpuutsttr+ = psttartt+; *outtputtstrr = 00; reeturrn mmax;26.左旋转转字符串串题目：定义字字符串的的左旋转转操作：把字符符串前面面的若干干个字符符移动到到字符串串的尾部部。如把把字符串串abccdeff

27、 左旋旋转2 位得到到字符串串cdeefabb。请实现现字符串串左旋转转的函数数。要求求时间对对长度为为n 的字字符串操操作的复复杂度为为O(nn)，辅辅助内存存为O(1)。ANSSWERRHavve ddonee itt. UUsinng rreveersee woord funnctiion aboove.27.跳跳台阶问问题题目目：一个个台阶总总共有nn 级，如如果一次次可以跳跳1 级，也也可以跳跳2 级。求总总共有多多少总跳跳法，并并分析算算法的时时间复杂杂度。这这道题最最近经常常出现，包包括MiicrooStrrateegy 等比较较重视算算法的公公司都曾曾先后选选用过个个这道题题作

28、为面面试题或或者笔试试题。AANSWWERff(n)=f(n-11)+ff(n-2), f(1)=1, f(22)=22, llet f(00) = 1, thhen f(nn) = fiibo(n-11);28.整整数的二二进制表表示中11 的个个数题目目：输入入一个整整数，求求该整数数的二进进制表达达中有多多少个11。例如输输入100，由于于其二进进制表示示为10010，有有两个11，因此此输出22。分析：这是一一道很基基本的考考查位运运算的面面试题。包括微软在内的很多公司都曾采用过这道题。ANSWERTraditional question. Use the equation xxxxx

29、x10000 & (xxxxxx10000-1) = xxxxxx00000Note: for negative numbers, this also hold, even with 100000000 where the “-1” leading to an underflow.int countOf1(int n) int c=0; while (n!=0) n=n & (n-1); c+; return c;another solution is to lookup table. O(k), k is sizeof(int);int couuntOOf1(intt n) intt c = 00; iif (n00) c+; n = n & (1= 8; rretuurn c;29.栈栈的puush、popp 序列列题目：输入两两个整数数序列。其其中一个个序