前言

數據結構與算法的重要性已不言而喻，最近，我整理出十大經典排序算法、五大常用算法總結，今天特意整理出微軟面試的100題，若有不足之處，歡迎指正！由於篇幅過長，前30道題目寫在上一篇，大家可以進我的個人主頁瀏覽，之後我會抽時間爭取把數據結構與算法做成一個系列，敬請期待！

31、和為n 連續正數序列

題目：輸入一個正數n，輸出所有和為n 連續正數序列。

例如輸入15，由於1+2+3+4+5=4+5+6=7+8=15，所以輸出3 個連續序列1-5、4-6 和7-8。

32、二元樹的深度

題目：輸入一棵二元樹的根結點，求該樹的深度。從根結點到葉結點依次經過的結點（含根、葉結點）形成樹的一條路徑，最長路徑的長度為樹的深度。

分析：這道題本質上還是考查二元樹的遍歷。

33、字符串的排列

題目：輸入一個字符串，打印出該字符串中字符的所有排列。

例如輸入字符串abc，則輸出由字符a、b、c 所能排列出來的所有字符串abc、acb、bac、bca、cab 和cba。

分析：這是一道很好的考查對遞歸理解的編程題。

34、調整數組順序使奇數位於偶數前面

題目：輸入一個整數數組，調整數組中數字的順序，使得所有奇數位於數組的前半部分，所有偶數位於數組的後半部分。要求時間複雜度為O(n)。

35、最長公共字串

題目：如果字符串一的所有字符按其在字符串中的順序出現在另外一個字符串二中，則字符串一稱之為字符串二的子串。注意，並不要求子串（字符串一）的字符必須連續出現在字符串二中。

請編寫一個函數，輸入兩個字符串，求它們的最長公共子串，並打印出最長公共子串。

例如：輸入兩個字符串BDCABA 和ABCBDAB，字符串BCBA 和BDAB 都是是它們的最長公共子串，則輸出它們的長度4，並打印任意一個子串。

分析：求最長公共子串是一道非常經典的動態規劃題。

36、從尾到頭輸出鏈表

鏈表結點定義如下：

struct ListNode

{

int m_nKey;

ListNode* m_pNext;

};

37、在O（1）時間內刪除鏈表結點

題目：給定鏈表的頭指針和一個結點指針，在O(1)時間刪除該結點。

鏈表結點的定義如下：

struct ListNode

{

int m_nKey;

ListNode* m_pNext;

};

void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);

分析：這道題考察編程基本功和反應速度，更重要的是考察面試者對時間複雜度的理解。

38、找出數組中兩個只出現一次的數字

題目：一個整型數組裡除了兩個數字之外，其他的數字都出現了兩次。請寫程序找出這兩個只出現一次的數字。要求時間複雜度是O(n)，空間複雜度是O(1)。

分析：這是一道很新穎的關於位運算的面試題。

39、找出鏈表的第一個公共結點

題目：兩個單向鏈表，找出它們的第一個公共結點。

鏈表的結點定義為：

struct ListNode

{

int m_nKey;

ListNode* m_pNext;

};

分析：這是一道微軟的面試題，在微軟的面試題中，鏈表出現的概率相當高。

40、在字符串中刪除特定的字符

題目：輸入兩個字符串，從第一字符串中刪除第二個字符串中所有的字符。例如，輸入”They are students.”和”aeiou”， 則刪除之後的第一個字符串變成”Thy r stdnts.”。

分析：在微軟的常見面試題中，與字符串相關的題目佔了很大的一部分，因為寫程序操作字符串能很好的反映面試者的編程基本功。

41、 尋找醜數

題目：我們把只包含因子2、3 和5 的數稱作醜數（Ugly Number）。例如6、8 都是醜數，但14 不是，因為它包含因子7。習慣上我們把1 當做是第一個醜數。求按從小到大的順序的第1500 個醜數。

42、輸出1 到最大的N 位數

題目：輸入數字n，按順序輸出從1 最大的n 位10 進制數。比如輸入3，則輸出1、2、3 一直到最大的3 位數即999。

分析：這是一道很有意思的題目，看起來很簡單，其實裡面卻有不少的玄機。

43、顛倒棧

題目：用遞歸顛倒一個棧。例如輸入棧{1, 2, 3, 4, 5}，1 在棧頂。顛倒之後的棧為{5, 4, 3, 2, 1}，5 處在棧頂。

