永久优化：微软技术面试100题第1-10题答案修正与优化

永久优化：微软技术面试100题第1-10题答案修正与优化

作者：July、Sorehead。
时间：二零一一年三月二十五日。
出处：http://blog.csdn.net/v_JULY_v。
---------------------------------------

前言：
自从微软面试100题发布以来，得到了千千万万热心网友的支持与关注，和帮助。尤其是，不少网友或在我发表的帖子上，或在本BLOG内，甚至来信指导，并指正我之前上传答案中，如答案V0.2版[第1-20题答案]的某些问题与错误。
在下，实在是非常感激不尽，衷心感谢大家。

ok，以下，是网友Sorehead帮忙校正的微软面试100题，第1-10题的答案指正与点评，以及他自己的理解。我个人觉得他的每一个意见，都比较中肯，与准确，且还指出了之前上传答案的诸多不足与问题，再次感谢他。

同时，文中对他在帖子上回复的内容，并未做太大的修改。我自己也并没有加太多的内容，大多都是他个人的理解。有任何问题，欢迎不吝指正。谢谢。

微软技术面试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
关于第一题，我再多说点：
我们可以中序遍历整棵树。按照这个方式遍历树，比较小的结点先访问。如果我们每访问一个结点，假设之前访问过的结点已经调整成一个排序双向链表，我们再把调整当前结点的指针将其链接到链表的末尾。当所有结点都访问过之后，整棵树也就转换成一个排序双向链表了。

// 遍历二元查找树  中序
void ergodicBSTree(BSTreeNode * pCurrent)
{
    if (NULL == pCurrent)
    {       
        return;
    }
    if (NULL != pCurrent->m_pLeft)
    {
        ergodicBSTree(pCurrent->m_pLeft);   
    }
 
    // 节点接到链表尾部
    convertToDoubleList(pCurrent);
    // 右子树为空
    if (NULL != pCurrent->m_pRight)
    {
        ergodicBSTree(pCurrent->m_pRight);
    }
}

// 二叉树转换成list
void  convertToDoubleList(BSTreeNode * pCurrent)
{
 
    pCurrent->m_pLeft = pListIndex;
    if (NULL != pListIndex)
    {
        pListIndex->m_pRight = pCurrent;
    }
    else
    {
        pHead = pCurrent;
    }   
    pListIndex = pCurrent;
    cout<<pCurrent->m_nValue<<endl;
}

或者网友何海涛所述：

void ConvertNode(BSTreeNode* pNode, BSTreeNode*& pLastNodeInList)   
{        
 if(pNode == NULL)             
  return;        
    
 BSTreeNode *pCurrent = pNode;       
 // Convert the left sub-tree       
 if (pCurrent->m_pLeft != NULL)         
  ConvertNode(pCurrent->m_pLeft, pLastNodeInList);       
 // Put the current node into the double-linked list      
 pCurrent->m_pLeft = pLastNodeInList;      
    
 if(pLastNodeInList != NULL)             
  pLastNodeInList->m_pRight = pCurrent;     
 pLastNodeInList = pCurrent;      
    
 // Convert the right sub-tree        
 if (pCurrent->m_pRight != NULL)             
  ConvertNode(pCurrent->m_pRight, pLastNodeInList);   
}   
  
BSTreeNode* Convert_Solution1(BSTreeNode* pHeadOfTree)   
{        
 BSTreeNode *pLastNodeInList = NULL;        
 ConvertNode(pHeadOfTree, pLastNodeInList);        
    
 // Get the head of the double-linked list        
 BSTreeNode *pHeadOfList = pLastNodeInList;        
 while(pHeadOfList && pHeadOfList->m_pLeft)             
  pHeadOfList = pHeadOfList->m_pLeft;        
 return pHeadOfList;   
}  

但显然，以下这种思路更容易理解些：

