本文自CSDN大牛的一篇博客：blog.csdn.net/v_july_v/article/details/6870251 作者：July、阿财
时间：二零一一年十月十三日。
我能够看到此文，还要多同学！让我得以及时分享给大家
微软面试100题全部答案
个人整理的前60题的答案可参见以下三篇文章：
1. 微软100题第1题-20题答案 blog.csdn.net/v_JULY_v/archive/2011/01/10/6126406.aspx [博
文 I]
2. 微软100题第21-40题答案 blog.csdn.net/v_JULY_v/archive/2011/01/10/6126444.aspx [博文
II]
3. 微软100题第41-60题答案 blog.csdn.net/v_JULY_v/archive/2011/02/01/6171539.aspx [博文
III]
最新整理的全部100题的答案参见如下（重复的，以及一些无关紧要的题目跳过）： 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; } }
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 { int data; int min; };
struct MinStack { MinStackElement * data;
int size; int top; }
MinStack MinStackInit(int maxSize) { MinStack stack; stack.size = maxSize;
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 void siftdown(int a[], int i, int n) { while (2*i+1 if (l+1
面试_微软面试100题全部答案