44、閒玩娛樂

（1）撲克牌的順子

從撲克牌中隨機抽5 張牌，判斷是不是一個順子，即這5 張牌是不是連續的。2-10 為數字本身，A 為1，J 為11，Q 為12，K 為13，而大小王可以看成任意數字。

（2）n 個骰子的點數。把n 個骰子扔在地上，所有骰子朝上一面的點數之和為S。輸入n，

打印出S 的所有可能的值出現的概率。

45、把數組排成最小的數

題目：輸入一個正整數數組，將它們連接起來排成一個數，輸出能排出的所有數字中最小的

一個。例如輸入數組{32, 321}，則輸出這兩個能排成的最小數字32132。

請給出解決問題的算法，並證明該算法。

分析：這是百度的一道面試題，從這道題我們可以看出百度對應聘者在算法方面有很高的要求。

46、旋轉數組中的最小元素

題目：把一個數組最開始的若干個元素搬到數組的末尾，我們稱之為數組的旋轉。輸入一個

排好序的數組的一個旋轉，輸出旋轉數組的最小元素。例如數組{3, 4, 5, 1, 2}為{1, 2, 3, 4, 5}的一個旋轉，該數組的最小值為1。

分析：這道題最直觀的解法並不難，我們應該利用輸入數組的特性找到更好的解法。

47、數值的整數次方

題目：實現函數double Power(double base, int exponent)，求base 的exponent 次方。

不需要考慮溢出。

48、 題目：設計一個類，我們只能生成該類的一個實例。

分析：只能生成一個實例的類是實現了Singleton 模式的類型。

49、對策字符串的最大長度

題目：輸入一個字符串，輸出該字符串中對稱的子字符串的最大長度。比如輸入字符串“google”，由於該字符串裡最長的對稱子字符串是“goog”，因此輸出4。

分析：可能很多人都寫過判斷一個字符串是不是對稱的函數，這個題目可以看成是該函數的

加強版。

50、數組中超過出現次數超過一半的數字

題目：數組中有一個數字出現的次數超過了數組長度的一半，找出這個數字。

分析：這道面試題百度、微軟和Google 在內的多家公司都採用過，解答這道題除了較好的編程能力外，還需要較快的反應和較強的邏輯思維能力。

51、二叉樹兩個結點的最低共同父結點

題目：二叉樹的結點定義如下：

struct TreeNode

{

int m_nvalue;

TreeNode* m_pLeft;

TreeNode* m_pRight;

};

輸入二叉樹中的兩個結點，輸出這兩個結點在數中最低的共同父結點。

52、複雜鏈表的複製

題目：有一個複雜鏈表，其結點除了有一個m_pNext 指針指向下一個結點外，還有一個m_pSibling 指向鏈表中的任一結點或者NULL。其結點的C++定義如下：

struct ComplexNode

{

int m_nValue;

ComplexNode* m_pNext;

ComplexNode* m_pSibling;

};

下圖是一個含有5 個結點的該類型複雜鏈表。

圖中實線箭頭表示m_pNext 指針，虛線箭頭表示m_pSibling 指針。為簡單起見，指向NULL 的指針沒有畫出。請完成函數ComplexNode* Clone(ComplexNode* pHead)，以複製一個複雜鏈表。

53、關於鏈表問題的面試題目如下：

（1）給定單鏈表，檢測是否有環。

使用兩個指針p1,p2 從鏈表頭開始遍歷，p1 每次前進一步，p2 每次前進兩步。如果p2 到達鏈表尾部，說明無環，否則p1、p2 必然會在某個時刻相遇(p1==p2)，從而檢測到鏈表中有環。

（2）給定兩個單鏈表(head1, head2)，檢測兩個鏈表是否有交點，如果有返回第一個交點。如果head1==head2，那麼顯然相交，直接返回head1。否則，分別從head1,head2 開始遍歷兩個鏈表獲得其長度len1 與len2，假設len1>=len2，那麼指針p1 由head1 開始向後移動len1-len2 步，指針p2=head2，下面p1、p2 每次向後前進一步並比較p1p2 是否相等，如果相等即返回該結點，否則說明兩個鏈表沒有交點。