BSTreeNode* ConvertNode(BSTreeNode* pNode, bool asRight)
{
      if(!pNode)
            return NULL;

      BSTreeNode *pLeft = NULL;
      BSTreeNode *pRight = NULL;

      // Convert the left sub-tree
      if(pNode->m_pLeft)
            pLeft = ConvertNode(pNode->m_pLeft, false);

      // Connect the greatest node in the left sub-tree to the current node
      if(pLeft)
      {
            pLeft->m_pRight = pNode;
            pNode->m_pLeft = pLeft;
      }

      // Convert the right sub-tree
      if(pNode->m_pRight)
            pRight = ConvertNode(pNode->m_pRight, true);

      // Connect the least node in the right sub-tree to the current node
      if(pRight)
      {
            pNode->m_pRight = pRight;
            pRight->m_pLeft = pNode;
      }

      BSTreeNode *pTemp = pNode;

      // If the current node is the right child of its parent, 
      // return the least node in the tree whose root is the current node
      if(asRight)
      {
            while(pTemp->m_pLeft)
                  pTemp = pTemp->m_pLeft;
      }
      // If the current node is the left child of its parent, 
      // return the greatest node in the tree whose root is the current node
      else
      {
            while(pTemp->m_pRight)
                  pTemp = pTemp->m_pRight;
      }
 
      return pTemp;
}

同样是上道题，给各位看一段简洁的代码，领悟一下c的高效与美：

void change(Node *p, Node *&last) //中序遍历
{
 if (!p)
  return;
 change(p->left, last);
 if (last)
  last->right = p;
 p->left = last;
 
 last = p;
 change(p->right, last);
}

void main()
{
 Node *root = create();
 Node *tail = NULL;
 change(root, tail);
 while (tail)
 {
  cout << tail->data << " ";
  tail = tail->left;
 }
 cout << endl;
} 

2.设计包含min函数的栈（栈）
定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。
要求函数min、push以及pop的时间复杂度都是O(1)。

#define STACK_LEN 50

typedef struct
{
        int     val;
        int     min;
} stack_item;

typedef struct
{
        stack_item      data[STACK_LEN];
        int             top;
} stack;

void push(stack *stk, int val)
{
        stk->data[++stk->top].val = val;
        if (stk->top > 0)
        {
                if (val < stk->data[stk->top - 1].min)  
                //如果当前push进的元素小于栈中最小元素
                        stk->data[stk->top].min = val;   //把当前元素置为栈中最小元素
                else
                //否则，不更新
                        stk->data[stk->top].min = stk->data[stk->top - 1].min; 
        }
        else
                stk->data[stk->top].min = val;
}

int pop(stack *stk)
{
        return stk->data[stk->top--].val;
}

int min(stack *stk)
{
        return stk->data[stk->top].min;
}

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; i<n; i++)
{
if(b<0)
b=a[i];
else
b+=a[i];
if(sum<b)
sum=b;
}
return sum;
}

Sorehead：
第三题：
答案中其实最开始的方法就挺好的，稍微改动一下就可以全部都是负数的情况，而不需要后面那样遍历两次。
下面是我写的代码。

int get_sub_sum_max(int *arr, int len)
{
int max, sum;

max = arr[0];
sum = 0;
while (len--)
{
sum += *arr++;

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小，s<m，则到 s的右边继续找
如果找到的第s小，s>m，则 到s的左边继续找。

举例说明：
2 1 3 6 4 5
假设第一次划分之后，3为中间元素：
1、如果要求找第3小的元素，而找到的s=m(要求)，则返回3
2、如果要求找第1小的元素，而找到的s>m，则在s的左边找
3、如果要求找第4小的元素，而找到的s<m，则在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,0
0在下排出现了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 < *head)
return 0;
p++;
}

if (!is_post_traverse(arr, pos - arr))
return 0;
return is_post_traverse(pos, head - pos);
}

第10题（字符串）
翻转句子中单词的顺序。
题目：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。

句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。
例如输入“I am a student.”，则输出“student. a am I”。

Sorehead：第十题，我刚看到题目的时候，并没有想到是直接在原字符串上做翻转操作，我觉得题目也没有这个强制要求。我采用的方法就像strcpy函数一样，给了一个同样大小的字符串指针传过去，用于保存翻转后的结果，当然这么做代码就很简单了。看了楼主的答案，才想起来原字符串直接操作这回事，除了答案中的方法，也确实没想到其它什么好方法。

对以上任何一题有任何问题，欢迎直接留言评论，或回复到此帖子上：微软100题维护地址。完。

---

版权所有。转载本BLOG内任何文章，请以超链接形式注明出处。