微软技术面试100题答案1.doc

微软技术面试100题第1-10题答案修正与优化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;Sorehead：第一题：基本就是采用一次遍历即可，楼主采用的是递归方法。但有两个建议：1、函数里面最好不好使用全局变量，采用参数传递的方式可能更好。全局变量能少用就少用。2、if (NULL = pCurrent)这种方式我也不是很推荐。我知道采用这种方式的好处是一旦少写了一个等号，编译器会报错，NULL不是一个合法左值。其实我最开始写代码时也是这么写的，很长时间都觉得挺好。但这有个悖论，就是一个开发者能够想起来这么写的时候，这说明他知道这么是要做等值判断，自然也会知道该写=而不是=，想不起来的时候自然也就该犯错误还是犯错误，并不能起到原本初衷。代码写多了，会发现这么写真有点多此一举。July关于第一题，我再多说点： 我们可以中序遍历整棵树。按照这个方式遍历树，比较小的结点先访问。如果我们每访问一个结点，假设之前访问过的结点已经调整成一个排序双向链表，我们再把调整当前结点的指针将其链接到链表的末尾。当所有结点都访问过之后，整棵树也就转换成一个排序双向链表了。view plaincopy to clipboardprint?1 / 遍历二元查找树 中序 2 void ergodicBSTree(BSTreeNode * pCurrent) 3 4 if (NULL = pCurrent) 5 6 return; 7 8 if (NULL != pCurrent-m_pLeft) 9 10 ergodicBSTree(pCurrent-m_pLeft); 11 12 13 / 节点接到链表尾部 14 convertToDoubleList(pCurrent); 15 / 右子树为空 16 if (NULL != pCurrent-m_pRight) 17 18 ergodicBSTree(pCurrent-m_pRight); 19 20 21 22 / 二叉树转换成list 23 void convertToDoubleList(BSTreeNode * pCurrent) 24 25 26 pCurrent-m_pLeft = pListIndex; 27 if (NULL != pListIndex) 28 29 pListIndex-m_pRight = pCurrent; 30 31 else 32 33 pHead = pCurrent; 34 35 pListIndex = pCurrent; 36 coutm_nValuem_pLeft != NULL) 46 ConvertNode(pCurrent-m_pLeft, pLastNodeInList); 47 / Put the current node into the double-linked list 48 pCurrent-m_pLeft = pLastNodeInList; 49 50 if(pLastNodeInList != NULL) 51 pLastNodeInList-m_pRight = pCurrent; 52 pLastNodeInList = pCurrent; 53 54 / Convert the right sub-tree 55 if (pCurrent-m_pRight != NULL) 56 ConvertNode(pCurrent-m_pRight, pLastNodeInList); 57 58 59 BSTreeNode* Convert_Solution1(BSTreeNode* pHeadOfTree) 60 61 BSTreeNode *pLastNodeInList = NULL; 62 ConvertNode(pHeadOfTree, pLastNodeInList); 63 64 / Get the head of the double-linked list 65 BSTreeNode *pHeadOfList = pLastNodeInList; 66 while(pHeadOfList & pHeadOfList-m_pLeft) 67 pHeadOfList = pHeadOfList-m_pLeft; 68 return pHeadOfList; 69 但显然，以下这种思路更容易理解些：view plaincopy to clipboardprint?70 BSTreeNode* ConvertNode(BSTreeNode* pNode, bool asRight) 71 72 if(!pNode) 73 return NULL; 74 75 BSTreeNode *pLeft = NULL; 76 BSTreeNode *pRight = NULL; 77 78 / Convert the left sub-tree 79 if(pNode-m_pLeft) 80 pLeft = ConvertNode(pNode-m_pLeft, false); 81 82 / Connect the greatest node in the left sub-tree to the current node 83 if(pLeft) 84 85 pLeft-m_pRight = pNode; 86 pNode-m_pLeft = pLeft; 87 88 89 / Convert the right sub-tree 90 if(pNode-m_pRight) 91 pRight = ConvertNode(pNode-m_pRight, true); 92 93 / Connect the least node in the right sub-tree to the current node 94 if(pRight) 95 96 pNode-m_pRight = pRight; 97 pRight-m_pLeft = pNode; 98 99 100 BSTreeNode *pTemp = pNode; 101 102 / If the current node is the right child of its parent, 103 / return the least node in the tree whose root is the current node 104 if(asRight) 105 106 while(pTemp-m_pLeft) 107 pTemp = pTemp-m_pLeft; 108 109 / If the current node is the left child of its parent, 110 / return the greatest node in the tree whose root is the current node 111 else 112 113 while(pTemp-m_pRight) 114 pTemp = pTemp-m_pRight; 115 116 117 return pTemp; 118 同样是上道题，给各位看一段简洁的代码，领悟一下c的高效与美：view plaincopy to clipboardprint?119 void change(Node *p, Node *&last) /中序遍历 120 121 if (!p) 122 return; 123 change(p-left, last); 124 if (last) 125 last-right = p; 126 p-left = last; 127 128 last = p; 129 change(p-right, last); 130 131 132 void main() 133 134 Node *root = create(); 135 Node *tail = NULL; 136 change(root, tail); 137 while (tail) 138 139 cout data left; 141 142 cout data+stk-top.val = val; 161 if (stk-top 0) 162 163 if (val datastk-top - 1.min) 164 /如果当前push进的元素小于栈中最小元素 165 stk-datastk-top.min = val; /把当前元素置为栈中最小元素 166 else 167 /否则，不更新 168 stk-datastk-top.min = stk-datastk-top - 1.min; 169 170 else 171 stk-datastk-top.min = val; 172 173 174 int pop(stack *stk) 175 176 return stk-datastk-top-.val; 177 178 179 int min(stack *stk) 180 181 return stk-datastk-top.min; 182 3.求子数组的最大和（数组）题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，因此输出为该子数组的和18。之前上传的答案是：int maxSum(int* a, int n) int sum=0; int b=0; for(int i=0; in; i+) if(b0) b=ai; else b+=ai; 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;Sorehead：第四题：对于楼主答案有两个建议： 1、我觉得既然是自己写代码来实现这些功能，就应该全部功能都自己来写，不去使用相关类库，这些类库基本也都是对一些数据结构的封装。 如果使用它们，写这些程序的意义就降低很多，毕竟很多相关问题的答案可以直接就通过类库来实现。 2、“递归调用本质就是压栈和出栈的过程”，这话说得很好。但代码中却有个不是很好的地方，就是采用递归调用方法的同时，有自己定义一个栈来保存树节点数据，这多少有些重复，本质上等于有两个栈，系统一个，自己使用std:vector创建一个。 这么做我觉得还不如自己创建一个栈，直接保存节点地址更好。 5.查找最小的k个元素（数组）题目：输入n个整数，输出其中最小的k个。例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。先介绍一下分治思想：关于分治思想：如果第一次 分划，找到的第s小符合要求m，则停止，如果找到的第s小，sm，则 到s的左边继续找。举例说明：2 1 3 6 4 5假设第一次划分之后，3为中间元素：1、如果要求找第3小的元素，而找到的s=m(要求)，则返回32、如果要求找第1小的元素，而找到的sm，则在s的左边找3、如果要求找第4小的元素，而找到的sm，则在s的右边找。上述程序的期望运行时间，最后证明可得O(n)，且假定元素是不同的。更多，请看这里：程序员面试题狂想曲：第三章、寻找最小的k个数、updated 10次。 第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,00在下排出现了6次，1在下排出现了2次，2在下排出现了1次，3在下排出现了0次.以此类推.Sorehead：第六题：说实话，这题除了一次次迭代尝试外，我没想到什么好的处理办法。假设上排的数组为a，下排对应的数组为b，元素个数为n，按照题目的意思可以得到以下公式：b1+b2+.+bn=na1*b1+a2*b2+.+an*bn=nb中的元素来源于a这种一次多项表达式的求解我不会。我觉得这题比实际上还要复杂，以下情况是必须要考虑的：1、上排的数据元素并不一定是排序的。2、上排的数据元素并不一定就有0，可能还有负数。3、上排的数据元素可能会有重复的。4、未必有对应的下排数据。除了上面提到的，就楼主的程序而言，个人觉得有以下几个改进建议：1、类中success是个多余的东西，如果设置这么一个成员变量，就不应该在函数setNextBottom中再无谓多一个reB变量。2、由于未必有解，getBottom可能限于死循环。3、getBottom中变量i完全是多余的。4、getFrequecy中判断有些是多余的，可以考虑把我上面提到的公司考虑进去。等有时间了，我再好好考虑如何写个比较好的程序。 第7题（链表）微软亚院之编程判断俩个链表是否相交给出俩个单向链表的头指针，比如h1，h2，判断这俩个链表是否相交。为了简化问题，我们假设俩个链表均不带环。问题扩展：1.如果链表可能有环列?2.如果需要求出俩个链表相交的第一个节点列?Sorehead指出：第七题：如果不需要求出两个链表相交的第一个节点，楼主提出的方法挺好的。如果需要求出相交第一个节点，我有以下思路：以链表节点地址为值，遍历第一个链表，使用Hash保存所有节点地址值，结束条件为到最后一个节点（无环）或Hash中该地址值已经存在（有环）。再遍历第二个链表，判断节点地址值是否已经存在于上面创建的Hash表中。这个方面可以解决题目中的所有情况，时间复杂度为O(m+n)，m和n分别是两个链表中节点数量。由于节点地址指针就是一个整型，假设链表都是在堆中动态创建的，可以使用堆的起始地址作为偏移量，以地址减去这个偏移量作为Hash函数。 第9题（树）判断整数序列是不是二元查找树的后序遍历结果题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true，否则返回false。例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果： 8 / / 6 10 / / / / 5 7 9 11因此返回true。如果输入7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回false。July：int is_post_traverse(int *arr, int len) int *head, *pos, *p; if (arr = NULL | len = 0) return 0; if (len = 1) return 1; head = arr + len - 1; p = arr; while (*p *head) p+; pos = p; while (p head) if (*p pLeft = NULL) 20 21 pRoot-MaxLeft = 0; 22 23 else /若左子树不为空 24 25 int TempLen = 0; 26 if(pRoot-pLeft-MaxLeft pRoot-pLeft-MaxRight) 27 /左子树上的，某一节点，往左边大，还是往右边大 28 29 TempLen+=pRoot-pLeft-MaxLeft; 30 31 else 32 33 TempLen+=pRoot-pLeft-MaxRight; 34 35 pRoot-nMaxLeft = TempLen + 1; 36 traversal_MaxLen(NODE* pRoot-pLeft); 37 /此处，加上递归 38 39 if(pRoot-pRigth = NULL) 40 41 pRoot-MaxRight = 0; 42 43 else /若右子树不为空 44 45 int TempLen = 0; 46 if(pRoot-pRight-MaxLeft pRoot-pRight-MaxRight) 47 /右子树上的，某一节点，往左边大，还是往右边大 48 49 TempLen+=pRoot-pRight-MaxLeft; 50 51 else 52 53 TempLen+=pRoot-pRight-MaxRight; 54 55 pRoot-MaxRight = TempLen + 1; 56 traversal_MaxLen(NODE* pRoot-pRight); 57 /此处，加上递归 58 59 60 if(pRoot-MaxLeft + pRoot-MaxRight 0) 61 62 MaxLength=pRoot-nMaxLeft + pRoot-MaxRight; 63 64 Sorehead： 十一题我写了一个非递规的方法，一方面是非递规并不复杂，另外一方面我不大喜欢楼主答案中采用全局变量的方式，我一直认为全局变量能少就少，最好不用。写的代码，如下：view plaincopy to clipboardprint?65 typedef struct _tree 66 67 int key; 68 struct _tree *left; 69 struct _tree *right; 70 int height_left; 71 int height_right; 72 tree; 73 74 #define TREE_HEIGHT 32 75 76 int get_tree_max_distance(tree *head) 77 78 tree *stack_nodeTREE_HEIGHT; 79 int stack_flagTREE_HEIGHT; 80 int top; 81 tree *node; 82 int max_len; 83 84 if (head = NULL) 85 return 0; 86 87 max_len = 0; 88 top = 0; 89 stack_nodetop = head; 90 stack_flagtop = 0; 91 while (top != -1) 92 93 node = stack_nodetop; 94 if (node = NULL) 95 96 top-; 97 continue; 98 99 100 if (stack_flagtop = 0) 101 102 stack_flagtop+; 103 stack_node+top = node-left; 104 stack_flagtop = 0; 105 106 else if (stack_flagtop = 1) 107 108 stack_flagtop+; 109 stack_node+top = node-right; 110 stack_flagtop = 0; 111 112 else 113 114 if (node-left != NULL) 115 node-height_left = node-left-height_left node-left-height_right ? node-left-height_left + 1 : node-left-height_right + 1; 116 else 117 node-height_left = 0; 118 if (node-right != NULL) 119 node-height_right = node-right-height_left node-right-height_right ? node-right-height_left + 1 : node-right-height_right + 1; 120 else 121 node-height_right = 0; 122 123 if (max_len height_left + node-height_right) 124 max_len = node-height_left + node-height_right; 125 126 top-; 127 128 129 return max_len; 130 一次遍历，由于必须是后序遍历，因此加了一个flag数组用于保存栈中节点的状态：0表示该节点刚开始处理；1表示其左子树遍历完毕；2表示右子树遍历完毕。当然可以创建一个结构把节点地址和这个标志放在一起。 树的前序遍历和中序遍历并不需要这个标志，所以只需要一个栈保存节点地址即可。非递归的方法，也可以如azuryy所示，这么写：view plaincopy to clipboardprint?131 struct Node 132 133 bool _visited; 134 135 Node* left; 136 Node* right; 137 int maxLeft; 138 int maxRight; 139 140 Node() 141 142 _visited = false; 143 maxLeft = 0; 144 maxRight = 0; 145 left = NULL; 146 right = NULL; 147 148 ; 149 150 int maxLen = 0; 151 152 stack nodeStack; 153 154 void findMaxLen( Node* root ) 155 156 Node* node; 157 158 if ( root = NULL ) 159 160 return ; 161 162 163 nodeStack.push( root ); 164 while( !nodeStack.empty() 165 166 node = nodeStack.top(); 167 168 if ( node-left = NULL & node-right = NULL ) 169 170 nodeStack.pop(); 171 node-_visited = true; 172 continue; 173 174 if ( node-left ) 175 176 if ( !node-left-_visited ) 177 178 nodeStack.push( node-left ) ; 179 180 else 181 182 node-maxLeft = max( node-left-maxLeft,node-left-maxRight ) + 1; 183 184 185 if ( ( !node-left | node-left-_visited ) & node-right ) 186 187 if ( !node-right-_visited ) 188 189 nodeStack.push( node-right ) ; 190 191 else 192 193 node-maxRight = max( node-right-maxLeft,node-right-maxRight ) + 1; 194 195 196 197 if ( !node-left | node-left-_visited ) & ( !node-right | node-right-_visited ) 198 199 maxLen = max( maxLen, node-maxLeft + node-maxRight ); 200 node-_visited = true; 201 nodeStack.pop(); 202 203 204 -思路改进：计算一个二叉树的最大距离有两个情况: * 情况A: 通过根节点，路径经过左子树的最深节点，再到右子树的最深节点。 * 情况B: 不通过根节点，而是左子树或右子树的最大距离路径，取其大者。只需要计算这两个情况的路径距离，并取其大者，就是该二叉树的最大距离。有人评价原书上的代码时，说：书上的代码有几个缺点: 1. 算法加入侵入式(intrusive)的资料nMaxLeft, nMaxRight 2. 使用全局变量 nMaxLen。每次使用要额外初始化。而且就算是不同的独立资料，也不能在多个线程使用这个函数 3. 逻辑比较复杂，也有许多 NULL 相关的条件测试。于是给出了下述改进代码：view plaincopy to clipboardprint?205 RESULT GetMaximumDistance(NODE* root) 206 207 if (!root) 208 209 RESULT empty = 0, -1 ; 210 / trick: nMaxDepth is -1 and then caller will plus 1 to balance it as zero. 211 return empty; 212 213 214 RESULT lhs = GetMaximumDistance(root-pLeft); 215 RESUL