（3）給定單鏈表(head)，如果有環的話請返回從頭結點進入環的第一個節點。

運用題一，我們可以檢查鏈表中是否有環。如果有環，那麼p1p2 重合點p 必然在環中。從p 點斷開環，方法為：p1=p, p2=p->next, p->next=NULL。此時，原單鏈表可以看作兩條單鏈表，一條從head 開始，另一條從p2 開始，於是運用題二的方法，我們找到它們的第一個交點即為所求。

（4）只給定單鏈表中某個結點p(並非最後一個結點，即p->next!=NULL)指針，刪除該結點。辦法很簡單，首先是放p 中數據,然後將p->next 的數據copy 入p 中，接下來刪除p->next即可。

（5）只給定單鏈表中某個結點p(非空結點)，在p 前面插入一個結點。辦法與前者類似，首先分配一個結點q，將q 插入在p 後，接下來將p 中的數據copy 入q中，然後再將要插入的數據記錄在p 中。

54、鏈表和數組的區別在哪裡？

分析：主要在基本概念上的理解，但是最好能考慮的全面一點。

55、（1）編寫實現鏈表排序的一種算法。說明為什麼你會選擇用這樣的方法？

（2）編寫實現數組排序的一種算法。說明為什麼你會選擇用這樣的方法？

（3）請編寫能直接實現strstr()函數功能的代碼。

56、阿里巴巴一道筆試題

題目：12 個高矮不同的人,排成兩排,每排必須是從矮到高排列,而且第二排比對應的第一排的人高,問排列方式有多少種?

（1）一個int 數組，裡面數據無任何限制，要求求出所有這樣的數a[i]，其左邊的數都小於等於它，右邊的數都大於等於它。能否只用一個額外數組和少量其它空間實現。

（2）一個文件，內含一千萬行字符串，每個字符串在1K 以內，要求找出所有相反的串對，如abc 和cba。

（3）STL 的set 用什麼實現的？為什麼不用hash？

題目：給定一個存放整數的數組，重新排列數組使得數組左邊為奇數，右邊為偶數。

要求：空間複雜度O(1)，時間複雜度為O（n）。

59、用C 語言實現函數void * memmove(void *dest, const void *src, size_t n)。memmove 函數的功能是拷貝src 所指的內存內容前n 個字節到dest 所指的地址上。

分析：由於可以把任何類型的指針賦給void 類型的指針, 這個函數主要是實現各種數據類型的拷貝。

60、又見字符串的問題

（1）給出一個函數來複制兩個字符串A 和B。字符串A 的後幾個字節和字符串B 的前幾個字節重疊。分析：記住，這種題目往往就是考你對邊界的考慮情況。

（2）已知一個字符串，比如asderwsde,尋找其中的一個子字符串比如sde 的個數，如果沒有返回0，有的話返回子字符串的個數。

61、怎樣編寫一個程序，把一個有序整數數組放到二叉樹中？

分析:本題考察二叉搜索樹的建樹方法，簡單的遞歸結構。關於樹的算法設計一定要聯想到遞歸，因為樹本身就是遞歸的定義。

62、（1）大整數數相乘的問題。

（2）求最大連續遞增數字串（如“ads3sl456789DF3456ld345AA”中的“456789”）

（3）實現strstr 功能，即在父串中尋找子串首次出現的位置。

63、金山筆試題，編碼完成下面的處理函數。

題目：函數將字符串中的字符'*'移到串的前部分，前面的非'*'字符後移，但不能改變非'*'字符的先後順序，函數返回串中字符'*'的數量。如原始串為：ab**cd**e*12，處理後為*****abcde12，函數並返回值為5。（要求使用盡量少的時間和輔助空間）

64、神州數碼、華為筆試題

（1）華為軟件研發筆試題，實現一單鏈表的逆轉。

（2）編碼實現字符串轉整型的函數（實現函數atoi 的功能），據說是神州數碼筆試題。如將字符串”+123”123, ”-0123”-123, “123CS45”123, “123.45CS”123, “CS123.45”0

（3）快速排序

（4）刪除字符串中的數字並壓縮字符串。如字符串”abc123de4fg56”處理後變為”abcdefg”。注意空間和效率。

（5）求兩個串中的第一個最長子串。

如"abractyeyt","dgdsaeactyey"的最大子串為"actyet"。

