微软面试100题系列

1首先，由1 号提出分配方案，然后大家表决，当且仅当超过半数的人同意时，
按照他的方案进行分配，否则将被扔进大海喂鲨鱼
如果1 号死后，再由2 号提出分配方案，然后剩下的4 人进行表决，
当且仅当超过半数的人同意时，按照他的方案进行分配，否则将被扔入大海喂鲨鱼。
依此类推
条件：每个海盗都是很聪明的人，都能很理智地做出判断，从而做出选择。
问题：第一个海盗提出怎样的分配方案才能使自己的收益最大化？

2.一道关于飞机加油的问题，已知：
每个飞机只有一个油箱，
飞机之间可以相互加油（注意是相互，没有加油机）
一箱油可供一架飞机绕地球飞半圈，
问题：
为使至少一架飞机绕地球一圈回到起飞时的飞机场，至少需要出动几架飞机？
（所有飞机从同一机场起飞，而且必须安全返回机场，不允许中途降落，中间没有飞机场）
//欢迎，关注另外不同的更精彩的100 题V0.2 版，和此V0.1 版的答案等后续内容。
完。

此外，关于此100 道面试题的所有一切详情，包括答案，资源下载，帖子维护，答案更新，
都请参考此文：横空出世，席卷Csdn [评微软等数据结构+算法面试100 题]。
--------------------------------------------------------------------------------


作者声明:
本人July 对以上所有任何内容和资料享有版权，转载请注明作者本人July 及出处。
向您的厚道致敬。谢谢。二零一零年十二月六日。

36
微软等数据结构+算法面试 100 题全部答案集锦
作者：July、阿财。
时间：二零一一年十月十三日。
引言
无私分享造就开源的辉煌。
今是二零一一年十月十三日，明日14 日即是本人刚好开博一周年。在一周年之际，特
此分享出微软面试全部100 题答案的完整版，以作为对本博客所有读者的回馈。
一年之前的10 月14 日，一个名叫July （头像为手冢国光）的人在一个叫csdn 的论
坛上开帖分享微软等公司数据结构+算法面试100 题，自此，与上千网友一起做，一起思考，
一起解答这些面试题目，最终成就了一个名为：结构之法算法之道的编程面试与算法研究并
重的博客，如今，此博客影响力逐步渗透到海外，及至到整个互联网。
在此之前，由于本人笨拙，这微软面试100 题的答案只整理到了前60 题（第1-60 题
答案可到本人资源下载处下载：http://v_july_http://wendang.chazidian.com/），故此，常有朋友留
言或来信询问后面40 题的答案。只是因个人认为：一、答案只是作为一个参考，不可太过
依赖；二、常常因一些事情耽搁（如在整理最新的今年九月、十月份的面试题：九月腾讯，
创新工场，淘宝等公司最新面试十三题、十月百度，阿里巴巴，迅雷搜狗最新面试十一题）；
三、个人正在针对那 100 题一题一题的写文章，多种思路，不断优化，即成程序员编程艺
术系列（详情，参见文末）。自此，后面 40 题的答案迟迟未得整理。且个人已经整理的前
60 题的答案，在我看来，是有诸多问题与弊端的，甚至很多答案都是错误的。
(微软10 题永久讨论地址：http://wendang.chazidian.com/u/20101126/10/b4f12a00-6280-492
f-b785-cb6835a63dc9_9.html)
互联网总是能给人带来惊喜。前几日，一位现居美国加州的名叫阿财的朋友发来一封邮
件，并把他自己做的全部100 题的答案一并发予给我，自此，便似遇见了知己。十分感谢。
任何东西只有分享出来才更显其价值。本只需贴出后面 40 题的答案，因为前 60 题的
答案本人早已整理上传至网上，但多一种思路多一种参考亦未尝不可。特此，把阿财的答案
再稍加整理番，然后把全部 100 题的答案现今都贴出来。若有任何问题，欢迎不吝指正。
谢谢。
上千上万的人都关注过此100 题，且大都都各自贡献了自己的思路，或回复于微软100
题维护地址上，或回复于本博客内，人数众多，无法一一标明，特此向他们诸位表示敬意和
37
感谢。谢谢大家，诸君的努力足以影响整个互联网，咱们已经迎来一个分享互利的新时代。
微软面试100 题全部答案
最新整理的全部 100 题的答案参见如下（重复的，以及一些无关紧要的题目跳过。且
因尊重阿财，未作过多修改。因此，有些答案是还有问题的，最靠谱的答案以程序员编程
艺术系列为准，亦可参考个人之前整理的前60 题的答案：
 第1-20 题答案：http://wendang.chazidian.com/v_JULY_v/archive/2011/01/10/6126406.aspx；
 第21-40 题答案：http://wendang.chazidian.com/v_JULY_v/archive/2011/01/10/6126444.aspx；
 第41-60 题答案：http://wendang.chazidian.com/v_JULY_v/archive/2011/02/01/6171539.aspx。
更新：有朋友反应，以下的答案中思路过于简略，还是这句话，一切以程序员编程艺术
系列（多种思路，多种比较，细细读之自晓其理）为准（我没怎么看阿财的这些答案，因为
编程艺术系列已经说得足够清晰了。之所以把阿财的这份答案分享出来，一者，编程艺术系
列目前还只写到了第二十二章，即100 题之中还只详细阐述了近30 道题；二者，他给的答
案全部是用英文写的，这恰好方便国外的一些朋友参考；三者是为了给那一些急功近利的、
浮躁的人一份速成的答案罢了）。July、二零一一年十月二十四日更新。
当然，读者朋友有任何问题，你也可以跟阿财联系，他的邮箱地址是：
kevinn9#http://wendang.chazidian.com (把#改成@)。

1.把二元查找树转变成排序的双向链表
题目：
输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点，只调整指针的指向。
10
/ \
6 14
/ \ / \
4 8 12 16
转换成双向链表
4=6=8=10=12=14=16。
首先我们定义的二元查找树节点的数据结构如下：
struct BSTreeNode
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
38
BSTreeNode *m_pRight; // right child of node
};
ANSWER:
This is a traditional problem that can be solved using recursion.
For each node, connect the double linked lists created from left and right child node to
form a full list.

/**
* @param root The root node of the tree
* @return The head node of the converted list.
*/
BSTreeNode * treeToLinkedList(BSTreeNode * root) {
BSTreeNode * head, * tail;
helper(head, tail, root);
return head;
}

void helper(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)。
39
ANSWER:
Stack is a LIFO data structure. When some element is popped from the stack, the status
will recover to the original status as before that element was pushed. So we can recover
the minimum element, too.

struct MinStackElement {
int data;
int min;
};

struct MinStack {
MinStackElement * data;