永久優化：微軟技術面試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
關于第一題，我再多說點：
我們可以中序周遊整棵樹。按照這個方式周遊樹，比較小的結點先通路。如果我們每通路一個結點，假設之前通路過的結點已經調整成一個排序雙向連結清單，我們再把調整目前結點的指針将其連結到連結清單的末尾。當所有結點都通路過之後，整棵樹也就轉換成一個排序雙向連結清單了。
[cpp:nogutter] view plain copy print ?
- // 周遊二進制查找樹 中序
- 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 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;
}
或者網友何海濤所述：
[cpp:nogutter] view plain copy print ?
- 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;
- }
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;
}
但顯然，以下這種思路更容易了解些： [cpp:nogutter] view plain copy print ?
- 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;
- }
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的高效與美：
[cpp:nogutter] view plain copy print ?
- 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;
- }
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)。
[cpp:nogutter] view plain copy print ?
- #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;
- }
#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函數一樣，給了一個同樣大小的字元串指針傳過去，用于儲存翻轉後的結果，當然這麼做代碼就很簡單了。看了樓主的答案，才想起來原字元串直接操作這回事，除了答案中的方法，也确實沒想到其它什麼好方法。
![職業規劃Android開發職業規劃[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)