65、（1）不開闢用於交換數據的臨時空間，如何完成字符串的逆序

（2）刪除串中指定的字符

（3）判斷單鏈表中是否存在環。

66、一道著名的毒酒問題

有1000 桶酒，其中1 桶有毒。而一旦吃了，毒性會在1 周後發作。現在我們用小老鼠做實驗，要在1 周內找出那桶毒酒，問最少需要多少老鼠。

67、有趣的石頭問題

有一堆1 萬個石頭和1 萬個木頭，對於每個石頭都有1 個木頭和它重量一樣，把配對的石頭和木頭找出來。

68、在一個int 數組裡查找這樣的數，它大於等於左側所有數，小於等於右側所有數。直觀想法是用兩個數組a、b。a[i]、b[i]分別保存從前到i 的最大的數和從後到i 的最小的數，一個解答。

69、微軟筆試題

求隨機數構成的數組中找到長度大於=3 的最長的等差數列, 輸出等差數列由小到大，如果沒有符合條件的就輸出格式：

輸入[1,3,0,5,-1,6]

輸出[-1,1,3,5]

要求時間複雜度，空間複雜度儘量小。

70、華為面試題

（1）判斷一字符串是不是對稱的，如：abccba。

（2）用遞歸的方法判斷整數組a[N]是不是升序排列。

最後壓軸之戲，終結微軟公司的面試題：

第1 組微軟較簡單的算法面試題

1、編寫反轉字符串的程序，要求優化速度、優化空間。

2、在鏈表裡如何發現循環鏈接？

3、編寫反轉字符串的程序，要求優化速度、優化空間。

4、給出洗牌的一個算法，並將洗好的牌存儲在一個整形數組裡。

5、寫一個函數，檢查字符是否是整數，如果是，返回其整數值。

（或者：怎樣只用4 行代碼編寫出一個從字符串到長整形的函數？）

第2 組微軟面試題

1、給出一個函數來輸出一個字符串的所有排列。

2、請編寫實現malloc()內存分配函數功能一樣的代碼。

3、給出一個函數來複制兩個字符串A 和B。字符串A 的後幾個字節和字符串B 的前幾個字節重疊。

4、怎樣編寫一個程序，把一個有序整數數組放到二叉樹中？

5、怎樣從頂部開始逐層打印二叉樹結點數據？請編程。

6、怎樣把一個鏈表掉個順序（也就是反序，注意鏈表的邊界條件並考慮空鏈表）？

第3 組微軟面試題

1、燒一根不均勻的繩，從頭燒到尾總共需要1 個小時。現在有若干條材質相同的繩子，問如何用燒繩的方法來計時一個小時十五分鐘呢？

2、你有一桶果凍，其中有黃色、綠色、紅色三種，閉上眼睛抓取同種顏色的兩個。抓取多少個就可以確定你肯定有兩個同一顏色的果凍？（5 秒-1 分鐘完成）

3、如果你有無窮多的水，一個3 公升的提捅，一個5 公升的提捅，兩隻提捅形狀上下都不均

勻，問你如何才能準確稱出4 公升的水？（40 秒-3 分鐘完成）

第4 組微軟面試題，挑戰思維極限

1、12 個球一個天平，現知道只有一個和其它的重量不同，問怎樣稱才能用三次就找到那個

球。13 個呢？（注意此題並未說明那個球的重量是輕是重，所以需要仔細考慮）（5 分鐘-1 小時完成）

2、在9 個點上畫10 條直線，要求每條直線上至少有三個點？（3 分鐘-20 分鐘完成）

3、在一天的24 小時之中，時鐘的時針、分針和秒針完全重合在一起的時候有幾次？都分別是什麼時間？你怎樣算出來的？（5 分鐘-15 分鐘完成）

最後

為了讓學習變得輕鬆高效， 現在給大家提供一個學習平臺，讓你在實踐中積累經驗掌握原理。主要方向是JAVA架構師，在這裡你可以學習Java工程化、高性能及分佈式、深入淺出、性能調優、Spring，MyBatis，Netty源碼分析和大數據等知識點，免費的大型互聯網Java技術視頻分享給大家。

後臺私信回覆“架構” 即可免費獲得這套價值一萬六的內部教材！

閱讀更多 Java後端開發 的文章

關鍵字: 面試題 編程語言 微軟