微软100题.docx
- 文档编号:1662353
- 上传时间:2023-05-01
- 格式:DOCX
- 页数:79
- 大小:74.09KB
微软100题.docx
《微软100题.docx》由会员分享,可在线阅读,更多相关《微软100题.docx(79页珍藏版)》请在冰点文库上搜索。
微软100题
微软等数据结构+算法面试100题全部答案集锦
作者:
July、阿财。
时间:
二零一一年十月十三日。
∙引言
无私分享造就开源的辉煌。
今是二零一一年十月十三日,明日14日即是本人刚好开博一周年。
在一周年之际,特此分享出微软面试全部100题答案的完整版,以作为对本博客所有读者的回馈。
一年之前的10月14日,一个名叫July(头像为手冢国光)的人在一个叫csdn的论坛上开帖分享微软等公司数据结构+算法面试100题,自此,与上千网友一起做,一起思考,一起解答这些面试题目,最终成就了一个名为:
结构之法算法之道的编程面试与算法研究并重的博客,如今,此博客影响力逐步渗透到海外,及至到整个互联网。
在此之前,由于本人笨拙,这微软面试100题的答案只整理到了前60题(第1-60题答案可到本人资源下载处下载:
http:
//v_july_
(微软10题永久讨论地址:
互联网总是能给人带来惊喜。
前几日,一位现居美国加州的名叫阿财的朋友发来一封邮件,并把他自己做的全部100题的答案一并发予给我,自此,便似遇见了知己。
十分感谢。
任何东西只有分享出来才更显其价值。
本只需贴出后面40题的答案,因为前60题的答案本人早已整理上传至网上,但多一种思路多一种参考亦未尝不可。
特此,把阿财的答案再稍加整理番,然后把全部100题的答案现今都贴出来。
若有任何问题,欢迎不吝指正。
谢谢。
上千上万的人都关注过此100题,且大都都各自贡献了自己的思路,或回复于微软100题维护地址上,或回复于本博客内,人数众多,无法一一标明,特此向他们诸位表示敬意和感谢。
谢谢大家,诸君的努力足以影响整个互联网,咱们已经迎来一个分享互利的新时代。
∙微软面试100题全部答案
更新:
有朋友反应,以下的答案中思路过于简略,还是这句话,一切以程序员编程艺术系列(多种思路,多种比较,细细读之自晓其理)为准(我没怎么看阿财的这些答案,因为编程艺术系列已经说得足够清晰了。
之所以把阿财的这份答案分享出来,一者,编程艺术系列目前还只写到了第二十二章,即100题之中还只详细阐述了近30道题;二者,他给的答案全部是用英文写的,这恰好方便国外的一些朋友参考;三者是为了给那一些急功近利的、浮躁的人一份速成的答案罢了)。
July、二零一一年十月二十四日更新。
当然,读者朋友有任何问题,你也可以跟阿财联系,他的邮箱地址是:
kevinn9# (把#改成@)。
1.把二元查找树转变成排序的双向链表
题目:
输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点,只调整指针的指向。
10
/\
614
/\/\
481216
转换成双向链表
4=6=8=10=12=14=16。
首先我们定义的二元查找树节点的数据结构如下:
structBSTreeNode
{
intm_nValue;//valueofnode
BSTreeNode*m_pLeft;//leftchildofnode
BSTreeNode*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(cur sum+=a[cur++]; if(sum>max){ max=sum; }elseif(sum<0){ sum=0; } } returnmax; } 4.在二元树中找出和为某一值的所有路径 题目: 输入一个整数和一棵二元树。 从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。 打印出和与输入整数相等的所有路径。 例如输入整数22和如下二元树 10 /\ 512 /\ 47 则打印出两条路径: 10,12和10,5,7。 二元树节点的数据结构定义为: structBinaryTreeNode//anodeinthebinarytree { intm_nValue;//valueofnode BinaryTreeNode*m_pLeft;//leftchildofnode BinaryTreeNode*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-nK O(kn): doinsertionsortuntilkelementsareretrieved. O(n+klogn): TakeO(n)timetobottom-upbuildamin-heap.Thensift-downk-1times. SotraditionalthatIdon’twanttowritethecodes... Onlygivesthesiftupandsiftdownfunction. /** *@param itheindexoftheelementinheapa[0...n-1]tobesiftedup voidsiftup(inta[],inti,intn){ while(i>0){ intj=(i&1==0? i-1: i+1); intp=(i-1)>>1; if(j
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 微软 100