人力资源微软面试一百道题目精选资料Word格式.docx
《人力资源微软面试一百道题目精选资料Word格式.docx》由会员分享，可在线阅读，更多相关《人力资源微软面试一百道题目精选资料Word格式.docx（65页珍藏版）》请在冰点文库上搜索。
句子中单词以空格符隔开。
为简单起见，标点符号和普通字母一样处理。
例如输入“Iamastudent.”，则输出“student.aamI”。
Answer:
Alreadydonethis.Skipped.
第11题
求二叉树中节点的最大距离...
如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，
我们姑且定义"
距离"
为两节点之间边的个数。
写一个程序，
求一棵二叉树中相距最远的两个节点之间的距离。
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;
}
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）。
1+..+n=n*（n+1）/2=（n^2+n）/2
itiseasytogetx/2,sotheproblemistogetn^2
thoughnoif/elseisallowed,wecaneasillygoaroundusingshort-pass.
usingmacrotomakeitfancier:
#define
T（X,Y,i）（Y&
（1<
<
i））&
X+=（Y<
i）
intfoo（intn）{
intr=n;
T（r,n,0）;
T（r,n,1）;
T（r,n,2）;
…T（r,n,31）;
returnr>
>
1;
第13题：
输入一个单向链表，输出该链表中倒数第k个结点。
链表的倒数第0个结点为链表的尾指针。
链表结点定义如下：
structListNode
{
intm_nKey;
ListNode*m_pNext;
};
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->
=NULL）{
p=p->
next,pk=pk->
returnp;
第14题：
输入一个已经按升序排序过的数组和一个数字，
在数组中查找两个数，使得它们的和正好是输入的那个数字。
要求时间复杂度是O（n）。
如果有多对数字的和等于输入的数字，输出任意一对即可。
例如输入数组1、2、4、7、11、15和数字15。
由于4+11=15，因此输出4和11。
Usetwocursors.Oneatfrontandtheotherattheend.Keeptrackofthesumbymovingthecursors.
voidfind2Number（inta[],intn,intdest）{
int*f=a,*e=a+n-1;
intsum=*f+*e;
while（sum!
=dest&
f<
e）{
if（sum<
dest）sum=*（++f）;
elsesum=*（--e）;
if（sum==dest）printf（“%d,%d\n”,*f,*e）;
第15题：
输入一颗二元查找树，将该树转换为它的镜像，
即在转换后的二元查找树中，左子树的结点都大于右子树的结点。
用递归和循环两种方法完成树的镜像转换。
例如输入：
/\/\
输出：
106
11975
定义二元查找树的结点为：
structBSTreeNode//anodeinthebinarysearchtree（BST）
intm_nValue;
//valueofnode
BSTreeNode*m_pLeft;
//leftchildofnode
BSTreeNode*m_pRight;
//rightchildofnode
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）,&
right））;
mirror（root->
left）;
right）;
voidmirrorIteratively（Node*root）{
stack<
Node*>
buf;
buf.push（root）;
while（!
stack.empty（））{
Node*n=stack.pop（）;
if（root->
left!
=NULL）buf.push（root->
right!
第16题：
题目（微软）：
输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。
例如输入
输出861057911。
Thenodesinthelevelsareprintedinthesimilarmannertheirparentswereprinted.SoitshouldbeanFIFOqueuetoholdthelevel.Ireallydon’trememberthefunctionnameofthestlqueue,soIwillwriteitinJava...
voidprintByLevel（Noderoot）{
Nodesentinel=newNode（）;
LinkedList<
Node>
q=newLinkedList<
（）;
q.addFirst（root）;
q.addFirst（sentinel）;
q.isEmpty（））{
Noden=q.removeLast（）;
if（n==sentinel）{
System.out.println（“\n”）;
}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的一道笔试题。
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;
if（a[*p]==1）return*p;
return‘\0’;
//thismusttheonethatoccursexact1time.
第18题：
n个数字（0,1,…,n-1）形成一个圆圈，从数字0开始，
每次从这个圆圈中删除第m个数字（第一个为当前数字本身，第二个为当前数字的下一个数
字）。
当一个数字删除后，从被删除数字的下一个继续删除第m个数字。
求出在这个圆圈中剩下的最后一个数字。
July：
我想，这个题目，不少人已经见识过了。
Actually,althoughthisisasotraditionalproblem,Iwasalwaystolazytothinkaboutthisoreventosearchfortheanswer.（Whatashame...）.Finally,bygoogleIfoundtheelegantsolutionforit.
Thekeysare:
1）ifweshifttheidsbyk,namely,startfromkinsteadof0,weshouldaddtheresultbyk%n
2）afterthefirstround,westartfromk+1（possibly%n）withn-1elements,thatisequaltoan（n-1）problemwhilestartfrom（k+1）thelementinsteadof0,sotheansweris（f（n-1,m）+k+1）%n
3）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=0
f（n）=1n=1
\f（n-1）+f（n-2）n=2
输入n，用最快的方法求该数列的第n项。
在很多C语言教科书中讲到递归函数的时候，都会用Fibonacci作为例子。
因此很多程序员对这道题的递归解法非常熟悉，但....呵呵，你知道的。
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）;
memcpy（_r,tmp,4*sizeof（int））;
第20题：
输入一个表示整数的字符串，把该字符串转换成整数并输出。
例如输入字符串"
345"
，则输出整数345。
ThisquestioncheckshowtheintervieweeisfamiliarwithC/C++?
I’msobadatC/C++...
intatoi（char*str）{
intneg=0;
char*p=str;
if（*p==‘-’）{
neg=1;
}elseif（*p==‘+’）{
intnum=0;
while（*p!
=‘\0’）{
if（*p>
='
0'
&
*p<
='
9'
）{
num=num*10+（*p-’0’）;
error（“illegalnumber”）;
returnnum;
Ididn’tfigureouthowtotellaoverflowproblemeasily.
第21题
2010年中兴面试题
编程求解：
输入两个整数n和m，从数列1，2，3.......n中随意取几个数,
使其和等于m,要求将其中所有的可能组合列出来.
ANSWER
Thisisacombinationgenerationproblem.
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;
n;
i++）
if（aux[i]）printf（“%3d”,i+1）;
printf（“\n”）;
thisisnotanelegantimplementation,however,itisnotnecessarytousegraycodeorothertechniquesforsuchaproblem,right?
第22题：
有4张红色的牌和4张蓝色的牌，主持人先拿任意两张，再分别在A、B、C三人额头上贴任意两张牌，A、B、C三人都可以看见其余两人额头上的牌，看完后让他们猜自己额头上是什么颜色的牌，A说不知道，B说不知道，C说不知道，然后A说知道了。
请教如何推理，A是怎么知道的。
如果用程序，又怎么实现呢？
Idont’likebrainteaser.AsanAIproblem,itseemsimpossibletowritethesolutionin20min...
Itseemsthatabrute-forceedgecuttingstrategycoulddo.Enumerateallpossibilities,thenforeachguydeletethepermutationthatcouldbereducediffailed（forA,B,Cat1stround）,Thenthereshouldbeonlyoneoronegroupofchoicesleft.
Butwhousesthisasaninterviewquestion?
第23题：
用最简单，最快速的方法计算出下面这个圆形是否和正方形相交。
"
3D坐标系原点（0.0,0.0,0.0）
圆形:
半径r=3.0
圆心o=（*.*,0.0,*.*）
正方形:
4个角坐标;
1:
（*.*,0.0,*.*）
2:
3:
4:
Crap...Itotallycannotunderstandthisproblem...Doesthe*.*representanypossiblenumber?
第24题：
链表操作，
（1）.单链表就地逆置，
（2）合并链表
Reversingalinkedlist.Alreadydone.
Whatdoyoumeanbymerge?
Aretheoriginallistssortedandneedtobekeptsorted?
Ifnot,arethereanyspecialrequirements?
Iwillonlydothesortedmerging.
Node*merge（Node*h1,Node*
升级会员 