第1页 / 共46页
第2页 / 共46页
第3页 / 共46页
第4页 / 共46页
第5页 / 共46页
第6页 / 共46页
第7页 / 共46页
第8页 / 共46页
微软等数据结构算法面试100题全部答案集锦.pdf
微软等数据结构++++算法面试100100100100题全部答案集锦
作者：July、阿财。
时间：二零一一年十月十三日。
引言
无私分享造就开源的辉煌。
今是二零一一年十月十三日，明日14日即是本人刚好开博一周年。在一周年之际，特此分享出微软面试
全部100题答案的完整版，以作为对本博客所有读者的回馈。
一年之前的10月14日，一个名叫 July 的人在一个叫 csdn 的论坛上开帖分享微软等公司数据结构+算法
面试100题，自此，与上千网友一起做，一起思考，一起解答这些面试题目，最终成就了一个名为：结构之法
算法之道的编程面试与算法研究并重的博客，如今，此博客影响力逐步渗透到海外，及至到整个互联网。
在此之前，由于本人笨拙，这微软面试100题的答案只整理到了前60题（第1-60题答案可到本人资源下
http://v_july_v.download.csdn.net/
http://v_july_v.download.csdn.net/
载处下载：http://v_july_v.download.csdn.net/
http://v_july_v.download.csdn.net/），故此，常有朋友留言或来信询问后面40题的答案。只是
因个人认为：一、答案只是作为一个参考，不可太过依赖；二、常常因一些事情耽搁（如在整理最新的今年
九月、十月份的面试题：九月腾讯，创新工场，淘宝等公司最新面试十三题、十月百度，阿里巴巴，迅雷搜狗
最新面试十一题）；三、个人正在针对那100题一题一题的写文章，多种思路，不断优化，即成程序员编程
艺术系列。自此，后面40题的答案迟迟未得整理。且个人已经整理的前60题的答案，在我看来，是有诸多问
题与弊端的，甚至很多答案都是错误的。
互联网总是能给人带来惊喜。前几日，一位现居美国加州的名叫阿财的朋友发来一封邮件，并把他自己
做的全部100题的答案一并发予给我，自此，便似遇见了知己。十分感谢。
任何东西只有分享出来才更显其价值。本只需贴出后面40题的答案，因为前60题的答案本人早已整理上
传至网上，但多一种思路多一种参考亦未尝不可。特此，把阿财的答案再稍加整理番，然后把全部100题的答
案现今都贴出来。若有任何问题，欢迎不吝指正。谢谢。
上千上万的人都关注过此100题，且大都都各自贡献了自己的思路，或回复于微软100100100100题维护地址上，或
回复于本博客内，人数众多，无法一一标明，特此向他们诸位表示敬意和感谢。谢谢大家，诸君的努力足以影
响整个互联网，咱们已经迎来一个分享互利的新时代。
微软面试100100100100题全部答案
最新整理的全部100题的答案参见如下（重复的，以及一些无关紧要的题目跳过。且因尊重阿财，未作过
多修改。因此，有些答案是有问题的，重点还可关注本人的程序员编程艺术系列，亦可参考个人之前
整理的前60题的答案：第1题-20题答案：http://blog.csdn.net/v_JULY_v/archive/2011/01/10/6126406.aspx，
第21-40题答案：http://blog.csdn.net/v_JULY_v/archive/2011/01/10/6126444.aspx，第41-60题答案：
http://blog.csdn.net/v_JULY_v/archive/2011/02/01/6171539.aspx）：
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
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;
}
int data;
int min;
};
struct MinStack {
MinStackElement * data;
int size;
int top;
}
MinStack MinStackInit(int maxSize) {
MinStack stack;
stack.size = maxSize;
}
2.设计包含 min 函数的栈。
定义栈的数据结构，要求添加一个 min 函数，能够得到栈的最小元素。
要求函数 min、push 以及 pop 的时间复杂度都是 O(1)。
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 {
stack.data = (MinStackElement*) malloc(sizeof(MinStackElement)*maxSize);
stack.top = 0;
return stack;
}
void MinStackFree(MinStack stack) {
free(stack.data);
}
void MinStackPush(MinStack stack, int d) {
if (stack.top == stack.size) error(“out of stack space.”);
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 ++;
}
int MinStackPop(MinStack stack) {
if (stack.top == 0) error(“stack is empty!”);
return stack.data[--stack.top].data;
}
int MinStackMin(MinStack stack) {
if (stack.top == 0) error(“stack is empty!”);
return stack.data[stack.top-1].min;
}
3.求子数组的最大和
题目：
输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为 O(n)。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，
因此输出为该子数组的和18。
ANSWER:
A traditional greedy approach.
Keep current sum, slide from left to right, when sum < 0, reset sum to 0.
int maxSubarray(int a[], int size) {
if (size<=0) error(“error array size”);
int sum = 0;
int max = - (1 << 31);
int cur = 0;
while (cur < size) {
sum += a[cur++];
if (sum > max) {
max = sum;
} else if (sum < 0) {
sum = 0;
}
}
return max;
}
4.在二元树中找出和为某一值的所有路径
题目：输入一个整数和一棵二元树。
从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。
打印出和与输入整数相等的所有路径。
例如输入整数22 和如下二元树
10
/ \
5 12
/ \
4 7
则打印出两条路径：10, 12 和10, 5, 7。
二元树节点的数据结构定义为：
struct BinaryTreeNode // a node in the binary tree
{
int m_nValue; // value of node
BinaryTreeNode *m_pLeft; // left child of node
BinaryTreeNode *m_pRight; // right child of node
};
ANSWER:
Use backtracking and recurison. We need a stack to help backtracking the path.
struct TreeNode {
int data;
TreeNode * left;
TreeNode * right;
};
void printPaths(TreeNode * root, int sum) {
int path[MAX_HEIGHT];
helper(root, sum, path, 0);
}
void helper(TreeNode * root, int sum, int path[], int top) {
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:
This is a very traditional question...
O(nlogn): cat I_FILE | sort -n | head -n K
O(kn): do insertion sort until k elements are retrieved.
O(n+klogn): Take O(n) time to bottom-up build a min-heap. Then sift-down k-1 times.
So traditional that I don’t want to write the codes...
Only gives the siftup and siftdown function.
/**
*@param i the index of the element in heap a[0...n-1] to be sifted up
void siftup(int a[], int i, int n) {
while (i>0) {
int j=(i&1==0 ? i-1 : i+1);
int p=(i-1)>>1;
if (j
}
第6 题
腾讯面试题：
给你10 分钟时间，根据上排给出十个数，在其下排填出对应的十个数
要求下排每个数都是先前上排那十个数在下排出现的次数。
上排的十个数如下：
【0，1，2，3，4，5，6，7，8，9】
举一个例子，
数值: 0,1,2,3,4,5,6,7,8,9
分配: 6,2,1,0,0,0,1,0,0,0
0 在下排出现了6 次，1 在下排出现了2 次，
2 在下排出现了1 次，3 在下排出现了0 次....
以此类推..
ANSWER:
I don’t like brain teasers. Will skip most of them...
第7 题
微软亚院之编程判断俩个链表是否相交
给出俩个单向链表的头指针，比如 h1，h2，判断这俩个链表是否相交。
为了简化问题，我们假设俩个链表均不带环。
问题扩展：
1.如果链表可能有环列?
2.如果需要求出俩个链表相交的第一个节点列?
ANSWER:
struct Node {
int data;
int Node *next;
};
// if there is no cycle.
int isJoinedSimple(Node * h1, Node * h2) {
while (h1->next != NULL) {
h1 = h1->next;
}
while (h2->next != NULL) {
h2 = h2-> next;
}
return h1 == h2;
}
// if there could exist cycle
int isJoined(Node *h1, Node * h2) {
}
}
Node* cylic1 = testCylic(h1);
Node* cylic2 = testCylic(h2);
if (cylic1+cylic2==0) return isJoinedSimple(h1, h2);
if (cylic1==0 && cylic2!=0 || cylic1!=0 &&cylic2==0) return 0;
Node *p = cylic1;
while (1) {
if (p==cylic2 || p->next == cylic2) return 1;
p=p->next->next;
cylic1 = cylic1->next;
if (p==cylic1) return 0;
}
Node* testCylic(Node * h1) {
Node * p1 = h1, *p2 = h1;
while (p2!=NULL && p2->next!=NULL) {
p1 = p1->next;
p2 = p2->next->next;
if (p1 == p2) {
return p1;
}
}
return NULL;
}
第8 题
此贴选一些比较怪的题，，由于其中题目本身与算法关系不大，仅考考思维。特此并作一题。
1.有两个房间，一间房里有三盏灯，另一间房有控制着三盏灯的三个开关，
这两个房间是分割开的，从一间里不能看到另一间的情况。
现在要求受训者分别进这两房间一次，然后判断出这三盏灯分别是由哪个开关控制的。
有什么办法呢？
ANSWER:
Skip.
2.你让一些人为你工作了七天，你要用一根金条作为报酬。金条被分成七小块，每天给出一
块。
如果你只能将金条切割两次，你怎样分给这些工人?
ANSWER:
1+2+4;
3. ★用一种算法来颠倒一个链接表的顺序。现在在不用递归式的情况下做一遍。
ANSWER:
Node * reverse(Node * head) {
if (head == NULL) return head;
if (head->next == NULL) return head;
Node * ph = reverse(head->next);
head->next->next = head;
head->next = NULL;
return ph;
}
Node * reverseNonrecurisve(Node * head) {
if (head == NULL) return head;
Node * p = head;
Node * previous = NULL;
while (p->next != NULL) {
p->next = previous;
previous = p;
p = p->next;
}
p->next = previous;
return p;
}
★用一种算法在一个循环的链接表里插入一个节点，但不得穿越链接表。
ANSWER:
I don’t understand what is “Chuanyue”.
★用一种算法整理一个数组。你为什么选择这种方法?
ANSWER:
What is “Zhengli?”
★用一种算法使通用字符串相匹配。
ANSWER:
What is “Tongyongzifuchuan”... a string with “*” and “?”? If so, here is the code.
int match(char * str, char * ptn) {
if (match(str++, ptn+1)) return 1;
if (*ptn == ‘\0’) return 1;
if (*ptn == ‘*’) {
do {
} while (*str != ‘\0’);
return 0;
}
if (*str == ‘\0’) return 0;
if (*str == *ptn || *ptn == ‘?’) {
return match(str+1, ptn+1);
}
return 0;
}
★颠倒一个字符串。优化速度。优化空间。
void reverse(char *str) {
reverseFixlen(str, strlen(str));
}
void reverseFixlen(char *str, int n) {
char* p = str+n-1;
while (str < p) {
char c = *str;
*str = *p; *p=c;
}
★颠倒一个句子中的词的顺序，比如将“我叫克丽丝”转换为“克丽丝叫我”，
实现速度最快，移动最少。
ANSWER:
Reverse the whole string, then reverse each word. Using the reverseFixlen() above.
void reverseWordsInSentence(char * sen) {
}
★找到一个子字符串。优化速度。优化空间。
ANSWER:
KMP? BM? Sunday? Using BM or sunday, if it’s ASCII string, then it’s easy to fast access the auxiliary array.
Otherwise an hashmap or bst may be needed. Lets assume it’s an ASCII string.
int bm_strstr(char *str, char *sub) {
}
However, this algorithm, as well as BM, KMP algorithms use O(|sub|) space. If this is not acceptable, Rabin-
carp algorithm can do it. Using hashing to fast filter out most false matchings.
#define HBASE 127
int rc_strstr(char * str, char * sub) {
int dest= 0;
}
}
}
int len = strlen(sen);
reverseFixlen(sen, len);
char * p = str;
while (*p!=’\0’) {
while (*p == ‘ ‘ && *p!=’\0’) p++;
str = p;
while (p!= ‘ ‘ && *p!=’\0’) p++;
reverseFixlen(str, p-str);
int len = strlen(sub);
int i;
int aux[256];
memset(aux, sizeof(int), 256, len+1);
for (i=0; i=0 && str[j--] == sub[k--])
}
int n = strlen(str);
i=len-1;
while (i
if (i++=len && strncmp(sub, p-len+1, len) == 0) return i-len;
p++;
}
★比较两个字符串，用 O(n)时间和恒量空间。
ANSWER:
What is “comparing two strings”? Just normal string comparison? The natural way use O(n) time and O(1)
space.
int strcmp(char * p1, char * p2) {
while (*p1 != ‘\0’ && *p2 != ‘\0’ && *p1 == *p2) {
p1++, p2++;
}
if (*p1 == ‘\0’ && *p2 == ‘\0’) return 0;
if (*p1 == ‘\0’) return -1;
if (*p2 == ‘\0’) return 1;
return (*p1 - *p2); // it can be negotiated whether the above 3 if’s are necessary, I don’t like to omit them.
}
★假设你有一个用1001 个整数组成的数组，这些整数是任意排列的，但是你知道所有的整数都在1 到
1000(包括1000)之间。此外，除一个数字出现两次外，其他所有数字只出现一次。假设你只能对这个数组做
一次处理，用一种算法找出重复的那个数字。如果你在运算中使用了辅助的存储方式，那么你能找到不用这种
方式的算法吗?
ANSWER:
Sum up all the numbers, then subtract the sum from 1001*1002/2.
Another way, use A XOR A XOR B = B:
int findX(int a[]) {
char * p = sub;
int len = 0;
int TO_REDUCE = 1;
while (*p!=’\0’) {
dest = HBASE * dest + (int)(*p);
TO_REDUCE *= HBASE;
len ++;
}
int hash = 0;
p = str;
int i=0;
while (*p != ‘\0’) {
}
return -1;
int k = a[0];
for (int i=1; i<=1000;i++)
k ~= a[i]~i;
}
return k;
}
★不用乘法或加法增加8 倍。现在用同样的方法增加7 倍。
ANSWER:
n<<3;
(n<<3)-n;
第9 题
判断整数序列是不是二元查找树的后序遍历结果
题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。
如果是返回 true，否则返回 false。
例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果：
8
/ \
6 10
/ \ / \
5 7 9 11
